Zadanie

Táto úloha sa dá nahradiť riešením sady arrays_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Mišovi “Žabovi” Anderlemu na

Všetci určite poznáte rozprávku o Snehulienke a siedmich trpaslíkoch. Snehulienka sa stratila v lese, našla domček v ktorom bývali trpaslíci, bol tam strašný neporiadok, a ona začala upratovať… Viete prečo nemali trpaslíci doma upratané? Nie, nebolo to preto, že by boli leniví… Trpaslíci toho majú len veľa na práci. Preto majú presne rozdelené, kto má čo spraviť, podľa poradia v ktorom sa v daný deň zobudili. Prvý chystá raňajky, druhý pripravuje stôl, tretí varí čaj, štvrtý upratuje… Aby sa v činnostiach vystriedali, a tiež, aby nemusel Spachtoš vždy vstávať ako prvý, každý deň vstávajú v inom poradí.

Aby trpaslíci vedeli zistiť, že sa už vystriedali všetky poradia, používajú nasledovný systém:

  • Každý z trpaslíkov má svoju obľúbenú cifru od \(0\) do \(9\).
  • Keď trpaslík ráno vstane, napíše svoju obľúbenú cifru na tabuľu, hneď za poslednú, ktorá tam bola. Takto vznikne každý deň na tabuli jedno číslo.
  • Trpaslíci si počítajú súčet čísel, ktoré sa objavujú na tabuli – predtým, ako idú spať, pripočítajú číslo z tabule k súčtu.
  • Keď je súčet dostatočne veľký, vystriedali sa všetky poradia a môžu sa začať striedať (a sčítavať) odznova.

Systém je dokonalý, no trpaslíci majú jeden problém. Nevedia, aký súčet má byť na tabuli po tom, čo sa vystriedali všetky poradia. Niekedy si tak nevšimnú, že sa už vystriedali a nasledujúce ráno nevstane nikto. Práve v takýto deň prišla Snehulienka a tá sa ako silná žena a nádejná programátorka rozhodla vyriešiť tento problém raz a navždy.

Úloha

Pre jednu domácnosť trpaslíkov dostanete jedno číslo \(c_i\), ktoré vzniklo na tabuli v prvý deň. Zistite, aký bude súčet čísel z tabule, keď sa vystriedajú všetky poradia trpaslíkov. Stručne povedané, zistite súčet všetkých permutácií cifier čísla \(c_i\).

Úlohu vyriešte pre \(n\) rôznych domácností trpaslíkov.

Formát vstupu

Na prvom riadku je číslo \(n\) (\(1 \leq n \leq 10^5\)). Nasleduje \(n\) riadkov, v každom z nich je jedno číslo \(c_i\) (\(0 \leq c_i \leq 10^{12}\)). Žiadne číslo iné ako 0 nezačína nulou.

Formát výstupu

Vypíšte \(n\) riadkov, na \(i\)-tom riadku bude súčet permutácií cifier \(i\)-teho čísla zo vstupu. Každý súčet sa zmestí do 64 bitovej premennej (typu Int64 v Pascale, long long v C++).

Príklad

Input:

5
2
47
33
750
4247

Output:

2
121
66
2664
113322

Trpaslík s cifrou \(2\) býva sám, preto musí vždy vstať prvý. Pre trpaslíkov s ciframi \(4\) a \(7\) existujú dve poradia, ako môžu vstať (\(47\) a \(74\)). Trpaslíci v tretej domácnosti majú rovnaké obľúbené cifry, ale aj tak ich rozlišujeme a preto majú tiež dve možnosti.

Hrubá sila

Riešenie hrubou silou vyzerá tak, že postupujeme presne podľa zadania. Postupne si vygenerujeme každú permutáciu cifier zadaného čísla a potom všetky takto vytvorené čísla sčítame. V jazyku C++ sa to dá robiť pomocou príkazu next_permutation(), ktorý generuje ďalšiu permutácie poľa. V Pythone sa na to dá použiť knižnica itertools. Ak si počet cifier zadaného čísla označíme \(k\), tak takéto riešenie má časovú zložitosť \(O(k!)\) (\(k\) faktoriál) a na testovači by malo získať 2 body.

from itertools import permutations

n = int(input())

for i in range(n):
    c = input()
    print(sum(int(''.join(p)) for p in permutations(c)))

Optimálne riešenie

Prvá otázka, ktorú musíme vyriešiť je, koľko rôznych permutácií \(k\) cifier vlastne existuje. Ak chceme z \(k\) cifier vyrobiť číslo, dôležité je, v akom poradí ich za seba naukladáme. Na prvé miesto môžeme dať ľubovoľnú z cifier k dispozícii, takže máme \(k\) možností. Na druhé miesto, ale už nemáme \(k\) možností, ale iba \(k-1\), lebo jedna cifra (aj keď nevieme ktorá) leží na prvej pozícii. Preto máme pre druhé miesto iba \(k-1\) možností, čo je dokopy pre prvé dve miesta \(k\cdot (k-1)\) možností.

Neprekvapivo, pre tretie miesto máme \(k-2\) možností a tak ďalej. Na poslednom, \(k\)-tom mieste máme len 1 možnosť, lebo nám zostala posledná nezaradená cifra. Dokopy máme teda \(k \cdot (k-1) \cdot (k-2) \ldots 2 \cdot 1\) možností. Takýto súčin čísel od 1 po \(k\) zvykneme tiež označovať \(k!\) (\(k\) faktoriál).

Označme si cifry nášho čísla zľava doprava ako \(a_k\ a_{k-1} \ldots a_2\ a_1\). Toto číslo si teda môžeme zapísať aj ako:

\[10^{k-1}\cdot a_k+10^{k-2}\cdot a_{k-1}+\ldots +10^1\cdot a_2+10^0\cdot a_1\]

Je jasné, že to koľko zaváži daná cifra je dané aj jej poradím v čísle. Skúsme teraz vypočítať, akú hodnotu pridá cifra \(a_1\) do súčtu všetkých permutácií. Ak dáme cifru \(a_1\) na prvú pozíciu tak nám do súčtu pridá \(10^{k-1}a_1\). Potrebujeme už len zistiť, v koľkých permutáciách bude \(a_1\) na prvom mieste. Keď si však takýmto spôsobom zafixujeme prvú cifru, ostane nám \(k-1\) cifier, ktoré chceme uložiť na \(k-1\) pozícií, teda máme \((k-1)!\) rôznych možností.

Ak dáme cifru \(a_1\) na druhú pozíciu, bude pridávať do súčtu hodnotu \(10^{k-2}a_1\) a opäť \((k-1)!\) krát, lebo zafixovaíím druhej pozície nám opäť ostane \(k-1\) cifier na \(k-1\) pozícií. A to isté bude platiť pre ľubovoľné miesto, kam našu cifru \(a_1\) uložíme. Ak toto všetko sčítame, dostaneme celkovú hodnotu, ktorú do súčtu permutácií pridá cifra \(a_1\) a táto hodnota bude:

\[10^{k-1}a_1(k-1)! + 10^{k-2}a_1(k-1)! + \ldots + 10^1a_1(k-1)! + 10^0a_1(k-1)!\]

Po vyňatí \(a_1\) a \((k-1)!\) sa nám to upraví na jednoduchší tvar

\[a_1(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1)\]

Táto istá úvaha však platí pre ľubovoľnú cifru, nie len pre \(a_1\). A cifry sú od seba nezávislé, preto celkový súčet permutácií bude určite rovný súčtu hodnôt, ktoré pridajú jednotlivé cifry. Výsledný súčet všetkých permutácií preto bude

\[a_1(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1) + a_2(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1) + \ldots + a_k(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1)\]

čo môžeme opäť upraviť na oveľa jednoduchší tvar

\[(a_1+a_2+\ldots+a_k)(k-1)!(10^{k-1}+10^{k-2}+\ldots 10 + 1)\]

Výsledok teda vieme vypočítať ako súčin troch členov. Prvý z nich je súčet cifier, druhý je \((k-1)!\), čo je \((k-1)(k-2)\ldots 1\) a tretí súčet mocnín 10. Každý z týchto členov vieme vypočítať v čase \(O(k)\), čo je teda výsledná časová zložitosť našeho programu. Pamäťová zložitosť je dokonca konštantná \(O(1)\), keďže cifry zadaného čísla vieme počítať postupne jeho delením 10.

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int n;
    cin>>n;
    for (int i=0; i<n; i++){
        long long a;
        cin>>a;
        int pocet=0; //počet cifier
        int sucet=0; //súčet cifier
        long long desiatky=0; //sucet mocnin 10
        long long desat=1;
        long long faktorial=1;
        while(a>0){
            desiatky+=desat;
            desat*=10;
            pocet++;
            faktorial*=pocet;
            sucet+=a%10; //a%10 nam da poslednu cifru cisla a
            a/=10; //a/10 nam odstrani poslednu cifru cisla a
        }
        cout<<faktorial*desiatky*sucet<<endl;
    }
}        

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ť.