U tragovima Objavljujem zadatke iz staze Algoritam (klasično sportsko programiranje. Za sat i pol trebate riješiti tri zadatka u Javi, C#, C++ ili Pythonu.)
1. Pita za šestero
Formuliranje problema
Vremensko ograničenje je 4 sekunde.
Imate pitu. Gledano odozgo, torta ima oblik (strogo) konveksnog poligona. Zadane su vam koordinate vrhova u cijelim brojevima X i Y.
Imaš pet prijatelja. Želite podijeliti pitu na šest dijelova jednake površine (ali ne nužno istog oblika). Naravno, svatko to može napraviti u pet rezova, ali samo profesionalac to može napraviti u tri rezova.
Pronađite tri reza u ravnim crtama kroz jednu točku koja će podijeliti pitu na šest jednakih dijelova. Ispiši {x, y, d1, d2, d3}, gdje je (x, y) zajednička točka sva tri reza, a d1, d2, d3 smjerni kutovi reza u radijanima.
DefinicijaRazred: CakeForSix
Metoda: rez
Parametri: int[], int[] Vraća: double[] Potpis metode: double[] cut(int[] x, int[] y)
(provjerite da je vaša metoda javna)
Bilješke
- Pozitivan smjer duž x-osi je 0 (radijani), pozitivan smjer duž y-osi je pi/2 (radijani).
- Rez u smjeru d sličan je rezu u smjeru pi*k+d za bilo koji cijeli broj k.
- Možete ispisati bilo koje upute, ne moraju biti od [0, pi).
- Gradjer će izračunati površinu vaših šest komada torte u duplo. Odgovor će biti prihvaćen ako je relativna ili apsolutna razlika između njih manja od 10^(-4).
- Točnije, neka X i Y budu najmanja i najveća od vaših šest površina koje je izračunao ocjenjivač. Tada će vaš odgovor biti prihvaćen ako Y
- (Originalna verzija problema koristila je preciznost 1e-7 umjesto 1e-4. Da bi se riješio ovaj problem u arhivi, ograničenje preciznosti je sniženo zbog prisutnosti pozivajućih slučajeva koji bi vjerojatno učinili problem nerješivim s preciznošću od 1e-7. U idealnom svijetu, ograničenja ne dopuštaju takve slučajeve i još uvijek zahtijevaju visoku preciznost, tako da rješavanje problema s nekom općom numeričkom optimizacijom nije jednostavno.)
Ograničenja
- x sadrži od 3 do uključivo 50 elemenata.
- y sadrži isti broj elemenata kao x.
- sve koordinate između 0 i uključivo 10 000
- x i y definiraju konveksni poligon u smjeru suprotnom od kazaljke na satu.
original na engleskom
Izjava o problemu
Vremensko ograničenje je 4 sekunde.
Imate tortu. Gledano odozgo, kolač je (strogo) konveksan poligon. Dane su vam koordinate njegovih vrhova u int[]sx i y.
Imaš pet prijatelja. Sada želite izrezati tortu na šest dijelova jednake površine (ali ne nužno jednakog oblika). Naravno, svatko to može učiniti u pet rezova — ali samo pravi profesionalac to može učiniti u tri!
Pronađite tri pravocrtna reza koja prolaze kroz istu točku koja siječe kolač na šest jednako velikih dijelova. Vrati {x, y, d1, d2, d3}, gdje je (x, y) zajednička točka tri reza, a d1, d2, d3 njihovi pravci u radijanima.
Definicija
Razred: CakeForSix
Metoda: rez
Parametri: int[], int[] Vraća: double[] Potpis metode: double[] cut(int[] x, int[] y)
(provjerite da je vaša metoda javna)
Bilješke
— Pozitivan smjer duž x osi je 0 (radijani), pozitivan smjer duž y osi je pi/2 (radijani).
— Rez u smjeru d je isti kao rez u smjeru pi*k+d za bilo koji cijeli broj k.
— Možete vratiti bilo koje upute, ne moraju biti od [0,pi).
— Gradjer će izračunati površine vaših šest komada kolača u duplo. Odgovor će biti prihvaćen ako je relativna ili apsolutna razlika između njih manja od 10^(-4).
— Preciznije, neka X i Y budu najmanje i najveće od vaših šest područja, kako je izračunao ocjenjivač. Tada će vaš odgovor biti prihvaćen ako je Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Originalna verzija problema koristila je preciznost 1e-7 umjesto 1e-4. Za rješavanje ovog problema u arhivi ograničenje preciznosti je spušteno zbog postojanja izazovnih slučajeva koji najvjerojatnije čine zadatak nerješivim s preciznošću 1e-7 U idealnom svijetu ograničenja ne bi dopuštala takve slučajeve i još uvijek zahtijevaju visoku preciznost, tako da nije lako riješiti problem putem neke opće numeričke optimizacije.)
ograničenja
— x će imati između 3 i uključivo 50 elemenata.
— y će imati isti broj elemenata kao x.
— Sve koordinate bit će između 0 i 10,000 XNUMX, uključivo.
— x i y će opisati konveksni poligon u smjeru suprotnom od kazaljke na satu.
Primjeri
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Vraća:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetričan, ali nepravilan šesterokut. Primjer odgovora odgovara vodoravnom rezanju na pola i pravljenju dva druga reza u središtu koja dijele svaki komad na tri dijela.
1)
{0, 1000, 0}
{0, 0, 1000}
Vraća:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Pravokutni trokut. Opet, možemo početi s jednim od tri reza duž osi simetrije.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Vraća:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Nepravilni peterokut.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Vraća: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Kvadrat se zakrenuo za 45 stupnjeva.
[]
U anketi mogu sudjelovati samo registrirani korisnici. , molim.
Riješio sam problem za
-
za manje od 10 minuta
-
10-30 minuta
-
30-60 minuta
-
1-2 sati
-
u više od 2 sata
-
drugi
Glasovalo je 42 korisnika. Suzdržano je bilo 47 korisnika.
Izvor: www.habr.com