Majka obľubuje poháre, a preto si nedávno kúpila sadu $$n$$ pohárov. Samozrejme, nie sú to len také obyčajné poháre, to by bola nuda. Majkine poháre majú navzájom rôzne objemy. Tieto objemy sú celé čísla od 1 do $$n$$. (Všetky objemy sú udávané v decilitroch.)
Keď Syseľ uvidel tieto poháre, hneď sa s nimi chcel nejak zahrať. Majka preto vymyslela nasledovnú hru: Naleje do všetkých pohárov okrem jedného vodu, a potom povie Sysľovi číslo $$v$$: celkový objem vody v pohároch. Syseľ potom musí uhádnuť, ktorý pohár je prázdny.
Vstup má jeden riadok a v ňom dve celé čísla $$n$$ a $$v$$ oddelené medzerou.
Platí $$1 \leq n \leq 10^9$$ a $$1 \leq v \leq 10^{18}$$. Navyše môžete predpokladať, že všetky testovacie vstupy sú riešiteľné: $$v$$ vždy naozaj zodpovedá tomu, že všetky poháre okrem jedného sú plné.
V polovici testovacích vstupov bude dokonca platiť, že $$n\leq 1\,000$$. S takýmito vstupmi by si mali poradiť aj menej efektívne programy.
Dajte si pozor na to, že váš program musí pracovať aj s hodnotami, ktoré sa nezmestia do bežnej (32-bitovej) celočíselnej premennej. Na ich uloženie potrebujete použiť premennú s dostatočne veľkým rozsahom – napríklad int64 v Pascale alebo long long v C++.
Takisto si dajte pozor, že kombinovanie 32-bitových a 64-bitových premenných nemusí dopadnúť podľa vašich očakávaní. Napríklad vynásobenie dvoch 32-bitových premenných vráti 32-bitové číslo bez ohľadu na to, či sa tam výsledok zmestí (ak nie, hodnota pretečie) a do akej premennej výsledok uložíte.
Vypíšte jediný riadok a v ňom jediné číslo $$x$$ – objem prázdneho pohára.
Nezabudnite ukončiť riadok znakom konca riadku. Teda napríklad v Pascale vypíšte výsledok volaním writeln(vysledok), v C++ zase volaním cout << vysledok << endl.
Input:
6 18
Output:
3
Pohár s objemom 3 dl je prázdny. Plné poháre majú dokopy objem 1+2+4+5+6 = 18 dl.
V tomto vzorovom riešení si predstavíme viacero možných spôsobov, ako riešiť tento problém, a po ich porovnaní vyberieme ten najefektívnejší.
Pomerne jednoduchý spôsob je postupne skúšať, ktorý pohár nám chýba, a potom overiť, či súčet objemov ostatných pohárov je rovný $$v$$. Na spočítanie objemu zvyšných pohárov potrebujeme urobiť $$n$$ operácií. A musíme to spraviť $$n$$ krát, pre každý pohár, ktorý by mohol chýbať, takže urobíme $$n \cdot n$$ operácií. Časová zložitosť tohto algoritmu je teda $$O(n^2)$$[^1].
Nedalo by sa toto riešenie zlepšiť? Musíme skutočne skúšať každý pohár? Začnime tým, že sčítame objem všetkých pohárov a tento súčet si označíme $$s$$. Objem pohára, ktorý nám chýba je zjavne $$s - v$$. Takto sme zlepšili zložitosť nášho programu na $$O(n)$$, keďže nám stačí sčítať $$n$$ čísel.
Všimnime si, že najpomalšia fáza v našom algoritme je vypočítať súčet objemov všetkých pohárov, čo je v podstate súčet $$1 + 2 + \dots + n$$. Pre takýto špeciálny súčet, ale existuje matematický vzorec. A na jeho odvodenie sa používa pekný matematický trik.
Napíšme si na papier postupnosť $$1$$ až $$n$$ a pod ňu ešte raz tú istú postupnosť, ale v obrátenom poradí.
$$ \begin{array}{*{13}c} 1 &+& 2 &+& 3 &+& \cdots &+& (n-2) &+& (n-1) &+& n \ n &+& (n-1) &+& (n-2) &+& \cdots &+& 3 &+& 2 &+& 1 \end{array} $$
Všimnime si, že súčet v každom stĺpci je $$n+1$$. Takže súčet čísel v oboch riadkoch je $$n(n+1)$$. Avšak, každé číslo sme zarátali dvakrát, takže súčet jedného riadku je polovica celkového súčtu, t.j. $$\frac{n(n+1)}{2}$$. Takto vieme súčet objemov všetkých pohárov vypočítať v konštantnom čase dosadením do vzorca. Pamäťová zložitosť je tiež konštantná.
#include <cstdio>
int main() {
long long N,V;
scanf("%lld%lld",&N,&V);
printf("%lld",(N * (N + 1)) / 2 - V);
}
program pohare;
var N,V : int64;
begin
readln(N,V);
writeln((N * (N + 1)) div 2 - V);
end.
Korešpondenčný seminár z programovania zastrešuje občianske združenie Trojsten.
Trojsten, o.z.
FMFI UK, Mlynská dolina
842 48 Bratislava
Programátorská súťaž pre základoškolákov
Materiály a úlohy na výučbu programovania
Intenzívny programátorský zážitok v lete