Táto úloha je programátorská. Ako svoje riešenie odovzdaj program vo svojom obľúbenom jazyku a automaticky sa dozvieš koľko si dostal/a bodov. Ak si takýto typ úloh ešte nikdy neriešil/a skús sa pozrieť ako by mal vyzerať ideálny program. Ak zatiaľ programovať nevieš, ale chcel/a by si vedieť môžeš skúsiť náš python tutoriál.
Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Hanke na [email protected]
Nie až tak dávno sa konalo prvé sústredenie PRASKu. Spoznalo sa tam veľa účastníkov, nových či starých a veľa z nich sa aj skamarátilo. Klaudia sa na konci sústredka rozprávala so všetkými účastníkmi a každého sa spýtala, koľko má na sústredku nových kamarátov. Všetci jej túto informáciu ochotne prezradili. Pri niektorých odpovediach sa Klaudia začudovala - veď toľko kamarátov si nikto nemohol stihnúť za jedno sústredko spraviť!
Každý účastník Klaudii povedal, koľko nových kamarátov spoznal na sústredku. Ak je toto číslo ale väčšie než $k$, klamal jej a s nikým sa neskamarátil (teda má $0$ nových kamarátov). Tvojou úlohou je zistiť, koľko nových kamarátstiev vzniklo, ak sa každé kamarátstvo skladá z práve dvoch účastníkov.
Na prvom riadku dostanete dve medzerou oddelené čísla $n$, $k$, označujúce počet účastníkov a maximálny počet kamarátov, koľkých mohol jeden účastník spoznať. Platí $2 \leq n \leq 10^7$ a $0 \leq k < n$.
Na druhom riadku je $n$ čísel $a_1, a_2, … , a_n$ - $a_i$ je počet nových kamarátov $i$-teho účastníka. Pre každé $i$ platí, že $0 \leq a_i < n$.
Na výstup vypíšte jedno číslo - počet vzniknutých kamarátstiev.
Pozor, toto číslo môže byť veľmi veľké - na jeho uloženie nestačí obyčajná (32-bitová) premenná. Namiesto toho musíš použiť 64-bitovú premennú. Ak programuješ v Pythone, toto nemusíš riešiť. Napríklad v C++ ale musíš použiť long long namiesto int.
Sú štyri sady vstupov, každá za 25 bodov. V prvej a druhej platí, že $n \leq 10^4$. Zvyšné dve sady nemajú žiadne obmedzenia navyše.
5 3
1 2 4 1 0
2
Druhý účastník sa skamarátil s prvým a štvrtým, tretí a piaty sa s nikým neskamarátili.
8 4
4 2 3 6 3 0 2 5
7
Keď máme jedno kamarátstvo, znamená to, že nám dvaja účastníci povedia, že majú kamaráta. Toto platí o každom kamarátstve. Čo nám ale pomôže je, že to platí aj opačne. Za každých dvoch kamarátov, o ktorých nám povedali, vieme pripočítať jedno kamarátstvo, keďže nemusíme vedieť, kto s kým sa skamarátil. Potrebujeme preto zistiť celkový súčet kamarátov.
Celkový súčet kamarátov vieme zistiť tak, že všetkých $n$ čísel zo vstupu sčítame. Takto by sme ale pripočítali aj kamarátov tých, ktorí nám klamali. Každé číslo teda pripočítame len v prípade, ak nie je väčšie ako $k$. Keďže kamarátov je dvakrát toľko, koľko je kamarátstiev, výsledkom bude polovica súčtu, ktorý sme vypočítali.
Nových kamarátov každého účastníka musíme načítať zo vstupu, a prípadne
pripočítať - časová zložitosť bude teda lineárna od počtu účastníkov: $O(n)$.
Keďže si ale nemusíme pamätať všetky čísla zo vstupu naraz,
ale čísla kamarátov stačí načítavať po jednom a postupne sčítavať,
pamäťová zložitosť bude konštantná $O(1)$. Takto môže vyzerať riešenie naprogramované v C++:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
long long kamarati = 0;
// spocitame novych kamaratov vsetkych ucastnikov:
for (int i = 0; i < n; i++)
{
int a;
cin >> a;
if (a <= k)
kamarati += k; // ak nam ucastnik neklame, pripocitame jeho pocet kamaratov
}
cout << kamarati / 2 << endl; // vypiseme pocet kamaratstiev, co je polovica poctu kamaratov
return 0;
}
A takto môže vyzerať v Pythone:
n, k = map(int, input().split())
a = map(int, input().split())
kamarati = 0
# spocitame novych kamaratov vsetkych ucastnikov:
for i in a:
if i <= k:
kamarati += i # ak nam ucastnik neklame, pripocitame jeho pocet kamaratov
print(kamarati // 2) # vypiseme pocet kamaratstiev, co je polovica poctu kamaratov
Môžeme si všimnúť, že v Pythone čísla nenačítavame po jednom ale všetky naraz. V Pythone by bolo komplikovanejšie načítavať čísla po jednom. Jediné, čo to ovplyvní je, že pamäťová zložitosť bude v tomto prípade $O(n)$.