På sporet af jeg publicerer opgaver fra sporet Algorithm (klassisk sportsprogrammmering. Du har halvanden time til at løse tre opgaver i Java, C#, C++ eller Python.)
1. Kage til seks
Problemformulering
Tidsgreb — 4 sekunder.
Du har en kage. Set ovenfra har kagen formen af en (strengt) konveks polygon. Du får koordinaterne for hjørnerne i heltal X og Y.
Du har fem venner. Du ønsker at dele kagen i seks dele af samme areal (men ikke nødvendigvis samme form). Selvfølgelig kan enhver gøre dette med fem skæringer, men kun en professionel kan gøre det med tre skæringer.
Find tre skæringer med lige linjer gennem ét punkt, som deler kagen i seks lige store dele. Udskriv {x, y, d1, d2, d3}, hvor (x, y) er det fælles punkt for alle tre skæringer, og d1, d2, d3 er skæringsretningerne i radianer.
DefinitionKlasse: CakeForSix
Metode: cut
Parametre: int[], int[]
Returnerer: double[]
Metode-signatur: double[] cut(int[] x, int[] y)
(vær sikker på, at din metode er offentlig)
Noter
- Positiv retning langs x-aksen er lig med 0 (radian), positiv retning langs y-aksen er lig med pi/2 (radian).
- En skæring i retning d er lig med en skæring i retning pi*k+d for enhver heltal k.
- Du kan angive enhver retning, de behøver ikke at være fra [0, pi).
- Graderen vil beregne arealerne af dine seks kagebiter i doubles. Svaret vil blive accepteret, hvis den relative eller absolutte forskel mellem dem er mindre end 10^(-4).
- Nærmere bestemt, lad X og Y være de mindste og de største af dine seks områder beregnet af graderen. Så vil dit svar blive accepteret, hvis Y < max (X+10^(-4), X*1+10^(-4))).
- (I den oprindelige version af opgaven blev der anvendt en præcision på 1e-7 i stedet for 1e-4. For at løse dette problem blev præcisionsgrænsen i arkivet sænket på grund af tilfælde, der sandsynligvis gør opgaven uløselig med præcision 1e-7. I en ideel verden tillader begrænsninger ikke sådanne tilfælde og kræver stadig høj præcision, så det er ikke let at løse problemet med en vis generel numerisk optimering.)
Begrænsninger
- x indeholder mellem 3 og 50 elementer inklusive.
- y indeholder så mange elementer som x.
- alle koordinater mellem 0 og 10 000 inklusive
- x og y definerer en konveks polygon i mod urets retning.
Originalen på engelsk
Problemstilling
Tidsgrænsen er 4 sekunder.
Du har en kage. Set ovenfra er kagen en (strengt) konveks polygon. Du får koordinaterne for dens hjørner i int[]s x og y.
Du har fem venner. Du vil nu spise kagen i seks stykker med samme areal (men ikke nødvendigvis samme form). Selvfølgelig kan enhver gøre det på fem snit — men kun en ægte professionel kan gøre det på tre!
Find tre lige snit, der går gennem det samme punkt, som deler kagen i seks lige store dele. Returner {x, y, d1, d2, d3}, hvor (x, y) er det fælles punkt for de tre snit, og d1, d2, d3 er deres retninger i radianer.
Definition
Klasse: CakeForSix
Metode: cut
Parametre: int[], int[]
Returnerer: double[]
Metode-signatur: double[] cut(int[] x, int[] y)
(vær sikker på, at din metode er offentlig)
Noter
— Den positive retning langs x-aksen er 0 (radianer), den positive retning langs y-aksen er pi/2 (radianer).
— Et snit i retning d er det samme som et snit i retning pi*k+d for enhver heltal k.
— Du må returnere enhver retning, de behøver ikke at være fra [0,pi).
— Bedømmeren vil beregne arealerne af dine seks kagedelene i doubles. Svaret accepteres, hvis den relative eller absolutte forskel mellem dem er mindre end 10^(-4).
— Mere præcist, lad X og Y være de mindste og største af dine seks arealer, som beregnet af bedømmeren. Dit svar accepteres, hvis Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (Den oprindelige version af problemet brugte 1e-7 præcision i stedet for 1e-4. For opskrivning af dette problem i arkivet blev præcisionsgrænsen sænket på grund af eksisterende udfordringstilfælde, der sandsynligvis gør opgaven usikker med 1e-7 præcision. I en ideel verden ville begrænsningerne ikke tillade sådanne tilfælde og stadig kræve høj præcision, så det ikke er nemt at løse problemet via nogen generel numerisk optimering.)
Begrænsninger
— x vil have mellem 3 og 50 elementer, inklusive.
— y vil have samme antal elementer som x.
— Alle koordinater vil være mellem 0 og 10.000, inklusive.
— x og y vil beskrive en konveks polygon i modstående retning.
Eksempler
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returnerer:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Symmetrisk, men ikke regulært sekskant. Eksemplet svarer til at skære det igennem halvvejs vandret og lave to andre snit ved midten, som deler hver del i tre dele.
1)
{0, 1000, 0}
{0, 0, 1000}
Returnerer:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Retvinklet trekant. Igen kan vi starte med et af de tre snit langs symmetriaksen.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returnerer:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Uregelmæssig femkant.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Returnerer: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Kvadrat, roteret 45 grader.
[]
Kun registrerede brugere kan deltage i undersøgelsen. , please.
Jeg løste opgaven på
mindre end 10 minutter
10-30 minutter
30-60 minutter
1-2 timer
mere end 2 timer
andet
42 brugere har stemt. 47 brugere har afholdt sig.
Kilde: habr.com
