CSES - Putka Open 2015 – 4/6 - Ratkaisut

A: Pizzeria

Tehtävä

Ensimmäinen osatehtävä ratkeaa käymällä kaikki mahdolliset täytevaihtoehdot läpi ja laskemalla niiden hinnat yhteen.

Toinen osatehtävä ratkeaa myös käymällä kaikki vaihtoehdot läpi. Toteutuksen täytyy olla kuitenkin tehokas ja laskea modulo oikein.

Kolmas osatehtävä perustuu havaintoon, että kun valittavana on n täytettä, jokainen täyte esiintyy 2^{n-1} kertaa pizzoissa. Niinpä kokonaishinta on s \cdot 2^{n-1}, missä s on täytteiden yhteishinta.

B: Taulukot

Tehtävä

Voidaan olettaa, että ylempi taulukko sisältää luvut järjestyksessä 1,2,\ldots,n. Vaikeutena on valita alemman taulukon sisältö.

Yksi mahdollinen konstruktio on etsiä pienin luku x väliltä 1,2,\ldots,n jolle pätee, että x+n on alkuluku. Tällöin myös (x+1)+(n-1) on alkuluku, samoin (x+2)+(n-2) jne., joten kaikki luvut väliltä voi parittaa samoiksi alkuluvuiksi. Tämän jälkeen pitää enää tehdä vastaava konstruktio luvulle x-1. Osoittautuu, että konstruktio onnistuu aina.

Esimerkiksi jos n=8, valitaan x=3. Tästä saadaan parit (3,8), (4,7), (5,6), (6,5), (7,4) ja (8,3). Tämän jälkeen n=2, mikä tuottaa parit (1,2) ja (2,1).

C: Labyrintti

Tehtävä

Yksinkertainen ratkaisu tehtävään on käyttää leveyshakua. Tehokas toteutus ratkaisee kaksi ensimmäistä osatehtävää.

Kolmas osatehtävä vaatii tehokkaan algoritmin. Tärkeä havainto on, että vain pieni määrä ruuduista on kiinnostavia: alkuruutu, loppuruutu sekä seinäruutujen käännöksissä olevat ruudut. Kaikki tällaisten ruutujen parit voi käydä läpi ja laskea suoran etäisyyden niiden välillä (jos välissä ei ole seinäruutuja). Tämän jälkeen ratkaisu selviää esimerkiksi Bellman-Fordin tai Dijkstran algoritmilla.