Zadanie

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

Úloha

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.

Formát vstupu

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\).

Formát výstupu

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.

Hodnotenie

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.

Príklad

Input:

5 3
1 2 4 1 0

Output:

2

Druhý účastník sa skamarátil s prvým a štvrtým, tretí a piaty sa s nikým neskamarátili.

Input:

8 4
4 2 3 6 3 0 2 5

Output:

7

Myšlienka

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.

Riešenie

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.

Časová a pamäťová zložitosť

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)\).

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