Problém týždňa 1

Zadanie

Na vstupe je veľaciferné nezáporné celé číslo, ktorého niektoré cifry (aspoň jedna) sú nahradené otáznikom.

Doplňte namiesto otáznikov cifry tak, aby vzniklo číslo deliteľné 9. Ak existuje viacero možností, nájdite najmenšiu z nich.

Formát vstupu

V jedinom riadku vstupu je reťazec tvorený $1$ až $10^5$ znakmi. Každý znak je buď cifra alebo otáznik. V reťazci je aspoň jeden otáznik. Ak je prvý znak reťazca cifra, nie je to 0.

Formát výstupu

Vypíšte jediný riadok a v ňom opravené číslo. Opravené číslo nesmie mať na začiatku zbytočné nuly. Ak existuje viacero možností ako číslo opraviť, vypíšte najmenšiu z nich.

# Vstup
12?3
# Výstup
1233

# Vstup
?
# Výstup
0

# Vstup
10??
# Výstup
1008

Riešenie

V zadaní sa spomína deliteľnosť číslom 9, preto úplne prirodzene by nás malo zaujímať, kedy je číslo deliteľné číslom 9. Rozmaznaní informatikou si môžeme povedať, že predsa vtedy, keď cislo % 9 == 0, to však nie je veľmi použiteľné, keď mi žiadne číslo v podstate nemáme, vyskytujú sa v ňom totiž nejaké otázniky. Našťastie, ešte z dávnej matematiky by sme si mohli pamätať, že číslo je deliteľné 9 ak je jeho ciferný súčet deliteľný 9. To znie ako správna myšlienka, pretože ľahko vieme zistiť, aký ciferný súčet majú cifry, ktoré reálne máme zadané a aký ciferný súčet majú mať cifry zakryté ?.

Ako prvé si teda môžeme spočítať všetky cifry v našom čísle, čím dostaneme čiastočný ciferný súčet. Vieme, že po doplnení otáznikov musí byť tento súčet deliteľný 9. Koľko mu do toho chýba teraz? No nie veľa, v skutočnosti najviac 8. Ak sa totiž pozrieme na zvyšok súčtu po delení 9, tak vieme určiť, koľko ešte musíme pripočítať aby sme dostali zvyšok 0 a teda číslo deliteľné 9. Pre číslo 185, ktoré má súčet 14, teda zvyšok 5 po delení 9 nám do deliteľnosti 9 chýba pripočítať 4.

Ak by sme teda chceli, stačilo by jeden otáznik vymeniť za tento doplnok do deliteľnosti (a keďže je menší ako 9 tak sa to zmestí do jednej cifry), všade inde dať 0 a máme vhodné číslo. Teda takmer. V zadaní sa píše, že vytvorené číslo má byť najmenšie možné. Ale tak nahradiť väčšinu otáznikov nulami znie ako dobrý spôsob zmenšovania čísla. Ak chceme vytvoriť čo najmenšie číslo, tak naozaj chceme dať na čo najviac miest 0 a iba namiesto posledného otáznika dať chýbajúcu cifru, ktorá doplní ciferný súčet.

Náš algoritmus teda vyzerá pomerne jednoducho – spočítaj cifry čísla, ktoré vidíme a z tohto súčtu zistime, akú cifru potrebujeme pridať, aby bol tento súčet deliteľný 9. Následne touto cifrou nahradíme posledný možný otáznik a všetky zvyšné nahradíme cifrou 0.

Ešte si pre istotu raz poriadne prečítame zadanie a pozrieme ukážkové vstupy, či sme na niečo nezabudli. Vo formáte výstupu sa spomína, že vytvorené číslo nemôže začínať prebytočnou cifrou 0. My však pridávame pomerne veľa núl, neporušujeme teda toto pravidlo? Čo ak bude ? na začiatku čísla?

Tak si poďme poriadne rozmyslieť, ako čo najjednoduchšie vyriešiť tento problém. Vieme, že na začiatku je ? a musíme si dať pozor, aby sme nevytvorili prebytočnú 0 na začiatku. 0 na začiatku však môže byť, ak má číslo práve jednu cifru. Ako prvé teda zistíme, aké dlhé je zadané číslo. Ak má 1 cifru, môžeme tam dať 0. V opačnom prípade tam 0 byť nemôže. Znamená to teda, že tam dáme tú chýbajúcu cifru a zvyšok vyplníme 0 ako pred tým? Nie úplne. Naším cieľom je vytvoriť čo najmenšie číslo a práve prvá cifra je tá, ktorá jeho veľkosť najviac ovplyvňuje. Najmenšia hodnota prvej cifry môže byť 1, mohli by sme tam teda tú 1 dať. Uvedomme si, že tým sme problém veľmi nezmenili. Opäť sme dostali číslo, v ktorom je niekoľko ?, ktoré potrebujeme nahradiť tak, aby bol ciferný súčet deliteľný 9. Teraz však už prvá cifra určite nie je ? (lebo je tam 1) a teda len zistíme súčet, posledný ? nahradíme doplnkom do 9 a zvyšné ? nulami.

Už je to dobre? Ešte stále nie, skúsme sa zamyslieť, kedy neplatí to, čo sme povedali pred chvíľou. Vtedy, keď neostali žiadne ďalšie ? na doplnenie. Vtedy sme si to tou 1 možno dosť pokazili. Takže ošetríme ešte tento prípad – v čísle je jediný ? a nachádza sa na prvej pozícii. Vtedy nemáme na výber, iba tam dať doplnok do deliteľnosti 9. S jednou špecialitkou, že ak je súčet zadaných čísel už na začiatku deliteľný 9, tak prvá cifra musí byť 9.

Riešenie vôbec nie je také ťažké, ako to možno vyzerá. Stačí si poriadne rozmyslieť všetky špeciálne prípady a poriadne sa zamyslieť nad vlastnými vyjadreniami, či nespôsobujú problém. A dokonca to vieme celé veľmi ľahko naprogramovať. Tu je návod.

Načítame si zadaný reťazec. S reťazcom sa v Pythone pracuje zle, pretože ho nevieme meniť, jednoduchšie teda bude previesť si ho do listu. To dokonca ľahko spravíme funkciou list(), ktorej do vnútra dáme list a ona nám vráti pole skladajúce sa z jeho znakov. Následne prejdeme celým poľom a zistíme, koľko ? sa v ňom nachádza a spočítame ciferný súčet neotáznikov. Treba si však dať pozor, že jednotlivé prvky poľa sú stále vo formáte reťazca a ak ich chceme sčítavať, tak treba použiť int() (a nepoužiť ju na ?).

Teraz ošetríme ? na začiatku poľa. Ak je ? prvý a pole má dĺžku 1, nahradíme tento otáznik cifrou 0. Ak je stále ? na začiatku, ale pole je dlhšie, zistíme, koľko tých otáznikov sa tam nachádza. Ak je tento otáznik jediný, musíme ho nahradiť doplnkom ciferného súčtu, pričom si špeciálne dáme pozor na doplnok 0, namiesto ktorého použijeme cifru 9. Ak je tam otáznikov viac, nahradíme ten prvý cifrou 1 a zväčšíme si o 1 aj ciferný súčet.

Po tejto časti programu vieme, že sme vyriešili ? na začiatku a ak tam ešte nejaké ? zostali, sú už na ďalších pozíciách. Túto časť teda nemusíme robiť vo vnútri ifu dvakrát (čo je mega cool). Ďalšiu časť programu totiž môžeme spraviť vždy, lebo napríklad ak tam žiadne ? nie sú, nič nespraví. Prejdeme pole odzadu, prvý ?, ktorý nájdeme nahradíme doplnkom deliteľnosti a všetky zvyšné nahradíme 0. Na to môžeme napríklad použiť premennú, v ktorej si pamätáme, či sme už stretli prvú ? odzadu. Ide to však aj jednoduchšie cez premennú, v ktorej si pamätáme, čo chceme zapisovať (môžete si rozmyslieť).

A ešte si celý čas dajte pozor, aby ste do poľa dávali reťazce a nie čísla. Teda použite str() pri zámene ? za číslo.

Testovanie a odovzdávanie

Zip súbor so vstupmi a testerom

K dispozícii dostanete niekoľko vstupov, vašou úlohou bude naprogramovať riešenie, ktoré vráti správnu odpoveď na každý z nich. Vstup je vždy v súbore cislo.in a výstup v súbore cislo.out. Môžete sa do nich pozerať a zisťovať, prečo na nich vaše riešenie nefunguje.

Aby ste si to vedeli pekne testovať, spravil som malý program, ktorý to bude robiť za vás. Možno vymyslím niečo lepšie časom, zatiaľ ale musíte používať toto. V podstate, vašou úlohou je iba doprogramovať jednu funkciu, ktorá sa následne otestuje na daných vstupoch a povie vám, že ktoré ste vyriešili. V tejto funkcii nemusíte riešiť vstup ani výstup. Vstup dostanete už trošku spracovaný v poli cislo[], výsledok má byť na konci funkcie tiež v tomto poli. Bližší popis nájdete v komentári daného programu.

Odovzdávať mi to môžete na mail, v podstate stačí poslať program, ktorý úlohu správne rieši a aj pre mňa jednoduchšie to bude, ak to v podstate pošlete všetko naraz (ale výhovorky “Robil som to priebežne, ale zrovna včera sa všetko vymazalo…” neberiem samozrejme :P)