Zadacha A (Shema)
	Avtor(y): A.Suhanov, I.Mironov

Kolichestvo testov: 1
Ogranichenie vremeni: 30 sekund

Na tekstovom tablo razmerom M strok na N stolbcov (1< =M,N< =100) izobrazhena shema, sostojaschaja iz odinarnyh i dvojnyh lomanyh linij, iduschih po strokam i po stolbcam tablo. Linii, tochki povorota lomanyh i tochki peresechenija izobrazhajutsja podhodjaschimi simvolami psevdografiki. Pustye kletki jekrana izobrazhajutsja simvolom "." (ASCII-kod 249). Nizhe privedeny dopustimye simvoly psevdografiki i ih ASCII-kody:

ris.1

Napishite programmu, kotoraja po zadannym lomanym stroit izobrazhenie na tablo. Ishodnye dannye raspolozheny v fajle po sledujuschemu formatu. Pervaja stroka soderzhit razmery tablo M i N. Kazhdaja iz sledujuschih strok soderzhit opisanie lomanoj. Lomanaja zadaetsja tolschinoj linii (1 ili 2) i posledovatel'nym perechisleniem koordinat tochek izloma (pervaja koordinata - nomer stroki, vtoraja - nomer stolbca). Fajl ishodnyh dannyh ne soderzhit pustyh strok.

Vyvesti v vyhodnoj fajl izobrazhenie shemy v vide matricy iz M strok, po N simvolov v kazhdoj.

Primechanija:

Lomanye ne mogut nakladyvat'sja drug na druga i na samih sebja. Izvestno, chto zadannuju vo vhodnom fajle shemu mozhno izobrazit' pri pomoschi ukazannyh simvolov psevdografiki. Ishodnye dannye korrektny, i ih proverka ne trebuetsja.

Primer fajla ishodnyh dannyh INPUT.TXT:

4 9
1 1 5 4 5
2 1 2 1 8 3 8 3 2 1 2

Primer vyhodnogo fajla OUTPUT.TXT dlja nashego primera:

	Zadacha B (Dyrokol)
	Avtor(y): A.Suhanov

Kolichestvo testov: ne bolee 6
Ogranichenie vremeni: 30 sekund na ves' nabor testov

Na gorizontal'nom stole lezhit kletchatyj list bumagi razmerom 2**N na 2**N (3< =N< =500) kletok. Ego skladyvajut N-3 raza tak, chto za odno skladyvanie perednjaja polovina lista nakladyvaetsja poverh zadnej, a zatem pravaja polovina lista nakladyvaetsja poverh levoj. Takim obrazom, na odnom shage linejnye razmery lista umen'shajutsja v dva raza, a v konce poluchaetsja stopka 8 na 8 kletok. Iz jetoj stopki pri pomoschi dyrokola udalili nekotorye kletki (iz vseh sloev odnovremenno). Trebuetsja opredelit' na skol'ko chastej raspadetsja ishodnyj list bumagi (chast'ju schitaetsja oblast', sostojaschaja iz kletok, svjazannyh po vertikali i (ili) gorizontali). Vo vhodnom fajle soderzhitsja odin ili neskol'ko naborov ishodnyh dannyh. Kazhdyj nabor - jeto N i matrica 8 na 8 nulej i edinic (0 - ostavljaem kletku, 1 - udaljaem). Vse chisla v ishodnom fajle (v tom chisle i jelementy matricy) razdeljajutsja probelami i (ili) simvolami perevoda stroki. Dlja kazhdogo nabora ishodnyh dannyh vyvesti v vyhodnoj fajl s novoj stroki iskomoe kolichestvo kuskov. Ishodnye dannye korrektny, i ih proverka ne trebuetsja.

Primer fajla ishodnyh dannyh INPUT.TXT:

4
0 1 0 0 0 0 1 0
1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

Primer vyhodnogo fajla OUTPUT.TXT dlja nashego primera:

11

	Zadacha C (Ivanushka i Carevna)
	Avtor(y): A.Suhanov

Kolichestvo testov: ne bolee 5
Ogranichenie vremeni: 60 sekund na ves' nabor testov

ris.3

Carevna privjazana k vysokomu stolbu, raspolozhennomu v centre bol'shogo bolota (tochka s koordinatami (0, 0)), i gromko plachet. Zloj Koschej obvjazal Carevnu verevkoj I (1< I< 6) raz (po chasovoj strelke). Konec jetoj dostatochno dlinnoj verevki popal v ruki k Ivanushke, kotoryj, sobiraetsja osvobodit' Carevnu i vzjat' ee v zheny. Dlja jetogo emu trebuetsja, derzha v rukah verevku, obojti vokrug Carevny rovno I raz (protiv chasovoj strelki) i vernut'sja v ishodnuju tochku. Boloto glubokoe i neprohodimoe, pojetomu Ivanushka mozhet peremeschat'sja po nemu, tol'ko prygaja s odnoj kochki na druguju. V rezul'tate takogo pryzhka za nogi Ivanushke zacepljaetsja opredelennoe (zadannoe dlja kazhdoj pary kochek) kolichestvo zeljonyh vodoroslej. Napishite programmu, kotoraja nahodit takoj put' spasenija Carevny, pri kotorom za nogi Ivanushke zacepljaetsja minimal'noe summarnoe kolichestvo zeljonyh vodoroslej.

Vo vhodnom fajle soderzhitsja odin ili neskol'ko naborov ishodnyh dannyh. Kazhdyj nabor - jeto

1. Kolichestvo kochek N (3<N<10).
2. Kolichestvo oborotov I.
3. Koordinaty kochek - N par veschestvennyh chisel (X1,Y1), ... (XN, YN).
4. Matrica A razmerom N na N, jelement matricy s koordinatami (stroka i, stolbec j) soderzhit kolichestvo zeljonyh vodoroslej, kotoroe zacepljaetsja za nogi Ivanushke, kogda on prygaet s kochki i na kochku j; diagonal'nye jelementy matricy nulevye i 0<A[i,j]<10000.
5. Nomer nachal'noj kochki S, na kotoroj stoit Ivanushka.

Nabory ishodnyh dannyh i vse chisla vo vhodnom fajle razdeljajutsja probelami i (ili) simvolami perevoda stroki. Kochki zanumerovany natural'nymi chislami ot 1 do N. Vyvod programmy: Dlja kazhdogo nabora ishodnyh dannyh vyvesti v vyhodnoj fajl s novoj stroki minimal'noe summarnoe kolichestvo zelenyh vodoroslej i put' Ivanushki, zadannyj posledovatel'nym perechisleniem nomerov kochek, po kotorym on prygaet (put' dolzhen nachinat'sja i zakanchivat'sja nomerom nachal'noj kochki S).

Primechjanija:

Chtoby ne povredit' Carevnu, Ivanushka ne dolzhen dopuskat', chtoby Carevna byla zamotana bolee 10 raz (kak po, tak i protiv chasovoj strelki). Ni odin otrezok, soedinjajuschij kochki, ne prohodit cherez centr bolota. V bolote nichego, krome nizkosteljuschihsja zeljonyh vodoroslej ne rastet, pojetomu Ivanushka mozhet ne bespokoit'sja, chto verevka nachnet na chto-libo namatyvat'sja i zaputyvat'sja. Kochki raspolozheny takim obrazom, chto iskomyj put' vsegda budet suschestvovat'. Ishodnye dannye korrektny, i ih proverka ne trebuetsja.

Primer fajla ishodnyh dannyh INPUT.TXT:

7 1
-14.5 3 17 21 0 30 15 -23 -2 -12 -33.1 -5 -7 17
0 2 10 13 9 7 15
9 0 9 31 1 9 1
9 9 0 13 9 1 9
9 9 1 0 9 9 9
9 1 9 1 0 9 9
9 9 9 9 1 0 9
1 9 7 9 9 9 0
1

Primer vyhodnogo fajla OUTPUT.TXT dlja nashego primera (sm. izobrazhenie puti na ris.3):

10 1 2 5 4 3 6 5 2 7 1

	Zadacha D (Dlinnoe ravenstvo)
	Avtor(y): I.Mironov

Kolichestvo testov: ne bolee 10
Ogranichenie vremeni: 60 sekund na ves' nabor testov

Rassmatrivajutsja arifmeticheskie vyrazhenija bez skobok, soderzhaschie celye chisla (neogranichennoj dliny) i znaki operacij: + (pljus), - (minus) i * (umnozhit'). Trebuetsja proverit' ravenstvo vida A=B, gde A i B - vyrazhenija, postroennye po opisannym vyshe pravilam.

Fajl ishodnyh dannyh soderzhit odno ili neskol'ko ravenstv, razdelennyh simvolom ";" (tochka s zapjatoj). Dlja kazhdogo takogo ravenstva vyvesti v vyhodnoj fajl s novoj stroki rezul'tat sravnenija: "verno" ili "neverno". Fajl ishodnyh dannyh mozhet soderzhat' probely i (ili) simvoly perevoda stroki. Programma dolzhna ignorirovat' jeti simvoly, kak neznachimye (razryvat'sja mogut dazhe chisla). Dlina fajla ishodnyh dannyh ne prevoshodit 40 Kbajt. Ishodnye dannye korrektny i ih proverka ne trebuetsja.

Primer fajla ishodnyh dannyh INPUT.TXT:

21-4*2 = -4 *-3; 23233542512352143524
12 - 232335425123521435242*10+  8 =0

Primer vyhodnogo fajla OUTPUT.TXT dlja nashego primera:

neverno
verno