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\).
= int(input())
T for t in range(T):
= input()
sifra = {}
kluc
= 0
ktore for znak in sifra:
if znak not in kluc:
if ktore == 0:
= 1
kluc[znak] elif ktore == 1:
= 0
kluc[znak] else:
= ktore
kluc[znak] += 1
ktore
= 0
odpoved = len(sifra)
dlzka_sifry = max(2, len(kluc))
zaklad for i in range(dlzka_sifry):
+= kluc[sifra[i]]*zaklad**(dlzka_sifry-i-1)
odpoved print(odpoved)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
::sync_with_stdio(0);
ios.tie(0);
cin.tie(0);
cout
int T;
>> T;
cin
while (T--) {
;
string sifra>> sifra;
cin
int kolkate = 0;
<char, int> kluc;
mapfor (auto ch : sifra) {
if (kluc.count(ch) == 0) {
if (kolkate == 0)
[ch] = 1;
klucelse if (kolkate == 1)
[ch] = 0;
klucelse
[ch] = kolkate;
kluc++;
kolkate}
}
= max((ll)2, (ll)kluc.size());
ll zaklad = sifra.length();
ll dlzka_sifry <ll> pows = {1};
vectorfor (int e = 1; e < dlzka_sifry; ++e)
.push_back(pows.back() * zaklad);
pows
= 0;
ll odpoved for (int i = 0; i < dlzka_sifry; i++)
+= kluc[sifra[i]] * pows[dlzka_sifry - i - 1];
odpoved << odpoved << "\n";
cout }
}
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ť.