Matematická olympiáda – kategorie P

Zadání úloh školního kola 53. ročníku

Řešení každého příkladu musí obsahovat podrobný popis použitého algoritmu, zdůvodnění jeho správnosti a diskusi o efektivitě zvoleného řešení (tzn. posouzení časových a paměťových nároků programu).

V úlohách P-I-1, P-I-2 a P-I-3 je třeba k řešení připojit odladěný program zapsaný v jazyce Pascal, C nebo C++. Program se odevzdává v písemné formě (jeho výpis je tedy součástí řešení) i na disketě, aby bylo možné otestovat jeho funkčnost. Slovní popis řešení musí být ovšem jasný a srozumitelný, aniž by bylo nutno nahlédnout do zdrojového textu programu. V úloze P-I-4 je nutnou součástí řešení program pro registrový počítač.

Řešení úloh domácího kola MO kategorie P vypracujte a odevzdejte nejpozději do 15.11.2003. Vzorová řešení úloh naleznete po tomto datu na Internetu na adrese http://mo.mff.cuni.cz. Na stejném místě jsou stále k dispozici veškeré aktuální informace o soutěži a také archív soutěžních úloh a výsledků z minulých ročníků.

P-I-1 Síť

Firma Připojse poskytovala svým zákazníkům velmi spolehlivé připojení na Internet. Vybudovala si pro tento účel svou vlastní datovou síť spojující několik největších měst v zemi. Síť se skládá z uzlů umístěných ve městech a z linek, které vedou mezi městy. Každá linka spojuje některé dva uzly. Síť měla tu vlastnost, že v případě přerušení jedné libovolné linky zůstala plně funkční, tzn. zbývající linky zajišťovaly propojení mezi každými dvěma městy.

Nedávno se firma rozhodla rozšířit své služby i pro zákazníky v dalších městech. Zřídila proto řadu nových linek, pomocí nichž byla tato města připojena k již existující síti. Nyní by ve firmě potřebovali vědět, zda je jejich síť stále ještě dostatečně spolehlivá, tj. zda i nadále existuje možnost spojení mezi každými dvěma městy i v případě výpadku jedné libovolné linky.

Soutěžní úloha

Napište program, který přečte ze vstupu seznam uzlů a linek tvořících síť a zjistí, zda má síť tu vlastnost, že pokud se libovolná jedna linka přeruší, všechna města v síti mohou mezi sebou nadále komunikovat pomocí zbývajících linek.

Formát vstupu

První řádek vstupního textového souboru sit.in obsahuje dvě kladná celá čísla n a m, kde n je počet měst propojených v síti a m je počet linek (n<=100). Pro jednoduchost jsou města označena čísly 1,2,...,n. Na každém z následujících m řádků vstupního souboru jsou zapsána dvě čísla, která určují města spojená linkou.

Můžete předpokládat, že je možné prostřednictvím exitujících linek komunikovat mezi každými dvěma městy v síti a že žádné dvě linky nespojují stejnou dvojici měst.

Formát výstupu

Výstupní textový soubor sit.out obsahuje jediný řádek, na němž je zapsáno slovo "ANO", jestliže lze v síti zadané na vstupu komunikovat mezi libovolnými dvěma městy i po přerušení libovolné jedné linky, a slovo "NE", pokud síť tuto vlastnost nemá.

Příklad 1

Soubor sit.in:
5 6 1 2 2 3 3 1 3 4 4 5 2 5 Soubor sit.out:
ANO

Příklad 2

Soubor sit.in:
4 4 1 2 2 3 3 1 3 4 Soubor sit.out:
NE Pokud se přeruší linka mezi městy 3 a 4, tato města spolu nebudou moci komunikovat.

P-I-2 Attosoft

Vašek si založil maličkou programátorskou firmu, kterou nazval příznačně AttoSoft (Mikro je 10^-6, nano je 10^-9, piko je 10^-12, femto je 10^-15, atto je 10^-18.) Nedávno se mu konečně podařilo získat prvního klienta. Ten mu dal za úkol napsat N jednoduchých programů.

Vašek je však líný sám programovat, a proto si na tuto práci najal N programátorů. Když ráno všichni přišli do práce, ukázalo se, že každý z nich umí naprogramovat pouze jeden z potřebných programů. Naštěstí každý z požadovaných programů uměl někdo z nich naprogramovat, takže se mohli pustit do práce. Objevil se však další problém. Firma AttoSoft vlastní pouze jeden počítač a na něm může v jednom okamžiku pracovat jen jeden programátor.

Vašek si uvědomil, že je důležité zvolit správné pořadí, v němž budou jednotliví programátoři pracovat u počítače. Podle podepsané smlouvy totiž programátory neplatí za vykonanou práci. Každého programátora platí za čas, který uplyne od začátku práce na celé zakázce až do okamžiku, kdy tento programátor dokončí svůj program. Vašek o každém z programátorů ví, kolik mu musí zaplatit za jednu hodinu a jak dlouho mu napsání jeho programu bude trvat. Pomozte mu zjistit, v jakém pořadí má poslat programátory pracovat na počítači, aby jim dohromady mohl zaplatit co nejméně.

Příklad

Mějme tři programátory A, B, C. Programátor A chce 100 Kč za hodinu a na svůj program potřebuje 2 hodiny. B dostane 20 Kč za hodinu a potřebuje na práci 5 hodin času. Programátor C požaduje 500 Kč za hodinu a bude pracovat 20 hodin.

Pokud by programovali v pořadí A, B, C, musel by Vašek zaplatit programátorovi A za 2 hodiny, programátorovi B za 7 hodin a programátorovi C za 27 hodin, což by ho přišlo celkově na 13 840 Kč. Jestliže budou programovat v pořadí C, B, A, bude to Vaška stát jenom 500 * 20 + 20 * 25 + 100 * 27 = 13 200 Kč, takže toto pořadí je výhodnější. (Ale není to ještě nejlepší možné řešení.)

Soutěžní úloha

Napište program, který přečte ze vstupu počet programátorů, jejich hodinové mzdy a časy potřebné na jejich práci a spočítá, v jakém pořadí má Vašek nechat programátory pracovat, aby jim dohromady zaplatil nejmenší možnou částku. Má-li úloha více různých řešení, program najde a vypíše jedno libovolné z nich.

Formát vstupu

První řádek vstupního textového souboru attosoft.in obsahuje jedno kladné celé číslo N (1<=N<=10 000), které udává počet programátorů. Následuje dalších N řádků; i-tý z nich obsahuje dvě celá čísla m_i, t_i (0<m_i, t_i<=30 000), kde m_i je hodinová mzda i-tého programátora a t_i je čas v hodinách, který i-tý programátor potřebuje na napsání svého programu.

Formát výstupu

Výstupní textový soubor attosoft.out obsahuje N řádků. Na j-tém z nich je zapsáno jedno celé číslo z rozmezí od 1 do N - číslo programátora, který bude programovat jako j-tý v pořadí.

Příklad

Soubor attosoft.in:
3 100 2 20 5 500 20 Soubor attosoft.out:
1 3 2 Vašek zaplatí 11 740 Kč.

P-I-3 Součty

Je dáno pole A[1..N] celých čísel. Napište program, který bude umět co nejrychleji provádět následující příkazy:

• změň hodnotu A[x] na y
• vypiš součet prvků A[x]+A[x+1]+...+A[y]

Váš program si na začátku výpočtu může pole A v rozumném čase vhodně předzpracovat.

Formát vstupu

Vstupní textový soubor soucty.in obsahuje předem neznámý počet řádků. Na prvním řádku souboru je uvedeno jediné celé číslo N (1<=N<=2 000). Druhý řádek obsahuje původní hodnoty uložené v poli A - celá čísla a₁, a₂, ..., a_N oddělená mezerami (0<=a_i<=1 000 000).

Vstupní soubor pokračuje několika řádky s příkazy, z nichž každý má některý z následujících tvarů:

• 1 x y (1<=x<=N, 0<=y<=1 000 000)
  změň hodnotu A[x] na y
• 2 x y (1<=x<=y<=N)
  vypiš hodnotu A[x]+...+A[y]

Vstup je ukončen řádkem obsahujícím jediné číslo 0.

Formát výstupu

Program musí vykonat všechny příkazy v pořadí, ve kterém jsou uvedeny na vstupu. Pro každý příkaz na vypsání součtu nějakých prvků pole musí do výstupního souboru soucty.out zapsat jeden řádek obsahující jedno celé číslo - součet příslušných prvků pole A v daném okamžiku.

Příklad

Soubor soucty.in:
14 1 4 3 1 1 3 1 1 3 1 4 1 1 1 2 1 14 2 3 6 1 2 0 2 3 6 1 3 0 2 3 6 0 Soubor soucty.out:
26 8 8 5

P-I-4 Registrový počítač

V této úloze se budeme zabývat registrovými počítači. Registr je něco podobného jako proměnná. V registru může být uloženo libovolně velké nezáporné celé číslo. Na rozdíl od proměnných, které mezi sebou můžeme sčítat, odčítat a násobit, s registrem lze provádět jen tři jednoduché operace: zvětšit jeho obsah o 1, zmenšit jeho obsah o 1 (pokud se pokusíme zmenšit obsah registru obsahujícího hodnotu 0, zůstane v něm 0) a otestovat registr, zda je v něm 0.

Registrový počítač může používat neomezený počet registrů označených R₀, R₁, R₂, atd. Vedle registrů má k dispozici ještě konečně velkou pomocnou paměť.

Program pro registrový počítač budeme zapisovat v jazyce velmi podobném programovacímu jazyku Pascal. Programovací jazyk registrového počítače bude oproti Pascalu rozšířen například o příkazy pro práci s registry, naopak některé příkazy z Pascalu v něm budou zakázány.

Registrový počítač bude řešit úlohy následujícího typu: počítač dostane na vstupu zadáno slovo (řetězec písmen) a po nějakém čase odpoví, zda je toto slovo správné nebo špatné. Aby nám mohl odpovědět, zavedeme do programovacího jazyka speciální příkazy Accept a Reject. Jakmile se během výpočtu vykoná příkaz Accept, vstupní slovo je správné a výpočet končí. Jestliže se provede příkaz Reject, slovo je špatné a výpočet končí. Pokud se výpočet zacyklí nebo pokud skončí, aniž by se provedl příkaz Accept nebo Reject, zadané vstupní slovo je rovněž špatné.

Příkaz "přičti 1 k obsahu registru R" budeme značit Inc(R), "odečti 1 od obsahu registru R" budeme značit Dec(R). Výraz Zero(R) je pravdivý, jestliže je v registru R nula, v opačném případě je nepravdivý. Na začátku výpočtu jsou ve všech registrech nuly.

V každém programu můžeme použít jen konečně mnoho registrů. Kromě nich můžeme použít už jen konstantní počet pomocných proměnných typu byte (taková proměnná obsahuje jedno celé číslo z rozmezí od 0 do 255 a nemůžeme tedy používat pole!) a jednu speciální proměnnou vstup typu char. Obsah proměnné vstup lze měnit pouze provedením příkazu Read(vstup). Jestliže počítač ještě nedočetl vstupní slovo, příkaz Read(vstup) z něj přečte jedno další písmeno a uloží ho do proměnné vstup. Pokud počítač již vstupní slovo dočetl, příkaz Read(vstup) uloží do proměnné vstup speciální znak $.

Jelikož registrový počítač má kromě registrů jen konečně mnoho paměti, nemůže si dovolit používat rekurzi (neměl by si kde pamatovat návratové adresy). My pro jistotu úplně zakážeme definovat a používat v programu procedury a funkce. Zakázáno je i volání všech standardních procedur a funkcí jazyka Pascal. V aritmetických výrazech lze používat pouze proměnné (tedy ne registry!), celočíselné konstanty, celočíselné operátory +, -, *, div, mod a závorky. V podmínkách se mohou používat výrazy Zero(R_i), běžné relační operátory (<, <=, ...), logické spojky a závorky.

Z klíčových slov jazyka Pascal jsou tedy v programovacím jazyku registrového počítače povolena pouze následující: var, begin, end, if, then, else, case, of, while, do, repeat, until, for, to, downto, div, mod, and, or, not a xor.

Příklad 1

Napište program pro registrový počítač, který bude řešit následující úlohu. Na vstupu je zadán řetězec písmen a, b, c. Nechť A označuje počet těch písmen a ve vstupním řetězci, za kterými už není žádné c. Podobně nechť B je počet b, za nimiž není žádné c. Počítač má vstupní řetězec označit za správný právě tehdy, když A=B.

Řešení

V registru R₁ si budeme pamatovat aktuální hodnotu A, v registru R₂ hodnotu B. Pokaždé, když přečteme ze vstupu písmeno c, oba registry vynulujeme. Na konci výpočtu jednoduše porovnáme hodnoty uložené v registrech. Rozmyslete si, že by stačilo použít jen jeden registr (v němž bychom měli hodnotu |A-B|).

var vstup:char; begin Read(vstup); while (vstup<>'$') do begin if (vstup='a') then Inc(R₁); if (vstup='b') then Inc(R₂); if (vstup='c') then begin while not Zero(R₁) do Dec(R₁); while not Zero(R₂) do Dec(R₂); end; Read(vstup); end; while not Zero(R₁) do begin Dec(R₁); if (Zero(R₂)) then Reject; Dec(R₂); end; if Zero(R₂) then Accept; end.

Příklad 2

Napište program pro registrový počítač, který bude řešit následující úlohu. Na vstupu bude zadán řetězec písmen a. Počítač ho označí za správný právě tehdy, když je jeho délka mocninou tří.

Řešení

Přečteme vstupní slovo, přičemž si do R₁ uložíme jeho délku. Potřebujeme zjistit, zda je to mocnina tří. Uloženou hodnotu proto budeme dělit třemi, dokud to půjde. Jestliže nakonec dostaneme podíl 0 a zbytek 1, původní číslo bylo mocninou tří, jinak nebylo.

var vstup:char; zbytek:byte; begin Read(vstup); while (vstup<>'$') do begin Inc(R₁); Read(vstup); end; if Zero(R₁) then Reject; while true do begin zbytek:=0; while not Zero(R₁) do begin Dec(R₁); zbytek:=(zbytek+1) mod 3; if (zbytek=0) then Inc(R₂); end; if (Zero(R₂) and (zbytek=1)) then Accept; if (zbytek<>0) then Reject; while not Zero(R₂) do begin Dec(R₂); Inc(R₁); end; end; end.

Soutěžní úloha

Napište program pro registrový počítač, který bude řešit následující úlohu. Vstupem programu bude řetězec písmen a, b, c, d. Počítač ho označí jako správný právě tehdy, jestliže obsahuje nejvíce písmen a (tzn. počet písmen a obsažených ve vstupním slově je větší než počet písmen b, zároveň počet písmen a je větší než počet písmen c a zároveň také počet písmen a je větší než počet písmen d).

Například vstupní slovo baacd je tedy správné, zatímco vstupní slovo baacdbb je špatné (neboť obsahuje více písmen b než a) a ani vstup ac není správný (neboť písmen a a c je v něm stejný počet).

Základním kritériem hodnocení kvality navrženého programu bude počet registrů, které váš program používá. Pokuste se napsat program, kterému jich stačí co nejméně. Druhým kritériem pak bude doba výpočtu programu.