ACM RTK - 2. skupina

It’s raining cubes

Si figurica v arkadni igrici, kjer s stropa padajo kocke. Vsako sekundo se nekje na stropu pojavi kocka, ki s stalno hitrostjo en kvadratek na sekundo pada proti tlom. Ti se lahko vsako sekundo premakneš en kvadratek levo ali desno. Tvoj cilj je, da se izogneš vsem kockam in preživiš; če te kakšna kocka uspe speštati pod sabo v bitne črepinje, pa si igro izgubil. Ko kocka pade na tla, tam ostane in ti blokira pot, tako da ne moreš mimo.

Skupno število kock označimo z n (lahko jih je veliko, n ≤ 107); za vsak čas t od 0 do n-1 vemo, da kocka, ki začne padati ob času t, pada na x-koordinati x_t. Vse kocke začnejo padati z višine h (kocka, ki se pojavi ob času t na višini h, torej pristane na tleh ob času t+h; ob tem času ti torej ne moreš več varno stati na polju x_t ali se nanj premakniti). Tvoj začetni položaj (ob času t = 0) je x = 0.

Števila n, h, x₀, x₁, ..., x_n−1 so podana. Opiši postopek (ali napiši program ali podprogram, če ti je lažje), ki na podlagi teh podatkov ugotovi, ali lahko preživiš ali ne. Če lahko preživiš, opiši tudi potrebne premike. Utemelji, zakaj tvoj postopek deluje.