Ramki

---

Imeetsja tekstovyj jekran iz M strok i N stolbcov (3<=M,N<=100). Pervonachal'no jekran zapolnen simvolom "." (ASCII-kod 249). Na jetom jekrane odna za drugoj risujutsja prjamougol'nye ramki tolschinoj v odin simvol. Kazhdaja ramka risuetsja pri pomoschi svoego simvola, javljajuschegosja zaglavnoj bukvoj latinskogo alfavita. Pri risovanii ramki ee simvoly zameschajut na jekrane ranee izobrazhennye. Ramki narisovany takim obrazom, chto u kazhdoj ramki vidna hotja by odna para protivolezhaschih uglov. Trebuetsja po dannomu izobrazheniju na jekrane opredelit', vozmozhno li odnoznachno vosstanovit' posledovatel'nost' risovanija ramok i 1) esli vosstanovlenie odnoznachno, opredelit' trebuemuju posledovatel'nost'; 2) esli vosstanovlenie neodnoznachno, opredelit' dve razlichnye vozmozhnye posledovatel'nosti risovanija ramok.

Ishodnye dannye programmy raspolozheny v tekstovom ASCII-fajle, imja kotorogo vvoditsja s klaviatury. Pervaja stroka ishodnogo fajla soderzhit razmery jekrana M i N. Dalee raspolozheno M strok po N simvolov v kazhdoj, zadajuschih izobrazhenie na jekrane.

Rezul'tat raboty programmy vyvoditsja odnovremenno na jekran i v tekstovyj ASCII-fajl s imenem OUTPUT.TXT. Pervaja stroka soderzhit odnu iz vozmozhnyh posledovatel'nostej risovanija ramok, zadannuju perechisleniem imen ramok bez probelov. Vtoraja stroka povtorjaet pervuju, esli vosstanovlenie odnoznachno, libo soderzhit druguju vozmozhnuju posledovatel'nost', esli vosstanovlenie neodnoznachno.

Primechanija: Zadannoe vo vhodnom fajle izobrazhenie zavedomo mozhno poluchit' posledovatel'nym risovaniem ramok. Kazhdaja storona ramki sostoit ne menee, chem iz 3 simvolov. Ramki ne mogut risovat'sja za predelami jekrana. Ishodnye dannye korrektny, i ih proverka ne trebuetsja.

Primer fajla ishodnyh dannyh:

6 4
....
.AAA
WWWA
WAWA
WHWH
WWW.  

Primer vyhodnogo fajla OUTPUT.TXT dlja privedennogo primera:

AW
AW  

Chto tut schitat'

---

Zadano natural'noe desjatichnoe chislo N (N<=1.000.000.000). Napisat' programmu vychislenija kolichestva prinadlezhaschih diapazonu ot 1 do N chisel, v dvoichnom predstavlenii kotoryh soderzhitsja rovno K znachaschih nulej. Naprimer, dlja N=18 i K=3 takih chisel - 3 (8, 17, 18).

Tehnicheskie trebovanija:

• vvod chisel N i K osuschestvljaetsja s klaviatury,
• poluchennyj rezul'tat vyvoditsja na jekran.

Tehnicheskie ogranichenija:

• korrektnost' vhodnyh dannyh ne proverjaetsja,
• vremja testirovanija ogranicheno

Detektiv

---

Iz gorodskogo muzeja byl pohischen krupnyj almaz. Vozglavivshij sledstvie major Pronin issledoval mesto prestuplenija i vyjasnil sledujuschee.

Muzej sostoit iz cepochki zalov s nomerami ot 1 do n (n<=10). Almaz nahodilsja v zale k. Posetiteli (ih ne bolee 10) prohodili po zalam v sootvetstvii s ih nomerami, ne vozvraschajas' nazad. Razmery zalov takovy, chto posetitel' zatrachival na prohod zala ne men'she minuty. V nekotoryh zalah nahodilis' smotriteli (ih ne bolee 10), kotorye ne mogli pohitit' kamen'. V zale, gde nahodilsja almaz, smotritelja ne bylo. Smotriteli zamechali ne vseh posetitelej, kotorye prohodili po zalu, no uzh esli smotritel' zametil posetitelja, to on objazatel'no zapominal vremja, kogda on ego uvidel, s tochnost'ju do minuty. Posetiteli muzeja, razgljadyvaja jeksponaty, ne vsegda obraschali vnimanie na ostal'nyh posetitelej, no uzh esli posetitel' obraschal na kogo-to vnimanie, to on zapominal vremja i mesto (nomer zala) ego nahozhdenija.

Predvaritel'noe rassledovanie pozvolilo majoru Proninu opredelit' promezhutok vremeni, kogda mog byt' pohischen almaz. On takzhe ustanovil, chto prestupnik dejstvoval v odinochku, mog sovershit' krazhu, tol'ko esli nahodilsja v jetot moment v zale odin, i na doprose mog dat' lozhnye pokazanija. Ostalos' vyjasnit' imja prestupnika.

S jetoj cel'ju major Pronin doprosil smotritelej i posetitelej i sostavil protokol, soderzhaschij informaciju o tom, kto, kogo, kogda i gde videl.

Trebuetsja napisat' programmu, kotoraja po vsej imejuschejsja u majora Pronina informacii opredeljaet krug posetitelej, kotorye mogli sovershit' prestuplenie.

Vhodnye dannye

Vhodnye dannye vvodjatsja iz fajla v sledujuschej posledovatel'nosti:

n k	kolichestvo zalov, nomer zala, gde byl almaz
t1 t2	promezhutok vremeni, kogda proizoshlo pohischenie
m	chislo smotritelej
imja_smotritelja_1
imja_smotritelja_2
...
imja_smotritelja_m
p	chislo posledujuschih strok v fajle
kto_1 kogo_1 kogda_1 nomer_zala_1
kto_2 kogo_2 kogda_2 nome_rzala_2
...
kto_p kogo_p kogda_p nomer_zala_p

Imena smotritelej i posetitelej zapisyvajutsja russkimi bukvami. Dlina imen ne prevyshaet 20 simvolov.

Primer fajla:

4 2
9:20 10:30
1
BabaNastja
5
BabaNastja PoruchikRzhevskij 10:15 1
AgentSidorov InostrannyjShpion 11:21 1
AgentSidorov InostrannyjShpion 11:22 2
AgentSidorov InostrannyjShpion 11:22 3
AgentSidorov InostrannyjShpion 11:24 4  

Lesnoe boloto razdeleno na 8x8 odinakovyh kletok. V nekotoryh kletkah bolota nahodjatsja kochki, a vse ostal'nye kletki s vodoj. Na odnoj iz kochek sidit ljagushka, a nad kakoj-to drugoj kletkoj bolota letaet komar. Ljagushka hochet s''est' komara, a komar staraetsja ot nee uletet'. Peremeschajutsja ljagushka i komar po ocheredi, pervyj hod - za ljagushkoj. Za odin pryzhok ljagushka peremeschaetsja na ljubuju iz kochek po gorizontali, vertikali ili diagonali. Komar za odin perelet peremeschaetsja na odnu iz 8 sosednih kletok. Esli ljagushka v pryzhke proletaet cherez kletku, nad kotoroj nahoditsja komar (ili prygaet na kletku, nad kotoroj letaet komar), to ona s''edaet komara. S''ev komara v poslednem pryzhke, ljagushka mozhet okazat'sja kak v vode, tak i na kochke.

Trebuetsja opredelit' minimal'noe chislo pryzhkov dlja togo, chtoby s''est' komara, libo vydat' soobschenie, chto komara s''est' nevozmozhno.

Vhodnye dannye

1. Vhodnye dannye programmy raspolozheny v tekstovom ASCII-fajle, imja kotorogo vvoditsja s klaviatury.
2. V pervyh 8 strokah fajla nahoditsja matrica razmerom 8x8, zadajuschaja shemu raspolozhenija kochek v vide nulej i edinic (0 - kletka s vodoj, 1 - kochka). Jelementy matricy v kazhdoj stroke zapisyvajutsja bez probelov. Dalee soderzhitsja stroka s koordinatami ljagushki (x1, y1) i komara (x2, y2 ), gde xi - nomer stroki, yi - nomer stolbca.

Primer fajla ishodnyh dannyh:

11111111
11111011
11101111
11111011
11110111
11011111
10111101
11111111
2 1 1 8  

Vyhodnye dannye

Vyhodnoj tekstovyj ASCII-fajl s imenem OUTPUT.TXT dolzhen soderzhat' snachala minimal'noe kolichestvo shagov, a zatem pervyj vozmozhnyj hod ljagushki, zadavaemyj koordinatami kochki, na kotoruju prygaet ljagushka. Esli komara s''est' nevozmozhno, to vyhodnoj fajl dolzhen soderzhat' odnu stroku s soobscheniem "Nevozmozhno".

Primer vyhodnogo fajla OUTPUT.TXT dlja privedennogo primera:

2
2 7  

Primechanija:

1. V vyhodnom fajle dolzhen soderzhat'sja tol'ko odin iz vozmozhnyh pervyh hodov ljagushki.
2. Ljagushka peremeschaetsja tol'ko s kochki na kochku, t.k. pri popadanii v vodu ona terjaet komara iz vida.
3. Ishodnye dannye korrektny, i ih proverka ne trebuetsja.
4. Reshenie zadachi dlja sluchaja, kogda minimal'noe kolichestvo pryzhkov ljagushki ne prevoshodit treh, budet takzhe ocenivat'sja.

5. Vremja testirovanija kazhdogo testa ogranicheno odnoj minutoj.

Parallel'nye vychislenija

---

Zadana programma, sostojaschaja iz N operatorov prisvaivanija (1<=N<=15). Kazhdyj operator zapisyvaetsja v sledujuschem vide: X=YopZ

gde X,Y,i Z - identifikatory, sostojaschie iz odnoj zaglavnoj latinskoj bukvy;

op - simvol odnoj iz arifmeticheskih operacij: "+" (slozhenie), "-" (vychitanie), "*" (umnozhenie) i "/" (delenie).

Trebuetsja raspredelit' operatory zadannoj programmy mezhdu dvumja odinakovymi processorami s obschej pamjat'ju tak, chtoby obschee vremja vypolnenija bylo minimal'nym, a smysl programmy ne izmenilsja.

Kazhdyj operator vypolnjaetsja za odin takt raboty processora. Chtoby sinhronizirovat' rabotu processorov vvedena komanda "NOP", kotoraja zaderzhivaet rabotu processora na odin takt. V processe odnovremennoj raboty dvuh processorov vypolnjaemye operatory mogut ispol'zovat' tol'ko takie obschie peremennye, kotorye nahodjatsja v pravyh chastjah operatorov prisvaivanija (naprimer, operatory "A=B+C" i "M=A+K" ne mogut vypolnjat'sja odnovremenno).

Vhodnye dannye

1. Vhodnye dannye raspolozheny v tekstovom ASCII-fajle, imja kotorgo vvoditsja s klaviatury.
2. Kazhdyj operator nahoditsja na otdel'noj stroke; fajl ne soderzhit probelov i pustyh strok; v konce poslednej stroki fajla simvolov konca stroki net.

Primer fajla ishodnyh dannyh:

W=A+B
F=A+P
B=W/F
W=B*C  

Vyhodnye dannye

1. Rezul'tat raboty objazatel'no pomeschaetsja v vyhodnoj tekstovyj ASCII-fajl s imenem OUTPUT.TXT.
2. V pervuju stroku fajla zapisyvaetsja iskomoe minimal'noe chislo taktov P.

3. Dalee sledujut P strok, v kotoryh v dve kolonki vypisany programmy dlja kazhdogo processora; kolonki dolzhny byt' vyrovneny po levomu kraju.

Primer vyhodnogo fajla OUTPUT.TXT dlja privedennogo primera:

3
W=A+B   F=A+P
NOP     B=W/F
W=B*C   NOP       

Primechanija:

1. Ishodnye dannye korrektny, i ih proverka ne trebuetsja.
2. Vremja testirovanija kazhdogo testa ogranicheno odnoj minutoj.

Randevu

---

Lokatory dal'nej kosmicheskoj svjazi zamechajut letjaschij v ploskosti orbity Zemli neizvestnyj asteroid s koordinatami (x,y). Asteroid letit s postojannoj skorost'ju, vektornoe znachenie kotoroj ravno (Vx, Vy). S Zemli iz tochki s koordinatami (0,0) nemedlenno startuet raketa s radiusom dejstvija R (R>0). Raketa letit po prjamoj s postojannoj skorost'ju v predelah ot 0 do W.

Trebuetsja opredelit', mozhet li raketa podletet' vplotnuju k asteroidu v predelah radiusa ee dejstvija i najti vektor skorosti rakety, pri kotorom vremja vstrechi rakety s asteroidom minimal'noe.

Vhodnye dannye

1. Vhodnye dannye raspolozheny v tekstovom ASCII-fajle, imja kotorogo vvoditsja s klaviatury.
2. V nachale fajla soderzhitsja chislo N - kolichestvo naborov ishodnyh dannyh (testov).
3. Dalee raspolozheny N naborov ishodnyh dannyh; kazhdyj nabor - shest' veschestvennyh chisel: X, Y, Vx, Vy, W, R.
4. Vse chisla v ishodnom fajle razdeljajutsja probelami i (ili) simvolami perevoda stroki.

Primer fajla ishodnyh dannyh:

2
5.3 2.8 10.6 5.6 11.0 50.0
3.0 -4.0 -3.0 4.0 5.0 10.0  

Vyhodnye dannye

1. Rezul'tat raboty pomeschaetsja v vyhodnoj tekstovyj ASCII-fajl s imenem OUTPUT.TXT.
2. Dlja kazhdogo nabora ishodnyh dannyh vyvesti s novoj stroki vektor skorosti (Ux,Uy) i minimal'noe vremja vstrechi, libo soobschenie "Vstrecha nevozmozhna".

Primer vyhodnogo fajla OUTPUT.TXT dlja privedennogo primera:

Vstrecha nevozmozhna
3.0 -4.0 0.5  

Primechanija:

• Rezul'tat reshenija zadachi dolzhen byt' vychislen s pogreshnost'ju ne bolee 0.01.
• Vlijaniem Zemli i vseh kosmicheskih ob''ektov prenebrech'.
• Raketa i asteroid dvigajutsja v odnoj ploskosti.
• Ishodnye dannye korrektny, i ih proverka ne trebuetsja.
• Obschee vremja testirovanija ogranicheno tremja minutami.