2. Rozdeľ, tak aby dobre bolo vzorové riešenie

6

2

2

0

13

6

373

186

Našou úlohou bolo zistiť koľkými spôsobmi si viedia miško a Klaudi rozdeliť džúsiky tak, aby platili 2 podmienky: obidvaja musia mať aspoň jededn džúsik a Miško ich musí mať viac.

Prvé riešenie

Máme teda \(d\) džúsikov. Označme \(m\) počet džúsikov, ktoré dostane Miško. Mohli by sme skúsiť všetkky možnosti na číslo \(m\). Vieme, že \(1 \leq m \leq d\) Keďže Miško musí dostať aspoň jeden džúsik a nevie ich dostať viac ako \(d\) (všetky). Klaudi by potom dostala \(d - m\) džúsikov. Treba ešte otestovať, či Klaudi dostala aspoň \(1\) džúsik a či ich má Miško viac. Môžeme si ešte všimnúť, že ak by Miško dostal \(d\) džúsikov, pre Klaudi by žiaden nezostal. A keď Miško dostane menaj ako \(d\) džúsikov, Klaudi určite dostane aspoň jeden. Potom to ani nemusíme v programe testovať.

Program by mohol vyzerať napríklad takto:

# načítame počet džúsikov
d = int(input())

# počet vyhovujúcich možností na začiatku nastavíme na 0
možnosti = 0

# prejdeme všetky možnosti na m
for m in range(1, d):
    
    # Klaudi dostane džúsikov
    k = d - m

    # ak Miško má viac džúsikov ako Klaudi
    if m > k:
        # vyhovujúca možnosť, zväčšíme ich počet
        možnosti += 1


# vypíšeme výsledný počet možností
print(možnosti)

Časová zložitosť tohto programu je \(O(d)\), keďže v cykle skúšame každú možnosť na \(m\), a tých je až (približne) \(d\). Pamäťová zložitosť je \(O(1)\) keďže si v každom momente pamätáme len niekoľko čísel.

Rýchlejšie riešenie

Pozrime sa na to, koľko najmenej džúšikov môže Miško dostať tak, aby mal viac ako Klaudi.

Ak by bol počet džúsikov párny, najmenej džúsikov, koľko by Miško dostal je \(\frac{d}{2} + 1\). Potom by Klaudi dostala \(\frac{d}{2} - 1\), čo je menej. Ak by Miško dostal čo i len o jeden džúsik menej, už by mali s Klaudi rovnako.

Ak by bol počet džúsikov nepárny, najmenej džúsikov, koľko by Miško dostal je \(\frac{d-1}{2} + 1\) (\(d-1\) je párne čislo). Potom by Klaudi dostala \(\frac{d-1}{2}\), čo je menej. Ak by Miško dostal čo i len o jeden džúsik menej, už by Klaudi mala viac.

Zistili sme, koľko najmenej môže Miško dostať džúsikov. Vieme, že Miško môže dostať najviac \(d-1\) džúsikov tak aby Klaudi dostala aspoň jeden. Každý počet džúsikov medzi tým je tiež správna (vyhovujúca) možnosť. Keď vieme koľko najviac a koľko najmenej džúsikov môže Miško dostať, ľahko zistíme počet možností. Je to \(najviac - najmenej + 1\).

Program by vyzeral takto:

# načítame počet džúsikov
d = int(input())

# Ak d je párne
if d % 2 == 0:
    najmenej = d // 2 + 1

# inak je d nepárne
else:
    najmenej = (d - 1) // 2 + 1

najviac = d - 1

možnosti = najviac - najmenej + 1

# vypíšeme výsledný počet možností
print(možnosti)

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

Časová zložitosť tohto programu je O(1). Robíme len niekoľko operácií s číslami. To znamená že náš program bude bežať približne rovnako dlho aj pre malé hodnoty \(d\), aj pre veľké. To napríklad u predošlého riešenia neplatilo. Pamäťová zložitosť je \(O(1)\), keďže si v každom momente pamätáme len niekoľko čísel.

Triky na skrátenie programu

Vo všeobecnosti neplatí, že kratší program je lepší. Je to skôr naopak, kratší menej prehľadný program býva horší. Ukážeme si však ako by sa dalo predošlé riešenie ešte skrátiť. Využijeme vlastnosť programovacieho jazyku, a to takzvané celočíselné delenie. V Pythone sa značí // a dáva nám výsledok po delení bezo zvyšku. Ak teda spravíme napr. 5 // 2 výjde nám výsledok \(2\). Síce \(5 \div 2 = 2 zv. 1\), zvyšok sa ale pri tejto operácií zahodí.

To vieme využiť vo svoj prospech. Nebudeme musieť rozlišovať medzi prípadom párneho a nepárneho \(d\). Náš program by sme potom vedeli napísať dokonca na dva riadky:

d = int(input())
print((d - 1) - (d // 2 + 1) + 1)