CSES - Putka Open 2015 – 5/6 - Ratkaisut

A: Keskiarvo

Tehtävä

Tehtävän ratkaisu on yllättävän yksinkertainen, koska suurimman keskiarvon väli muodostuu aina yhdestä luvusta. Niinpä riittää etsiä taulukosta suurin luku.

B: Laivanupotus

Tehtävä

Tehtävän voi ratkaista konstruktiolla, jossa on lävistäjän suuntaisia tarkistuskohtia neljän ruudun välein. Esimerkiksi tapauksen 8 \times 8 ratkaisu on:

...*...*
..*...*.
.*...*..
*...*...
...*...*
..*...*.
.*...*..
*...*...

C: Käännöt

Tehtävä

Jokaista alkuperäisen luvun numeroa voi tarkastella erillisenä, jolloin riittää laskea, monessako käännössä numero esiintyy kussakin kohdassa lukua. Osoittautuu, että tästä muodostuu säännöllinen kuvio, jonka avulla ratkaisun voi laskea tehokkaasti myös silloin, kun n=10^5.