- KSP
- Séria
- Akcie
- Ostatné
- Iné semináre
Korešpondenčný seminár z programovania
Príklady 1. kola zimnej časti 21. ročníka KSP-Z
Milé naše riešiteľky, mílí naši riešitelia,
Srdečne vás všetkých pozývame riešiť ďalší ročník Korešpondenčného seminára z programovania. To, že si čítate zadania kategórie Z, pravdepodobne znamená, že KSP idete riešiť po prvýkrát. Nezabudnite si poriadne prečítať pravidlá! Ak ste tak už urobili, určite viete, že najlepších spomedzi vás na jar pozveme na týždňové sústredenie. Skrátka, je sa na čo tešiť, je o čo bojovať, hor sa riešiť! Svoje riešenia nám posielajte najneskôr do 20. októbra 2003. Nezabudnite k nim priložiť známky v hodnote 15,- Sk.
KSPáci
- Zľavy na železniciach
- Zapálenie druidského ohňa
- Zadania písomky
- Záhrada víly Amálky
- Získajte body zadarmo!
1. Zľavy na železniciach
(15 bodov)
Ako ste si už určite všimli, každý rok sa menia ceny dopravy. Ani tento rok nie je výnimkou. Zákazníka často nalákajú hlavne zľavy, ktoré skoro každá spoločnosť ponúka. Väčšinou je týchto zliav čo najviac, aj keď väčšina ich je úplne na nič. Akcia, ktorú plánujú železnice na budúci rok, bude vyzerať nasledovne: Zverejní sa zoznam veľmi veľa rôznych zliav. Ako študenti máte nárok vybrať si pri kúpe lístku hocikoľko z nich, ktoré chcete použiť. Aby ste si však nemohli vybrať len tie výhodné, vami vybrané zľavy musia v zozname nasledovať za sebou.
Úloha
Napíšte program, ktorý načíta N – počet zliav a zoznam zliav. Zľava je kladné reálne číslo, ktorým sa násobí cena lístku. Nájdite úsek zliav, ktorý vám umožní získať najlepšiu možnú výslednú zľavu. (Ak je takýchto úsekov viac, stačí vypísať ľubovoľný jeden spomedzi nich.)
Príklad
Vstup
N=7
0.7 2 0.6 3 4 0.05 13
Výstup
Najlepšie je vybrať si úsek od 6 do 6.
(Budete platiť len 5% ceny lístku.)
2. Zapálenie druidského ohňa
(15 bodov)
Janko znova vyletel z algebry. Kráčal zahmlenou Bratislavou a bol nekonečne nešťastný. Zrazu sa zem zdvihla a udrela ho do čela. Janko si vo svojom žiali nevšimol malinu, čo rástla pri Matfyze. Keď sa prebral, okolo neho neboli budovy milovanej školy, ale stromy, tráva a nekonečná divočina. Na sebe mal rytierske brnenie a v ruke meč. Neveriacky naň hľadel. Po čase prišiel na to, že sa nachádza na území kráľa Richarda. Potreboval sa však dostať späť na opravný termín z algebry. Bezradne sa pohyboval lesom a premýšľal. Keď zdvihol pohľad, zistil, že stojí na čistine a uvidel skupinku starčekov. Mali dlhé brady a na nechtoch pleseň. "Keby to tak bol druidi..." pomyslel si Janko. Druidi boli mocní zaklínači, vedeli komunikovať s duchmi sveta a keby zapálili svoj čarovný oheň a dali sily dokopy, vedeli by napríklad aj dostať Janka späť do Bratislavy. Pomaly sa mu začala vracať nádej.
Samotný rituál bol jednoduchý – stačilo, aby sa druidi postavili do vrcholov pravidelného N-uholníka a Janko zapálil v jeho strede oheň. Druidi však boli starí a hrozne senilní. Každú chvíľu jeden z nich zabudol, že robia zaklínadlo a začal sa ponevierať po lúke. Janko je už zúfalý z toho čakania, preto by potreboval program, ktorý by mu oznamoval, či všetci druidi stoja správne.
Úloha
Na vstupe je číslo N a súradnice N bodov. Zistite, či sú to vrcholy pravidelného N-uholníka. Body nie sú nutne v správnom poradí a stred nemusí byť počiatkom sústavy súradníc.
Príklad
Vstup
N=5
1,8
2,2
6,7
3,5
4,4
Výstup
Nie.
3. Zadania písomky
(15 bodov)
Jeden profesor na jednej nemenovanej škole má svoje obľúbené číslo M, ktoré veľmi rád všade používa. Vždy pred písomkou zverejní čísla príkladov zo zbierky, z ktorých potom jeden vyberie na písomke. Študenti od svojich predchodcov vedia, že na písomke dá spomedzi zverejnených príkladov M-tý od konca. Majú však problém. Toľko čísel príkladov si nik z nich nezapamätá a nemajú si ich ani kam zapísať. (Nik z nich nemá zošít ani nič podobné – veď kto by si už len písal poznámky, že?) Jeden študent si ale nosí na hodiny počítač. Pomôžte mu napísať program, ktorému bude zadávať čísla, ktoré hovorí profesor a ktorý na konci vypíše, aký príklad dostanú na písomke.
Úloha
Váš program bude všetky informácie dostávať z klávesnice. Ako prvé dostane profesorovo obľúbené číslo M. Nasleduje veľa (kladných celých) čísel príkladov zo zbierky. Vstup je ukončený číslom 0. Vašou úlohou je zistiť číslo M-tého príkladu od konca. Najdôležitejšie je aby váš program potreboval čo najmenej pamäte. (Profesorovo obľúbené číslo je síce pomerne malé, ale príkladov môže zadať vééľmi veľa!)
Príklad
Vstup
M=6
5 1 8 56 7 14 23 47 11 4 58 32 0
Výstup
23
4. Záhrada víly Amálky
(15 bodov)
Víla Amálka má v záhrade onbloň. (Strom podobný tybloni.) Onbloň je veľmi zaujímavý strom. Ono to vlastne ani nie je strom, je to iba N onbĺk (očíslovaných od 1 do N), medzi ktorými je M vetvičiek. Každá vetvička spája práve dva onblká a naviac platí, že keby po strome behala veverička, vedela by po týchto vetvičkách prebehnúť medzi ľubovoľnými dvomi onblkami. Na každej onbloni rastú onblká dvoch farieb – modrej a červenej, pričom modrých onbĺk je vždy viac ako červených. Okrem toho, že je onbloň veľmi vzácna, je o nej známe iba to, že vyrastie iba zo semienok modrého onblka.
Víla Amálka nikoho nepustí do svojej záhrady, ale profesorovi Indigovi sľúbila, že mu daruje jedno onblko, ktorého číslo jej povie. Okrem toho je ochotná odpovedať na otázky, či majú dve onblká, ktoré sú na jednej vetve, rovnakú farbu (1 – majú rovnakú farbu, 0 – nemajú).
Profesor Indigo by si chcel vypestovať vlastnú onbloň. Nechce nič nechať na náhodu a preto vás poprosil, aby ste mu napísali program. Ten by mu mal radiť, aké otázky má klásť a na koniec, keď už si bude istý, ktoré onblko si má profesor vybrať.
Snažte sa, aby ste nekládli príliš veľa otázok, lebo si víla Amálka všetko rozmyslí a žiadne onblko nebude.
Úloha
Na vstupe sú čísla N, M – počet onbĺk a počet vetiev onblone. Nasleduje M dvojíc onbĺk, medzi ktorými vedú vetvičky.
Váš program sa má uživateľa (Amálky) pýtať otázky, t.j. vždy vypíše dvojicu čísel onbĺk, medzi ktorými vedie vetvička a načíta odpoveď (0 alebo 1 podľa toho, či sa farby príslušných onbĺk rovnajú). Keď už si je program istý, že niektoré onblko je modré, vypíše jeho číslo a skončí.
Najdôležitejšie je aby váš program položil čo najmenej otázok, druhým kritériom hodnotenia bude čas behu vášho programu.
Príklad
Vstup
N=7, M=7
1 2 1 5 1 3 5 3 4 3 3 6 6 7
Vstup
program: 3 6? 0 (rôzne) program: 3 4? 0 (rôzne) program: 3 1? 0 (rôzne) program: 3 5? 1 (rovnaké) program: 6 7? 1 (rovnaké) program: chcem onblko 6
5. Získajte body zadarmo!
(15 bodov)
Zadanie tejto úlohy sa nikomu nechcelo vymýšľať. Najskôr sme vám chceli prideliť body náhodne, ale to by nebolo fér. A tak sme situáciu vyriešili nasledovne: Zverejníme vám funkciu BODY. Tá berie ako vstup 32-bitové celé číslo so znamienkom a vráti celé číslo od 0 do 15. Vašou úlohou je poslať nám vstup pre túto funkciu. Hodnota, ktorú funkcia vráti pre váš vstup, bude zároveň počet bodov, ktorý za túto úlohu získate. A nezabudnite nám napísať aj to, ako ste na váš vstup prišli, lebo môžete pár z týchto ľahko získaných bodov ľahko stratiť! Funkciu uvádzame v jazyku Pascal, dúfame, že riešitelia používajúci iné programovacie jazyky jej zápisu budú rozumieť.Kód funkcie BODY (a pomocných funkcií):
function lala(a,b : longint) : longint;
begin if (a*b>0) then lala:=lala(a-1,b-1) else lala:=b-a; end;
function huhu(a,b : longint) : longint;
begin if (a<=b) then huhu:=0 else huhu:=lala(b+1042,a+1047)-5; end;
function dodo(a,b : longint) : boolean;
var i : longint;
begin
if (a=0) then begin dodo:=true; exit; end;
if (huhu(b,a)<>0) then begin dodo:=false; exit; end;
for i:=1 to b-huhu(b,a)-1 do
if dodo(a-i,b) then
begin dodo:=(lala(huhu(b,a)+a,huhu(a,b)+b)<>0); exit; end;
dodo:=dodo(a-b,b);
end;
function zuzu(a : longint) : boolean;
var i,j : longint;
begin
j:=0;
for i:=a+huhu(a,a) downto 2 do if dodo(a,i) then
if (j>0) then begin zuzu:=dodo(4+7*(100000 div a),7); exit; end else j:=i;
zuzu:=(j>0);
end;
function BODY(VSTUP : longint) : longint;
var a,b : integer;
begin
a:=2; b:=0;
if ((VSTUP<2) or (VSTUP>2000000000)) then begin BODY:=0; exit; end;
while not dodo(VSTUP,a) do repeat inc(a); until zuzu(a);
while dodo(VSTUP,a) do begin VSTUP:=VSTUP div a; inc(b); end;
if (a<5) then begin BODY:=a; exit; end;
if (VSTUP=1) then inc(b,2) else begin
VSTUP:=(VSTUP+3) div 2; b:=1;
while (VSTUP>0) do begin dec(VSTUP); b:=(5*b) mod 15; end;
end;
BODY:=b;
end;
© KSP, 18. september 2003, webmaster
