Pa pÄdÄm Es publicÄju problÄmas no Algoritma celiÅa (klasiskÄ sporta programmÄÅ”ana. Pusotras stundas laikÄ jÄatrisina trÄ«s uzdevumi Java, C#, C++ vai Python valodÄ.)
1. PÄ«rÄgs seÅ”iem
ProblÄmas paziÅojums
Laika ierobežojums ir 4 sekundes.
Jums ir pÄ«rÄgs. Skatoties no augÅ”as, kÅ«kai ir (stingri) izliekta daudzstÅ«ra forma. Jums tiek dotas virsotÅu koordinÄtas X un Y veselos skaitļos.
Tev ir pieci draugi. JÅ«s vÄlaties sadalÄ«t pÄ«rÄgu seÅ”os vienÄda laukuma gabalos (bet ne vienmÄr vienÄda forma). Protams, ikviens var to izdarÄ«t piecos griezumos, bet tikai profesionÄlis to var izdarÄ«t trÄ«s griezumos.
Atrodiet trÄ«s iegriezumus taisnÄs lÄ«nijÄs caur vienu punktu, kas sadalÄ«s pÄ«rÄgu seÅ”Äs vienÄdÄs daļÄs. DrukÄt {x, y, d1, d2, d3}, kur (x, y) ir visu trÄ«s griezumu kopÄjais punkts, un d1, d2, d3 ir griezumu virziena leÅÄ·i radiÄnos.
DefinīcijaKlase: CakeForSix
Metode: sagriezt
Parametri: int[], int[] Atgriež: double[] Metodes paraksts: double[] cut(int[] x, int[] y)
(pÄrliecinieties, ka jÅ«su metode ir publiska)
piezīmes
- PozitÄ«vais virziens pa x asi ir 0 (radiÄnos), pozitÄ«vais virziens pa y asi ir pi/2 (radiÄnos).
- Izgriezums d virzienÄ ir lÄ«dzÄ«gs izgriezumam pi*k+d virzienÄ jebkuram veselam skaitlim k.
- JÅ«s varat izvadÄ«t jebkurus virzienus, tiem nav jÄbÅ«t no [0, pi).
- Greideris aprÄÄ·inÄs jÅ«su seÅ”u kÅ«kas gabalu laukumu dubultÄ. Atbilde tiks pieÅemta, ja relatÄ«vÄ vai absolÅ«tÄ atŔķirÄ«ba starp tÄm ir mazÄka par 10^(-4).
- PrecÄ«zÄk, ļaujiet X un Y bÅ«t mazÄkajiem un lielÄkajiem no jÅ«su seÅ”iem laukumiem, ko aprÄÄ·inÄjis greiders. Tad jÅ«su atbilde tiks pieÅemta, ja Y
- (SÄkotnÄjÄ problÄmas versijÄ tika izmantota precizitÄte 1e-7, nevis 1e-4. Lai atrisinÄtu Å”o problÄmu arhÄ«vÄ, precizitÄtes ierobežojums tika pazeminÄts, jo bija izsaukÅ”anas gadÄ«jumi, kas, iespÄjams, padarÄ«tu problÄmu neatrisinÄmu ar precizitÄti. no 1e-7. IdeÄlÄ pasaulÄ ierobežojumi nepieļauj Å”Ädus gadÄ«jumus un joprojÄm prasa augstu precizitÄti, tÄpÄc problÄmas risinÄÅ”ana ar vispÄrÄ«gu skaitlisku optimizÄciju nav vienkÄrÅ”a.)
Ierobežojumi
- x satur no 3 līdz 50 elementiem ieskaitot.
- y satur tÄdu paÅ”u elementu skaitu kÄ x.
- visas koordinÄtas no 0 lÄ«dz 10 000 ieskaitot
- x un y definÄ izliektu daudzstÅ«ri pretÄji pulksteÅrÄdÄ«tÄja virzienam.
oriÄ£inÄls angļu valodÄ
ProblÄmas izklÄsts
Laika ierobežojums ir 4 sekundes.
Jums ir kÅ«ka. Skatoties no augÅ”as, kÅ«ka ir (stingri) izliekts daudzstÅ«ris. Jums tiek dotas tÄ virsotÅu koordinÄtas int[]sx un y.
Tev ir pieci draugi. Tagad vÄlaties kÅ«ku sagriezt seÅ”os vienÄda laukuma gabalos (bet ne vienmÄr vienÄdas formas). Protams, ikviens to var izdarÄ«t piecos griezumos, taÄu tikai Ä«sts profesionÄlis to var izdarÄ«t trÄ«s!
Atrodiet trÄ«s taisnas lÄ«nijas griezumus, kas iet caur to paÅ”u punktu, kas sagriež kÅ«ku seÅ”Äs vienÄdi lielÄs daļÄs. AtgrieÅ”anÄs {x, y, d1, d2, d3}, kur (x, y) ir trÄ«s griezumu kopÄjais punkts, un d1, d2, d3 ir to virzieni radiÄnos.
Definīcija
Klase: CakeForSix
Metode: sagriezt
Parametri: int[], int[] Atgriež: double[] Metodes paraksts: double[] cut(int[] x, int[] y)
(pÄrliecinieties, ka jÅ«su metode ir publiska)
Piezīmes
ā PozitÄ«vais virziens pa x asi ir 0 (radiÄnos), pozitÄ«vais virziens pa y asi ir pi/2 (radiÄnos).
ā Griezums virzienÄ d ir tÄds pats kÄ griezums virzienÄ pi*k+d jebkuram veselam skaitlim k.
ā Varat atgriezt jebkurus norÄdÄ«jumus, tiem nav jÄbÅ«t no [0,pi).
ā Greideris aprÄÄ·inÄs jÅ«su seÅ”u kÅ«kas gabalu laukumus dubultÄ. Atbilde tiks pieÅemta, ja relatÄ«vÄ vai absolÅ«tÄ atŔķirÄ«ba starp tÄm ir mazÄka par 10^(-4).
ā PrecÄ«zÄk, ļaujiet X un Y bÅ«t mazÄkajiem un lielÄkajiem no seÅ”iem laukumiem, ko aprÄÄ·inÄjis greiders. PÄc tam jÅ«su atbilde tiks pieÅemta, ja Y < max( X + 10^(-4), X * (1+10^(-4)) ).
ā (SÄkotnÄjÄ uzdevuma versijÄ tika izmantota precizitÄte 1e-7, nevis 1e-4. Å Ä«s problÄmas risinÄÅ”anai arhÄ«vÄ precizitÄtes robeža tika pazeminÄta, jo pastÄvÄja izaicinÄjuma gadÄ«jumi, kas, visticamÄk, padara uzdevumu neatrisinÄmu ar precizitÄti 1e-7 IdeÄlÄ pasaulÄ ierobežojumi nepieļautu Å”Ädus gadÄ«jumus un joprojÄm prasa augstu precizitÄti, tÄpÄc problÄmu nav viegli atrisinÄt, izmantojot vispÄrÄju skaitlisko optimizÄciju.)
Ierobežojumi
ā x bÅ«s no 3 lÄ«dz 50 elementiem, ieskaitot.
ā y bÅ«s tÄds pats elementu skaits kÄ x.
ā Visas koordinÄtas bÅ«s no 0 lÄ«dz 10,000 XNUMX ieskaitot.
ā x un y apraksta izliektu daudzstÅ«ri pretÄji pulksteÅrÄdÄ«tÄja virzienam.
piemÄri
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Atgriežas:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Simetrisks, bet neregulÄrs seÅ”stÅ«ris. Atbildes piemÄrs atbilst tÄ pÄrgrieÅ”anai uz pusÄm horizontÄli un divu citu izgriezumu veikÅ”anai centrÄ, kas sadala katru gabalu trÄ«s daļÄs.
1)
{0, 1000, 0}
{0, 0, 1000}
Atgriežas:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Taisns trÄ«sstÅ«ris. Atkal mÄs varam sÄkt ar vienu no trim griezumiem pa simetrijas asi.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Atgriežas:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
NeregulÄrs piecstÅ«ris.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
AtgrieŔana: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
KvadrÄts pagriezts par 45 grÄdiem.
[]
AptaujÄ var piedalÄ«ties tikai reÄ£istrÄti lietotÄji. , lÅ«dzu.
Es atrisinÄju problÄmu par
-
mazÄk nekÄ 10 minÅ«tÄs
-
10-30 minūtes
-
30-60 minūtes
-
1-2 stundas
-
vairÄk nekÄ 2 stundu laikÄ
-
cits
Nobalsoja 42 lietotÄji. 47 lietotÄji atturÄjÄs.
Avots: www.habr.com