Zadanie

MisQo sedí v školskej lavici a rozvíja svoju jemnú motoriku búchaním jednej fixky o druhú. To ho po čase omrzí a rozhodne sa zabaviť sa niečím iným. Na lavici má položenú kopu ceruziek. Každá je zastrúhaná do rôznej dĺžky. Vezme lepidlo a ceruzky začne lepiť o seba a vyrábať z nich rebrík.

“Koľko najviac stupienkov vlastne môže mať ten rebrík?”, hovorí si.

Nechce sa mu ale nad tým rozmýšľať, skúste to teda zistiť zaňho.

Úloha

Na výrobu rebríka s \(k\) stupienkami potrebuje MisQo \(k+2\) ceruziek, ktoré použije takto:

  • Dve ceruzky s dĺžkou aspoň \(k+1\) použije ako boky rebríka, na ktoré bude lepiť stupienky.
  • Na stupienky potrebuje ďalších \(k\) ceruziek s dĺžkou aspoň \(1\), pričom širšie ceruzky budú z rebríka vytŕčať.
  • Medzi jednotlivými stupienkami budú rozostupy dĺžky 1, pričom aj prvý a posledný stupienok musia mať od koncov bočných ceruziek vzdialenosť aspoň 1.

Najlepšie to celé pochopíte na obrázku:

Na prvý rebrík použil MisQo dve ceruzky dĺžky 3 ako boky a dve ceruzky dĺžky 1 ako stupienky. Aj druhý rebrík je vyrobený správne – boky sú znova z dvoch ceruziek dĺžky 3, stupienok je jedna ceruzka dĺžky 2. Na poslednom rebríku vidíme, že ceruzky môžu mať navzájom rôzne dĺžky – v tomto prípade 3 a 101 na boky a 2 a 3 na stupienky.

Vašou úlohou je zistiť najväčší počet stupienkov rebríka, ktorý vie Miško vyrobiť takýmto spôsobom.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^5\)) udávajúce počet ceruziek. Ďalej nasleduje \(n\) riadkov – každý z nich obsahuje jedno celé číslo \(a_i\), ktoré zodpovedá dĺžke \(i\)-tej ceruzky, pričom platí \(1 \leq a_i \leq 10^6\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo \(k\) - najväčší počet stupienkov rebríka, ktorý vie Miško vyrobiť. Ak sa nedá z ceruziek postaviť žiadny rebrík, vypíš nulu.

Príklad

Input:

5
6 
1
4
8
2

Output:

3

Ako základ rebríka použijeme dve najdlhšie ceruzky s dĺžkou 8 a 6. Zostanú nám 3 ceruzky, ktoré na tie zvislé vieme prilepiť. Rebrík teda bude mať 3 stupienky.

Input:

4
2
1
2
1

Output:

1

Ak si vyberieme ceruzky dĺžky 2 ako základ rebríka, ostanú nám dve ceruzky dĺžky 1 na stupienky. Z nich ale vieme použiť iba jednu, keďže boky rebríka sú príliš krátke.

Môžeme si všimnúť, že nezáleží na tom, ktoré ceruzky použije MisQo na stupienky, pretože o každej vieme, že má dĺžku aspoň \(1\) (garantuje nám to zadanie) a žiadne iné obmedzenia na ne nemáme.

Bočné ceruzky chceme mať čo najdlhšie, aby sme mohli mať potenciálne čo najdlhší rebrík. Keďže je nám jedno, ktoré ceruzky budú stupienky, je najlepšie použiť dve najdlhšie ceruzky zo vstupu ako bočné, nikde inde nám tieto dlhé ceruzky chýbať nebudú.

Najväčšia možná dĺžka rebríka je potom daná dĺžkou kratšej z dvoch najdlhších ceruziek – ak má druhá najdlhšia ceruzka zo vstupu dĺžku \(l\), tak najdlhší možný rebrík má \(l-1\) stupienkov.

Druhá vec, ktorá nás obmedzuje, je celkový počet ceruziek. MisQo nemôže postaviť rebrík s viac ako \(n-2\) stupienkami (ktoré mu ostali po odložení dvoch bočných ceruziek).

Obe obmedzenia platia súčasne, teda vezmeme minimum z ich hodnôt. Ak je \(n=1\), druhá najdlhšia ceruzka neexistuje – tento prípad vyriešime osobitne a vypíšeme preň \(0\) – žiaden rebrík sa postaviť nedá.

Celé riešenie vieme implementovať v čase lineárnom od počtu ceruziek: \(O(n)\). Stačí nám dvakrát prejsť celý zoznam dĺžok a vypočítať zopár porovnaní.

n = int(input())
if n <= 1:
    print(0)
    exit()
pencil_lengths = [int(input()) for i in range(n)]
longest = max(pencil_lengths)
pencil_lengths.remove(longest)
second_longest = max(pencil_lengths)
print(min(n - 2, second_longest - 1))

Pre pohodlnejšiu implementáciu najskôr nájdeme maximum dĺžok ceruziek, odstránime ho zo zoznamu pomocou funkcie remove a nájdeme maximum zostávajúcich dĺžok, ktoré je druhou najväčšou dĺžkou ceruzky. Je dôležité mať na pamäti, že funkcia remove má lineárnu zložitosť voči dĺžke zoznamu, pretože všetky prvky za odstraňovaným prvkom sa musia posunúť o jednu pozíciu doľava v zozname a týchto prvkov môže byť až \(O(n)\). Tu na tom nezáleží, pretože aj tak robíme lineárne hľadanie maxima. Avšak neopatrné volanie funkcie remove (napr. opakovane v cykle) môže často zhoršiť zložitosť algoritmu, a preto na to treba myslieť.

Úloha sa dá implementovať v čase \(O(n)\) aj s konštantnou pamäťovou zložitosťou, nepotrebujeme si totiž pamätať celý zoznam ceruziek, ale stačia nám iba aktuálne dve najdlhšie a celkový počet ceruziek.

n = int(input())

naj, dvanaj = -1, -1
for i in range(n):
    k = int(input())

    if k > naj:
        dvanaj = naj
        naj = k
    elif k > dvanaj:
        dvanaj = k

print(max(0, min(dvanaj-1, n-2)))

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