Na stopách publikuji úlohy z oboru Algoritmus (klasické sportovní programování. Během hodiny a půl je třeba vyřešit tři úlohy v Java, C#, C++ nebo Pythonu.)
1. Koláč pro šest
Formulace úkolu
Časový limit — 4 sekundy.
Máte koláč. Pokud se díváte zhora, koláč má tvar (přísně) konvexního mnohoúhelníku. Jsou vám dány souřadnice vrcholů v celých číslech X a Y.
Máte pět přátel. Chcete rozdělit koláč na šest částí se stejnou plochou (ale nemusí mít stejný tvar). Samozřejmě, že to může udělat kdokoliv za pět řezů, ale pouze profesionál to může udělat za tři řezy.
Najděte tři řezy přímkami procházejícími jedním bodem, které rozdělí koláč na šest stejně velkých částí. Vraťte {x, y, d1, d2, d3}, kde (x, y) je společný bod všech tří řezů a d1, d2, d3 jsou úhly směru řezů v radiánech.
DefiniceTřída: CakeForSix
Metoda: cut
Parametry: int[], int[]
Vrací: double[]
Podpis metody: double[] cut(int[] x, int[] y)
(ujistěte se, že vaše metoda je veřejná)
Poznámky
- Pozitivní směr podél osy x je roven 0 (radián), pozitivní směr podél osy y je roven pi/2 (radián).
- Řez ve směru d je podobný řezu ve směru pi*k+d pro libovolné celé číslo k.
- Můžete vypsat jakékoliv směry, nemusí být nutně v [0, pi).
- Grader vypočítá plochy vašich šesti částí koláče jako doubles. Odpověď bude přijata, pokud relativní nebo absolutní rozdíl mezi nimi je menší než 10^(-4).
- Přesněji, nechť X a Y jsou nejmenší a největší z vašich šesti oblastí, které vypočítal grader. Pak bude vaše odpověď přijata, pokud Y < max(X + 10^(-4), X * 1 + 10^(-4))).
- (V původní verzi úlohy byla použita přesnost 1e-7 místo 1e-4. Pro vyřešení tohoto problému byl v archivu snížen limit přesnosti z důvodu výskytu případů, které pravděpodobně činí úlohu neřešitelnou s přesností 1e-7. V ideálním světě omezení nepovolují takové případy a stále vyžadují vysokou přesnost, takže řešení tohoto problému pomocí obecné numerické optimalizace není jednoduché.)
Omezení
- x obsahuje od 3 do 50 prvků včetně.
- y obsahuje tolik prvků, kolik x.
- všechny souřadnice mezi 0 a 10 000 včetně
- x a y určují konvexní mnohoúhelník proti směru hodinových ručiček.
Originál v angličtině
Prohlášení o problému
Časový limit je 4 sekundy.
Máte dort. Z pohledu shora je dort (přísně) konvexním mnohoúhelníkem. Dostali jste souřadnice jeho vrcholů v int[]s x a y.
Máte pět přátel. Nyní chcete dort rozdělit na šest kusů se stejnou plochou (ale nemusí mít nutně stejný tvar). Samozřejmě, že to lze udělat pěti řezy — ale pouze pravý profesionál to zvládne ve třech!
Najděte tři přímé řezy procházející stejným bodem, které rozdělí dort na šest stejně velkých částí. Vraťte {x, y, d1, d2, d3}, kde (x, y) je společný bod tří řezů a d1, d2, d3 jsou jejich směry v radiánech.
Definice
Třída: CakeForSix
Metoda: cut
Parametry: int[], int[]
Vrací: double[]
Podpis metody: double[] cut(int[] x, int[] y)
(ujistěte se, že vaše metoda je veřejná)
Poznámky
— Kladný směr podél osy x je 0 (radiánů), kladný směr podél osy y je pi/2 (radiánů).
— Řez ve směru d je stejný jako řez ve směru pi*k+d pro libovolné celé číslo k.
— Můžete vrátit jakékoliv směry, nemusí být z [0, pi).
— Grader spočítá plochy vašich šesti kusů dortu jako doubles. Odpověď bude akceptována, pokud je relativní nebo absolutní rozdíl mezi nimi menší než 10^(-4).
— Přesněji řečeno, ať X a Y jsou nejmenší a největší z vašich šesti ploch, jak je spočítal grader. Pak bude vaše odpověď akceptována, pokud Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (Původní verze úlohy používala přesnost 1e-7 místo 1e-4. Pro upsolving této úlohy v archivu byla přesnost snížena kvůli existenci výzev, které pravděpodobně činí úkol neřešitelným s přesností 1e-7. V ideálním světě by omezení neměla umožnit takové případy a stále by vyžadovala vysokou přesnost, aby nebylo snadné problém vyřešit pomocí nějaké obecné numerické optimalizace.)
Omezení
— x bude mít mezi 3 a 50 prvky, včetně.
— y bude mít stejný počet prvků jako x.
— Všechny souřadnice budou v rozmezí od 0 do 10 000, včetně.
— x a y popíšou konvexní mnohoúhelník v protisměrném pořadí.
Příklady
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Vrátí:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Symetrický, ale ne pravidelný šestiúhelník. Příklad odpovědi odpovídá rozřezání ho napůl horizontálně a provedení dvou dalších řezů ve středu, které každou část rozdělí na tři části.
1)
{0, 1000, 0}
{0, 0, 1000}
Vrátí:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Obdélníkový trojúhelník. Opět můžeme začít s jedním ze tří řezů podél osy symetrie.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Vrátí:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Neppravidelný pětiúhelník.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Vrátí: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Čtverec otočený o 45 stupňů.
[]
Pouze registrovaní uživatelé se mohou účastnit ankety. , prosím.
Vyřešil jsem úlohu za
méně než 10 minut
10-30 minut
30-60 minut
1-2 hodiny
více než 2 hodiny
jiné
Hlasovalo 42 uživatelů. Zdrželo se 47 uživatelů.
Zdroj: habr.com
