CSES - Putka Open 2015 – 3/6 - Ratkaisut

A: Kasat

Tehtävä

Ensimmäinen osatehtävä ratkeaa simuloimalla Uolevin siirtoja yksi kerrallaan.

Toinen osatehtävä ratkeaa toteuttamalla tehokkaasti loppusiirrot, joiden aikana jokaisessa kasassa on tasaisesti tikkuja. Osoittautuu, että joko kasojen sisältö säilyy vakiona tai se vuorottelee kahden yhdistelmän välillä.

Kolmas osatehtävä vaatii, että myös tasapainoa edeltävän osuuden toteutus on tehokas. Siinä on muutamia tapauksia riippuen siitä, miten tikut ovat jakautuneet kasoihin.

B: Onnenluku

Tehtävä

Ensimmäinen osatehtävä ratkeaa käymällä kaikki välin a \ldots b luvut läpi ja tarkastamalla, moniko niistä on onnenluku.

Toinen osatehtävä ratkeaa muodostamalla kaikki onnenluvut, jotka ovat välillä a \ldots b. Tämä onnistuu tehokkaasti käymällä läpi kaikki vaihtoehdot, mitkä kaksi numeroa muodostavat onnenluvun.

Kolmas osatehtävä ratkeaa laskemalla dynaamisella ohjelmoinnilla onnenlukujen määrän. Laskemista helpottaa se, että riittää laskea funktion f(n) arvoja, missä f(n) on onnenlukujen määrä välillä 1 \ldots n. Tällöin ratkaisu tehtävään on f(b)-f(a-1).

C: Ruudukko

Tehtävä

Tehtävän ratkaisemiseen on olemassa monta mahdollista konstruktiota.

Hyvä lähtökohta on esittää luku summana 2:n potensseja. Tämän jälkeen riittää muodostaa jokaiselle 2:n potenssille oma käytävä, jotka yhdistyvät lopuksi. Ratkaisu muodostuu valitsemalla ruudukkoon ne käytävät, joiden 2:n potenssien summana saadaan haluttu luku.