Putkaposti: Lukujenvihaaja

Kiitokset tehtävästä: Ville Pettersson

Uolevin uusin harrastus on lukujen hävittäminen. Hän on kehittänyt tarkoitukseen yksinkertaisen menetelmän. Jos luku on parillinen, Uolevi jakaa sen kahdella. Jos taas luku on pariton, hän vähentää siitä yhden. Tällä tavalla päästään aina lopuksi lukuun nolla. Esimerkiksi luvun 10 hävittäminen tapahtuu näin: 10 / 2 = 5, 5 - 1 = 4, 4 / 2 = 2, 2 / 2 = 1, 1 - 1 = 0. Luvun 10 hävittämiseen tarvitaan siis kolme jakoa ja kaksi vähennystä.

Jakaminen on Uoleville mieluista, mutta vähentämisestä hän ei juuri pidä. Nyt Uolevi on päättänyt hävittää suuren joukon kokonaislukuja. Kuinka monta kertaa hän joutuu vähentämään ykkösen lukujen hävittämiseksi?

Tehtävä

Jokaisessa testitapauksessa on joukko lukuja väliltä 1 - n, jotka kaikki täytyy hävittää. Jos n on 5, hävitettävänä on siis luvut 1, 2, 3, 4 ja 5. Silloin ykkösiä täytyy vähentää yhteensä 1 + 1 + 2 + 1 + 2 = 7 kertaa. Nämä määrät on laskettu tehtävän alussa kuvatun menetelmän avulla.

Tehtävänäsi on laskea vähennysten yhteismäärä, kun n on:

1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 1234567898, 12345678987, 123456789876, 1234567898765, 12345678987654, 123456789876543, 1234567898765432, 12345678987654321

Vastausohje

Jokaiselle riville tulee testitapauksen n ja vähennysten lukumäärä.

Vastaus voisi näyttää seuraavalta:

5 7

Tämä vastaus ei kuitenkaan kelpaisi, koska n = 5 ei kuulu testitapauksiin.