Zadana belaja doska razmerom NxN kletok, vykrashennyh v belyj i chernyj cveta. Za odin hod mozhno perekrasit' vse kletki odnoj stroki ili odnogo stolbca v protivopolozhnyj cvet. Napishite programmu, kotoraja vvodit chislo N (2<=N<=50), nachal'nuju raskrasku doski NxN i opredeljaet posledovatel'nost' hodov, s pomosch'ju kotoryh poluchaetsja belaja doska, ili soobschaet, chto takoj posledovatel'nosti ne suschestvuet. Raskraska doski zadaetsja tablicej NxN nulej i edinic, gde 0 - belaja kletka, 1 - chernaja.

Naprimer, dlja doski, izobrazhennoj na risunke, dopustimym resheniem javljaetsja posledovatel'nost':

stroka 1
stolbec 4
stolbec 1
stroka 4

Na ploskosti raspolozhena sistema iz N odinakovyh shesterenok, kotoraja privoditsja v dvizhenie vrascheniem shesterenki № 1 po chasovoj strelke. Sceplennye shesterenki mogut vraschat'sja tol'ko v raznyh napravlenijah.

Trebuetsja opredelit' napravlenie vraschenija kazhdoj shesterenki sistemy, libo ustanovit', chto sistemu zaklinit.

Ishodnye dannye programmy: kolichestvo shesterenok N (1<=N<=100) i nabor par (i,j), kotorye opredeljajut nomera sceplennyh shesterenok.

Naprimer, dlja sistemy shesterenok, izobrazhennoj na ris.2, ishodnymi dannymi budut chislo 5 i pary (1,2), (2,3), (4,5), (2,4), (3,5) Vyvod programmy mozhet byt' sledujuschim:

shesterenka 1: po chasovoj strelke
shesterenka 2: protiv chasovoj strelki
shesterenka 3: po chasovoj strelke
shesterenka 4: po chasovoj strelke
shesterenka 5: protiv chasovoj strelki

Zadana jelektricheskaja shema iz rezistorov (soprotivlenij). Shema javljaetsja parallel'no-posledovatel'noj (P.-P. shema), t.e. soderzhit tol'ko posledovatel'nye i parallel'nye soedinenija rezistorov. Formal'no, ponjatie P.-P. shemy mozhno predstavit' sledujuschimi pravilami:

Kazhdyj rezistor zadaetsja velichinoj soprotivlenija. Trebuetsja vychislit' obschee soprotivlenie zadannoj shemy. Napomnim, chto

1. v sluchae A soprotivlenie shemy ravno soprotivleniju edinstvennogo vhodjaschego v nee rezistora;

2. v sluchae B soprotivlenie shemy ravno summe soprotivlenij posledovatel'no soedinennyh shem;

3. v sluchae V soprotivlenie shemy vychisljaetsja po formule: R=1/(1/R1+...+1/Rn), gde R1, ..., Rn - soprotivlenija parallel'no soedinennyh shem.

Primechanija. V parallel'nom i posledovatel'nom soedinenijah uchastvujut po krajnej mere dve shemy. Velichiny soprotivlenij zadajutsja v odnoj sisteme izmerenija natural'nymi chislami. Izobrazhenie shemy ne soderzhit probelov i sostoit ne bolee, chem iz 80 simvolov.

Naprimer, dlja shemy, zadannoj strokoj (16:(22-42)) iskomoe soprotivlenie budet ravno 12.8.

Gorodskoj teoreticheskij tur (2-oj tur)

Ishodnye dannye - natural'noe chislo N. Sostav'te programmu, kotoraja vychisljaet kolichestvo razlichnyh lesenok, sostojaschih rovno iz N odinakovyh kubikov. Zdes' lesenka C jeto nabor iz stupenek, razmer kotoryh umen'shaetsja snizu vverh. Lesenka soderzhit po krajnej mere dve stupen'ki, stupen'ka sostoit po krajnej mere iz odnogo kubika. Na risunke priveden primer takoj lesenki dlja N=11, a dlja N=5 takih lesenok dve.

Rassmatrivajutsja cepochki iz nulej i edinic odinakovoj (bol'shoj) dliny. Nad nimi mozhno vypolnjat' sledujuschie operacii:

NOT - vse nuli zamenjajutsja edinicami, a edinicy C nuljami (u jetoj operacii odin argument);

AND - operacija s dvumja argumentami: chisla, stojaschie v odinakovyh mestah, umnozhajutsja, i poluchennoe chislo zapisyvaetsja v to zhe mesto rezul'tata;

OR - operacija s dvumja argumentami: chisla, stojaschie v odinakovyh mestah, sravnivajutsja, i naibol'shee iz nih zapisyvaetsja v to zhe mesto rezul'tata. Takim obrazom, OR (a, b) = NOT ( AND ( NOT (a), NOT (b) ) ).

Napishite programmu, kotoraja vvodit natural'noe chislo N (Ng1995), chetyre cepochki a, b, c i d dliny N i opredeljaet:

(1) mozhno li posledovatel'nym primeneniem perechislennyh operacij poluchit' d iz a, b i c;

(2) pri utverditel'nom otvete stroit nuzhnuju posledovatel'nost' operacij (dostatochno odnoj posledovatel'nosti).

Primer 1. Dlja N=6, a=011000, b=111010, c=010001 i d=100010, vyvod programmy mozhet byt' sledujuschim:

(1) Da

(2) AND(NOT(a),OR(b,a))

Primer 2. Dlja N=6, a=011000, b=111010, c=010001 i d=000010, otvet na punkt (1) otricatel'nyj.

Jablonja nazyvaetsja dvoichnoj, esli v kazhdoj tochke vetvlenija stvol ili vetv' razvetvljaetsja nadvoe. Tochki vetvlenija, koren' i koncy vetok C jeto uzly dereva. Izvestna massa kazhdogo uchastka jabloni mezhdu dvumja sosednimi uzlami. Pervonachal'no v jablone N uzlov, a nuzhno ostavit' M. Jablonju mozhno rezat' v osnovanijah vetvej, pri jetom vetv' i vsja chast' dereva, rastuschaja vyshe, udaljajutsja.

Ishodnye dannye: N, M (1<M<N<=100) i spisok iz N-1 trojki. Kazhdaja trojka soderzhit nomera uzlov, opredeljajuschih uchastok i ego massu (uzly perenumerovany ot 1 do N).

Napishite programmu, kotoraja vvodit ishodnye dannye i nahodit plan podrezki dereva, ostavljajuschij naimen'shuju summarnuju massu ostavshihsja uchastkov.

Naprimer, dlja ishodnyh dannyh: N=8, M=3 i nabora troek (1, 2, 19), (2, 4, 13), (3, 2, 12), (3, 8, 17), (3, 6, 11), (5,8,10) i (8,7,8), vyvod programmy mozhet byt' sledujuschim:

Obrezat' vetki: (2,4),(3,8),(3,6).

Gorodskoj prakticheskij tur (3-yj tur)

Ocenka zadachi: 60 ballov

Imeetsja set' iz N (3<=N<=15) uzlov, nekotorye iz kotoryh soedineny dugami. Zadan zamknutyj put' P, prohodjaschij po dugam seti i soderzhaschij kazhdyj uzel rovno odin raz. Napishite programmu, kotoraja risuet na jekrane uzly i soedinjajuschie ih dugi tak, chtoby uzly nahodilis' v vershinah pravil'nogo N-ugol'nika, i nikakie dve dugi ne peresekalis' i ne prohodili cherez vershiny mnogougol'nika. Uzly izobrazhajutsja malen'kimi kruzhochkami zheltogo cveta. Dugi izobrazhajutsja krivymi, sostojaschimi iz otrezkov i (ili) dug okruzhnostej. Dugi, soderzhaschiesja v puti P, risujutsja fioletovym cvetom, a ostal'nye - zelenym. Risunok dolzhen byt' podhodjaschim obrazom otmasshtabirovan.

Ishodnye dannye raspolozheny v tekstovom fajle (imja fajla vvoditsja s klaviatury) po sledujuschemu formatu: kolichestvo uzlov N; kolichestvo dug M; spisok iz M dug, kazhdaja duga zadaetsja paroj nomerov soedinjaemyh uzlov; zamknutyj put' P, zadannyj spiskom iz N+1 nomerov uzlov v porjadke obhoda (nomer pervogo uzla sovpadaet s nomerom poslednego).

Primer fajla ishodnyh dannyh:

4 5
1 2 4 2 1 3 3 4 1 4
2 4 3 1 2

Chisla v ishodnom fajle razdeljajutsja probelami i (ili) simvolami perevoda stroki. Esli set' nevozmozhno narisovat' trebuemym obrazom, programma dolzhna vydat' na jekran sootvetstvujuschee soobschenie i zakonchit' rabotu. Dopuskaetsja chastichnoe reshenie zadachi, proverjajuschee tol'ko vozmozhnost' izobrazhenija shemy (15 ballov). Ishodnye dannye korrektny i ih proverka ne trebuetsja.

Predusmotrite vozmozhnost' spokojno razgljadet' Vashe tvorenie.

Ocenka zadachi: 40 ballov

Laboratorija intellektual'nyh sistem razrabotala novyj jazyk programmirovanija s nazvaniem LIST-95. Jazyk prednaznachen dlja raboty s dlinnymi spiskami. Edinstvennyj tip v jazyke - jeto spisok iz celyh chisel, ne prevoshodjaschih po modulju odnogo milliarda. Konstantami v jetom jazyke javljajutsja konechnye arifmeticheskie progressii (kotorye zadajutsja nachal'nym jelementom, raznost'ju i chislom jelementov). Raznost' progressii mozhet ravnjat'sja nulju, togda spisok budet sostojat' iz zadannogo kolichestva odinakovyh chisel. Edinstvennyj operator - jeto operator prisvaivanija, v pravoj chasti kotorogo stoit libo progressija, libo binarnaja operacija, operandami kotoroj mogut byt' tol'ko imena peremennyh. Dopustimymi javljajutsja sledujuschie operacii:

Sceplenie (konkatenacija) spiskov. Oboznachenie: A # B. Rezul'tat: spisok, poluchennyj pripisyvaniem jelementov spiska B v konec spiska A.

Slozhenie spiskov odinakovoj dliny. Oboznachenie: A + B. Rezul'tat: spisok, poluchennyj pojelementnym slozheniem jelementov spiskov A i B.

Umnozhenie spiskov odinakovoj dliny. Oboznachenie: A * B. Rezul'tat: spisok, poluchennyj pojelementnym umnozheniem jelementov spiskov A i B.

Progressii predstavljajutsja v jazyke tak: , a operator prisvaivanija tak: Peremennaja := Konstanta ili Peremennaja := Peremennaja Operacija Peremennaja. Peremennymi javljajutsja zaglavnye bukvy latinskogo alfavita. Programma sostoit iz odnogo ili neskol'kih operatorov prisvaivanija. Kazhdyj operator prisvaivanija zapisyvaetsja na otdel'noj stroke. Rezul'tatom raboty programmy na jazyke LIST-95 javljaetsja spisok, poluchennyj v poslednem operatore prisvaivanija.

Napishite programmu, kotoraja vvodit chislo N (1<=N<=1000000000), programmu na jazyke LIST-95 i opredeljaet znachenie N-go jelementa rezul'tirujuschego spiska.

Ishodnye dannye raspolozheny v tekstovom fajle (imja fajla vvoditsja s klaviatury) po sledujuschemu formatu. Pervaja stroka soderzhit chislo N. So vtoroj stroki i do konca fajla raspolozhena programma na jazyke LIST-95. Tekst programmy ne soderzhit probelov i pustyh strok. V konce poslednej stroki programmy simvolov perevoda stroki net.

Primechanija. Ishodnye dannye korrektny i ih proverka ne trebuetsja. Programma, zadannaja vo vhodnom fajle ispolnjaetsja korrektno, t.e. v pravyh chastjah prisvaivanij ispol'zujutsja tol'ko inicializirovannye peremennye i dliny operandov u operacij slozhenija i umnozhenija spiskov sovpadajut. Kolichestvo strok vo vhodnom fajle ne prevyshaet 100. Rezul'tat raboty programmy vyvoditsja na jekran.

Primer fajla ishodnyh dannyh:

 23
X:=<1,2,2000000>
A:=<2,2,2000000>
X:=X+X
A:=A#X

Dlja privedennogo vyshe primera programma dolzhna vydat', chto na 23-em stoit chislo 46.

Ogranichenie vremeni: 1 minuta na kazhdyj test.