1. Hlúpa intergalatická pošta! vzorové riešenie

820

12

8573

16

Ako najjednoduchšie riešenie je si sitúaciu odsimulovať. Spraviť si pole [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] a pamätať si pozíciu, na ktorej sa nachádzame. Túto pozíciu meníme a pre každé číslo v pin-e si pomocou cyklu cez pole zistíme, ktorá strana je bližšie a na tú stranu sa vydáme. Pri takomto počítaní nemôžeme zabudnúť, že pole je ako keby tvaru kruhu a preto musíme myslieť na pozície na krajoch (1 -> 0 a 0 -> 1). Toto však nie je úplne najlepšie riešenie.

Problém si chceme simulovať, ale nechceme manuálne pohybovať ukazovátkom. Vlastne, z každého bodu máme dve cesty kadiaľ sa vieme vybrať. Buď doľava alebo doprava. Minimum pohybov potrebných na napísanie pinu dostaneme vtedy, keď si vždy vyberieme tú kratšiu cestu. Ešte však treba vymyslieť logiku za tým, koľko krokov potrebujeme na to, aby sme sa dostali na číslo z nejakej pozície.

Stále si potrebujeme pamätať našu pozíciu, no nejdeme krok po kroku, ale vypočítame si počet krokov, ktoré potrebujeme. V našom cykle pozíciu potom vždy updatujeme iba na miesto, kam sa chceme presunúť.

Treba si uvedomiť že k počtu krokov môžeme ihneď pripočítať dĺžku pin kódu, keďže určite budeme musieť každé číslo stlačiť.

Ak sa chceme dostať z čísla 5 na 6 alebo 6 na 5 je to vlastne \(\text{abs}(6-5)\) alebo \(\text{abs}(5-6)\), čo je rovnaké číslo. Musíme však rátať aj s tým, že cesta druhou stranou vie niekedy byť rýchlejšia. Cestu druhou stranou dostaneme keď od celkového počtu políčok odčítame vzdialenosť, ktorú by sme prešli ak by sme nepoužili cestu z 1 na 0. Teda pre nás je to \(10 - \text{abs}(5-6)\), čo nám dá výsledok 9, čo je naozaj počet krokov, keby putujeme druhou stranou. Vzorec na výpočet najkratšej vzdialenosti z pozície \(i\) na pozíciu \(x\) bude teda vyzerať takto: \(\text{min}(\text{abs}(x-i), 10 - \text{abs}(x-i))\)

Menšiu z týchto dvoch možností (ísť doľava alebo doprava) pripočítame k počtu krokov a opakujeme pre všetky čísla v pin-e. Keď prejdeme všetkými číslami v pin-e, vypíšeme celkový počet krokov.

def main():
    code = input()
    res = 0
    prev = 1
    res += len(code)  # pridame pocet znakov, kedze aj zadat znak stoji 1
    for c in code:
        num = int(c)
        if num == 0:
            num = 10  # toto aby 0 bola ako keby na desiatej pozicii
        # pridame minimalnu vzdialenost medzi cislami
        res += min(abs(num - prev), 10 - abs(num - prev))  # 10-abs(num-prev) je vzdialenost ak pouzijeme cyklus
        prev = num  # aktualizujeme nasu poziciu
    print(res) 

if __name__ == "__main__":
    main() # je dobre pouzit main, python potom bezi rychlejsie

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string code;
    cin >> code;
    long long res = 0;
    int prev = 1;
    res+=code.size(); // pridame pocet znakov, kedze aj zadat znak stoji 1
    for(char c : code){
        int num = c - '0'; // prevedieme znak na cislo
        if(num == 0){
            num = 10; // toto aby 0 bola ako keby na desiatej pozicii
        }
        res += min(abs(num-prev), 10-abs(num-prev)); // pridame minimalnu vzdialenost medzi cislami
        //10-abs(num-prev) je vzdialenost ak pouzijeme cyklus
        prev = num; // aktualizujeme nasu poziciu
    }
    std::cout << res << std::endl; //vypiseme vysledok a newline!!
}