Putkaposti: Junarata

Kiitokset tehtävästä: Ville Pettersson

Ympyränmuotoisen junaradan varrella on numeroituja tauluja, jotka täytyy kerätä junaan yksi kerrallaan numerojärjestyksessä. Taulujen keräämiseksi junan täytyy ajaa tietty määrä kierroksia. Esimerkiksi jos taulut ovat järjestyksessä 3, 1, 5, 4, 2, ensimmäisellä kierroksella kerätään taulut 1 ja 2, toisella 3 ja 4 ja kolmannella 5. Näin junan täytyy ajaa yhteensä kolme kierrosta. Keräyksen helpottamiseksi junan kuljettaja saa vaihtaa halutessaan kahden taulun paikan ennen keräyksen aloittamista.

Tehtävä

Jokaiseen testitapaukseen kuuluu joukko numeroituja tauluja. Juna ohittaa taulut vasemmalta oikealle eli ajaa ensin ensimmäisen taulun vierestä, sitten toisen, sitten kolmannen jne., kunnes viimeisen taulun jälkeen alkaa uusi kierros lähtöpaikasta. Tehtävänä on laskea pienin tarvittava kierrosten määrä ja kuinka monta tapaa on valita alussa vaihdettava numeropari tämän kierrosmäärän saavuttamiseksi.

Esimerkissä kierroksia tarvitaan vähimmillään kaksi. Numeroiden vaihtotapoja on silloin kolme:

• 3, 4, 5, 1, 2
• 3, 1, 4, 5, 2
• 3, 1, 2, 4, 5

Muut seitsemän mahdollista numeronvaihtoa johtavat suurempaan kierrosmäärään.

Tehtävään kuuluu yhdeksän erikokoista testitapausta, jotka ovat tiedostossa junar.zip (450 kt). Tiedostoissa ensimmäisellä rivillä on numerotaulujen määrä ja seuraavilla riveillä kunkin taulun numero järjestyksessä vasemmalta oikealle.

Vastausohje

Jokaiselle riville tulee:

• numerotaulujen määrä
• pienin kierrosmäärä
• vaihtotapojen määrä

Vaihtotapojen määrään ei lasketa sitä tapausta, jossa mitään numeroita ei vaihdeta.

Vastaus voisi näyttää seuraavalta:

5 2 3

Tämä on esimerkin oikea vastaus, mutta sitä ei tehtävässä kysytty.