In die voetspore Ek publiseer probleme vanaf die Algoritme-snit (klassieke sportprogrammering. In een en 'n half uur moet jy drie probleme in Java, C#, C++ of Python oplos.)
1. Pastei vir ses
Probleemstelling
Die tydsbeperking is 4 sekondes.
Jy het 'n pastei. As dit van bo af gesien word, het die koek die vorm van 'n (streng) konvekse veelhoek. Jy kry die koördinate van die hoekpunte in X- en Y-heelgetalle.
Jy het vyf vriende. Jy wil die tert in ses stukke van gelyke oppervlakte verdeel (maar nie noodwendig dieselfde vorm nie). Natuurlik kan enigiemand dit in vyf snitte doen, maar net 'n pro kan dit in drie snitte doen.
Soek drie reguitlynsnitte deur een punt wat die tert in ses gelyke dele sal verdeel. Druk {x, y, d1, d2, d3}, waar (x, y) die gemeenskaplike punt van al drie snitte is, en d1, d2, d3 die rigtinghoeke van die snitte in radiale is.
DefinisieKlas: CakeForSix
Metode: sny
Parameters: int[], int[] Wys: dubbel[] Metode handtekening: dubbel[] sny(int[] x, int[] y)
(maak seker jou metode is publiek)
Notes
- Die positiewe rigting langs die x-as is 0 (radiane), die positiewe rigting langs die y-as is pi/2 (radiane).
- 'n Sny in die d-rigting is soortgelyk aan 'n snit in die pi*k+d-rigting vir enige heelgetal k.
- Jy kan enige aanwysings uitvoer, dit hoef nie van [0, pi te wees nie).
- Die gradeerder sal die oppervlakte van jou ses stukke koek in dubbel bereken. Die antwoord sal aanvaar word as die relatiewe of absolute verskil tussen hulle minder as 10^(-4) is.
- Meer presies, laat X en Y die kleinste en grootste van jou ses areas wees wat deur die gradeerder bereken word. Dan sal jou antwoord aanvaar word as Y
- (Die oorspronklike weergawe van die probleem het 'n presisie van 1e-7 in plaas van 1e-4 gebruik. Om hierdie probleem in die argief op te los, is die presisielimiet verlaag as gevolg van die teenwoordigheid van oproepgevalle wat die probleem waarskynlik onoplosbaar sou maak met 'n presisie van 1e-7. In 'n ideale wêreld laat die perke nie sulke gevalle toe nie en vereis steeds hoë presisie, dus is dit nie maklik om die probleem met 'n paar algemene numeriese optimalisering op te los nie.)
Beperkings
- x bevat van 3 tot 50 elemente ingesluit.
- y bevat dieselfde aantal elemente as x.
- alle koördinate tussen 0 en 10 000 ingesluit
- x en y definieer 'n konvekse veelhoek in 'n antikloksgewyse rigting.
oorspronklike in Engels
Probleemstelling
Tydsbeperking is 4 sekondes.
Jy het 'n koek. Van bo gesien is die koek 'n (streng) konvekse veelhoek. Jy kry die koördinate van sy hoekpunte in die int[]sx en y.
Jy het vyf vriende. Jy wil nou die koek in ses stukke van gelyke oppervlakte sny (maar nie noodwendig gelyke vorm nie). Natuurlik kan enigiemand dit in vyf snitte doen - maar net 'n ware pro kan dit in drie doen!
Soek drie reguitlynsnitte wat deur dieselfde punt gaan wat die koek in ses ewe groot dele gesny het. Keer terug {x, y, d1, d2, d3}, waar (x, y) die gemeenskaplike punt van die drie snitte is, en d1, d2, d3 hul rigtings in radiale is.
Definisie
Klas: CakeForSix
Metode: sny
Parameters: int[], int[] Wys: dubbel[] Metode handtekening: dubbel[] sny(int[] x, int[] y)
(maak seker jou metode is publiek)
Notes
— Die positiewe rigting langs die x-as is 0 (radiale), die positiewe rigting langs die y-as is pi/2 (radiane).
— 'n Sny in rigting d is dieselfde as 'n snit in rigting pi*k+d vir enige heelgetal k.
— Jy mag enige aanwysings terugstuur, dit hoef nie van [0,pi af te wees nie).
— Die gradeerder sal die oppervlaktes van jou ses koekstukke in dubbels bereken. Die antwoord sal aanvaar word as die relatiewe of absolute verskil tussen hulle minder as 10^(-4) is.
— Meer presies, laat X en Y die kleinste en die grootste van jou ses areas wees, soos deur die gradeerder bereken. Dan sal jou antwoord aanvaar word as Y < maks( X + 10^(-4), X * (1+10^(-4)) ).
— (Die oorspronklike weergawe van die probleem het 1e-7-presisie in plaas van 1e-4 gebruik. Vir die oplossing van hierdie probleem in die argief is die presisielimiet verlaag as gevolg van die bestaan van uitdagingsgevalle wat die taak heel waarskynlik onoplosbaar maak met 1e-7 presisie In 'n ideale wêreld sal die beperkings nie sulke gevalle toelaat nie en steeds hoë presisie vereis, sodat dit nie maklik is om die probleem op te los deur 'n paar algemene numeriese optimalisering nie.)
beperkings
— x sal tussen 3 en 50 elemente hê, insluitend.
— y sal dieselfde aantal elemente as x hê.
— Alle koördinate sal tussen 0 en 10,000 XNUMX wees, insluitend.
— x en y sal 'n konvekse veelhoek in antikloksgewyse volgorde beskryf.
voorbeelde
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Opgawes:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
’n Simmetriese maar onreëlmatige seshoek. Die voorbeeld antwoord stem ooreen om dit horisontaal in die helfte te sny en twee ander snitte in die middel te maak wat elke stuk in drie dele verdeel.
1)
{0, 1000, 0}
{0, 0, 1000}
Opgawes:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Reghoekige driehoek. Weereens kan ons begin met een van drie snitte langs die simmetrie-as.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Opgawes:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Onreëlmatige vyfhoek.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Returns: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
'n Vierkant het 45 grade gedraai.
[]
Slegs geregistreerde gebruikers kan aan die opname deelneem. , asseblief.
Ek het die probleem opgelos vir
-
in minder as 10 minute
-
10-30 minute
-
30-60 minute
-
1-2 uur
-
oor meer as 2 uur
-
ander
42 gebruikers het gestem. 47 gebruikers het buite stemming gebly.
Bron: will.com