Zadanie

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.

Formát vstupu

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.

Upozornenie

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.

Formát výstupu

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.

Príklad

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.

  1. Ak ste ešte nikdy nepočuli o \(O\)-notácii, tak si o nej môžete niečo prečítať na stránke ksp.sk/riesenie/zlozitost↩

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