Jälgedes Avaldan probleemid Algoritmi rajalt (klassikaline spordiprogrammeerimine. Pooleteise tunni jooksul tuleb lahendada kolm ülesannet Java, C#, C++ või Python keeles.)
1. Pirukas kuuele
Probleemi avaldus
Ajapiirang on 4 sekundit.
Sul on pirukas. Ülalt vaadates on kook (rangelt) kumera hulknurga kujuline. Teile antakse tippude koordinaadid X ja Y täisarvudes.
Sul on viis sõpra. Tahad piruka jagada kuueks võrdse pindalaga tükiks (kuid mitte tingimata sama kujuga). Muidugi saab igaüks seda teha viie lõikega, kuid ainult proff suudab seda teha kolme lõikega.
Otsige kolm lõiget sirgjooneliselt läbi ühe punkti, mis jagavad piruka kuueks võrdseks osaks. Trüki {x, y, d1, d2, d3}, kus (x, y) on kõigi kolme lõike ühine punkt ja d1, d2, d3 on lõigete suunanurgad radiaanides.
MääratlusKlass: CakeForSix
Meetod: lõigatud
Parameetrid: int[], int[] Tagastab: double[] Meetodi signatuur: double[] cut(int[] x, int[] y)
(veenduge, et teie meetod on avalik)
Märkused
- Positiivne suund piki x-telge on 0 (radiaanid), positiivne suund piki y-telge on pi/2 (radiaanid).
- Lõige d-suunas on sarnane pi*k+d-suunalise lõikega mis tahes täisarvu k korral.
- Saate väljastada mis tahes suuna, need ei pea olema alates [0, pi).
- Teehöövel arvutab teie kuue koogitüki pindala kahekordselt. Vastus võetakse vastu, kui nende suhteline või absoluutne erinevus on väiksem kui 10^(-4).
- Täpsemalt olgu X ja Y teehöövli arvutatud kuuest pindalast väikseimad ja suurimad. Seejärel võetakse teie vastus vastu, kui Y
- (Ülesande algversioonis kasutati täpsust 1e-7, mitte 1e-4. Selle probleemi lahendamiseks arhiivis alandati täpsuspiiri, kuna esines kutsumisjuhtumeid, mis muudaksid probleemi tõenäoliselt täpsusega lahendamatuks 1e-7. Ideaalses maailmas ei luba piirangud selliseid juhtumeid ja nõuavad siiski suurt täpsust, seega pole probleemi lahendamine üldise numbrilise optimeerimisega lihtne.)
Piirangud
- x sisaldab 3 kuni 50 elementi (kaasa arvatud).
- y sisaldab sama arvu elemente kui x.
- kõik koordinaadid vahemikus 0 kuni 10 000 (kaasa arvatud).
- x ja y määratlevad kumera hulknurga vastupäeva.
Originaal inglise keeles
Probleemipüstituses
Ajapiirang on 4 sekundit.
Sul on kook. Ülevalt vaadatuna on kook (rangelt) kumer hulknurk. Sulle antakse selle tippude koordinaadid punktides int[]sx ja y.
Sul on viis sõpra. Nüüd soovite koogi lõigata kuueks võrdse pindalaga (kuid mitte tingimata võrdse kujuga) tükiks. Muidugi saab igaüks seda teha viie lõikega – kuid ainult tõeline proff suudab seda teha kolmega!
Leidke kolm sama punkti läbivat sirgjoonelist lõiget, mis lõikasid koogi kuueks võrdselt suureks osaks. Tagastus {x, y, d1, d2, d3}, kus (x, y) on kolme lõike ühine punkt ja d1, d2, d3 on nende suunad radiaanides.
Määratlus
Klass: CakeForSix
Meetod: lõigatud
Parameetrid: int[], int[] Tagastab: double[] Meetodi signatuur: double[] cut(int[] x, int[] y)
(veenduge, et teie meetod on avalik)
märkused
— Positiivne suund piki x-telge on 0 (radiaanid), positiivne suund piki y-telge on pi/2 (radiaanid).
— Lõikus suunas d on sama mis lõikamine suunas pi*k+d mis tahes täisarvu k korral.
— Võite tagastada mis tahes juhised, need ei pea olema alates [0,pi).
— Teehöövel arvutab teie kuue koogitüki pindala kahekordselt. Vastus võetakse vastu, kui nende suhteline või absoluutne erinevus on väiksem kui 10^(-4).
— Täpsemalt, olgu X ja Y teie kuuest piirkonnast väikseimad ja suurimad, nagu teehöövel on arvutanud. Seejärel aktsepteeritakse teie vastust, kui Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Ülesande algversioon kasutas 1e-7 asemel 1e-4 täpsust. Selle probleemi lahendamiseks arhiivis alandati täpsuspiiri, kuna esinesid väljakutsejuhtumid, mis tõenäoliselt muudavad ülesande 1e-7 täpsusega lahendamatuks Ideaalses maailmas ei lubaks piirangud selliseid juhtumeid ja nõuavad siiski suurt täpsust, nii et probleemi lahendamine üldise numbrilise optimeerimise abil ei ole lihtne.)
Piirangud
— x sisaldab 3–50 elementi (kaasa arvatud).
— y-l on sama arv elemente kui x-il.
— Kõik koordinaadid on vahemikus 0 kuni 10,000 XNUMX (kaasa arvatud).
— x ja y kirjeldavad kumerat hulknurka vastupäeva.
näited
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Tagastamine:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Sümmeetriline, kuid ebakorrapärane kuusnurk. Näidisvastus vastab selle horisontaalselt pooleks lõikamisele ja kahe teise sisselõigete tegemisele keskele, mis jagavad iga tüki kolmeks osaks.
1)
{0, 1000, 0}
{0, 0, 1000}
Tagastamine:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Täisnurkne kolmnurk. Jällegi saame alustada ühega kolmest lõikest piki sümmeetriatelge.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Tagastamine:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Ebakorrapärane viisnurk.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Tagastamine: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
45 kraadi pööratud ruut.
[]
Küsitluses saavad osaleda ainult registreerunud kasutajad. palun.
Ma lahendasin probleemi eest
-
vähem kui 10 minutiga
-
10-30 minuti
-
30-60 minuti
-
1-2 tundi
-
rohkem kui 2 tunni jooksul
-
muu
42 kasutajat hääletas. 47 kasutajat jäi erapooletuks.
Allikas: www.habr.com