Zadanie
Neferjerry vyšla na balkón jej luxusného sídla. Do tváre jej hneď udrela všade prítomná horúčava Egypta. Rozpálený suchý vzduch bol narušený iba údermi vejárov jej otrokov. Pomaly sa presunula k lehátku skrytom v tieni, ľahla si naň a nechala sa kŕmiť bobuľkami hrozna. Život hlavného architekta faraónov bol plný prepychu a pohodlia.
V poslednom čase ju však trápilo nové zadanie. Postaviť obrovskú Cheopsovu pyramídu bola hračka. Naplniť skrytú hrobku Tutanchamóna kliatbami bola výzva, ale nič čo by nezvládla. To čo však od nej žiadal Tutanjanón bolo takmer nemožné.
Všetci predsa vedia, že pyramída sa stavia z obrovských kamenných blokov tvaru kocky. Z nich sa tvorí \(h\) poschodí pyramídy. Najspodnejšie poschodie je štvorec, ktorého jedna strana má \(x\) blokov, najvrchnejšie poschodie je tvorené jediným blokom. Zvyšné poschodia sú následne pekne vycentrované na stred pyramídy. A doteraz bolo zvykom, že tieto poschodia boli takisto štvorcové.
Nový faraón si však zmyslel, že vôbec nebude vadiť ani keď to budú “takmer štvorce”. A namiesto toho aby ju nechal navrhnúť najkrajšiu takúto pyramídu, rozhodol sa vybrať si ju náhodne. Neferjerry preto povedal, aby zistila, koľko rôznych pyramíd by mohla postaviť, aby vedel, z čoho si vyberá. A hoci kopy pergamenov zapísaných výpočtami sa zväčšujú, Neferjerry nie je o nič bližšie k riešeniu.
Rozmýšľajúc sa pozrela na vás, ako ju ovievate a kŕmite hroznom. Však na čo mať otrokov (čítaj riešiteľov KSP), ak nie na špinavú prácu a nudné výpočty. Rukou prešla po koženom biči, ktorý jej ležal pri nohách a s úsmevom sa otočila na vás: “Mám pre vás úlohu…”
Úloha
Vašou úlohou bude zistiť počet pyramíd, ktoré Neferjerry môže postaviť faraónovi Tutanjanovi. Tieto pyramídy musia spĺňať nasledovné podmienky:
- vrchné poschodie je tvorené jedným blokom
- pyramída má práve \(h\) poschodí
- spodné poschodie je tvorené \(x \times x\) blokmi
- každé poschodie je v oboch rozmeroch aspoň o dva bloky kratšie ako poschodie pod ním (to spôsobí, že keď ich vycentrujeme na stred, tak každé poschodie bude vo všetkých štyroch smeroch aspoň o jeden blok kratšie ako to pod ním a pyramída bude pekná)
- každé poschodie musí byť “takmer štvorec” – to je taký obdĺžnik, v ktorom je absolútna hodnota rozdielu jeho šírky a dĺžky najviac 3 (všimnite si, že štvorec je tiež “takmer” štvorec)
Dve pyramídy považujeme za rôzne ak sa líšia vo veľkosti aspoň jedného poschodia z pohľadu od Cheopsovej pyramídy. To znamená, že pyramída, ktorej tretie poschodie má veľkosť \(3\times 4\) je rozdielna od pyramídy, ktorej tretie poschodie má veľkosť \(4 \times 3\).
Keďže počet takýchto pyramíd môže byť naozaj veľký, vypíšte zvyšok tohto čísla po delení \(1\,000\,000\).
Formát vstupu
Vstup je tvorený dvoma číslami \(h\) a \(x\) (\(2 \leq h \leq 2\,000\), \(3 \leq x \leq 5\,000\)) – prvé určuje výšku pyramídy a druhé veľkosť najspodnejšieho poschodia. Vo všetkých vstupoch platí, že \(x \geq 2\cdot h - 1\), teda vždy sa dá postaviť aspoň jedna taká pyramída.
V jednotlivých sadách navyše platia nasledovné obmedzenia:
Sada | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
\(h \leq\) | \(2\) | \(10\) | \(100\) | \(2000\) | \(500\) | \(1\,000\) | \(2\,000\) | \(2\,000\) |
\(x \leq\) | \(15\) | \(50\) | \(500\) | \(500\) | \(1\,500\) | \(3\,500\) | \(5\,000\) | \(5\,000\) |
Formát výstupu
Na výstup vypíšte jedno číslo – počet pyramíd, ktoré spĺňajú všetky uvedené podmienky, modulo \(1\,000\,000\).
Príklad
Input:
3 7
Output:
9
Vrchné aj spodné poschodia sú jednoznačne určené. Stredné poschodie môže mať nasledovné veľkosti: \(5\times 5\), \(5\times 4\), \(5\times 3\), \(4\times 5\), \(4\times 4\), \(4\times 3\), \(3\times 5\), \(3\times 4\), \(3\times 3\).
Input:
12 23
Output:
1
Každé poschodie musí byť štvorec o dva menší ako poschodie pod ním.
Input:
7 20
Output:
397944
Zopakujme si zadanie úlohy. Máme spočítať počet pyramíd, ktoré majú \(h\) poschodí, vrchné je veľkosti \(1\times 1\), spodné \(x\times x\) a poschodia medzi sú “takmer štvorce”, teda ich šírka a dĺžka sa nelíši o viac ako 3. Navyše sa poschodia postupne od spodu zužujú, presnejšie, šírka aj výška každého poschodia je aspoň o 2 menšia ako poschodia priamo pod ním.
Vždy, keď riešime problém s počítaním možností mali by sme sa zamyslieť, či nevieme využiť dynamické programovanie. Pri tejto technike si najskôr sformulujeme problém a následne skúšame vypočítať jeho riešenie na základe jemu podobných podproblémov.
Nie vždy je vhodné si ako problém zobrať úlohu zadania, skôr by malo platiť, že pomocou zvoleného problému vieme ľahko na zadanie odpovedať. V tomto prípade je to však pomerne ľahké a priamo zo zadania vyplýva nasledovná otázka: Koľkými spôsobmi vieme postaviť korektnú pyramídu výšky \(n\), ktorej spodné poschodie má veľkosť \(w\times h\)?
Keďže pyramídy nemusia mať vždy štvorcové podstavy, problém sme si trochu zovšeobecnili na podstavy \(w \times h\). Stále však vieme ľahko odpovedať na pôvodnú otázku, stačí, keď nastavíme \(w = x\) a \(h = x\).
Ďalším krokom je zistiť, či vieme na túto otázku odpovedať pomocou výsledkov pre jednotlivé podproblémy. Čo to vlastne ten podproblém je? Je to pôvodná otázka, do ktorej dosadíme iné, menšie parametre. Teda napríklad, koľko je pyramíd výšky \(n-1\) s veľkosťou základne \(4\times 3\). Aby sme nemuseli našu otázku vždy rozpisovať, označme si počet pyramíd výšky \(n\) so základňou \(w \times h\) ako \(P(n, w, h)\).
Náš pôvodný problém je nájsť hodnotu \(P(n, x, x)\). Ako takéto pyramídy vyzerajú? Ich spodné poschodie je veľké \(x \times x\) a potom sú tam poukladané zvyšné poschodia. Tieto zvyšné poschodia však tvoria korektnú pyramídu výšky \(n-1\). Jediné čo nevieme je, akú podstavu tieto menšie pyramídy majú. Uvedomme si však, že napríklad, každú pyramídu výšky \(n-1\), ktorej podstava je \((x-2) \times (x-2)\) vieme postaviť na poschodie \(x \times x\) a dostať tak pyramídu, ktorú hľadáme. Tým pádom, hodnota \(P(n, x, x)\) obsahuje všetky možnosti \(P(n-1, x-2, x-2)\).
A to je už skladanie podproblémov. Vidíme, že ak vypočítame \(P(n-1, x-2, x-2)\), táto hodnota nám pomôže pri výpočte hľadaného \(P(n, x, x)\). No ale \(P(n-1, x-2, x-2)\) je ten istý problém, len trochu menší, na jeho riešenie preto môžeme použiť ten istý postup. A to je základnou myšlienkou dynamického programovania.
Ak chceme vypočítať \(P(n, x, x)\), musíme zistiť, aké všetky pyramídy veľkosti \(n-1\) vieme položiť na poschodie \(x \times x\). Ich výšku poznáme, stačí teda skúsiť všetky možnosti pre podstavu. Z toho plynie nasledovný jednoduchý program. Odporúčam si ho prečítať, ak ste sa s dynamickým programovaním ešte nestretli. Pekne ukazuje, aká jednoduchá je to technika, keď si položíte správnu otázku.
#include <cstdio>
#include <algorithm>
using namespace std;
int MOD = 1000000;
int Mem[300][700][700];
// počet pyramíd výšky n, ktorých podstava je veľká w krát h
int P(int n, int w, int h) {
// skontroluj najjednoduchšie prípady a už zapamätané riešenia
if(n == 1 && w == 1 && h == 1) return 1;
if(n == 1) return 0;
if(w <= 0 || h <= 0) return 0;
if(Mem[n][w][h] != -1) return Mem[n][w][h];
// vyskúšaj všetky možné podstavy
int res = 0;
for(int i = 0; i < w-1; i++)
for(int j = 0; j < h-1; j++) {
if(abs(i-j) > 3) continue; // skontroluj, či je to takmer štvorec
res += P(n-1, i, j);
}
return Mem[n][w][h] = (res % MOD);
}
int main() {
int n,x;
scanf("%d %d",&n,&x);
// nastavím pole Mem na -1 - nič ešte nemáme spočítané
for(int i=0; i<300; i++)
for(int j=0; j<700; j++)
for(int k=0; k<700; k++)
Mem[i][j][k] = -1;
printf("%d\n",P(n,x,x));
}
Vo vyššie uvedenom programe si všimnite dve dôležité veci. Jednak, naša rekurzia musí mať ukončenie. To je väčšinou určené podproblémom, ktorý vieme vyriešiť ručne. V našom prípade pyramída výšky 1 s podstavou \(1 \times 1\), ktorá je naozaj len jedna. Takisto si však treba dať pozor na prípady, ktoré už k riešeniu nevedú. Druhým pozorovaním je, že aby sme dookola nepočítali tie isté veci, pamätáme si už vypočítané výsledky v poli Mem[]
. Táto technika sa volá memoizácia a výrazne zrýchľuje väčšinu rekurzívnych funkcií. Naozaj jediné čo s Mem[]
robíme je, že si do tohto poľa vkladáme vypočítané hodnoty a ak sa pýtame na niečo, čo už máme zapamätané, vrátime namiesto toho túto hodnotu.
Aká je časová zložitosť nášho programu. Pri takomto type rekurzií sa to v skutočnosti odhaduje pomerne ľahko. Stačí zistiť koľko rôznych podproblémov môžeme riešiť a ako dlho nám trvá riešenie jedného z nich. Možných podproblémov je \(n \cdot x \cdot x\) – všetky možnosti pre výšku, šírku a dĺžku pyramídy. Výpočet jednej možnosti je pritom \(x \cdot x\), pretože musíme vyskúšať všetky možnosti pre šírku a dĺžku podstavy o poschodie vyššie. Celková zložitosť je preto \(O(nx^4)\).
Zapojenie “takmer štvorcov”
Naše riešenie je príliš pomalé, je však zrejmé, že to tak vôbec nemusí byť a veľa vecí sme si zbytočne zjednodušili. Napríklad sme nijak nevyužili fakt, že jednotlivé poschodia musia byť takmer štvorce. Skúšame preto úplne zbytočné možnosti ako \(P(10, 9, 3)\). Síce vieme spočítať počet takýchto pyramíd, ale na čo nám sú, ak podstavu \(9 \times 3\) nikdy nevieme použiť? Toto platí o rekurziách a dynamikách aj všeobecne. Keď sa ich snažíme zrýchliť, vždy si treba klásť otázku, či niečo nepočítame dvakrát, poprípade zbytočne.
Zapojenie takmer štvorcov ovplyvňuje dve miesta v kóde – počítanie možných podstáv pre nižšie pyramídy a samotný počet a tvar podproblémov. Začnime tým prvým. V predchádzajúcom riešení sme pre pyramídu výšky \(n-1\) skúšali všetky možné šírky a dĺžky pre podstavu. My však vieme, že ich rozdiel môže byť najviac 3. Ako v riešení vyskúšať všetky takéto veľkosti? Uvedomme si, že stále chceme skúšať každú možnú šírku, k danej šírke však už neskúšame všetky dĺžky, ale iba tých 7 zaujímavých – o 3 menšiu až o 3 väčšiu ako šírka. Toto zrýchli počítanie možností na \(O(x)\), keďže 7 je iba malá konštanta.
Druhú úpravu musíme spraviť priamo vo formáte podproblému, nechceme počítať a vôbec dovoľovať podproblémy, ktoré nás nezaujímajú. Jeden z dôvodov je napríklad aj ten, že sa nám tým zmenší veľkosť nášho poľa Mem[]
, čo je dôležité, pretože vytvoriť pole nejakej veľkosti trvá rovnako veľa času. Ak by sme teda tieto podproblémy nepočítali, ale mali by sme pre ne vytvorené miesto v pamäti, vôbec by sme si nepomohli. Náš problém si preto preformulujeme na Koľkými spôsobmi vieme postaviť korektnú pyramídu výšky \(n\), ktorej spodné poschodie má šírku \(w\) a dĺžku o \(dx\) inú? Pričom samozrejme \(dx\) môže mať iba hodnoty \(-3\) až \(3\).
Ako sa zmenila časová zložitosť našeho riešenia? Počet podproblémov je už iba \(n \cdot 7x\) – určíme si výšku, šírku a dĺžka už môže mať iba jednu zo 7 možností na základe šírky. A jeden podproblém vypočítame v čase \(7x\) – skúsime každú šírku a iba 7 okolitých dĺžok. Výsledné riešenie má teda zložitosť \(O(n \cdot x^2)\).
K implementácii tohto riešenia ešte dodajme, že je ťažké si pole indexovať zápornými číslami, preto \(dx\) nebude nadobúdať hodnoty \(-3\) až \(3\) ale \(0\) až \(6\). Počet hodnôt je rovnaký, sú kladné, je však na nás, aby sme sa v nich nedoplietli a správne ich používali.
#include <cstdio>
#include <algorithm>
using namespace std;
int MOD = 1000000;
int Mem[2000][5000][7];
// počet pyramíd výšky n, ktorých podstava je veľká w krát w+dx-3
int P(int n, int w, int dx) {
int h = w + dx - 3;
// skontroluj najjednoduchšie prípady a už zapamätané riešenia
if(n == 1 && w == 1 && dx == 3) return 1;
if(n == 1) return 0;
if(w <= 0 || h <= 0) return 0;
if(Mem[n][w][dx] != -1) return Mem[n][w][dx];
// vyskúšaj všetky podstavy tvaru takmer štvorca
int res = 0;
for(int i = 0; i < w-1; i++)
for(int j = -3; j < 4; j++) {
if(h - (i + j) < 2) continue;
res += P(n-1, i, j + 3);
}
return Mem[n][w][dx] = (res % MOD);
}
int main() {
int n,x;
scanf("%d %d",&n,&x);
// nastavím pole Mem na -1 - nič ešte nemáme spočítané
for(int i=0; i<2000; i++)
for(int j=0; j<5000; j++)
for(int k=0; k<7; k++)
Mem[i][j][k] = -1;
printf("%d\n", P(n,x,3));
}
Rýchlejšie počítanie jedného podproblému
Predchádzajúce riešenie však stále nie je dostatočne rýchle. Nie je však veľa vecí, ktoré by sme vedeli zmeniť. Počet podproblémov už veľmi nezmeníme, predsa len, musíme si pamätať výšku a veľkosť základne. To znamená, že treba zrýchliť výpočet jedného podproblému. Pri aktuálnom riešení postupne skúšame všetky o jedno nižšie pyramídy, ktoré sa zmestia na zadanú podstavu. Bohužiaľ, my poznáme odpoveď iba pre konkrétnu veľkosť podstavy a preto musíme robiť všetky tie skúšania. Čo by sa ale stalo, keby sme namiesto toho vedeli odpovedať na nasledovný problém: Koľkými spôsobmi vieme postaviť korektnú pyramídu výšky \(n\), ktorej spodné poschodie je nanajvýš \(w\) široké a \(w + dx\) dlhé? Označme si túto hodnotu \(T(n, w, dx)\). Potom predsa platí, že \(P(n, w, dx) = T(n-1, w-2, dx)\), pretože sa viem rovno dozvedieť počet pyramíd, ktoré viem dať na podstavu \(w \times (w + dx)\).
No dobre, ale pomohli sme si vôbec? Lebo sme si iba vytvorili nový dynamický problém, ktorý však stále potrebujeme vedieť vypočítať. Ako však uvidíme, vyriešiť tento problém je o niečo jednoduchšie. Takže ešte raz, hľadáme počet pyramíd výšky \(n\), ktorých podstava je nanajvýš \(w \times (w+dx)\). Medzi ne určite patria pyramídy, ktorých podstava je presne takto veľká. A tých vieme, že je \(T(n-1, w-2, dx)\). Následne už len potrebujeme pripočítať pyramídy, ktorých podstava je menšia. Menšia môže byť v šírke alebo dĺžke. Čo keby ich šírka bola najviac \(w-1\)? Potom počet takýchto pyramíd je \(T(n, w-1, dx+1)\) – sú vysoké \(n\) poschodí, ich šírka je \(w-1\) a ich dĺžka je rovnaká ako pred tým, čo spôsobí, že \(dx\) sa zväčší o 1 (lebo \(w\) sa o 1 zmenšilo). A keď chceme pyramídy, ktoré majú kratšiu dĺžku, dostaneme hodnotu \(T(n, w, dx-1)\). No a hodnoty \(T()\) zahŕňajú všetky nanajvýš takto veľké pyramídy, nemusíme preto skúšať všetky možné veľkosti podstavy.
Toto avšak nie je všetko, musíme si uvedomiť chybu v našom riešení. Hodnoty \(T(n, w-1, dx+1)\) a \(T(n, w, dx-1)\) obsahujú totiž niekoľko rovnakých pyramíd. Presnejšie, každá pyramída výšky \(n\), ktorej podstava je nanajvýš \((w-1) \times (w+dx-1)\) spadá pod obe tieto čísla, pretože takto veľké podstavy sú rovnako nanajvýš veľké ako podstavy \((w-1) \times (w+dx)\) a aj podstavy \(w \times (w+dx-1)\). No dobre, ale tieto pyramídy sú práve pyramídy \(T(n, w-1, dx)\) a ak sme ich započítali dvakrát, tak ich potrebujeme raz odpočítať. To nás dostáva k výslednému vzorcu:
\[T(n, w, dx) = T(n-1, w-2, dx) + T(n, w-1, dx+1) + T(n, w, dx-1) - T(n, w-1, dx)\]
Malá poznámka na záver. Tento vzorec je dobrý, ale občas nemusí byť úplne pravidvý. Totiž podstavy \((w-1) \times (w+dx)\) nemusia už byť platné, lebo ich rozdiel je priveľký. V takom prípade túto hodnotu nepripočítavame, čím nám nevzniknú duplikáty a teda nechceme ani odčítavať \(T(n, w-1, dx)\). To sú však skôr implementačné detaily, na ktoré si treba dať pozor, keď sa však budete zamýšľať nad tým, čo píšete a čo tie veci znamenajú, ľahko sa im vyhnete.
Vo výsledku hodnoty \(P()\) ani nepotrebujeme počítať, celú úlohu vieme vyriešiť pomocou hodnôt \(T()\). A aká je zložitosť? Počet podproblémov \(T()\) je stále \(n \cdot 7x\). Akurát ich počítanie sa zrýchlilo, pretože nám stačí vypočítať vyššie uvedený vzorec, čo trvá konštantne veľa času. Celková časová zložitosť je \(O(nx)\). Pamäťová zložitosť je totožná počtu podproblémov, teda tiež \(O(nx)\). Túto by sme vedeli síce zmenšiť, ak by sme použili dynamické programovanie namiesto rekurzie s memoizáciou, takéto riešenie však nebolo vyžadované.
#include <cstdio>
#include <algorithm>
using namespace std;
int MOD = 1000000;
int Mem[2000][5000][7];
// počet pyramíd výšky n, ktorých podstava je nanjvýš veľká w krát w+dx-3
int T(int n, int w, int dx) {
int h = w + dx - 3;
// skontroluj najjednoduchšie prípady a už zapamätané riešenia
if(n == 1 && w >= 1 && h >= 1) return 1;
if(w <= 0 || h <= 0) return 0;
if(Mem[n][w][dx] != -1) return Mem[n][w][dx];
// spočítaj možné pyramidy
int res = T(n-1, w-2, dx);
bool t = true;
if(abs(w-1-h) <= 3) res += T(n, w-1, h-(w-1)+3);
else t = false;
if(abs(w-h+1) <= 3) res += T(n, w, (h-1)-w+3);
else t = false;
// ak som zarátal duplikáty
if(t) res -= T(n, w-1, dx);
return Mem[n][w][dx] = ((res%MOD + MOD) % MOD);
}
int main() {
int n,x;
scanf("%d %d",&n,&x);
// nastavím pole Mem na -1 - nič ešte nemáme spočítané
for(int i=0; i<2000; i++)
for(int j=0; j<5000; j++)
for(int k=0; k<7; k++)
Mem[i][j][k] = -1;
printf("%d\n",T(n-1, x-2, 3));
}
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ť.