´ torske
´u
´ lohy
Programa
1
Z´
aklady
1.1 Vypiˇste na obrazovku ”Hello, World!”
1.2 Zeptejte se na jm´eno uˇzivatele a vypiˇste ”Ahoj <JM´
ENO>”
1.3 Naˇctˇete cel´e ˇc´ıslo X, pˇriˇctˇete k nˇemu 5 a vypiˇste souˇcet.
1.4 Zeptejte se na ˇc´ısla A a B (celoˇc´ıseln´e, A > B, jsou na jednom ˇr´adku oddˇelen´e mezerou) a
vypiˇste:
(a) souˇcet A + B
(b) souˇcin A · B
(c) celoˇc´ıseln´
y pod´ıl A/B
(d) zbytek po dˇelen´ı ˇc´ısla B ˇc´ıslem A
1.5 Na vstupu dostanete ˇc´ısla A, B a znak C oddˇelen´e mezerou. C je z mnoˇziny {+, −, ∗, /}. Proved’te
s ˇc´ısly poˇzadovanou matematickou operaci (dˇelen´ı pro jednoduchost pouze celoˇc´ıseln´e).
1.6 Ve vˇezen´ı v´
am daj´ı posledn´ı ˇsanci zachr´anit si ˇzivot. Kat si vymysl´ı dvˇe ˇc´ısla a v´am sdˇel´ı jejich
souˇcet a rozd´ıl. Pokud dok´
aˇzete spr´avnˇe urˇcit ˇc´ısla, kter´a si kat vymyslel, z˚
ustanete trˇcet ve
vˇezen´ı do konce ˇzivota. Pokud neuh´adnete, poprav´ı v´as rovnou. Kat se ale m˚
uˇze spl´est. (Kati
na tom s matematikou nejsou moc dobˇre.) Pokud se tak stane, staˇc´ı v´am ˇr´ıci, ˇze takov´a ˇc´ısla
neexistuj´ı.
Na vstupu dostanete ˇc´ısla A a B, kde A = X + Y a B = X − Y . Vypiˇste ˇc´ısla X a Y .
Pˇr´ıklad vstupu:
7 3
Pˇr´ıklad v´ystupu:
5 2
1.7 Brzdn´a dr´
aha vozidla pˇri rychlosti 100 km · h−1 je zhruba 48 m. Pokud faktory jako je tˇren´ı,
brzdn´
y syst´em nebo gumy apod. z˚
ustanou nezmˇenˇeny, m˚
uˇzeme odhadnout brzdnou dr´ahu jako
u
´mˇernou vzhledem k druh´e mocninˇe rychlosti auta. Vypoˇc´ıtejte brzdnou dr´ahu pro rychlost X
z´ıskanou ze standardn´ıho vstupu.
Pˇr´ıklad vstupu:
50
76
Pˇr´ıklad v´ystupu:
12.0
27.7
1.8 * Lenochod se snaˇz´ı vyˇsplhat na vysokou strmou sk´alu (zvl´aˇstn´ı lenochod, ˇze?), kter´a m´
a V
metr˚
u. Lenochod dok´
aˇze za den vystoupat o A metr˚
u vzh˚
uru (a tak´e o tolik kaˇzd´
y den vystoup´
a).
V noci ale klesne zpˇet o B metr˚
u. Kter´
y den od zaˇc´atku stoup´an´ı se dostane na vrchol?
2
Podm´ınky
2.1 Naˇctˇete dvˇe ˇc´ısla A a B a vypiˇste vˇetˇs´ı z nich.
2.2 Zeptejte se uˇzivatele, kolik je 5 + 3 ∗ 2 a zkontrolujte jeho odpovˇed’. Pokud bude spr´avn´a vypiˇste
SPRAVNE, v opaˇcn´em pˇr´ıpadˇe CHYBA.
2.3 Na vstupu dostanete na prvn´ım ˇr´
adku dvˇe ˇc´ısla (A a B) oddˇelen´a mezerou a na dalˇs´ım ˇr´
adku
jedno ˇc´ıslo X. Ovˇeˇrte, zda plat´ı A − B = X. Pokud ano, vypiˇste ANO, pokud ne, vypiˇste NE.
2.4 Na ˇr´adku jsou zadan´
a tˇri ˇc´ısla oddˇelen´a mezerou. Vypiˇste nejvˇetˇs´ı z nich.
1
2.5 Na prvn´ım ˇr´
adku dostanete ˇc´ısla A a B (1 ≤ A ≤ B ≤ 30000), na dalˇs´ım ˇr´adku ˇc´ıslo X. Zjistˇete,
zda plat´ı, ˇze A ≤ X ≤ B.
2.6 B´ed’a je hrozivˇe netrpˇeliv´
y a sv´
ych narozenin se nem˚
uˇze doˇckat. R´ad by vˇedˇel, kolik mu v tomto
kalend´aˇrn´ım roce do narozenin zb´
yv´a. Napiˇste mu program.
Na vstupu dostanete na prvn´ım ˇr´
adku je datum, kdy se v´as B´ed’a pt´a, na druh´em ˇr´adku je
datum kdy m´
a narozeniny. Obˇe data jsou zadan´a jako dvˇe ˇc´ıslice oddˇelen´e mezerou.
Vypiˇste poˇcet dn´ı, kter´e zb´
yvaj´ı do dan´eho data. Prvn´ı den nezapoˇc´ıt´avejte, posledn´ı ano. Pokud
’
B´ed a uˇz letos narozeniny mˇel, vypiˇste Letos uz ne. Rok nen´ı pˇrestupn´
y a mˇes´ıce maj´ı bˇeˇzn´
y
poˇcet dn˚
u.
Pˇr´ıklad vstupu:
12 5
25 5
Pˇr´ıklad v´ystupu:
13
2.7 Na ˇsachovnici jsou postaveny dvˇe d´
amy. Zjistˇete, zda se vz´ajemnˇe ohroˇzuj´ı...
Na vstupu dostanete na dvou ˇr´
adc´ıch jejich souˇradnice. Kaˇzd´
y ˇr´adek obsahuje pr´avˇe dvˇe ˇc´ısla,
v intervalu od jedn´e do osmi. Pokud se kr´alovny ohroˇzuj´ı, vypiˇste ANO, v opaˇcn´em pˇr´ıpadˇe NE.
Pˇr´ıklad vstupu:
2 3
5 7
3
Pˇr´ıklad v´ystupu:
NE
Cykly
3.1 Vypiˇste ˇc´ısla od 1 do 100.
3.2 Vypiˇste ˇc´ısla od 1000 do 200.
3.3 Uˇzivatel zad´
a ˇc´ıslo X. Vypiˇste vˇsechna ˇc´ısla od 0 do X.
3.4 Vypiˇste vˇsechna sud´
a ˇc´ısla od 1 do 200.
3.5 Vypiˇste vˇsechna ˇc´ısla dˇeliteln´
a tˇremi nebo ˇctyˇrmi od 1 do 200.
3.6 Na vstupu dostanete ˇc´ıslo X. Vypiˇste vˇsechna prvoˇc´ısla menˇs´ı neˇz X.
3.7 Na vstupu dostanete dvˇe ˇc´ısla A, B. Najdˇete jejich nejvˇetˇs´ıho spoleˇcn´eho dˇelitele.
3.8 Na vstupu dostanete dvˇe ˇc´ısla A, B. Najdˇete jejich nejmenˇs´ı spoleˇcn´
y n´asobek.
3.9 Na prvn´ım ˇr´
adku dostanete dvˇe ˇc´ısla N a K, kde N je poˇcet ˇc´ısel, kter´e n´asleduj´ı na n´asleduj´ıc´ım
ˇr´adku oddˇelen´
ych mezerou a K je hledan´e ˇc´ıslo. Zjistˇete, zda se dan´e ˇc´ıslo v posloupnosti nach´
az´ı.
Pokud ano, vypiˇste jeho pozici, pokud ne, vypiˇste NE.
3.10 Na ˇr´adku dostanete pˇredem nezn´
am´
y poˇcet ˇc´ısel oddˇelen´
ych mezerou. Vypiˇste:
(a) jejich poˇcet
(b) jejich pr˚
umˇer (celoˇc´ıseln´
y)
(c) minimum
(d) maximum
3.11 Na prvn´ım ˇr´
adku dostanete ˇc´ıslo N a na dalˇs´ıch N ˇr´adc´ıch ˇc´ısla. Zjistˇete, zda ˇc´ısla tvoˇr´ı:
(a) rostouc´ı posloupnost
(b) klesaj´ıc´ı posloupnost
(c) line´arn´ı posloupnost (plat´ı, ˇze x2 − x1 = x4 − x3 )
2
3.12 Na pˇredem nezn´
am´em poˇctu ˇr´
adk˚
u dostanete ˇc´ısla. Najdˇete libovoln´e:
(a) lok´aln´ı minimum (pro lok´
aln´ı minimum plat´ı, ˇze xn−1 > xn < xn+1 ).
(b) lok´aln´ı maximum (xn−1 < xn > xn+1 ).
ˇSI
´C
3.13 * Na vstupu dostanete tˇri ˇc´ısla oddˇelen´a mezerou - bude se jednat o datum ve tvaru DEN ME
ROK. Vaˇs´ım u
´kolem je zjistit, kter´
y den v t´
ydnu to zrovna byl1 . (Pondˇel´ı ˇci u
´ter´
y? Nebo nˇeco
jin´eho?) Jenˇze to nebude tak jednoduch´e. Nˇekter´e roky jsou pˇrestupn´e, jin´e ne. Nav´ıc to nebylo
vˇzdy stejnˇe.
Do roku 1582 se pouˇz´ıval Juli´
ansk´
y kalend´aˇr. U toho platilo, ˇze pˇrestupn´
y je kaˇzd´
y ˇctvrt´
y rok.
Zaveden´ım Gregori´
ansk´eho kalend´
aˇre se ale opravila nepˇresnost mˇeˇren´ı d´elky roku a znaˇcnˇe
zkomplikovalo pravidlo pˇrestupnosti. Rok je pˇrestupn´
y pr´avˇe tehdy, pokud je dˇeliteln´
y 4, ale
nen´ı dˇeliteln´
y 100, nebo pokud je dˇeliteln´
y 400. Matematicky zaps´ano - rok x je pˇrestupn´
y
pokud plat´ı:
[(4|x) ∧ (100 - x)] ∨ (400|x)
Kalend´aˇr byl nav´ıc posunut, aby se srovnala odchylka. Den n´asleduj´ıc´ı po 4. ˇr´ıjnu 1582 byl
vyhl´aˇsen jako 15. ˇr´ıjen 1582.
Pˇr´ıklad vstupu:
29 1 2010
15 11 1997
11 2 1732
Pˇr´ıklad v´ystupu:
patek
sobota
patek
3.14 Dostali jste zak´
azku od Nescaf´e na v´
yrobu automat˚
u na k´avu. Potˇrebujete napsat program,
kter´
y urˇc´ı jakou hotovost m´
a automat vr´atit a v jak´
ych minc´ıch. Stav´ıte automat nov´e generace,
proto dok´
aˇze pˇrij´ımat veˇsker´e mince i bankovky: 1 Kˇc, 2 Kˇc, 5 Kˇc, 10 Kˇc, 20 Kˇc, 50 Kˇc, 100 Kˇc,
200 Kˇc, 500 Kˇc, 1.000 Kˇc, 2.000 Kˇc, 5.000 Kˇc. Samozˇrejmˇe se snaˇz´ıte vr´atit co nejm´enˇe minc´ı
(bankovek).
Na vstupu dostanete ˇc´ısla C a V , kde C je cena vybran´eho n´apoje a V je vhozen´a ˇc´astka. Na
v´
ystupu vyp´ıˇsete mince, kter´e budete vracet ve tvaru KOLIKR´
AT x MINCE.
Pˇr´ıklad vstupu:
11 100
Pˇr´ıklad v´ystupu:
1 x 50
1 x 20
1 x 10
1 x 5
2 x 2
3.15 Pythagorejsk´
a ˇc´ısla jsou ˇc´ısla a, b, c ∈ N, pro kter´a plat´ı a2 + b2 = c2 . Na vstupu dostanete ˇc´ıslo
K. Najdˇete vˇsechna pythagorejsk´
a ˇc´ısla pro a, b, c < K.
3.16 Na vstupu je d´
ana posloupnost cel´
ych ˇc´ısel. Najdˇete nejdelˇs´ı rostouc´ı podposloupnost.
Pˇr´ıklad vstupu:
1 2 3 1 2 8 6 2 4 5 8 9 12 3 4 7 9 6
Pˇr´ıklad v´ystupu:
2 4 5 8 9 12
3.17 Napiˇste program, kter´
y urˇc´ı pˇresn´
y vˇek podle zadan´eho data. Na prvn´ım ˇr´adku vstupu bude
aktu´aln´ı datum, na druh´em datum narozen´ı. V´
ystup bude vyj´adˇren poˇctem dn˚
u.
Pˇr´ıklad vstupu:
12 11 2010
9 6 1999
1
Pˇr´ıklad v´ystupu:
4174
Pˇr´ıklad z kvalifikaˇcn´ıho kola soutˇeˇze PilsProg 2010
3
3.18 Na vstupu m´
ate danou velmi dlouhou posloupnost ˇc´ısel, kde se kaˇzd´e ˇc´ıslo vyskytuje v sud´em
poˇctu, v´
yjimkou je jedno ˇc´ıslo, kter´e se v posloupnosti vyskytuje pr´avˇe jednou. Napiˇste program,
kter´
y toto ˇc´ıslo najde.
Pˇr´ıklad vstupu:
1 3 5 2 2 4 3 1 5 5 5
Pˇr´ıklad v´ystupu:
4
3.19 Na2 vstupu m´
ate zad´
ano ˇc´ıslo, kter´e se vejde do typu longint. Je potˇreba toto ˇc´ıslo rozloˇzit na
vˇsechny prvoˇcinitele.
Pˇr´ıklad vstupu:
156
Pˇr´ıklad v´ystupu:
2 2 3 13
3.20 Na vstupu dostanete posloupnost N cel´
ych ˇc´ısel. Tato ˇc´ısla tvoˇr´ı jakousi smyˇcku. Vypiˇste na
kolik´at´em ˇc´ısle mus´ıte zaˇc´ıt, aby po pˇriˇcten´ı n´asleduj´ıc´ıch N − 1 ˇc´ısel byl souˇcet vˇzdy nez´aporn´
y.
Pokud nelze, vypiˇste nulu. Pokud dan´
ych pozic existuje v´ıc, vypiˇste prvn´ı z nich. Pozice jsou
ˇc´ıslov´any od jedn´e.
Pˇr´ıklad vstupu:
3 0 -5 4 2 -1 2 3
Pˇr´ıklad v´ystupu:
4
ˇ ıslo
3.21 M´ate zadanou mˇr´ıˇzku o rozmˇerech 2 × 2 a v kaˇzd´em jej´ım kvadrantu jedno pˇrirozen´e ˇc´ıslo. C´
vlevo nahoˇre si oznaˇcme napˇr. A, vpravo nahoˇre B, vpravo dole C a vlevo dole D. Mˇr´ıˇzkou
m˚
uˇzete libovolnˇe ot´
aˇcet, pˇriˇcemˇz plat´ı st´al´a pozice definovan´
ych p´ısmen (neboli A je vˇzdy vlevo
nahoˇre apod.).
Vaˇs´ım u
´kolem je urˇcit poˇcet minim´
aln´ıch otoˇcen´ı mˇr´ıˇzkou, tak aby
−
B
C
bylo maxim´aln´ı.
Pˇr´ıklad v´ystupu:
2
Pˇr´ıklad vstupu:
3 2
1 4
4
A
D
Pole
4.1 Na vstupu dostanete 100 ˇc´ısel oddˇelen´
ych mezerou. Vypiˇste je v obr´acen´em poˇrad´ı.
4.2 Na prvn´ım ˇr´
adku dostanete ˇc´ıslo N (1 ≤ N ≤ 500) a na dalˇs´ım ˇr´adku N ˇc´ısel oddˇelen´
ych
mezerou. Vypiˇste ˇc´ısla po dvojic´ıch - na prvn´ım ˇr´adku vyp´ıˇsete 1. ˇc´ıslo a N -t´e ˇc´ıslo, na druh´em
ˇr´adku 2. ˇc´ıslo a (N − 1)-t´e ˇc´ıslo...
4.3 M´ate matici (tabulku) ˇc´ısel, kter´e budou zad´any n´asleduj´ıc´ım zp˚
usobem: Na prvn´ım ˇr´adku dostanete dvˇe ˇc´ısla A a B (1 ≤ A, B ≤ 100) oddˇelen´a mezerou. Bude n´asledovat A ˇr´adk˚
u a na
kaˇzd´em z nich B ˇc´ısel oddˇelen´
ych mezerou.
(a) Vypoˇctˇete souˇcet v jednotliv´
ych sloupc´ıch.
(b) Vypoˇctˇete souˇcet na obou u
´hlopˇr´ıˇck´ach.
4.4 Na vstupu dostanete ˇretˇezec, kter´
y obsahuje slova oddˇelen´a mezerami. Vypiˇste:
(a) poˇcet slov
(b) nejdelˇs´ı slovo
(c) nejkratˇs´ı slovo
(d) kaˇzd´e slovo s poˇctem v´
yskyt˚
u.
4.5 Pascal˚
uv troj´
uheln´ık3 zaˇc´ın´
a jedniˇckou a na dalˇs´ıch ˇr´adc´ıch pokraˇcuje vˇzdy souˇctem dvou ˇc´ısel
z pˇredchoz´ıho. Pˇr´ıklad Pascalova troj´
uheln´ıku:
2
3
Z online soutˇeˇze PROSO
Podrobnosti o Pascalovˇe troj´
uheln´ıku a o tom, v ˇcem je tak zaj´ımav´
y
4
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Napiˇste program, kter´
y dostane jako parametr ˇc´ıslo H a vyp´ıˇse H-tou u
´roveˇ
n (ˇr´adek) Pascalova
troj´
uheln´ıku.
Pˇr´ıklad vstupu:
4
Pˇr´ıklad v´ystupu:
1 3 3 1
4.6 Na dostanete pozici dvou dam (koˇ
n˚
u, stˇrelc˚
u...) na ˇsachovnici. Vypiˇste ANO, pokud se figurky
ohroˇzuj´ı. V opaˇcn´em pˇr´ıpadˇe vypiˇste NE.
5
Funkce
5.1 Napiˇste funkci, kter´
a pˇrijme jeden celoˇc´ıseln´
y parametr a vr´at´ı jeho druhou mocninu.
5.2 Vytvoˇrte funkci, kter´
a pˇrijme dva parametry - X a Y a vr´at´ı X Y .
5.3 Napiˇste funkci, kter´
a dostane jeden parametr X a vr´at´ı: 1 + 2 + 3 + ... + X.
5.4 Napiˇste funkci, kter´
a obdrˇz´ı jako parametr pole a vr´at´ı souˇcet vˇsech poloˇzek v tomto poli.
5.5 Napiˇste funkci, kter´
a obdrˇz´ı jako parametr pole ˇc´ısel a vyp´ıˇse hodnotu, kter´a se nejˇcastˇeji opakuje.
5.6 Napiˇste funkci na urˇcen´ı N-t´eho Fibonacciho ˇc´ısla4 . Na vstupu bude celoˇc´ıseln´
y parametr N a
na v´
ystupu N -t´e Fibonacciho ˇc´ıslo.
5.7 Napiˇste funkci, kter´
a urˇc´ı, zda je zadan´
y rok pˇrestupn´
y. Rok je pˇrestupn´
y pr´avˇe tehdy, pokud
je dˇeliteln´
y ˇctyˇrmi. V´
yjimku tvoˇr´ı roky, kter´e jsou dˇeliteln´e stem - ty jsou pˇrestupn´e pouze
tehdy, pokud jsou z´
aroveˇ
n dˇeliteln´e 4005 . Na vstupu funkce dostane rok z rozmez´ı 0..3000 a
vr´at´ı logickou hodnotu (true - pˇrestupn´
y rok, false - nepˇrestupn´
y rok).
5.8 Faktori´al z ˇc´ısla x je ˇc´ıslo 1 · 2 · 3 · ... · x (a znaˇc´ı se x!). Napiˇste funkci, kter´a bude faktori´
al
poˇc´ıtat.
5.9 Dokonal´e ˇc´ıslo je takov´e ˇc´ıslo, kter´e se rovn´a souˇctu vˇsech sv´
ych kladn´
ych dˇelitel˚
u (kromˇe sebe
samotn´eho). Pˇr´ıklad - ˇc´ıslo 6 m´
a dˇelitele 1, 2 a 3. Jejich souˇcet 1 + 2 + 3 = 6, proto je ˇc´ıslo
6 dokonal´e. Napiˇste funkci, kter´
a zjist´ı, zda je ˇc´ıslo dokonal´e. Bude pˇrij´ımat jeden celoˇc´ıseln´
y
parametr a v´
ystupem bude logick´
a hodnota True × False.
5.10 * M´ame mˇr´ıˇzku o velikosti N × N a nach´az´ıme se v doln´ım lev´em rohu. Chceme pˇrij´ıt na poˇcet
zp˚
usob˚
u, kter´
ymi se m˚
uˇzeme dostat do horn´ıho prav´eho rohu, tak abychom se pˇri cestˇe nevraceli
a nepˇrekroˇcili u
´hlopˇr´ıˇcku. Pohybujeme se po hran´ach bud’ ve smˇeru osy X nebo Y .
Na vstupu se nach´
az´ı velikost mˇr´ıˇzky, na v´
ystupu poˇcet moˇzn´
ych cest.
Pˇr´ıklad vstupu:
4
Pˇr´ıklad v´ystupu:
14
5.11 * Na vstupu je zad´
ano jedno cel´e ˇc´ıslo N (1 ≤ N ≤ 40). Najdˇete vˇsechny rostouc´ı posloupnosti
pˇrirozen´
ych ˇc´ısel, jejichˇz souˇcet d´
av´
a dohromady N . Aby to nebylo tak jednoduch´e, mus´ı platit
pravidlo super-parity - z ˇc´ısel, kter´e budou d´avat po souˇctu ˇc´ıslo N , mus´ı b´
yt pr´avˇe polovina
sud´a a polovina lich´
a.
4
5
Co jsou to Fibonacciho ˇc´ısla naleznete tˇreba na Wikipedii.
Pokud jsem v´
am akor´
at zamotal hlavu, m˚
uˇzete se opˇet pod´ıvat na Wikipedii, nebo zp´
atky na pˇr´ıklad 3.13
5
Obr´
azek 1: Uk´
azka moˇzn´
ych cest pˇri velikosti mˇr´ıˇzky 4 × 4
Pˇr´ıklad vstupu:
4
Pˇr´ıklad v´ystupu:
1 1 2 4
1 2 2 3
5.12 Palindromy jsou takov´
a slova, kter´
a m˚
uˇzeme ˇc´ıst odpˇredu i zezadu a slovo se nezmˇen´ı. Pˇr´ıklad
takov´eho palindromu je tˇreba ANNA. Na vstupu dostanete ˇc´ıslo N a na dalˇs´ıch N ˇr´adc´ıch jednotliv´a slova. Vaˇs´ım u
´kolem je urˇcit, kter´e z nich jsou palindromy a kter´e ne. Pro kaˇzd´e slovo
vypiˇste ANO nebo NE.
Pˇr´ıklad v´ystupu:
NE
ANO
ANO
NE
ANO
ANO
Pˇr´ıklad vstupu:
6
VLK
ANNA
RADAR
TRESTANEC
BLB
MADAM
5.13 Na6 vstupu dostanete dva ˇretˇezce, oba kratˇs´ı neˇz 255 znak˚
u. Vaˇs´ım u
´kolem je zjistit, kolika
zp˚
usoby lze prvn´ı ˇretˇezec sloˇzit z p´ısmen (i mezer!) druh´eho, tak aby p´ısmena byla v nepˇreh´azen´em
poˇrad´ı.
Pˇr´ıklad vstupu:
Programatorska soutez
PPProgramatorska souteztez
6
Pˇr´ıklad v´ystupu:
12
Algoritmy
6.1
Binary Search
6.1.1 Napiˇste funkci, kter´
a pˇrijme vzestupnˇe seˇrazen´e pole ˇc´ısel a ˇc´ıslo K. Pokud bude ˇc´ıslo K v poli
existovat vr´
at´ı jeho pozici (index), pokud ne, vr´at´ı pozici nejbliˇzˇs´ıho ˇc´ısla.
6.1.2 Napiˇste program, kter´
y na prvn´ım ˇr´adku naˇcte ˇc´ısla N , R a K, kde R je poˇcet n´asleduj´ıc´ıch
ˇr´adk˚
u s N ˇc´ısly oddˇelen´
ych mezerou. Zjistˇete, zda se mezi ˇc´ısly nach´az´ı ˇc´ıslo K, pokud ano,
vypiˇste jeho pozici.
6.1.3 Vymyslete algoritmus, kter´
y v zadan´e matici o rozmˇerech a × b nalezne ˇc´ıslo, kter´e m´a hodnotu
pˇresnˇe a + b.
6
Z online soutˇeˇze PROSO prvn´ıho kola v roce 2010
6
6.2
ˇ
Razen´
ı
6.2.1 Na prvn´ım ˇr´
adku dostanete ˇc´ıslo N . Na dalˇs´ım ˇr´adku N ˇc´ısel oddˇelen´
ych mezerou. Vypiˇste je
v seˇrazen´em poˇrad´ı podle velikosti vzestupnˇe.
6.2.2 * Chcete pˇrepˇrahat vlaky7 . Funguje to tak, ˇze m´ate toˇcnu, na kterou najedete se dvˇema vag´
ony
a otoˇc´ıte je neboli prohod´ıte jejich poˇrad´ı. Na zaˇc´atku m´ate N vag´on˚
u oˇc´ıslovan´e permutac´ı ˇc´ısel
1, 2, 3...N (napˇr. pro N = 4 v poˇrad´ı 3, 1, 2, 4). Pomoc´ı ot´aˇcen´ı sousedn´ıch vag´on˚
u na toˇcnˇe,
chcete z´ıskat vag´
ony seˇrazen´e vzestupnˇe. Ot´azkou je, kolik otoˇcen´ı minim´alnˇe potˇrebujete.
Na vstupu dostanete na prvn´ım ˇr´
adku ˇc´ıslo N a na dalˇs´ım ˇr´adku N zpˇreh´azen´
ych ˇc´ısel. V´
ystupem
bude ˇc´ıslo rovno minim´
aln´ımu poˇctu potˇrebn´
ych otoˇcen´ı.
Pˇr´ıklad vstupu:
4
4 3 2 1
Pˇr´ıklad v´ystupu:
6
6.2.3 * Nem´ate pen´ıze na knihovnu, proto vˇsechny kn´ıˇzky o programov´an´ı skl´ad´ate do jednoho sloupce
na sebe. Samozˇrejmˇe byste mˇeli r´
adi kn´ıˇzky seˇrazen´e, dole zaˇc´ınat p´ısmenem A (Algoritmy) a
nahoˇre konˇcit p´ısmenem Z (Zend Framework). Probl´em je, ˇze kn´ıˇzky m˚
uˇzete pˇrerovn´avat jenom
tak, ˇze nˇekterou vyt´
ahnete (odkudkoli) a um´ıst´ıte ji nahoru. Ot´azkou je, kolikr´at budete muset
nˇejakou knihu vytahovat a pokl´
adat na vrchol sloupce, abyste nakonec mˇeli knihy seˇrazen´e?
Trochu si to zjednoduˇs´ıme a knihy si oˇc´ıslujeme od 1 do N . Na prvn´ım ˇr´adku programu dostanete
toto N a na dalˇs´ıch N ˇr´
adc´ıch ˇc´ısla (1..N ) knih, tak jak jsou nyn´ı ve sloupci odspoda nahoru.
Na v´
ystupu bude ˇc´ıslo, kolikr´
at mus´ıme nˇejakou knihu vyt´ahnout a poloˇzit nahoru, abychom je
nakonec mˇeli srovnan´e.
Pˇr´ıklad v´ystupu:
2
Pˇr´ıklad vstupu:
4
1
3
4
2
6.3
Halda
6.3.1 Jste na dostiz´ıch a chcete si vsadit. M´ate ˇc´astku C a chcete ji rozdˇelit mezi N koˇ
n˚
u tak, aby v´
aˇs
zisk byl co nejvyˇsˇs´ı, at’ vyhraje jak´
ykoliv.
Pˇr´ıklad - m´
ate 100 Kˇc a na tˇri konˇe jsou vyps´any tyto kurzy:
• k˚
un
ˇ A: za 1 Kˇc z´ısk´
ate 3 Kˇc
• k˚
un
ˇ B: za 1 Kˇc z´ısk´
ate 5 Kˇc
• k˚
un
ˇ C: za 1 Kˇc z´ısk´
ate 7 Kˇc
Spr´avn´e rozhodnut´ı bude n´
asleduj´ıc´ı, na konˇe A vsad´ıte 49 Kˇc, na konˇe B 30 Kˇc a na posledn´ıho
konˇe 21 Kˇc. Pokud vyhraje prvn´ı k˚
un
ˇ z´ısk´ate 3 × 49 = 147, v pˇr´ıpadˇe v´ıtˇezstv´ı druh´eho 5 × 30 =
150, pˇri v´
yhˇre tˇret´ıho 7 × 21 = 147. Nejniˇzˇs´ı moˇzn´a v´
yhra je 147 Kˇc. Na v´
ystup vyp´ıˇsete ˇcist´
y
zisk - 47 Kˇc.
Na vstupu dostanete na prvn´ım ˇr´
adku ˇc´ısla C a N , na dalˇs´ım ˇr´adku N ˇc´ısel s kurzy jednotliv´
ych
koˇ
n˚
u. Na v´
ystupu vyp´ıˇsete zisk v nejhorˇs´ım pˇr´ıpadˇe.
Pˇr´ıklad vstupu:
100 3
3 5 7
7
Pˇr´ıklad v´ystupu:
47
Z fin´
alov´eho kola soutˇeˇze PilsProg 2010 - u
´loha v origin´
aln´ım zad´
an´ı.
7
6.4
6.4.1
Bloudˇ
en´ı po grafech
8
Na vstupu dostaneme dopravn´ı mapu Anglie zadanou jako seznam spojen´ı (ˇzelezniˇcn´ıch tras),
kter´e vedou mezi r˚
uzn´
ymi mˇesty (vˇzdy obˇema smˇery). Pro jednoduchost pˇredpokl´adejme, ˇze
pouˇzit´ı takov´eho spojen´ı trv´
a jednotkov´
y ˇcas. U kaˇzd´eho spojen´ı je na vstupu tak´e naps´
ano
pˇrirozen´e ˇc´ıslo, kolik pana Babbage jeho pouˇzit´ı stoj´ı. Tak´e dostanete naps´ano, ve kter´em mˇestˇe
Babbage zaˇc´ın´
a a kde bydl´ı Ada.
Na v´
ystupu vypiˇste posloupnost spojen´ı (neboli cestu), kter´a ze vˇsech cest z Babbageho stanoviˇstˇe do Adina bydliˇstˇe, kter´e pouˇz´ıvaj´ı nejm´enˇe spojen´ı, stoj´ı nejm´enˇe penˇez, tj. souˇcet ohodnocen´ı vˇsech spojen´ı na cestˇe je nejmenˇs´ı. Pokud je takov´
ych cest v´ıc, vypiˇste libovolnou z nich.
6.4.2 Dostanete upravenou ˇsachovnici, na kter´e jsou nˇekter´a pol´ıˇcka vyˇr´ıznuta. Pak dostanete souˇradnice,
na kter´e je um´ıstˇen kr´
al a souˇradnici m´ısta, na kter´e se s kr´alem chcete dostat. Mus´ıte se ovˇsem
vyhnout vystˇriˇzen´
ym pol´ıˇck˚
um. Najdˇete nejkratˇs´ı cestu9 .
Na vstupu nejdˇr´ıve dostanete pozici kr´ale a pozici c´ılov´eho m´ısta (souˇradnice jsou vˇzdy 1 ≤
x, y ≤ 8, x a y jsou oddˇelen´e mezerou). Pot´e dostanete ˇc´ıslo N a na dalˇs´ıch N ˇr´adc´ıch souˇradnice
vystˇriˇzen´
ych pol´ıˇcek.
Vypiˇste souˇradnice vˇsech pol´ıˇcek, pˇres kter´e kr´al mus´ı j´ıt.
Pˇr´ıklad v´ystupu:
2 2
3 3
4 2
5 1
6 1
7 1
Pˇr´ıklad vstupu:
1 1
8 1
3
2 1
3 1
3 2
8
9
Z 23. roˇcn´ıku KSP
Kr´
al se m˚
uˇze pohybovat vˇsemi osmi smˇery
8
Download

Příklady (PDF, 15.10.2011)