Zoznam úloh

4. Startupove úspechy

Zadanie

Lukáš tvrdo pracoval na svojom startupe a podarilo sa mu ho predať za veeľa peňazí firme Mäta. Nevedel čo s toľkými peniazmi, tak si povedal že pôjde do kasína.

Úloha

V kasíne sa hádžu $n$-stenné kocky $m$-krát. Vašou úlohou je zistiť, či v daných hodoch padlo každé číslo 1 až $n$ aspoň raz. Pozor, 1 sa ráta ako žolík a môže nahradiť iné číslo. Ak to platí, označíme to že máme “postupku”.

V prípade že sa v týchto hodoch nachádza postupka, vypíšte najčastejší hod. Ak ich je viacero, ten najnižší (ak sme hodili 4,6 aj 9 20-krát, vypíšte 4). Ak sa nenachádza v hodoch postupka, vypíšte 0.

Formát vstupu

V prvom riadku vstupu je číslo $n$ ($1 \leq n \leq 10^6$) udávajúce maximálne číslo na kocke V druhom riadku vstupu je číslo $m$ udávajúce počet hodov kockou. Následne nasleduje $m$ riadkou s hodnotami hodov od 1 po n.

V jednotlivých sadách platia nasledujúce obmedzenia:

Sada 1 2 3 4
$1 \leq n \leq$ $50$ $5 \ 000$ $5 \times 10^4$ $5 \times 10^5$
$n \leq m \leq$ $100$ $10^4$ $10^5$ $10^6$

Formát výstupu

Ak sa medzi hodených kockách nachádza postupka od 1 po $n$ vypíš číslo ktore sa medzi hodeními kockami vyskytovalo najčastejšie(ak ich je viac vypíš najmenšie). Pokiaľ tam neni postupka vypíš 0.

Príklady

Vstup

3
5
1
2
2
2
2

Výstup

0

Nenachádza sa tu postupka od 1 do 3. 

3
5
3
2
3
1
2

Výstup

2

Nachádza sa tam postupka od 1 do 3, najviac krát sa tam nachádza 2 a 3 ale 2 je menšie takže vypíšem 2. 

3
5
1
1
2
1
2

Výstup

1

Nachádza sa tam postupka od 1 do 3 (1 vie “zastúpiť 3”), najviackrát sa tam nachádza 1.

Táto úloha mala dve časti:

  1. Zistiť pre každú stenu kocky, koľkokrát padla
  2. Zistiť, či padla postupka aspoň raz

Prvý krok dokážeme spraviť v $O(m)$ - počet hodov kocky. Je to preto, že si spravíme pole dĺžky n (počet stien kocky). Vždy keď narazíme na hod i, tak zvýšime i-tý index o 1. Druhý krok vieme spraviť v $O(n)$, keďže potrebujeme zistiť, či každý prvok nášho predpočítaného poľa je viac ako jedna, prípadne ho nahradíme žolíkom - 1kou.

Spolu je teda časová zložitosť $O(n+m)$.

Program v pythone mohol vyzerať napríklad takto:

def over_postupku(pocetStien:int, pocetHodovN:list[int]):
    postupka = 1
    for i in range(pocetStien):
        if pocetHodovN[i] == 0:
            if pocetHodovN[0] >= 0:
                pocetHodovN[0]  -= 1
            else:
                postupka = 0
                break
    return postupka

def zrataj_hody(pocetStien:int, pocetHodov:int):
    pocetHodovN = pocetStien * [0]

    for _ in range(pocetHodov):
        hod = int(input()) -1
        pocetHodovN[hod] += 1
    return pocetHodovN

pocetStien = int(input())
pocetHodov = int(input())


pocetHodovN = zrataj_hody(pocetStien, pocetHodov)


postupka = over_postupku(pocetStien, pocetHodovN)
if postupka == 1:
    print(pocetHodovN.index(max(pocetHodovN)) +1)
else:
    print(0)
Pre odovzdávanie sa musíš prihlásiť.
Trojsten

Súťaž PRASK zastrešuje občianske združenie Trojsten.

Kontakt
Ďalšie projekty