Zadanie

Vladko je masívny podnikateľ, ktorý vlastní obrovské pole. Nemá ale čas ho sám poorať. Preto si zavolal Merlina z ďalekej Prahy aby mu ho pooral. Merlina fakt baví orať polia. Robí to už od malička, takže nemal čas chodiť do školy ani naučiť sa počítať v desiatkovej sústave. Keď Merlin dooral, napísal na papier koľko metrov štvorcových pooral v nejakej číselnej sústave a to odovzdal Vladkovi. Vladko Merlina silno podceňuje a ani nemá poňatia v akej sústave to je, tak chce zisťiť, koľko najmenej metrov štvorcových to mohlo byť.

Úloha

Na vstupe dostanete postupnosť symbolov. Táto postupnosť reprezentuje číslo. Každý symbol reprezentuje jednu cifru a rovnaké cifry reprezentujú rovnaké cifry. Napríklad postupnosť abcdcdd môže znamenať \(8264644_9\) v deviatkovej sústave čo je \(4412434_{10}\) v desiatkovej sústave alebo \(2351511_6\) v šestkovej sústave čo je \(123523_{10}\) v desiatkovej sústave. Vašou úlohou bude zistiť aké najmenšie čislo to mohlo byť a vypísať ho v desiatkovej sústave. Ďalej ešte viete, že Merlin nepoužíva jednotkovú sústavu a číslo sa nezačína nulami.

Formát vstupu

V prvom riadku vstupu je číslo \(t\) (\(1 \leq t \leq 10^4\)) udávajúce počet postupností.

Potom nasleduje \(t\) riadkov. Na každom riadku je jedna postupnosť nanajvýš \(l\) symbolov \(a_i\) (symboly sú malé a veľké písmená anglickej abecedy a cifry 0 až 9).

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4 5, 6 7, 8
\(1 \leq t \leq\) \(10\) \(10\) \(10^3\) \(10^4\) \(3 \cdot 10^4\) \(10^5\)
\(1 \leq l \leq\) \(3\) \(4\) \(5\) \(6\) \(10\) \(19\)

Formát výstupu

Vypíš \(t\) riadok, na každom bude najmenšie číslo, ktoré mohla postupnosť znakov reprezentovať v desiatkovej sústave.

Príklad

Input:

3
Ab
mama
r3Kt

Output:

2
10
75

Prvá postupnosť bude reprezentovať \(10_2\), čiže \(2_{10}\). Druhá postupnosť bude reprezentovať \(1010_2\), čiže \(10_{10}\). Tretia postupnosť bude reprezentovať \(1023_4\), čiže \(75_{10}\) – všimnite si, že aj cifry môžeme nahradiť.

Bruteforce

Naivné riešenie je vyskúšať všetky možné základy číselných sústav a pre každý základ vyskúšať všetky možné poradia cifier. Počet rôznych cifier na vstupe je maximálne 62, takže počet rôznych poradí cifier je \(62! \approx 3\cdot10^{85}\). S kombináciou so všetkými možnými základmi číselných sústav dostávame veľmi veľa možností, ktoré musíme všetky vyskúšať.

Zaujímavá myšlienka

Čo si môžme uvedomiť je, že nám bude stačiť číselná sústava so základom rovnakým, ako je počet rôznych cifier v čísle na vstupe. Menší základ nemôže byť, lebo potom by 2 symboly museli reprezentovať rovnakú cifru, čo nemôže nastať. Viacej to taktiež nemôže byť. Označme počet rôznych cifier \(n\) a počet cifier \(m\). Ak by bol základ \(n\), potom symbol úplne naľavo by mal hodnotu rádovo \(n^{m-1}\). Ak by bol základ väčší, tak by mal hodnotu rádovo \((n+1)^{m-1} > n^{m-1}\).

Optimálne riešenie

Teraz keď už vieme, aký základ má Merlinova číselná sústava, stačí nám zistiť priradenie cifier. To spravíme jednoducho tak, že najľavejšej cifre priradíme najmenšiu hodnotu (hodnotu 1, lebo číslo sa nemôže začínať nulou). Potom nasledujúca cifra bude mať druhú najmenšiu hodnotu. Takže posledná cifra bude mať hodnotu \(n-1\).

T = int(input())
for t in range(T):
    sifra = input()
    kluc = {}

    ktore = 0
    for znak in sifra:
        if znak not in kluc:
            if ktore == 0:
                kluc[znak] = 1
            elif ktore == 1:
                kluc[znak] = 0
            else:
                kluc[znak] = ktore
            ktore += 1

    odpoved = 0
    dlzka_sifry = len(sifra)
    zaklad = max(2, len(kluc))
    for i in range(dlzka_sifry):
        odpoved += kluc[sifra[i]]*zaklad**(dlzka_sifry-i-1)
    print(odpoved)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;

    while (T--) {
        string sifra;
        cin >> sifra;

        int kolkate = 0;

        map<char, int> kluc;
        for (auto ch : sifra) {
            if (kluc.count(ch) == 0) {
                if (kolkate == 0)
                    kluc[ch] = 1;
                else if (kolkate == 1)
                    kluc[ch] = 0;
                else
                    kluc[ch] = kolkate;
                kolkate++;
            }
        }

        ll zaklad = max((ll)2, (ll)kluc.size());
        ll dlzka_sifry = sifra.length();
        vector<ll> pows = {1};
        for (int e = 1; e < dlzka_sifry; ++e)
            pows.push_back(pows.back() * zaklad);

        ll odpoved = 0;
        for (int i = 0; i < dlzka_sifry; i++)
            odpoved += kluc[sifra[i]] * pows[dlzka_sifry - i - 1];
        cout << odpoved << "\n";
    }
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.