!we are sorry but this page is in czech only!

Zadání úloh lokálního kola FEL ČVUT 1997

Katedra počítačů ČVUT FEL & Czech ACM Chapter
Soutěž v programování 1997

Problém A - Hacker
Problém B - Opraváři
Problém C - Sčítačka
Problém D - Tlumočníci
Problém E - Kdo za to může
Problém F - Most přes řeku
Problém G - Area

Problém A

Hacker

Římský imperátor Caesar používal při doručování tajných zpráv jednoduchou, ale účinnou šifru. Uspořádal znaky abecedy do kruhu a obě komunikující strany si dohodly bezpečnou cestou šifrovací klíč -- celé kladné číslo N. Zprávu zašifroval tak, že každý znak zprávy nahradil znakem, který se na šifrovacím kruhu nalézal N znaků za znakem původním.

Šéf egyptské kontrarozvědky Sinuhat však nelenil, najal nejlepší hackery a odborníky přes šifry a zaměstnal je luštěním. Hackeři časem pochopili šifrovací algoritmus, ale bez znalosti šifrovacích klíčů danou zprávu stejně nemohli rozluštit.

Hlavní analytik Phodeysiss, fanda do počítačů, však přislíbil Sinuhatu, že dokáže určit, zda-li zpráva obsahuje nějaký vzorek. Prohlásil, že ke zjištění přítomnosti vzorku v zašifrované zprávě použije hrubou výpočetní sílu posledního modelu multiprocesorového počítače eta-zeta-upsilon-beta-epsilon-XII firmy M-omega-tau-omega-rho-omega-lambda-alpha, vybaveného MMMMXCVI procesory typu otrok organizovanými do pyramidy s dvouřadým kuličkovým matematickým koprocesorem a externí papyrusovou pamětí.

Vaším úkolem je navrhnout pro Phodeysisse algoritmus hledání vzorku v zašifrované zprávě.

Specifikace vstupu

Vstup se skládá z N zadání. První řádek obsahuje celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání je tvořeno dvojicí řádků definující jeden dotaz na výskyt vzorku ve zprávě. První řádek dvojice obsahuje hledaný nezašifrovaný vzorek, druhý řádek obsahuje zašifrovanou zprávu, oba řádky jsou z obou stran ohraničeny uvozovkami. Prohledávaná zpráva i hledaný vzorek obsahují pouze znaky velké abecedy a mezery. Šifrovací kruh obsahuje znaky v tomto pořadí: QWERTYUIOPASDFGHJKLZXCVBNM. Mezera je umístěna na kruhu mezi M a Q.

Hledané vzorky nejsou delší než 1000 znaků, délka zprávy není omezena.

Specifikace výstupu

Pro každé zadání musí výstup obsahovat právě jeden řádek textu, který bude obsahovat větu Vzorek se nevyskytuje ve zprave., pokud pro žádný šifrovací klíč zpráva neobsahuje hledaný vzorek, nebo větu Vzorek se muze vyskytovat ve zprave., pokud existuje alespoň jeden šifrovací klíč takový, že zašifrováním vzorku získáme část zprávy.

Příklad vstupu

2
"BUDE VALKA"
"G TFWMOGTWNDXZD"
"ACM CONTEST"
"HPUDPPWHDIPDFPPER"

Příklad výstupu

Vzorek se muze vyskytovat ve zprave.
Vzorek se nevyskytuje ve zprave.

Problém B

Opraváři

Firma Šťoural s.r.o. se již dlouhou dobu zabývá drobnými opravami porouchaných počítačů. Obvyklý pracovní den začíná tím, že pověřený pracovník přiveze počítače určené k opravě. Do opravy se pustí současně několik opravářů. Jeden opravář může v daném okamžiku opravovat nejvýše jeden počítač, na opravě jednoho počítače může pracovat nejvýše jeden opravář. Jakmile nějaký opravář dokončí práci, začne ihned opravovat další počítač. Není-li již žádný počítač k dispozici, opravář nemá další pracovní povinnosti.

Různé opravy mohou trvat různou dobu. Strojový čas opravovaných počítačů je velice drahý, protože jde o mimořádně výkonné počítače. Ředitel firmy pan Šťoural chce optimalizovat pořadí provádění jednotlivých oprav a rozdělení oprav mezi opraváře tak, aby byl ušlý zisk co možná nejmenší.

Navrhněte algoritmus, který určí optimální pořadí provádění oprav jednotlivými opraváři a vyjádří zisk ušlý odstavením počítačů při čekání na opravu a během opravy.

Specifikace vstupu

Vstup se skládá z N zadání. První řádek vstupního souboru obsahuje celé kladné číslo N. Dále následují jednotlivá zadání, každé tvořené jediným řádkem. Ten obsahuje celá kladná čísla M, K, A₁, A₂, ..., A_K, navzájem oddělená mezerami, mající tento význam: M je počet opravářů, kteří daný den opravují, K je počet opravovaných počítačů, A₁ až A_K jsou doby potřebné na opravu jednotlivých počítačů v daném dnu měřeno na minuty.

Pro vstupní hodnoty platí tato omezení: A_i < 1000, M < 1000, K < 1000.

Specifikace výstupu

Pro každé zadání musí výstup obsahovat právě jeden řádek textu, na kterém bude věta Minimalni usly zisk je XX minut strojoveho casu., kde za XX se dosadí vypočtený minimální nutný počet minut.

Příklad vstupu

2
6 4 29 75 12 18
2 4 13 25 12 25

Příklad výstupu

Minimalni usly zisk je 134 minut strojoveho casu.
Minimalni usly zisk je 100 minut strojoveho casu.

Problém C

Sčítačka

Součástí nového, dlouho očekávaného rozsáhlého softwareového projektu s pracovním názvem Babacus-Calculus 97 je i modul Universal Super Engenious Integer Numbers Adder. Úkolem tohoto modulu je sčítání libovolného počtu celých čísel libovolné velikosti. Na navržení efektivního algoritmu vypsala významná zahraniční firma Babacus Systems Engineering Inc. výběrové řízení, v němž zvítězila skupina studentů katedry počítačů ČVUT FEL, tvořící také tým organizátorů programátorské soutěže, které se právě účastníte. Protože se ale oproti očekávání tento tým musí zabývat některými jinými problémy typu nefunkční name server, stojíte před úkolem navrhnout zjednodušenou variantu algoritmu a napsat program, který dokáže sečíst 2 až 10 nezáporných celých čísel z intervalu <0; 10²⁵⁰).

Specifikace vstupu

Vstup se skládá z N zadání. První řádek obsahuje celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání začíná jedním řádkem, který obsahuje počet čísel určených k sečtení. Čísel není více než deset a vždy jsou alespoň dvě. Dále následují jednotlivá čísla. Každé z čísel je na samostatném řádku. Žádný řádek není delší než 250 znaků. Za posledním číslem zadání následuje jeden prázdný řádek.

Specifikace výstupu

Pro každé zadání musí výstup obsahovat jeden řádek obsahující součet zadaných čísel. Nevýznamné nuly musí být ve výstupu potlačeny.

Příklad vstupu

2
2
011111111111111111111111111111111111111111111111111
0000000888888888888888888888888888888888888888888888888888888

3
0001234
000000000034568145
100000000000000000000000000000000000000000000000000000785632

Příklad výstupu

888899999999999999999999999999999999999999999999999999
100000000000000000000000000000000000000000000000000035355011

Problém D

Tlumočníci

Agentura CNN (Co nechci nepřekládám) poskytuje služby v oblasti tlumočnictví. Evidenci všech tlumočníků agentury CNN zajišťuje počítač. Při příchodu požadavku na tlumočení z jednoho jazyka do druhého chce agentura co nejdříve zjistit, zda je schopna tomuto požadavku vyhovět. Vaším úkolem je napsat program, který toto zjistí.

V agentuře pracuje T tlumočníků, z nichž každý ovládá alespoň jeden jazyk. Celkový počet jazyků označme J. Každý tlumočník je jednoznačně identifikován celým kladným číslem t, 1 <= t <= T, každý jazyk má přiřazeno unikátní celé kladné číslo j, 1 <= j <= J. Pro každého tlumočníka je zadána množina jazyků, které ovládá.

Napište program, který pro dané dva jazyky j₁ a j₂ rozhodne, zda agentura může zajistit tlumočení mezi těmito dvěma jazyky, tj. zda existuje posloupnost jazyků l₁, l₂, ..., l_n taková, že l₁ = j₁, l_n = j₂ a pro všechna i, 1 <= i < n existuje t, 1 <= t <= T takové, že tlumočník t ovládá jazyky l_i a l_i+1. Pokud agentura může vyhovět požadavku na tlumočení, je úkolem programu najít minimální množinu tlumočníků, kteří jsou schopni toto tlumočení zajistit. Tj. najít takovou minimální množinu {t_i₁, t_i₂, ..., t_{i_m}}, pro kterou existuje posloupnost jazyků l₁, l₂, ..., l_m+1 taková, že l₁ = j₁, l_m+1 = j₂ a tlumočník t_{i_k} ovládá jazyky l_k a l_k+1, pro všechna k, 1 <= k <= m. Pokud existuje více řešení (tj. množina {t_i₁, t_i₂, ..., t_{i_m}} není určena jednoznačně), stačí nalézt libovolné z nich.

Specifikace vstupu

Vstup se skládá z N zadání. První řádek vstupního souboru obsahuje celé kladné číslo N. Dále následují jednotlivá zadání. Na prvním řádku každého zadání jsou uvedena čísla T (počet tlumočníků) a J (počet jazyků) oddělená mezerou, 1 <= T,J <= 500. Dále následuje T řádků, z nichž vždy t-tý řádek udává, jaké jazyky ovládá tlumočník číslo t. Čísla jazyků na řádku jsou oddělena mezerou, mohou být uvedena v libovolném pořadí a jsou ukončena číslem 0. Žádné číslo se na jednom řádku nevyskytne více než jednou. Poslední řádek zadání tvoří čísla j₁ a j₂, j₁ <> j₂, oddělená mezerou. Za každým zadáním následuje jeden prázdný řádek. Prázdný řádek obsahuje znak 'přechod na nový řádek' předcházený libovolným počtem mezer.

Specifikace výstupu

Pro každé zadání musí výstup obsahovat právě jeden řádek textu. Pokud je agentura schopna vyhovět požadavku na tlumočení z jazyka j₁ do jazyka j₂, má výstup tento tvar: Agentura pouzije tyto tlumocniky: t₁ t₂ ... t_m., kde za t₁, t₂, ..., t_m se dosadí čísla tlumočníků. Čísla tlumočníků jsou oddělena právě jednou mezerou. Pokud agentura nemůže zajistit tlumočení mezi jazyky j₁ a j₂, má výstup tento tvar: Agentura nemuze zajistit tlumoceni z jazyka j₁ do jazyka j₂., kde za j₁ a j₂ se dosadí čísla jazyků.

Příklad vstupu

Příklad výstupu

Agentura pouzije tyto tlumocniky: 2 1.
Agentura nemuze zajistit tlumoceni z jazyka 4 do jazyka 1.
Agentura pouzije tyto tlumocniky: 2 3 4 1.

Problém E

Kdo za to může

Ekonomická situace našeho státu není dobrá. Lze říci, že v tom se dnes shodne nejen lid prostý, ale i skupina lidí v této věci obzvláště angažovaná, nazývaná vládou. Vláda je ovšem od toho, aby vládla a vyrovnávala se i s takto nepříjemnými záležitostmi. Naše vláda zvolila jako řešení nepříznivé ekonomické situace soubor ekonomických opatření, takzvaný balíček. Jak ale bývá zvykem v našich končinách, není jasné, kdo je vlastně odpovědný za to, že vůbec takovýto balíček potřebujeme. Je ale možné, že to jednou jasné bude a viníci patrně vládu opustí. Protože nechceme žádného člena vlády rozzlobit, použijeme spravedlivý způsob, jak viníka označit - rozpočítávání. Jedna, dva, tři, my jsme bratři. Ale podle hesla všichni jsou si rovni, někteří jsou si rovnější bychom rádi provedli rozpočítání tak, abychom určili někoho, koho si předem vybereme.

A vy máte za úkol pomoci vládě tím, že napíšete program, který dovolí určit, u kterého člena vlády máme začít s rozpočítáváním, když víme, u kterého chceme skončit a jak dlouhé je rozpočítávadlo.

Postup je takovýto: pohlédneme do očí členu vlády, který je první na řadě, a pravíme pevným hlasem jedna. Poté pohlédneme na nejbližšího člena směrem vpravo (máme pravicovou vládu) a proneseme dvě. Tak cyklicky postupujeme stále dokola, až dojdeme na konec rozpočítávadla. Člena, na kterého padne poslední číslo rozpočítávadla, označíme jako nevinného a vyjmeme ho z kruhu. Pokud zbývá v kruhu více lidí, pokračujeme v rozpočítávání od vyřazeného člena dále. Pokud zbyde poslední člen vlády, máme viníka a končíme.

Specifikace vstupu

Vstup se skládá z N zadání. První řádek vstupního souboru obsahuje celé kladné číslo N. Dále následují na samostatných řádcích jednotlivá zadání. Na každém řádku jsou uvedena čísla P (počet členů vlády), D (délka rozpočítávadla) a V (číslo viníka) oddělená mezerou, 1 <= P,D,V <= 5000. Členové vlády jsou číslováni 1 ... P.

Specifikace výstupu

Pro každé zadání musí výstup obsahovat právě jeden řádek textu, na kterém je jedno číslo S, 1 <= S <= P, udávající číslo člena vlády, u kterého máme začít s rozpočítáváním.

Příklad vstupu

Příklad výstupu

1
3
1

Problém F

Most přes řeku

Dnes je tomu již několik let, kdy domorodý africký kmen Hulvátů vykopal válečnou sekeru. Tento kmen je velmi moderně vyzbrojen a používá na svých taženích tak pokrokovou techniku, jako jsou kulomety a tanky. Taková výzbroj poskytuje sice značnou výhodou proti soupeřům, představuje však nemalý problém v případě překonávání vodního toku. Jelikož hulvátská domovina obsahuje nespočet různých řek, říček, potoků a jezer, je tento problém velmi aktuální.

Všechny hranice mezi souší a vodou jsou vždy pravoúhlé a kopírují přesně jednotkové čtverečky ortogonální sítě, kterou si kdysi Hulváti stanovili jako základní podklad pro vytváření svých map. Protože hulvátské mapy jsou počítačem zpracovány na velmi dobré úrovni, není problém získat z nich tvar vodního toku, přetransformovat jej tak, aby probíhal vždy vertikálně (t.j. vstupoval do mapy na horním okraji a vystupoval na spodním okraji) a jeho břehy ležely přesně na hranách ortogonální sítě a stanovit souřadnice obou břehů pro každou vodorovnou řadu jednotkových čtverečků. Tato transformace má navíc tu vlastnost, že výsledné souřadnice všech levých břehů jsou vždy menší než souřadnice všech pravých břehů.

Naštěstí pro společenský život Hulvátů vynalezl hulvátský vědec Postolomlatos přenosné a lehko sestavitelné mosty, složené ze stejně velkých čtvercových dílů, takzvaných pontonů. Všechny pontony mají přesně velikost jednotkového čtverečku a lze je spojovat mezi sebou a připojovat k břehu pouze jejich celými stranami. V rámci nově stanoveného balíčku ekonomických opatření vydal náčelník kmene Velký Mlask nařízení, že k překonání každého vodního toku se smí použít pouze takové množství pontonů, jaké je nezbytně nutné.

Vaším úkolem je vytvořit program, který najde nejvhodnější místo k přechodu řeky (t.j. takové místo, ve kterém je počet pontonových dílů k překonání řeky nejmenší) a určí počet pontonů potřebný k postavení souvislého mostu z jednoho břehu na druhý.

Příklad zpracované mapy je uveden na následujícím obrázku včetně jednoho ze správných řešení. V tomto případě bylo k přechodu řeky použito tří pontonů.

Specifikace vstupu

Vstup se skládá z N zadání. První řádek vstupního souboru obsahuje celé kladné číslo N. Dále následují jednotlivá zadání. Každé z těchto zadání obsahuje na prvním řádku jedno celé kladné číslo K, které udává délku sledovaného úseku řeky. Následuje postupně K řádků, z nichž každý se týká jedné řady jednotkových čtverečků (postupně odshora) a obsahuje dvě celá čísla A a B, oddělená mezerou a udávající souřadnici levého a pravého břehu. Vždy bude A < B, A < 100000 a B < 100000.

Specifikace výstupu

Pro každé zadání musí výstup obsahovat právě jeden řádek s tímto textem: K prechodu reky je treba XX pontonu., kde místo XX bude uveden minimální počet pontonů potřebných k postavení mostu z jednoho břehu řeky na druhý.

Příklad vstupu

Příklad výstupu

K prechodu reky je treba 3 pontonu.
K prechodu reky je treba 1 pontonu.

Problem G

Area

You are to write a program that computes the area of a rectangle delimited by the surrounding path. The path is allways closed and runs along the grid lines, i.e. between the squares of the grid. You can safely assume that the path never touches or crosses itself.

Input Specification

The first line of the input file contains the number of test cases in the file. Each test case that follows consists of two lines. The first line of each case contains two integer numbers X and Y specifying the starting point of the path. The second line contains a string of variable length. Every letter in the string symbolizes a move of length one along the grid. Only the letters 'W' ("west"), 'E' ("east"), 'N' ("north"), 'S' ("south"), and '.' ("end of path", no move) appear in the string. The end-of-path character ('.') is immediately followed by the end of the line. The length of each input line will never exceed 100000 characters.

Output Specification

For each test case, output must contain one single line with the text The area is XX squares. - the letters XX should be replaced by the computed area of the given polygon.

Sample Input

1
2 1
EENNWNENWWWSSSES.

Output for Sample Input

The area is 10 squares.