3. Dobré hádanie vzorové riešenie

3 6 7 3
1
2
8

3
9
42

151 993 103 3
1893
2499
24

285994
377651
3624

Poznáme recept (čísla \(a\), \(b\) a \(c\)) špeciálnej množiny a potrebujeme vedieť povedať, aké číslo sa nachádza na \(n\)-tej pozícii v nej.

Nájdeme prvých n čísel

Prvým nápadom na riešenie môže byť, že podľa receptu vyrátame prvých \(n\) čísel. To vieme spraviť tak, že postupne pre každé číslo od \(1\) vyššie zistíme, či číslo patrí do špeciálnej množiny, a opakujeme, kým nenájdeme \(n\) takých čísel, pričom \(n\)-té z nich je odpoveďou na otázku.

Ako teda zistíme, či nejaké číslo patrí do Pythonovej množiny? No, priamočiaro implementujeme podmienky z receptu: \(a\) delí \(x\), no \(b\) nedelí \(x\). Alebo \(a\), \(b\) aj \(c\) delia \(x\). Nejaké \(a\) delí nejaké \(x\), práve vtedy keď zvyšok po delení \(x / a\) je nula. Inak povedané, ak \(x \bmod a = 0\).

Takéto riešenie by teda pre každú z \(m\) otázok prešlo všetky čísla od 1 po \(n\)-té číslo množiny. Všimnime si, že každé číslo množiny musí byť deliteľné \(a\). Z tohto dôvodu si odhadnime, že čísel od 1 po \(n\)-té číslo množiny je \(a \cdot n\). Tým pádom je časová zložitosť celého riešenia \(O(m a n)\). Pamäťová zložitosť je konštantná, teda \(O(1)\), keďže si nič špeciálne (žiadne polia, iba pár premenných) nepotrebujeme pamätať.

Za takéto riešenie bolo možné získať najviac 2 body.

Nebudeme sa opakovať

Hm… Keď pri každej otázke overujeme vždy čísla od \(1\), znamená to, že asi veľa čísel overujeme viacnásobne. Teda zbytočne strácame čas rátaním rovnakých vecí. Vieme vymyslieť také riešenie, ktoré každé číslo overí najviac jedenkrát?

Jasné. Vieme si na začiatku programu vyrátať prvých niekoľko veľa čísel Pythonovej množiny. Tie si budeme ďalej pamätať a pri otázke sa iba pozrieme do pamäte a vrátime číslo na \(n\)-tej pozícii. Prípadne si vieme najprv prečítať všetky otázky, nájsť najväčšie \(n\) a vyrátať si prvých \(\max(n)\) čísel.

Samotné hľadanie odpovedí v predrátanej množine trvá konštantne dlho, no predrátanie nám podľa odhadu v predchádzajúcom prístupe zaberie \(O(a \max(n))\). V pamäti si teraz potrebujeme držať predpočítanú Pythonovu množinu, čo znamená, že pamäťová zložitosť je \(O(\max(n))\).

Za takéto riešenie bolo možné získať 4 body. Ak vylepšíme program tak, že nebudeme skúšať úplne všetky čísla po jednom ale iba po násobkoch \(a\), dostaneme 6 bodov.

Koľké v poradí je toto číslo?

Vieme nejakým spôsobom zistiť odpoveď bez toho, aby sme si museli vyrátať všetky menšie čísla v množine? Áno, vieme. O ľubovoľnom čísle vieme povedať, na akej pozícii v Pythonovej množine sa nachádza (ak číslo nie je v množine, tak dostaneme pozíciu najbližšieho menšieho čísla z množiny).

Koľko existuje čísel menších alebo rovných \(x\), ktoré delí \(a\)? Na túto jednoduchú otázku existuje jednoduchá odpoveď: \(x / a\).

Koľko existuje takých čísel menších alebo rovných \(x\), že ich delí \(a\), \(b\) aj \(c\) súčasne? Je ich presne \(x / \operatorname{lcm}(a, b, c)\). (LCM ako least common multiple alebo NSN – najmenší spoločný násobok)

Koľko existuje čísel menších alebo rovných \(x\), ktoré delí \(a\), ale nedelí ich \(b\)? Je to v podstate odčítanie množín. Čiže \(x / a - x / \operatorname{lcm}(a, b)\).

Keďže dve pravidlá z receptu na zostrojenie Pythonovej množiny tvoria dve disjunktné množiny (v jednom \(b\) delí, v druhom nedelí), môžeme k nim pristupovať osobitne a iba ich sčítame: \((x / a - x / \operatorname{lcm}(a, b)) + (x / \operatorname{lcm}(a, b, c))\)

Vidíme, že potrebujeme vedieť iba \(\operatorname{lcm}(a, b)\) a \(\operatorname{lcm}(a, b, c)\), ktoré sú pri všetkých otázkach rovnaké. Takže si ich môžeme vyrátať iba raz na začiatku a ďalej používať iba tieto dve zapamätané čísla, aby sme ich nerátali vždy odznova. Tým pádom zložitosť tohto výpočtu zanedbáme.

Binárne vyhľadávanie

Zistenie pozície nejakého čísla vieme šikovne využiť v riešení hlavne vtedy, keď budeme odpoveď hľadať binárne a nie zaradom od jednotky.

Na začiatku si stanovíme hranice intervalu, na ktorom hľadáme odpoveď, na najmenšie a najväčšie možné číslo v množine (\(10^{15}\) by malo stačiť). Pozrieme sa na číslo v strede tohto intervalu a zistíme, koľké je v poradí v Pythonovej množine. Ak je hľadané \(n\) väčšie, opakujeme postup s pravou polovicou tohto intervalu (stred, koniec). Ak je menšie, pokračujeme s ľavou polovicou (začiatok, stred).

Keď už dostaneme \(n\), potrebujeme ešte nájsť najbližšie menšie alebo rovné číslo patriace do množiny, keďže číslo v strede ľubovoľného intervalu vôbec nemusí spĺňat recept. Toto zaberie rádovo zanedbateľne málo operácií. Maximálne \(ac\), ak by sme postupne dekrementovali odpoveď po jednotkách. Ak uvažujeme rovno celé násobky \(a\), bude to maximálne \(c\) operácií. Myšlienka dôkazu: Ak sú \(a\) a \(b\) rôzne, do množiny môže v najhoršom prípade patriť druhý najbližší menší násobok \(a\), ak by ten prvý bol zároveň aj násobkom \(b\). Ak sú \(a\) a \(b\) rovnaké, hľadáme najbližšie menšie alebo rovné číslo deliteľné \(a\) a \(c\) zároveň.

Pracovný interval pri hľadaní odpovede zmenšujeme binárnym vyhľadávaním vždy na polovicu. Z toho vyplýva, že pred nájdením \(n\) vykonáme \(O(\log(n))\) operácií. Následné zarovanenie na najbližšie menšie alebo rovné číslo z množiny môžeme zanedbať. A teda celkovú zložitosť pri \(m\) otázkach dostaneme \(O(m \log(n))\). Keďže si nepotrebujeme nič špeciálne pamätať (okrem konštantného počtu premenných), pamäťová zložitosť je konštatná, teda \(O(1)\).

V tomto prípade nám toto riešenie stačilo na plný počet. Existuje však aj niečo ešte lepšie.

Počkať, to ešte nebol vzorák?

Pozrime sa ešte raz na tú matematiku. Už spomenutým vzorcom vieme v konštantnom čase povedať, na akej pozícii sa nachádza nejaké číslo (túto funkciu si nazvyme \(get\_pos(x)\)). Vieme to ale aj opačne. Dôležité sú pre nás čísla \(\operatorname{lcm}(a, b)\) a \(\operatorname{lcm}(a, b, c)\). Medzi \(0\) a \(\operatorname{lcm}(a, b, c)\) je rovnaký počet prvkov množiny ako medzi \(\operatorname{lcm}(a, b, c)\) a \(2 \cdot \operatorname{lcm}(a, b, c)\). A rovnako to platí aj pre všetky ďalšie intervaly medzi bezprostredne nasledujúcimi násobkami \(\operatorname{lcm}(a, b, c)\).

Vo vnútri týchto intervalov zase platí, že každých \(\operatorname{lcm}(a, b)\) čísel sa opakuje rovnaký počet prvkov Pythonovej množiny (násobky \(a\) bez násobku \(\operatorname{lcm}(a, b)\)), keďže všeobecne platí, že \(\operatorname{lcm}(a, b) \leq \operatorname{lcm}(a, b, c)\) pre ľubovoľné \(a, b, c\). Práve pre zistenie presného počtu v každom takomto intervale použijeme už spomínanú funkciu \(get\_pos(x)\). Teda, \(get\_pos(\operatorname{lcm}(a, b))\) nám povie, koľko prvkov množiny sa opakuje každých \(\operatorname{lcm}(a, b)\) čísel, a rovnako to funguje aj pri \(\operatorname{lcm}(a, b, c)\).

Ak teda dostaneme nejaké \(n\), \(n / get\_pos(\operatorname{lcm}(a, b, c))\) nám povie, koľko krát sa v \(n\)-tom čísle množiny nachádza \(\operatorname{lcm}(a, b, c)\), resp. na ktorom spomínanom intervale medzi násobkami \(\operatorname{lcm}(a, b, c)\) sa nachádza \(n\)-té číslo. Podobne, zvyšok zase vydelíme \(get\_pos(\operatorname{lcm}(a, b))\) a zistíme, na ktorom miniintervale sa nachádza medzi násobkami \(\operatorname{lcm}(a, b)\). Ak ešte máme nejaký zvyšok, je to počet násobkov \(a\), ktoré ešte potrebujeme k číslu pridať. Tieto tri medzivýsledky vynásobíme príslučnými deliteľmi (\(\operatorname{lcm}(a, b, c)\), \(\operatorname{lcm}(a, b)\) a \(a\)), sčítame to a máme výsledok, čiže \(n\)-té číslo Pythonovej množiny. Samozrejme, delíme celočíelne so zvyškom.

Pozor ale na to, že pri delení prvého zvyšku \(x\) číslom \(\operatorname{lcm}(a, b)\) chceme v skutočnosti deliť \(x - 1\) a k zvyšku tohto delenia potom prirátame jednotku. To z toho dôvodu, že v prípade, že by \(x\) bolo násobkom \(\operatorname{lcm}(a, b)\), nezostal by nám žiadny zvyšok, čiže by sme k medzivýsledku už neprirátali žiadny ďalší násobok \(a\) v ďalšom kroku a dostali by sme tým pádom zlý výsledok, keďže práve násobky \(\operatorname{lcm}(a, b)\) nepatria do množiny a patrí tam vždy až ďalší najbližší násobok \(a\). Ak tam pridáme tú \(-1\), tento hraničný prípad vyriešime.

Toto riešenie má časovú zložitosť konštantnú, teda \(O(1)\), keďže si stačí iba raz vyrátať \(\operatorname{lcm}(a, b)\) a \(\operatorname{lcm}(a, b, c)\) a ďalej už vieme vyrátať výsledky iba vzorcom pozostávajúcim z konštantného počtu výpočtov. Pamäťová zložitosť je tiež \(O(1)\), keďže si stačí pamätať iba konštantný počet premenných.

Nejakým nedopatrením sa stalo, že za toto riešenie bolo možné získať najviac rovnaký plný počet bodov (\(8\)), aj keď je lepšie než to predchádzajúce. Avšak, vo výnimočných prípadoch boli rozdané aj nejaké bonusové bodíky.

#include <iostream>
#include <algorithm> 

using namespace std;

int main () {
    long long a, b, c, lcm_ab, lcm_all, m, n;
    cin >> a >> b >> c >> m;

    // vyratame potrebne lcm
    lcm_ab = (a * b) / __gcd(a, b);
    lcm_all = (lcm_ab * c) / __gcd(lcm_ab, c);

    // vseobecne pozicia cisla n: n / a - n / lcm_ab + n / lcm_all
    // na kazdej takejto pozicii acko neratame
    long long pos_ab = lcm_ab / a - 1 + lcm_ab / lcm_all;
    // lcm_all je na kazdej takejto pozicii
    long long pos_all = lcm_all / a - lcm_all / lcm_ab + 1;

    for (long long i = 0; i < m; i++) {
        cin >> n;

        // zaratame vsetky lcm_all
        long long result = n / pos_all * lcm_all;
        // odratame si z n, ze uz sme zaratali tie lcm_all
        n -= n / pos_all * pos_all;

        // pozor na n-1
        if (n > 0) {
            // kolko krat vynechame ab
            result += (n - 1) / pos_ab * lcm_ab;
            // odratame uz tieto pozicie
            n -= (n - 1) / pos_ab * pos_ab;
        }

        // doplnime acka
        result += n * a;

        cout << result << "\n";
    }
}

from math import gcd


def main ():
    a, b, c, m = [int(i) for i in input().split()]
    
    # vyratame potrebne lcm
    lcm_ab = (a * b) // gcd(a, b)
    lcm_all = (lcm_ab * c) // gcd(lcm_ab, c)

    # vseobecne pozicia cisla n: n / a - n / lcm_ab + n / lcm_all
    # na kazdej takejto pozicii acko neratame
    pos_ab = lcm_ab // a - 1 + lcm_ab // lcm_all
    # lcm_all je na kazdej takejto pozicii
    pos_all = lcm_all // a - lcm_all // lcm_ab + 1

    for _ in range(m):
        n = int(input())

        # zaratame vsetky lcm_all
        result = n // pos_all * lcm_all
        # odratame si z n, ze uz sme zaratali tie lcm_all
        n -= n // pos_all * pos_all

        # pozor na n-1
        if n > 0:
            # kolko krat vynechame ab
            result += (n - 1) // pos_ab * lcm_ab
            # odratame uz tieto pozicie
            n -= (n - 1) // pos_ab * pos_ab

        # doplnime acka
        result += n * a

        print(result)


main()