Zadanie

Bola jar. Sniežik sa topil, kvietky kvitli, rástli listy. Ale najmä, hovnivále kládli vajíčka. Ale to nie je len tak, naklásť vajíčka a bezstarostne sa zabávať. Treba ich schovať, ukryť pred beštiami. Náš Lajniak Lajko to mal tentokrát obzvlášť obtiažne. Jeho partnerka ho požiadala, aby zohnal trus, v ktorom pod zemou schovajú vajíčka. Tento materiál je nevyhnutný, aby sa larvy mali čím živiť.

Lajko je ale veľmi zábudlivý lajniak, a minulé leto zabudol svoje zásoby trusu vo Firme Korporátnych Slimákov, kde v tom čase brigádoval. Aby ich dostal naspäť, musel by otvoriť svoj starý firemný trezor. Bohužiaľ, zabudol aj svoj PIN. Našťastie, FKS ponúka zmenu PINu, ak si ho niekto zabudol. Tento proces funguje nasledovne:

Firma Korporátnych Slimákov Lajkovi zaradom navrhne \(p\) rôznych PINov, každý o rovnakej dĺžke \(n\). Užívateľ ide zaradom, a keď je na PINe, ktorý sa mu páči, môže si ho zvoliť. Systém ale ponúka aj ďalšiu zmenu, ak si užívateľ chce výber rozmyslieť. Má to ale háčik. Môže si ďalší PIN zvoliť iba ak sa líši v len jednej cifre od toho, ktorý si zvolil naposledy. Takto si užívateľ môže PIN zmeniť koľkokrát len chce, pokiaľ sa každý ďaľší PIN líši v len jednej cifre. Keďže tento systém naprogramovali slimáci, zmena PINu prebieha pomocou operácie, ktorá zmení jednu cifru v PINe o \(1\), buď sa cifra zväčší, alebo zmenší. Keby si Lajko chcel zmeniť PIN \(0000\) na PIN \(0700\), systému by to trvalo \(7\) operácii.

Lajko ako minulý brigádnik vo firme o tomto systéme vie. Je zároveň veľmi citlivý, čo sa týka problémov jeho pamäte. Chce sa teda vyhnúť zmene PINu. Čiže samozrejme sa namiesto toho pokúsi preťažiť slimačí systém menenia PINu tým, že ho donúti vykonať čo najviac operácií pre každú sadu navrhnutých PINov. Keď systém preťaží, určite sa mu trezor otvorí, a dostane sa k svojmu vysnívanému trusu. Pomôžte Lajkovi zistiť, koľko najviac operácií vie od systému v danej sade vynútiť.

Úloha

Dostanete \(p\) rôznych PINov, každý o rovnakej dĺžke \(n\). V PINe môžu byť aj nuly. Jeden PIN si zvolíte ako začiatočný. Následne si môžete vždy PIN zmeniť na ľubovoľný v zozname nasledujúci PIN, pokiaľ sa od toho, čo máte teraz, líši len v jednej cifre. Ak sa líši vo viacerých cifrách, zobrať si ho nemôžete a idete na ďalší navrhnutý PIN. Keď si takto zmeníte PIN, tak podľa toho, o koľko sa dve rozdielne cifry líšia, toľko sa vykoná operácií. Keď sa dostanete na posledný PIN, po ňom si už ďalej PIN meniť nemôžete.

Vašou úlohou bude zistiť, koľko najviac operácií sa dá vykonať pre daný zoznam navrhnutých PINov.

Formát vstupu

Na prvom riadku dostanete číslo \(n\) (\(1 \leq n \leq 6\)) – počet cifier v každom PINe. Na druhom riadku bude číslo \(p\) (\(1 \leq p \leq 100\,000\)) – počet PINov.

Nasleduje \(p\) riadkov, na \(i\)-tom sa nachádza PIN \(p_i\), pričom PIN je ľubovoľná kombinácia cifier \(0\) až \(9\) o dĺžke \(n\).

Formát výstupu

Vypíšte jedno číslo – najväčší možný počet operácií, ktoré sa dajú vykonať.

Príklad

Input:

4
6
8823
2145
2185
3385
4145
4445

Output:

5

Lajko si zvolí \(2145\) ako začiatočný PIN. Od neho sa môže dostať na \(2185\), čo by vykonalo \(4\) operácie, alebo na \(4145\), čo by vykonalo iba \(2\). Lenže sa mu oplatí zvoliť si \(4145\) aj tak, pretože z neho sa vie dostať na \(4445\), čo by dokopy vykonalo \(5\) operácií. Neexistuje iná stratégia, pomocou ktorej by systém vykonal viac, ako \(5\) operácií.

Input:

5
11
00000
60000
00100
10100
60100
10190
10390
61100
20100
10380
20190

Output:

20

Pomalé riešenie

Jeden spôsob je cez brute-force. Držíme si v pamäti PINy ako idú zaradom. Iterujeme cez pole PINov od začiatku. Pre každý PIN si budeme v pamäti držať najlepší výsledok pre ten PIN. Čiže pre prvý PIN v poli by to bola 0. Pre každý ďalší PIN porovnáme najlepšie výsledky s PINmi ktoré sme už prešli, ktoré sa zároveň od terajšieho PINu líšia len v jednej cifre. Pridáme najlepší výsledok PINu, ktorý porovnávame, a pridáme k nemu rozdiel cifier, v ktorých sa dva PINy líšia. Na konci iterovania sa pozrieme, aké najväčšie číslo sme týmto dosiahli, a to bude naša odpoveď. Takýto algoritmus by mal časovú zložitosť \(O(p^2)\), pretože by sme pre každý PIN vykonali minimálne toľko operácii, koľko PINov je už za nami, a máme dokopy \(p\) pinov.

Vzorové riešenie

Vieme sa dostať k lepšiemu riešeniu pomocou dynamického programovania. Vieme, že \(n \leq 6\), a tým pádom počet rôznych PINov určite nepresiahne \(10^6\). Inicializujeme pole \(L\) o veľkosti \(10^n\), kde každý index reprezentuje jeden možný PIN. Napr. PIN \(00002\) by sa nachádzal na indexe \(2\) v poli \(L\), a na tomto indexe by sme našli najlepšiu odpoveď pre tento PIN.

Budeme si pamätať najlepšiu možnú odpoveď pre každý možný PIN, čo na začiatku bude \(-1\). \(-1\) preto, lebo chceme vedieť, či sa daný PIN vôbec nachádza v našom poli PINov, a bolo by dobré túto skutočnosť nejak označiť. Pre každý PIN, ktorý pri iterovaní stretneme, nastavíme v poli \(L\) na jeho indexe najlepšiu odpoveď na aspoň \(0\). Týmto označíme, že sa tento PIN v poli PINov nachádza.

Trik v tomto riešení je, že keď iterujeme PINmi, tak namiesto toho, aby sme kontrolovali všetky predošlé PINy, tak skontrolujeme všetky PINy, ktoré sú tomuto PINu “susedné”. Dva piny sú susedné vtedy, keď sa líšia v jednej cifre. Každý PIN má teda \(10n-1\) susedných PINov, pretože každý PIN má \(n\) cifier, kde cifra môže byť ľubovoľné číslo od \(0\) po \(9\). Pre každý takýto susedný PIN sa pozrieme na pole \(L\), a ak sme tento PIN stretli (čiže hodnota na tom indexe nie je \(-1\)), tak zoberieme rozdiel cifier týchto dvoch PINov, a sčítame ho s hodnotou v poli \(L\). Takto dostaneme potenciálnu najlepšiu odpoveď pre tento PIN. Ak v ďaľšom susednom PINe vypočítame vyššiu hodnotu, tak v poli \(L\) prepíšeme na tú vyššiu. Takúto kontrolu všetkých susedných PINov spravíme pre každý PIN vo vstupe a na konci algoritmu vypíšeme najvyššiu možnú odpoveď, ktorú sme kedy vypočítali. Časová zložitosť tohto algoritmu je \(O(10np)\) = \(O(np)\), čo je v našom prípade lepšie ako \(O(n^2)\), pretože u nás platí \(1 \leq n \leq 6\) a \(1 \leq p \leq 100,000\). Pamäťová zložitosť \(O(10^n)\), kvôli dĺžke poľa \(L\).

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, len;
    cin >> len;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;++i)
        cin >> a[i];

    vector<int> pwrs(len+1);
    pwrs[0] = 1;
    for(int i=1;i<=len;++i) pwrs[i] = pwrs[i-1] * 10;

    vector<int> best(pwrs[len],-1);

    for(int x : a)
    {
        best[x] = max(best[x],0);
        for(int p=0;p<len;++p)
        {
            int dig = (x/pwrs[p])%10;
            int raw = x - dig*pwrs[p];
            for(int d=0;d<=9;++d)
            {
                int src = raw + d*pwrs[p];
                if(best[src] < 0) continue;
                best[x] = max(best[x],best[src] + abs(d-dig));
            }
        }
    }

    cout << *max_element(best.begin(),best.end()) << "\n";

}
n = int(input())
p = int(input())
l = [-1 for i in range(10**n)]
result = 0
pows = [1]
for i in range(n + 1):
    pows.append(pows[-1] * 10)
for i in range(p):
    pin = input()
    bestanswer = 0
    for j in range(n):
        otherpin = list(pin)
        for x in range(10):
            otherpin[j] = str(x)
            newpin = int(''.join(otherpin))
            if l[newpin] > -1:
                answer = (abs(newpin - int(pin)))//pows[n-j-1] + l[newpin]
                if answer > bestanswer:
                    bestanswer = answer

    l[int(pin)] = bestanswer
    if bestanswer > result:
        result = bestanswer

print(result)

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