Po stopách Zverejňujem problémy zo stopy Algorithm (klasické športové programovanie. Za jeden a pol hodiny potrebujete vyriešiť tri problémy v Jave, C#, C++ alebo Pythone.)
1. Koláč pre šesť
Vyhlásenie o probléme
Časový limit je 4 sekundy.
Máš koláč. Pri pohľade zhora má torta tvar (striktne) konvexného mnohouholníka. Dostanete súradnice vrcholov v celých číslach X a Y.
Máš päť priateľov. Chcete koláč rozdeliť na šesť kusov rovnakej plochy (ale nie nevyhnutne rovnakého tvaru). Samozrejme, každý to zvládne na päť strihov, ale na tri strihy len profík.
Nájdite tri rezy v priamych líniách cez jeden bod, ktoré rozdelia koláč na šesť rovnakých častí. Vytlačte {x, y, d1, d2, d3}, kde (x, y) je spoločný bod všetkých troch rezov a d1, d2, d3 sú smerové uhly rezov v radiánoch.
DefiníciaTrieda: CakeForSix
Metóda: rez
Parametre: int[], int[] Vráti: double[] Signatúra metódy: double[] cut(int[] x, int[] y)
(uistite sa, že vaša metóda je verejná)
poznámky
- Kladný smer pozdĺž osi x je 0 (radiány), kladný smer pozdĺž osi y je pi/2 (radiány).
- Rez v smere d je podobný rezu v smere pi*k+d pre akékoľvek celé číslo k.
- Môžete zadať ľubovoľné smery, nemusia byť od [0, pi).
- Zrovnávač vypočíta plochu vašich šiestich kúskov koláča v dvojnásobkoch. Odpoveď bude akceptovaná, ak je relatívny alebo absolútny rozdiel medzi nimi menší ako 10^(-4).
- Presnejšie, nech sú X a Y najmenšia a najväčšia z vašich šiestich oblastí vypočítaných porovnávačom. Potom bude vaša odpoveď prijatá, ak Y
- (Pôvodná verzia problému používala presnosť 1e-7 namiesto 1e-4. Na vyriešenie tohto problému v archíve bol limit presnosti znížený kvôli prítomnosti prípadov volania, ktoré by pravdepodobne urobili problém neriešiteľným s presnosťou 1e – 7. V ideálnom svete limity takéto prípady neumožňujú a stále vyžadujú vysokú presnosť, takže riešenie problému pomocou nejakej všeobecnej numerickej optimalizácie nie je jednoduché.)
Obmedzenie
- x obsahuje 3 až 50 prvkov vrátane.
- y obsahuje rovnaký počet prvkov ako x.
- všetky súradnice medzi 0 a 10 000 vrátane
- x a y definujú konvexný mnohouholník v smere proti smeru hodinových ručičiek.
Originál v angličtine
Vyhlásenie o probléme
Časový limit je 4 sekundy.
Máš tortu. Pri pohľade zhora je torta (striktne) konvexný mnohouholník. Dostanete súradnice jeho vrcholov v int[]sx a y.
Máš päť priateľov. Teraz chcete tortu rozrezať na šesť kusov rovnakej plochy (ale nie nevyhnutne rovnakého tvaru). Samozrejme, každý to môže urobiť v piatich rezoch - ale iba skutočný profesionál to dokáže v troch!
Nájdite tri rovné rezy prechádzajúce tým istým bodom, ktoré rozrežú tortu na šesť rovnako veľkých častí. Návrat {x, y, d1, d2, d3}, kde (x, y) je spoločný bod troch rezov a d1, d2, d3 sú ich smery v radiánoch.
Definícia
Trieda: CakeForSix
Metóda: rez
Parametre: int[], int[] Vráti: double[] Signatúra metódy: double[] cut(int[] x, int[] y)
(uistite sa, že vaša metóda je verejná)
Poznámky
— Kladný smer pozdĺž osi x je 0 (radiány), kladný smer pozdĺž osi y je pi/2 (radiány).
— Rez v smere d je rovnaký ako rez v smere pi*k+d pre akékoľvek celé číslo k.
— Môžete sa vrátiť ľubovoľným smerom, nemusia byť z [0,pi).
— Zrovnávač vypočíta plochy vašich šiestich kúskov koláča dvakrát. Odpoveď bude akceptovaná, ak je relatívny alebo absolútny rozdiel medzi nimi menší ako 10^(-4).
— Presnejšie, nech sú X a Y najmenšia a najväčšia z vašich šiestich oblastí, ako ich vypočíta porovnávač. Potom bude vaša odpoveď prijatá, ak Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Pôvodná verzia problému používala presnosť 1e-7 namiesto 1e-4. Na vyriešenie tohto problému v archíve bol limit presnosti znížený z dôvodu existencie prípadov výzvy, ktoré s najväčšou pravdepodobnosťou robia úlohu neriešiteľnou s presnosťou 1e-7 V ideálnom svete by obmedzenia takéto prípady neumožňovali a stále by vyžadovali vysokú presnosť, takže nie je ľahké vyriešiť problém pomocou nejakej všeobecnej numerickej optimalizácie.)
obmedzenia
— x bude mať 3 až 50 prvkov vrátane.
— y bude mať rovnaký počet prvkov ako x.
— Všetky súradnice budú medzi 0 a 10,000 XNUMX vrátane.
— x a y budú opisovať konvexný mnohouholník v protismere hodinových ručičiek.
príklady
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Vracia:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Symetrický, ale nepravidelný šesťuholník. Príklad odpovede zodpovedá rozrezaniu na polovicu vodorovne a vykonaniu dvoch ďalších rezov v strede, ktoré rozdelia každý kus na tri časti.
1)
{0, 1000, 0}
{0, 0, 1000}
Vracia:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Správny trojuholník. Opäť môžeme začať jedným z troch rezov pozdĺž osi súmernosti.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Vracia:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Nepravidelný päťuholník.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Vrátenie: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Štvorec otočený o 45 stupňov.
[]
Do prieskumu sa môžu zapojiť iba registrovaní užívatelia. Prosím.
Problém som vyriešil pre
-
za menej ako 10 minút
-
10 30-minúty
-
30 60-minúty
-
1-2 hodiny
-
za viac ako 2 hodiny
-
ďalšie
Hlasovalo 42 užívateľov. 47 užívateľov sa zdržalo hlasovania.
Zdroj: hab.com