I fotsporene Jeg publiserer problemer fra Algoritme-sporet (klassisk sportsprogrammering. På halvannen time må du løse tre oppgaver i Java, C#, C++ eller Python.)
1. Pai for seks
Formulering av problemet
Tidsbegrensningen er 4 sekunder.
Du har en pai. Sett ovenfra har kaken formen av en (strengt) konveks polygon. Du får koordinatene til toppunktene i X- og Y-heltall.
Du har fem venner. Du vil dele paien i seks stykker med like areal (men ikke nødvendigvis samme form). Selvfølgelig kan hvem som helst gjøre det i fem kutt, men bare en proff kan gjøre det i tre kutt.
Finn tre snitt i rette linjer gjennom ett punkt som vil dele paien i seks like deler. Skriv ut {x, y, d1, d2, d3}, hvor (x, y) er fellespunktet for alle tre kuttene, og d1, d2, d3 er retningsvinklene til kuttene i radianer.
DefinisjonKlasse: CakeForSix
Metode: kutte
Parametere: int[], int[] Returnerer: double[] Metodesignatur: double[] cut(int[] x, int[] y)
(pass på at metoden din er offentlig)
Merknader
- Den positive retningen langs x-aksen er 0 (radianer), den positive retningen langs y-aksen er pi/2 (radianer).
- Et kutt i d-retningen ligner et kutt i pi*k+d-retningen for et hvilket som helst heltall k.
- Du kan sende ut alle retninger, de trenger ikke være fra [0, pi).
- Graderen vil beregne arealet til de seks kakestykkene dine i dobler. Svaret vil bli akseptert hvis den relative eller absolutte forskjellen mellom dem er mindre enn 10^(-4).
- Mer presist, la X og Y være de minste og største av dine seks arealer beregnet av graderen. Da vil svaret ditt bli akseptert hvis Y
- (Den opprinnelige versjonen av problemet brukte en presisjon på 1e-7 i stedet for 1e-4. For å løse dette problemet i arkivet ble presisjonsgrensen senket på grunn av tilstedeværelsen av oppringningssaker som sannsynligvis ville gjøre problemet uløselig med en presisjon av 1e-7. I en ideell verden tillater ikke grensene slike tilfeller og krever fortsatt høy presisjon, så det er ikke lett å løse problemet med noen generell numerisk optimalisering.)
Restriksjoner
- x inneholder fra 3 til 50 elementer inkludert.
- y inneholder samme antall elementer som x.
- alle koordinater mellom 0 og 10 000 inklusive
- x og y definerer en konveks polygon i retning mot klokken.
Original på engelsk
Problemstilling
Tidsbegrensningen er 4 sekunder.
Du har en kake. Sett ovenfra er kaken en (strengt) konveks polygon. Du får koordinatene til toppene i int[]sx og y.
Du har fem venner. Du vil nå skjære kaken i seks stykker med like areal (men ikke nødvendigvis lik form). Selvfølgelig kan hvem som helst gjøre det i fem kutt - men bare en ekte proff kan gjøre det på tre!
Finn tre rettlinjede kutt som går gjennom samme punkt som skjærer kaken i seks like store deler. Returner {x, y, d1, d2, d3}, der (x, y) er fellespunktet for de tre kuttene, og d1, d2, d3 er deres retninger i radianer.
Definisjon
Klasse: CakeForSix
Metode: kutte
Parametere: int[], int[] Returnerer: double[] Metodesignatur: double[] cut(int[] x, int[] y)
(pass på at metoden din er offentlig)
Merknader
— Den positive retningen langs x-aksen er 0 (radianer), den positive retningen langs y-aksen er pi/2 (radianer).
— Et kutt i retning d er det samme som et kutt i retning pi*k+d for et heltall k.
— Du kan returnere alle veibeskrivelser, de trenger ikke være fra [0,pi).
— Graderen vil beregne arealene til de seks kakestykkene dine i dobler. Svaret vil bli akseptert hvis den relative eller absolutte forskjellen mellom dem er mindre enn 10^(-4).
— Mer presist, la X og Y være de minste og største av dine seks områder, beregnet av graderen. Deretter vil svaret ditt bli akseptert hvis Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Den opprinnelige versjonen av problemet brukte 1e-7 presisjon i stedet for 1e-4. For å løse dette problemet i arkivet ble presisjonsgrensen senket på grunn av eksistensen av utfordringstilfeller som mest sannsynlig gjør oppgaven uløselig med 1e-7 presisjon I en ideell verden ville begrensningene ikke tillate slike tilfeller og fortsatt kreve høy presisjon, slik at det ikke er lett å løse problemet via noen generell numerisk optimalisering.)
begrensninger
— x vil ha mellom 3 og 50 elementer, inkludert.
— y vil ha samme antall elementer som x.
— Alle koordinater vil være mellom 0 og 10,000 inklusive.
— x og y vil beskrive en konveks polygon i rekkefølge mot klokken.
Примеры
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returnerer:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
En symmetrisk, men uregelmessig sekskant. Eksempelsvaret tilsvarer å kutte den i to horisontalt og lage to andre kutt nedover i midten som deler hver del i tre deler.
1)
{0, 1000, 0}
{0, 0, 1000}
Returnerer:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Høyre trekant. Igjen kan vi starte med ett av tre kutt langs symmetriaksen.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returnerer:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Uregelmessig femkant.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Returer: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
En firkant rotert 45 grader.
[]
Kun registrerte brukere kan delta i undersøkelsen. , vær så snill.
Jeg løste problemet for
-
på mindre enn 10 minutter
-
10-30 minutter
-
30-60 minutter
-
1-2 timer
-
på mer enn 2 timer
-
andre
42 brukere stemte. 47 brukere avsto.
Kilde: www.habr.com