Príprava k domácemu kolu OI 2025/2026¶

41. ročník, kategória B¶

  • pre žiakov 1. a 2. ročníka SŠ a vyšších ročníkov ZŠ
  • iba domáce a krajské kolo
  • potrebné iba úplné základy programovania
  • vhodné na tréning

Úlohy¶

každá úloha za 10 bodov

  • Programátorské - automatické testovanie vyladeného programu
  • Teoretické - spísaný popis riešenia
  • Model - teoretická úloha so študijným textom
  • pomerne náročné
  • obsah vysoko prekračujúci ŠVP
  • dlhé a komplexné úlohy a študijné texty

Uľahčenie

  • neočakáva sa, že vyriešite všetko
  • úlohy sa dajú riešiť čiastočne
  • na postup na krajské kolo treba len 10 bodov
  • k domácemu kolu existujú návodné úlohy (na stránke oi.sk)
  • teoretické úlohy sa opierajú najmä o matematiku

Zdroje

  • stránka olympiády https://oi.sk/
  • návodné úlohy k domácemu kolu https://oi.sk/archiv/2025/sl-2025-1-ine-B-navodne.pdf
  • organizátori anderle.michal@gmail.com, rastislav.krivos-bellus@upjs.sk
  • korešpondenčný seminár z programovania https://www.ksp.sk/
  • programátorská kuchárka https://www.ksp.sk/kucharka/
  • informatický krúžok na UPJŠ https://ics.upjs.sk/kruzok/ [+ PALMA https://palma.strom.sk/]

Slovné riešenie¶

Malo by obsahovať

  • Popis myšlienky - high-level čo váš algoritmus bude robiť
  • Popis algoritmov a dátových štruktúr, ktoré využívate
  • Zdôvodnenie správnosti - hlavné argumenty zdôvodňujúce korektnosť programu
  • Odhad časovej zložitosti
  • Inšpiráciu hľadajte vo vzorových riešeniach
  • Popis nemá byť preloženie programu! (napr. netreba názvy premenných)
  • Za odhad zložitosti je málo bodov.

https://www.ksp.sk/idealne-riesenie/

B-I-1 Preteky¶

image.png

image-2.png

image.png

$t \cdot t$ ?

RZP $\frac{a \cdot t^2}{2}$

In [1]:
1+2+3+4+5
Out[1]:
15
In [2]:
t = 5

for i in range(t):
    output = output+i+1
output

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[2], line 4
      1 t = 5
      3 for i in range(t):
----> 4     output = output+i+1
      5 output

NameError: name 'output' is not defined
In [3]:
t = 5

output = 0
for i in range(t):
    output = output+i+1
output
Out[3]:
15
In [4]:
t = 5 #cas

s = 0 #draha
v = 0 #rychlost
for i in range(t):
    v += 1
    s += v
s
Out[4]:
15
In [5]:
t = 5 #cas

s = 0 #draha
v = 0 #rychlost
for i in range(t):
    v += 1
    s += v
print(s)

15
In [11]:
t = 10 #cas

s = 0 #draha
v = 0 #rychlost
for i in range(t):
    v += 1
    s += v
print(s)

55
In [ ]:
t = 10 #cas

s = 0 #draha
v = 0 #rychlost
for _ in range(t): #nepouzivana premenna
    v += 1
    s += v
print(s)
In [7]:
t**2/2
Out[7]:
50.0

$\frac{t \cdot (t+1)}{2}$

In [10]:
t*(t+1)//2
Out[10]:
55

image.png

detto

image-2.png

bude mi to trvať $v-x$ sekúnd

$$ \sum^{v}_{r=x+1} r = v+(v-1)+\cdots + (x+1) = \frac{v \cdot (v+1)}{2}-\frac{x \cdot (x+1)}{2}$$

image.png

In [13]:
10**8
Out[13]:
100000000

$\frac{t \cdot (t+1)}{2} \geq 10^8$

In [15]:
t = 1
while t*(t+1)//2 < 10**8:
    t += 1
t
Out[15]:
14142

$t^2+t-200.000.000 \geq 0$

image.png

In [20]:
5-1+10-6 #rychlost
Out[20]:
8
In [21]:
5+1+10+6 #cas
Out[21]:
22
In [22]:
1+2+3+4+5 +4 +5+6+7+8+9+10+11+12+13+14 +13+12+11+10+9+8
Out[22]:
177

Ako rýchlejšie?

postupne zrýchľovať , ostať, postupne spomaľovať

max. na konci 8, ale priebežne môže aj viac ako 8

B-I-2 Nedočkavosť¶

image-2.png image.png

In [ ]:

image.png

počet navzájom rôznych susedov K

image.png

simulujeme ďalej ako keby boli K aj v prvých

image.png

dôkaz sporom

image.png

In [ ]:

B-I-3 Cesty v mriežke¶

image-8.png

image.png

In [26]:
r, s = 2, 4
# prazdne pole s r riadkami a s stlpcami
mriezka = [[0 for _ in range(s)] for _ in range(r)]
mriezka[0][0] = 1 # pociatocna hodnota
for x in range(r):
    for y in range(s):
        if x != 0: # existuje policko nadomnou
            mriezka[x][y] += mriezka[x - 1][y]
        if y != 0: # existuje policko nalavo
            mriezka[x][y] += mriezka[x][y - 1]
print(mriezka[r - 1][s - 1])

4
In [27]:
r, s = 3, 4
# prazdne pole s r riadkami a s stlpcami
mriezka = [[0 for _ in range(s)] for _ in range(r)]
mriezka[0][0] = 1 # pociatocna hodnota
for x in range(r):
    for y in range(s):
        if x != 0: # existuje policko nadomnou
            mriezka[x][y] += mriezka[x - 1][y]
        if y != 0: # existuje policko nalavo
            mriezka[x][y] += mriezka[x][y - 1]
print(mriezka[r - 1][s - 1])
mriezka

10
Out[27]:
[[1, 1, 1, 1], [1, 2, 3, 4], [1, 3, 6, 10]]

image.png

image-3.png

image-4.png

image-5.png

image-6.png

image-7.png

image.png

In [ ]:

image.png

In [ ]:

image.png

In [31]:
20+20+20+20 #max
Out[31]:
80

image.png

In [ ]:

image.png

In [ ]:

B-I-4 Krtko staviteľ¶

image.png

image.png

image.png

image.png

Z -> ε|aZ

image.png

Z -> ε|aZ|bZ

image.png

Z -> A|B
A -> ε|aA|bA
B -> hlina|a55

image.png

image.png

image.png

Z -> a2|a3|a10|...|a3457

image.png

Z -> aZ|ε

image.png

Z -> aaaaaZ|ε

násobky 5-tich (0, 5, 10, 15, ...)

Z -> aZ|aaaaa

image.png

Z -> aZ|Y
Y -> bY|ε
In [ ]:

image.png

Z -> aZ|aaaaaY
Y -> bY|bbbbb

image.png

Z -> aY
Y -> aY|bY|ε

image.png

Z -> aZ|bZ|Y
Y -> a

skrátene

Z -> aZ|bZ|a

image.png

IMG_20251029_163521_resized_20251029_045203724.jpg

In [ ]: