7. Kocúre a klbko vzorové riešenie

2
11 11 2 2
1 6 1 6

1
20

Víťazné pozície

V tejto úlohe sme sa pohrali s teóriou hier, kde sme chceli spočítať koľko zo začiatočných pozícií je víťazných pre Aničku – teda ak začnú hrať hru hru s dĺžkami špagátov \(a\) a \(b\), či vie Anička vyhrať ak vie optimálne.

Keďže hra je symetrická (možné ťahy sú rovnaké bez ohľadu na to, kto je na ťahu), vieme všeobecne hovoriť o každej dvojici dĺžok špagátov či je víťazná pre mačiatko na ťahu. Stav hry (alebo pozíciu) si označíme ako \((a, b)\) – dĺžky špagátov.

Ako zistíme ktoré pozície sú víťazné? Zjavne, ak sa mačiatko dostalo na ťah a ostal mu jeden špagát nenulovaj dĺžky, a druhý špagát došiel, znamená to že mačiatko na prechádzajúcom ťahu prehralo. Preto sú pozície \((a, 0)\) a \((0,b)\) vyhrávajúce pre všetky celé čísla \(a, b > 0\).

Poďme sa pozrieť na pozíciu \((a, b)\), pričom \(a \leq b > 0\) (prípad, že \(b\leq a > 0\) je symetrický). Mačiatko na ťahu vie skrátiť prvý špagát na dĺžky \(a-b, a - 2b,\dots, a-kb \geq 0\) (pre nejaké celé číslo \(k\)).

Predstavme si, že vieme pre každú z pozícií \((a - b, b), \dots, (a\mod b, b)\) či je vyhrávajúca alebo nie. Ak medzi nimi je aspoň jedna prehrávajúca, mačiatko na ťahu spraví tento ťah a zrazu sa dostane na ťah druhé mačiatko, ale je v prehrávajúcej pozícii. A keďže prehrávajúca pozícia nie je vyhrávajúca, znamená to, že nech robí, čo robí, ak jeho oponent hrá optimálne, prehrá. V tomto prípade je tak pozícia \((a, b)\) vyhrávajúca.

Na druhú stranu, ak sú pozície \((a - b, b), \dots, (a - kb, b)\) všetky vyhrávajúce, mačiatko na ťahu nemá na výber, nech robí, čo robí, každý jeho ťah dôjde do pozície odkiaľ vie vyhrať súper. Vtedy teda musí byť pozícia \((a, b)\) prehrávajúca.

Z tohto pozorovania sa vieme dostať k jednoduchému dynamickému programovaniu ktoré nám vyrieši prvú sadu: iterujeme \(a\) od \(1\) po \(a_2\) a \(b\) od \(1\) po \(b_1\), a pre každú pozíciu si skontrolujeme, či existuje medzi ťahmi nejaký do prehrávajúcej pozície (pre všetky “menšie” pozície sme si už v dynamickom programovsaní spočítali odpoveď). Ak áno, zaznačíme si pozíciu ako vyhrávajúcu. Ak nie, tak ako prehrávajúcu.

Po vypočítaní odpovede pre všetky pozície jednoducho spočítame počet vyhrávajúcich pozícií v intervale hier ktoré Bláčik a Anička budú hrať.

Pre každú z \(t\) otázok vieme použiť tú istú tabuľku – netreba ju navyše prepočítavať ak ju spravíme dosť veľkú.

Toto riešenie funguje v časovej zložitosti približne \(O(\max (a_2, b_2)^2 \log (\max(a_1, b_2)))\) (pomocou zložitejšej matematiky si vieme odhadnúť že priemerný počet možných ťahov na pozíciu je v skutočnosti približne logaritmický od možného počtu pozícií, a nie lineárny).

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define lli long long int

bool memo(lli a, lli b, vector<vector<int> > &W) {
    if (a == 0 || b == 0) return true;
    if (W[a][b] != -1) return W[a][b];
    
    bool seen_l = false;
    if (a < b) {
        int k = 1;
        while (k * a <= b) {
            if (!memo(a, b - k * a, W)) seen_l = true;
            k ++;
        }
    }
    else {
        int k = 1;
        while (k * b <= a) {
            if (!memo(a - k * b, b, W)) seen_l = true;
            k ++;
        }
    }
    
    W[a][b] = seen_l;
    return seen_l;
}

int main() {
    cin.sync_with_stdio(false); cin.tie();
    cout.sync_with_stdio(false); cout.tie();
    int t; cin >> t;
    vector<vector<int> > winning(501, vector<int>(501, -1));
    
    FOR(i, t) {
        lli a1, a2, b1, b2;
        cin >> a1 >> a2 >> b1 >> b2;
        
        lli count = 0;
        for (int a = a1; a <= a2; a ++) {
            for (int b = b1; b <= b2; b ++)
                count += (int)(memo(a, b, winning));
        }
        cout << count << "\n";
    }
}

Prvé pozorovanie

Oplatí sa nám naozaj skúšať všetkých \(\max a_2 \max b_2\) pozícií?

Ak \(a \leq b < 2a\) (alebo \(b\leq a\leq 2b\)), vtedy nemá mačiatko na ťahu na výber – má presne jeden ťah ktorý môže spraviť. Zamyslime sa tak nad prípadom, že \(b \geq 2a\). Mačiatko na ťahu má aspoň dva možné ťahy: do pozície \((b \mod a, a)\), alebo do pozície \((a+(b\mod a), a)\). Všimite si, že v pozícii \((a+b\mod a, a)\) je možný len jediný ťah: do \((b\mod a, a)\).

Rozoberme si najskôr prípad, že pozícia \((b\mod a, a)\) je vyhrávajúca. V tom prípade, ak mačiatko na ťahu (povedzme že je to Anička) prejde do pozície \((a+(b\mod a), a)\), Bláčik musí následne ísť do pozície \((b\mod a, a)\), kde sa dostane na ťah Anička. Táto pozícia je však vyhrávajúca, teda v tomto prípade má Anička vyhrávajúcu stratégiu s pozície \((a, b)\).

No a v prípade, že je pozícia \((b\mod a, a)\) prehrávajúca? Potom vieme, že keď sa tam Anička pohne, nech Bláčik robí čo robí, určite prehrá ak Anička ďalej hrá optimálne.

Ukázali sme si tak, že v oboch prípadoch má Anička vyhrávajúcu stratégiu, teda vždy keď \(b\geq 2a\) je pozícia \((b, a)\) vyhrávajúca. Všimnite si, že nemusíte počítať presnú Aničkinu stratégiu – stačí nám vedieť či z pozície vyhrá, alebo nie.

Takto vieme jednoducho overiť, či je nejaké pozícia \((a, b)\) vyhrávajúca (bez ujmy na všeobecnosti uvažujme \(a\leq b\), inak je situácia symetrická): ak \(b\geq 2a\) (v tomto prípade je zahrnutý prípad \(a=0\)), pozícia je vyhrávajúca. Inak sa posuňme na pozicíu \((b-a, a)\) a postupujeme rovnakým spôsobom, pričom pozícia \((a,b)\) je vyhrávajúca práve ak je pozícia \((b-a, a)\) prehrávajúca.

Koľko nám takýto výpočet bude trvať? Po dvoch ťahoch z \((a, b)\) dostaneme na \((2a - b, b - a)\), \(b-a < a\), takže sa nám najväčšie z čísel zmenšilo o polovicu. Teda určite na overenie výhernosti pozície \((a, b)\) (s \(a\leq b\)) nepotrebujeme viac ako \(2\log b\) krokov.

Takto si jednoducho vieme overiť kto vyhráva každú z hier ktorú mačiatka spolu hrajú, a algoritmus celkovo zaberie \(O((a_2-a_1+1)(b_2-b_1+1)\log\max(a_2,b_2))\) času, a dokonca ho vieme implementovať v konštantnej pamäti¹. Toto riešenie stačí na štyri body.

[1] V prípade, že ho implementujete cez cykly. Ak používate rekurziu ako doleuvedený kód, tak zásobník v rekurzii zožerie \(O(\log\max(a_2,b_2))\) pamäti.

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define lli long long int

bool memo(lli a, lli b) {
    if (a == 0 || b == 0) return true;
    if (a > b) return memo(b, a);
    if (b > a * 2) return true;
    return (!memo(b - a, a));
}

void solve() {
    lli a1, a2, b1, b2;
    cin >> a1 >> a2 >> b1 >> b2;
    
    lli count = 0;
    for (lli a = a1; a <= a2; a ++) {
        for (lli b = b1; b <= b2; b ++) count += (int)(memo(a, b));
    }
    cout << count << "\n";
}

int main() {
    cin.sync_with_stdio(false); cin.tie();
    cout.sync_with_stdio(false); cout.tie();
    int t; cin >> t;
    FOR(i, t) solve();
}

Ako to zlepšiť?

V druhej polovice vstupov mačiatka hrajú priveľa hier aby sme každú kontrolovali separátne². Musíme vymyslieť niečo lepšie.

[2] Pýtate sa kedy to stihnú? Mačiatka sú veľmi hyperaktívne

Jedna možnosť, ktorá podľa šikovnosti implementácie vie získať medzi \(6\) a \(8\) bodmi je pre každé \(a\) medzi \(a_1\) a \(a_2\) simulovať všetky \(b\) naraz, a v každom kroku počítať koľko z pozícií vyhráva okamžite (podľa horeuvedeného pravidla).

Implementácia tejto verzie nie je úplne triviálna, a nechávam ju ako zamyslenie sa na čitateľa (hoci je vzorák, naopak, implementačne veľmi jednoduchý, ako čoskoro uvidíte, skúsiť si nakódiť túto verziu je samo o sebe vcelku zaujímavá úloha na zamyslenie :)

Optimálne riešenie

Poďme sa ďalej zamyslieť nad našou úvahou, že pozícia \((a, b)\) s \(a\leq b\) je vyhrávajúca ak \(b\geq 2a\). Ak nie je, potom je vyhrávajúca ak je \((b-a, a)\) prehrávajúca. Teraz máme dva prípady. Ak \(a\leq 2(b-a)\), potom je táto pozícia vyhrávajúca, podľa predchádzajúceho pravidla. Toto je ekvivalentné prípadu, že \(b\geq \frac32 a\).

V druhom prípade platí \(a < 2(b-a)\), a hra pokračuje do stavu \((2a - b, b - a)\). Zas máme dva prípady: ak \(b-a \geq 2(2a - b)\), čiže \(b \geq \frac 53 a\), vtedy je pozícia víťazná, inak…

$\(\frac21, \frac 32, \frac 53,\dots\), to znie skoro povedome! A veru, ak takto pokračujeme ďalej, dostaneme sériu zlomkov susediacich fibonacciho čísel. Indukciou si vieme dokázať, že po \(2i+1\) iteráciach z \((a, b)\) takto dostaneme \((b\cdot F_{2i+1} - a\cdot F_{2i+2}, a\cdot F_{2i+1} - b\cdot F_{2i})\), a po \(2(i+1)\) iteráciach z \((a, b)\) dostaneme \((a\cdot F_{2i+3} - b\cdot F_{2i+2}, b\cdot F_{2i+1} - a\cdot F_{2i+2})\), pričom \(F_n\) zaznačuje \(n\)-té Fibonacciho číslo (\(F_0=0, F_1=1, F_{n+2}=F_n + F_{n+1}\)).

Z tohto dostaneme, že na to, aby bola pozícia \((a, b)\) vyhrávajúca, musí platiť \(b\geq a F_{2k+4}/F_{2k+3}\) a zároveň \(b\leq a F_{2k+5}/F_{2k+4}\) (ako sa ukáže, pre všetky \(k\))

Ak ste niekedy počuli z zlatom reze, tak viete že pomer vedľajších Fibonacciho čísel konverguje ku \(\phi\), a teda \((a, b)\) je vyhrávajúca pozícia práve vtedy ak \(b\geq \phi a\) (alebo \(a\geq \phi b\)).

Takto vieme počet vyhrávajúcich pozícií pre Aničku spočítať v konštantnom čase: jednoducho spočítame pre každé možné \(a\), koľko \(b\) v intervale \([b_1, b_2]\) platí \(b\geq a\phi\), alebo \(b\leq a/\phi\).

\(\phi\) vieme jednoducho odhadnúť ako pomer dostatočne veľkých Fibbonacciho čísel – takto sa vieme vyhnúť problémom s zaokrúhľovaním necelých čísel pri overovaní koncov víťazných intervalov.

Celé riešenie tam má lineárnu časovú, a konštantnú pamäťovú zložitosť.

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)	for(int i=0;i<(int)n;i++)
#define lli long long int

void solve(lli f1, lli f2) {
    lli a1, a2, b1, b2;
    cin >> a1 >> a2 >> b1 >> b2;
    
    if (a2 - a1 > b2 - b1) {
        swap(a1, b1); swap(a2, b2);
    }
    
    lli count = 0;
    for (lli a = a1; a <= a2; a ++) {
        lli lb = a * f1 / f2;
        lli ub = a * f2 / f1;
        if (ub * f1 < f2 * a) ub ++;
        
        count += max(0LL, min(lb, b2) + 1LL - b1) + max(0LL, b2 - max(ub, b1) + 1LL);
    }
    cout << count << "\n";
}

int main() {
    cin.sync_with_stdio(false); cin.tie();
    cout.sync_with_stdio(false); cout.tie();
    int t;
    cin >> t;
    
    lli f1 = 1, f2 = 1;
    FOR(i, 45) {
        swap(f1, f2);
        f2 += f1;
    }
    
    FOR(i, t) solve(f1, f2);
}