• KSP
• • Home
  • Novinky
  • Pravidlá
  • FAQ
  • Kuchárka
  • Liaheň
• Séria
• • Zadania a výsledky
  • Odovzdaj riešenie
  • Ideálne riešenie
  • Archív zadaní
  • Zbierka
• Akcie
• • Sústredenia
  • Proboje
  • Akadémia a klub
  • LTT
• Ostatné
• • Podporte nás
    2% z daní
  • Organizátori
  • Sponzori
  • Kontakt
• Iné semináre
• • Trojsten
  • KMS
  • FKS
  • Iné súťaže

Korešpondenčný seminár z programovania

Priklady 3. kola

Mili nasi riesitelia,

ani sme sa nenazdali, a je tu tretie, posledne kolo KSP-Z. K tretiemu kolu, ako ku kazdemu inemu, patria zadania. Vase riesenia nam posielajte do 26. aprila 1999 spolu so znamkami.

Spolu so zadaniami vam posielame aj zaujemku o spolocny splav seminarov BKMS, FKS a KSP. Vsetky informacie sa dozviete na prilozenom letaciku, ak sa vam napad splavu paci, ohlaste sa.

1. ZY nevergreeny
2. Zakerny rozvrh
3. Zamaskuje Ferdo zamestnanie?
4. Zazvorove pivo II
5. Znizovanie zadlzenosti

Isto viete, ze evergreen je piesen, ktora zostava popularna aj dlhy cas po svojom vzniku. Naopak nevergreen je taka piesen, ktora este nikdy nebola skutocnym hitom - ci uz preto, ze je uplne nova, alebo preto, ze jej kvalita je prilis nizka (resp. vysoka) na to, aby sa zapacila davom. ZY Radio je rozhlasova stanica urcena pre narocnych posluchacov, ktora vysiela iba ZY nevergreeny. To su take nevergreeny, ktorych meno sa sklada iba z pismen Z a Y.

Uloha: Napiste program, ktory pomoze pracovnikom ZY Radia spolahlivo urcovat, ktora piesen je ZY nevergreen. Program bude v nekonecnom cykle prijimat spravy od uzivatelov a bude na ne vhodnym sposobom reagovat. Spravy su dvoch typov: Hit m a Skontroluj m, kde m je retazec obsahujuci iba velke pismena.

Sprava typu Hit m oznamuje programu, ze piesen s nazvom m sa stala hitom a teda uz nikdy nemoze byt vysielana na stanici ZY Radio.

Sprava typu Skontroluj m znamena, ze niektory redaktor chce pustit piesen s nazvom m a potrebuje vediet, ci tato piesen je ZY nevergreen, t.j. ci je nazov pozostava len z pismen Z a Y a ci doteraz nebola zaevidovana pomocou spravy Hit m.

Priklad:

> Hit ZYZY
> Skontroluj ABC
ABC nie je nevergreen
> Skontroluj ZZZ
ZZZ je nevergreen
> Hit ZZZ
> Hit AAA
> Skontroluj ZZZ
ZZZ nie je nevergreen

Ako iste vsetci viete, Tomas je velmi snazivy student, a preto hned po zverejneni rozvrhov sa rozhodol zapisat si co najviac prednasok. Naraz moze byt najviac na jednej prednaske a kazdu zapisanu prednasku musi absolvovat celu (teda casy prednasok sa nesmu prekryvat). Ako tak pridaval a uberal prednasky zo svojho rozvrhu, objavil sa skriatok VIL a povedal: "To mas, Tomas, jednoduche. Prednasky si budes zapisovat jednu po druhej. Ako prvu si pekne zapises tu, ktora skonci najskor. Potom si vzdy zapis taku prednasku, ktora sa ti neprekryva so ziadnou uz zapisanou, a ktora konci najskor. Ak je takych prednasok viac (nutne musia koncit v rovnakom case), mozes si vybrat lubovolnu z nich. Ked si nebudes moct zapisat ziadnu dalsiu prednasku, vedz, ze ich mas zapisanych najviac, ako sa len da."

Uloha: Ak si myslite, ze VIL poradil Tomasovi dobre, napiste co najefektivnejsi program podla jeho navodu. V tomto pripade zdovodnite (resp. pokuste sa dokazat), ze Tomas si podla VILovej rady skutocne zapise maximalny mozny pocet prednasok. V opacnom pripade navrhnite svoj vlastny sposob riesenia, naprogramujte ho a nezabudnite zdovodnit, preco sa VIL myli a zdokumentovat to na vhodnom kontrapriklade.

Vas program by mal nacitat pocet prednasok N, tyzdenny rozvrh skladajuci sa z N riadkov tvaru

a vypise jeden mozny maximalny zoznam prednasok, ktore si moze Tomas zapisat. Ale pozor! Ak Tomas zisti, ze nema najvyssi mozny pocet prednasok, psychicky sa zruti a mate ho na svedomi.

Priklad:
Vstup:
3 prednasky:
PON 07:20-09:45 Kognitivna psychologia
UTO 09:30-10:00 Teoria hier
PON 09:00-10:35 Programovanie

Vystup:
Tomas si moze zapisat max. 2 prednasky.
PON 07:20-09:45 Kognitivna psychologia
UTO 09:30-10:00 Teoria hier

Agent Ferdo pracuje uz niekolko desatroci pre SIS (Slovensku informaticku spolocnost) na istej nemenovanej americkej univerzite. Po dlhe roky sa mu darilo plnit ulohy - ziskavat technicke plany najnovsich algoritmov. V sucasnosti je vsak jeho pozicia ohrozena - tajna sluzba ho odhalila a vedie ho v databaze pod cislom i. Ferdo je jeden z najlepsich agentov svojho druhu a dokaze sa dostat na kratky cas aj k pocitacom tajnej sluzby. Lenze na to, aby sa dal vymazat niektory agent z databazy, je potrebne zadat jeho cislo zakodovane a na kodovanie sa pouziva velmi prefikany kodovaci algoritmus.

Algoritmus zakoduje kazde cislo ako k-ticu prirodzenych cisel v rozsahu od 1 po n. Pre cislo i sa prislusna k-tica najde takto: Zostrojime vsetky k-tice z cisel 1,..., n a usporiadame ich lexikograficky (t.j. usporiadame ich najprv podla prvej cifry; tie, ktore maju prvu cifru rovnaku, usporiadame dalej podla druhej cifry atd.). Z takto vzniknuteho zoznamu potom vyskrtame vsetky k-tice, v ktorych sa nejake cislo opakuje. Kodom cisla i bude i-ta polozka vysledneho zoznamu (polozky v zozname cislujeme od 1).

Uloha: Pomozte Ferdovi a napiste program, ktory nacita cisla n, k a i a vypise kod cisla i. Snazte sa, aby bol vas program co najrychlejsi, lebo cisla n, k a i mozu byt aj pomerne velke (rozhodne nie je velmi efektivne vytvarat zoznam vsetkych k-tic z cisel 1 az n).

Priklad:
Vstup:
n = 4, k = 3, i = 3

Vystup:
Kod je 1 3 2.

Zazvorove pivo II sa stale nechava rozvazat zavoznikom Zachariasom. Je vyrobene vylepsenou recepturou a je na to velmi pysne. Prave sa nechava predavat v meste A (a mimochodom vsetkym vyborne chuti), ale chcelo by sa dostat na velkolepy festival piva do mesta B. Zazvorove pivo II si brusi zuby na hlavnu cenu - zlaty krigel a skromne uznava, ze jeho vyhliadky su ruzove. Teda ak sa tam dostane. Ma to totiz hacik - zdrazelo myto. Rovnako ako v casoch, ked sa pomocou Zachariasa rozvazalo Zazvorove pivo I, aj teraz treba pri kazdom vstupe so Zachariasom a vozom do hocijakeho mesta zaplatit myto. Ale teraz si kazde mesto stanovilo vlastnu vysku myta. A tak si Zazvorove pivo II zadumane spliecha a premysla, kade ist, aby cesta vysla co najlacnejsie.

Uloha: Na vstupe mate zadane prirodzene cislo N>1 urcujuce pocet miest (mesta su cislovane cislami 1 az N) a pre kazde mesto i je dana vyska myta v[i]>0 v tomto meste. Dalej su zadane cisla miest A a B a cislo M urcujuce pocet ciest medzi mestami. Kazda z M ciest je zadana dvojicou cisel miest, medzi ktorymi vedie. Zistite, ci sa Zazvorove pivo II moze dostat z mesta A do mesta B. Ak ano, vypiste trasu, veducu z A do B taku, aby bol sucet myt v mestach, cez ktore trasa vedie, najmensi mozny. Ak je takychto tras viac, vypiste lubovolnu.

Priklad:

Vstup:
N=7,
myto po rade: 1, 5, 8, 2, 10, 1, 3
A=3, B=4
M=6
cesty:
1 6
2 3
2 7
4 7
4 5
3 5

Vysledkom je trasa iduca cez mesta 3, 2, 7 a 4, na ktorej treba zaplatit myto vo vyske 5+3+2=10. Existuje este trasa 3, 5, 4, ale na nej treba zaplatit myto vo vyske 12.

Nase hospodarstvo je vo velmi zlom stave. Hadam ani nieto podniku, ktory by nemal nejake dlhy. A nie je zriedkavy ani pripad, ze jeden podnik sucasne niektorym podnikom dlhuje a ine podniky su naopak jeho dlznikmi. Ak podnik X dlzi podniku Y sumu k korun, budeme to zapisovat ako d(X,Y)=k.

Skupina ekonomickych expertov vymyslela sposob ako celkovu zadlzenost znizovat. Navrhuju zaviest pouzivanie zmluvy o prevode dlhu. Ak pre nejake podniky X, Y a Z su dlhy d(X,Y) a d(Y,Z) obidva aspon k korun, potom podniky X a Y mozu uzavriet zmluvu o prevode dlhu velkosti k, na zaklade ktorej sa dlhy d(X,Y) a d(Y,Z) obidva znizia o k korun a naopak dlh d(X,Z) sa o k korun zvysi (pripadne vznikne novy dlh). Ak vznikne tymto sposobom dlh typu d(X,X), automaticky zanika. Takymito zmluvami medzi podnikmi je mozne celkovu zadlzenost postupne znizovat dovtedy, kym uz sa ziadna zmluva o prevode dlhu nebude dat uzavriet. Otazkou zostava, aky bude vysledok.

Uloha: Napiste program, ktory nacita pocet podnikov N, pocet dlhov medzi podnikmi M a jednotlive dlhy. Kazdy dlh je zadany ako trojica cisel X, Y a k (kde d(X,Y)=k). Podniky su cislovane cislami 1, 2, ... N. Vas program ma vypisat zoznam dlhov, ktory je jednym z moznych vysledkov pouzivania zmluvy o prevode. Vas zoznam teda musi byt taky, ze mohol vzniknut postupnym uzatvaranim zmluv a sucasne uz nie je mozne uzavriet ziadnu dalsiu zmluvu.

Priklad:
Vstup:
N=4, M=4
Dlhy:
1 2 30
2 3 40
2 4 10
4 1 10

Vystup:
1 2 20
2 3 20