Kirjautuminen

Haku

Tehtävät

Putkaposti: Junarata

Kirjoittaja: Antti Laaksonen

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:

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:

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.

Vastaukset

40 henkilöllä on tulos. Suluissa oleva luku tarkoittaa ratkaistujen tapausten määrää.

os (9), KemXy (9), Touho (9), A1A (9), BadSource (9), Sami (9), Chiman (9), FooBat (9), Metabolix (9), lukujenVihaaja (9), Pekka Karjalainen (9), jlaire (9), Sisuaski (9), Konvehti (9), Laitinen (9), L2-K2 (9), kllp (9), Jhuunhym (9), jnalanko (9), Laakeri (9), TapaniS (9), öppis (9), symbols (9), johku90 (9), Legu (9), membolic (9), Jaska (9), Ruokauuni (9), isashkar (9), copyrite (8), mikaelh (7), Torgo (7), Deewiant (5), Jalmari91 (5), Anaatti (5), ahr (5), Andu (4), qalle (4), Jepso (3), Salama (3)

Kirjaudu sisään Ohjelmointiputkaan, niin voit lähettää vastauksen tehtävään.

Keskustelu

Katso myös Putkaposti 7: Junarata.

Tietoa sivustosta