CSES - Putka Open 2015 – 6/6 - Ratkaisut

A: Tutkat

Tehtävä

Jos kaikki tutkat ovat samalla suoralla, Timpan sijaintia ei ole mahdollista selvittää, koska Timppa voi olla kummalla tahansa puolella suoraa. Sen sijaan kaikissa muissa tapauksissa Timpan sijainnin saa selville. Niinpä riittää tarkistaa, ovatko pisteet samalla suoralla.

B: Bittilista

Tehtävä

Osoittautuu, että listalla ovat kaikki bittijonot, joissa ensimmäinen ja viimeinen bitti on sama (molemmat ovat nollia tai molemmat ovat ykkösiä). Tämä johtuu siitä, että jokainen bittijonossa esiintyvä bitin vaihdos tuottaa joko jonon 01 tai 10.

C: Shakki

Tehtävä

Tähän tehtävään on monia mahdollisia konstruktioita, ja satunnaisuudesta voi olla hyötyä. Yksi mahdollinen ratkaisu on jakaa lauta neljään osaan 4 \times 4 -alineliöiksi. Ensimmäinen askel on varmistaa, että jokaisessa alineliössä on yhtä paljon mustia ja valkeita ruutuja. Tämän jälkeen alineliöt voi käsitellä toisistaan riippumattomasti ja järjestää niiden ruudut oikeaan järjestykseen.