A nyomában Problémákat teszek közzé az Algoritmus sávból (klasszikus sportprogramozás. Másfél óra alatt három feladatot kell megoldani Java, C#, C++ vagy Python nyelven.)
1. Pite hatra
Probléma nyilatkozat
Az időkorlát 4 másodperc.
Van egy pite. Felülről nézve a torta (szigorúan) konvex sokszög alakú. Megadjuk a csúcsok koordinátáit X és Y egész számokban.
Öt barátod van. Hat egyenlő területű (de nem feltétlenül azonos alakú) darabra szeretné osztani a pitét. Természetesen bárki meg tudja csinálni öt vágásban, de csak egy profi képes három vágással.
Keressen három egyenes vonalú vágást egy ponton keresztül, amelyek hat egyenlő részre osztják a tortát. Nyomtassa ki a következőt: {x, y, d1, d2, d3}, ahol (x, y) mindhárom vágás közös pontja, d1, d2, d3 pedig a vágások irányszögei radiánban.
MeghatározásOsztály: CakeForSix
Módszer: vágás
Paraméterek: int[], int[] Visszatér: double[] Metódus aláírása: double[] cut(int[] x, int[] y)
(Győződjön meg róla, hogy a módszer nyilvános)
Megjegyzések
- A pozitív irány az x tengely mentén 0 (radián), a pozitív irány az y tengely mentén pi/2 (radián).
- A d irányú vágás hasonló a pi*k+d irányú vágáshoz bármely k egész szám esetén.
- Bármilyen irányt kiadhatsz, nem kell, hogy [0, pi]-től származzanak.
- Az osztályozó kétszeresen kiszámolja a hat szelet tortád területét. A választ akkor fogadjuk el, ha a köztük lévő relatív vagy abszolút különbség kisebb, mint 10^(-4).
- Pontosabban, legyen X és Y a legkisebb és a legnagyobb az osztályozó által kiszámított hat terület közül. Akkor válaszát elfogadjuk, ha Y
- (A probléma eredeti verziója 1e-7 pontosságot használt 1e-4 helyett. A probléma megoldása érdekében az archívumban a pontossági határt csökkentették, mivel olyan hívási esetek voltak jelen, amelyek valószínűleg precízen megoldhatatlanná teszik a problémát Ideális világban a korlátok nem teszik lehetővé az ilyen eseteket, és még mindig nagy pontosságot igényelnek, így a probléma általános numerikus optimalizálással történő megoldása nem egyszerű.)
Korlátozások
- Az x 3-50 elemet tartalmaz.
- y ugyanannyi elemet tartalmaz, mint x.
- minden koordináta 0 és 10 000 között van
- x és y egy konvex sokszöget határoz meg az óramutató járásával ellentétes irányban.
eredeti angolul
Problémanyilatkozat
Az időkorlát 4 másodperc.
Van egy tortád. Felülről nézve a torta egy (szigorúan) domború sokszög. Megadjuk a csúcsainak koordinátáit az int[]sx és y-ban.
Öt barátod van. Most a tortát hat egyenlő területű (de nem feltétlenül azonos alakú) darabra szeretné felvágni. Természetesen ezt bárki meg tudja csinálni öt vágásban – de csak egy igazi profi képes háromra!
Keressen három egyenes vonalú vágást, amelyek ugyanazon a ponton haladnak át, amelyek hat egyforma nagy részre vágják a tortát. Return {x, y, d1, d2, d3}, ahol (x, y) a három vágás közös pontja, és d1, d2, d3 az irányuk radiánban.
Meghatározás
Osztály: CakeForSix
Módszer: vágás
Paraméterek: int[], int[] Visszatér: double[] Metódus aláírása: double[] cut(int[] x, int[] y)
(Győződjön meg róla, hogy a módszer nyilvános)
Megjegyzések
— A pozitív irány az x tengely mentén 0 (radián), a pozitív irány az y tengely mentén pi/2 (radián).
— A d irányú vágás bármely k egész számra megegyezik a pi*k+d irányú vágással.
— Bármilyen irányt visszaküldhet, azoknak nem kell a [0,pi) helyről származniuk.
— Az osztályozó kétszeresen számítja ki a hat tortadarabod területét. A választ akkor fogadjuk el, ha a köztük lévő relatív vagy abszolút különbség kisebb, mint 10^(-4).
— Pontosabban, legyen X és Y a legkisebb és a legnagyobb a hat terület közül, a gréder által kiszámítva. Ekkor a válaszát elfogadjuk, ha Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (A feladat eredeti verziója 1e-7 pontosságot használt 1e-4 helyett. Ennek a feladatnak az archívumban való megoldásához a pontossági határt csökkentették a kihívás esetek miatt, amelyek nagy valószínűséggel 1e-7 pontossággal teszik megoldhatatlanná a feladatot. Egy ideális világban a korlátok nem engedik meg az ilyen eseteket, és még mindig nagy pontosságot igényelnek, így nem könnyű valamilyen általános numerikus optimalizálással megoldani a problémát.)
megszorítások
— x 3 és 50 közötti elemből áll.
— y-nek ugyanannyi eleme lesz, mint x-nek.
— Minden koordináta 0 és 10,000 XNUMX között lesz.
— x és y egy konvex sokszöget ír le az óramutató járásával ellentétes sorrendben.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Garancia:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Szimmetrikus, de szabálytalan hatszög. A példa válasz megfelel annak, hogy vízszintesen kettévágjuk, és két másik vágást készítünk a közepén, amelyek mindegyik darabot három részre osztják.
1)
{0, 1000, 0}
{0, 0, 1000}
Garancia:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Derékszögű háromszög. Ismét a szimmetriatengely mentén három vágás egyikével kezdhetjük.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Garancia:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Szabálytalan ötszög.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Visszaküldés: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
45 fokkal elforgatott négyzet.
[]
A felmérésben csak regisztrált felhasználók vehetnek részt. , kérem.
számára megoldottam a problémát
-
kevesebb, mint 10 perc alatt
-
10-30 perc
-
30-60 perc
-
1-2 óra
-
több mint 2 órán belül
-
más
42 felhasználó szavazott. 47 felhasználó tartózkodott.
Forrás: will.com