Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (2. soutěžní den) 44. ročníku

P-III-4

Ekonomická situace způsobila, že se mnoho společností zadlužilo. Každá ze společností může být jak věřitelem (prodává své výrobky), tak dlužníkem (kupuje suroviny a polotovary). Aby bylo možno minimalizovat celkovou zadluženost, bylo dohodnuto, že je možné, aby se společnosti oddlužily tím, že své pohledávky u jedněch společností budou splácet pohledávkami u jiných společností. Jestliže například společnost 1 dluží 100$ společnosti 2, společnost 2 dluží společnosti 3 50$ a společnost 3 dluží společnosti 1 75$, je celkový dluh 225$, ale po započtení vzájemných pohledávek dluží společnost 1 společnosti 2 25$ a společnost 3 dluží společnosti 2 25$, takže celkový dluh myní činí pouze 50$.

Společnosti jsou identifikovány celými čísly. Můžete předpokládat, že jich není více než 1000. Dluh je uveden v celých jednotkách měny.

Úloha

Vytvořte soubor DLUHY.PAS a uložte do něj program, který dělá postupně následující:
Celou činnost program opakuje, dokud nepřečte celý vstupní soubor DLUHY.DAT. V jednom souboru může být více zadání samostatných úloh.

Příklad

Soubor DLUHY.DAT

3 1 2 100 2 3 50 3 1 75 2 1 2 100 2 3 50

Soubor DLUHY.RES

225 1 2 25 3 2 25 50 150 1 2 50 1 3 50 100

P-III-5

Město je protkáno sítí rovnoběžných silnic, jdoucích od západu na východ a od severu na jih. Silnice jsou očíslovány celými čísly. Na okraji města existují 2 na sebe kolmé silnice s čísly 0. Čísla ostatních silnic znamenají vzdálenost této silnice od silnice s číslem 0, která je s ní rovnoběžná. Křižovatka silnic je označena dvojicí čísel (i,j), kde i je číslo silnice vedoucí od západu na východ a j je číslo silnice vedoucí ze severu na jih. Na všech křižovatkách je zakázáno odbočovat vlevo a rovněž je zakázáno kdekoliv na silnici se otáčet. Je dán seznam křižovatek, které musíme navštívit. Vaším úkolem je určit, v jakém pořadí je možné projet zadanými křižovatkami tak, abychom dodrželi pravidla silničního provozu, nikde neprotnuli svoji dráhu a abychom navštívili všechny zadané křižovatky. Předpokládá se při tom, že při cestě není potřeba doplňovat pohonné hmoty.

Úloha

Vytvořte soubor MESTO.PAS a vložte do něj program, který dělá následující:
  1. ze vstupního souboru MESTO.DAT načte postupně řádky s dvojicemi čísel i, j identifikujícími křižovatky, dokud není soubor vyčerpán.
  2. Určí počet různých křižovatek N na vstupu a zapíše jej do výstupního souboru MESTO.RES.
  3. Do výstupního souboru MESTO.RES zapíše na N řádků dvojice čísel označující křižovatky v pořadí, v němž budou navštíveny.

Příklad

Soubor MESTO.DAT

3 6 6 4 5 2 3 2 6 4 0 2 1 0

Soubor MESTO.RES

6 5 2 6 4 3 6 0 2 1 0 3 2