Pestrye chisla
	Avtory: S.Volchenkov (g.Jaroslavl')

K-znachnoe chislo (K< =10) nazyvaetsja pestrym, esli vse ego cifry razlichny. Pri jetom nol' ne mozhet byt' pervoj cifroj.

Trebuetsja

• nahodit maksimal'no dlinnuju cepochku pestryh K-znachnyh chisel, v kotoroj kazhdoe sledujuschee chislo v dva raza bol'she predyduschego;
• nahodit vse takie cepochki maksimal'noj dliny.

Vhodnye dannye

Chislo vvoditsja s klaviatury

Vyhodnye dannye

Primechanija

Zadacha ocenivaetsja iz 20 ballov. Vremja testirovanija ne bolee 1 minuty.

	Transljator
	Avtory: A.Suhanov (S.-Peterburg), E.Andreeva (Moskva)

Rassmatrivajutsja dva algoritmicheskih jazyka: Beta i Psi (opisanija jazykov prilagajutsja nizhe). Trebuetsja perevesti programmu s jazyka Beta na jazyk Psi. Rezul'tirujuschaja programma na jazyke Psi dolzhna realizovyvat' tot zhe samyj algoritm, chto i ishodnaja programma na jazyke Beta.

Primer vozmozhnogo perevoda:

10 N=5
20 SUM=SUM+N
35 N=N-1
40 IF N> 0 THEN WALKTO
70 TYPE Sum
999 END
 

DEF N, Var, C;
START
   Var := 0; c := 1;
   WHILE c <  6 DO
      IF c = 1 THEN N:= 5; c:=c+1; FI;
      IF c = 2 THEN Var:=Var+N; c:=c+1; FI;
      IF c = 3 THEN N:=N-1; c := c+1; FI;
      IF c = 4 THEN
         IF N> 0 THEN c := 1; FI;
         c := c+1;
      FI;
      IF c = 5 THEN Print (Var);
         c := c+1;
      FI;
   OD;
FINISH
 

Primechanija

1. Tekst ishodnoj programmy sostoit ne bolee, chem iz 100 strok, a kazhdaja stroka soderzhit ne bolee 80 simvolov.
2. Tekst ishodnoj programmy ne soderzhit sintaksicheskih oshibok.
3. Programmy na jazyke Psi, soderzhaschie sintaksicheskie oshibki, na sootvetstvie ishodnoj programme proverjat'sja ne budut.
4. Zadacha ocenivaetsja iz 40 ballov. Reshenija zadachi dlja sluchaja, kogda v ishodnoj programme otsutstvujut operatory WALKTO, takzhe budut ocenivat'sja.
5. Vremja testirovanija programmy ogranicheno.

Opisanie jazyka Beta

• Programma na jazyke Beta sostoit iz posledovatel'nosti operatorov; kazhdyj operator raspolagaetsja v otdel'noj stroke i emu vsegda predshestvuet metka (natural'noe chislo < = 10000).
• Vse metki razlichny i uporjadocheny po vozrastaniju, operator otdeljaetsja ot metki probelami.
• Imja peremennoj sostoit iz odnoj ili neskol'kih latinskih bukv (ne bolee 8 bukv), bol'shie i malen'kie bukvy nerazlichimy. Imena peremennyh ne mogut sovpadat' s kljuchevymi slovami, iz kotoryh strojatsja operatory.
• Ispolnenie programmy nachinaetsja s pervogo operatora.
• Poslednim v tekste programmy vsegda javljaetsja operator END.
• Znachenija peremennyh, konstanty i znachenija vyrazhenij v jazyke javljajutsja celochislennymi i nahodjatsja v diapazone ot -32768 do 32767.
• V nachale raboty programmy znachenija vseh peremennyh ravny nulju.
• Programma mozhet soderzhat' lishnie razdelitel'nye probely. Imena peremennyh, imena operatorov, metki i konstanty zapisyvajutsja bez probelov.
• Tekst programmy ne soderzhit pustyh strok.

Nizhe perechisleny operatory jazyka Beta:

Opisanie jazyka Psi

• Programmy na jazyke Psi sostoit iz opisanija peremennyh i tela programmy.
• Opisanie peremennyh nachinaetsja so slova DEF, za kotorym sledujut imena vseh peremennyh, ispol'zuemyh v programme. Peremennye v spiske razdeljajutsja zapjatymi i ne mogut povtorjat'sja, posle poslednej peremennoj stavitsja simvol ; (tochka s zapjatoj).
• Telo programmy sostoit iz posledovatel'nosti operatorov, zakljuchennyh mezhdu slovami START i FINISH.
• Operatory razdeljajutsja simvolom ; (tochka s zapjatoj).
• Ponjatija peremennoj, konstanty, vyrazhenija i uslovija sovpadajut s sootvetstvujuschimi ponjatijami v jazyke Beta.
• Programma mozhet soderzhat' pustye stroki i lishnie razdelitel'nye probely.
• Imena peremennyh, imena operatorov, metki i konstanty zapisyvajutsja bez probelov. Imena peremennyh ne mogut sovpadat' s kljuchevymi slovami, iz kotoryh strojatsja operatory.
• Peremennye v nachale raboty programmy prinimajut sluchajnye znachenija.

Nizhe perechisleny operatory jazyka Psi:

	Shlangi
	Avtory: V.Prohorov

Ustanovka sostoit iz ustrojstv A i B, soedinennyh mezhdu soboj lezhaschimi na zemle shlangami. Kazhdoe ustrojstvo imeet N patrubkov, pronumerovannyh ot 1 do N kak izobrazheno na ris. 1. Kazhdyj iz shlangov soedinjaet patrubki oboih ustrojstv s odinakovymi nomerami. Shlangi mogut raspolagat'sja drug otnositel'no druga proizvol'nym obrazom s edinstvennym ogranicheniem: pri peremeschenii tochki vdol' ljubogo shlanga ot A k V rasstojanie ot nee do A tol'ko vozrastaet. Nomer shlanga sovpadaet s nomerom patrubka ustrojstva A.

ris.1

Dlja uluchshenija propusknoj sposobnosti shlangov bylo resheno provesti pereukladku shlangov tak, chtoby sdelat' ih neperesekajuschimisja (sm. ris. 2). Dlja jetogo obhodchiku poruchili zapisat' informaciju o tochkah peresechenij shlangov po napravleniju dvizhenija ot ustrojstva A k ustrojstvu B. Dlja kazhdogo ocherednogo peresechenija obhodchik zapisal pary chisel: nomer shlanga, lezhaschego snizu, i nomer shlanga, raspolozhennogo sverhu, sootvetstvenno (v kazhdoj tochke peresekajutsja ne bolee dvuh shlangov.

ris.2

Trebuetsja

Napisat' programmu, kotoraja po zadannym N (schitat' N< 3) i proizvol'noj posledovatel'nosti peresechenij shlangov opredeljala by:

(a) net li zavedomyh oshibok v zapisi obhodchika;
(b) vozmozhno li obespechit' neperesechenie shlangov putem ih ljubyh peremeschenij bez otsoedinenija ot patrubkov.

Vhodnye dannye

Vhodnye dannye raspolagajutsja v fajle INPUT.TXT. V pervoj stroke jetogo fajla nahoditsja chislo, vo vtoroj - zapisannye cherez probel vyshenazvannye pary natural'nyh chisel.

Dannye vo vhodnom fajle vsegda sootvetstvujut opisannomu formatu fajla INPUT.TXT.

Dlja ris.1 vhodnye dannye v fajle INPUT.TXT imejut vid:

3
2 1 3 1 2 3 3 2 1 3 1 2

Vyhodnye dannye

Rezul'taty reshenija dolzhny vyvodit'sja na jekran monitora. Pri jetom dopustimy sledujuschie soobschenija:

(a) Uncorrect input data - pri obnaruzhenii zavedomyh oshibok v zapisi obhodchika;
(b) Correct input data - pri otsutstvii zavedomyh oshibok v zapisi obhodchika;
(v) Solvable - pri vozmozhnosti obespechit' neperesechenie shlangov;
(g) Unsolvable - pri nevozmozhnosti obespechit' neperesechenie shlangov.

Dlja privedennogo vyshe primera fajla INPUT.TXT programma dolzhna vydat' soobschenija:

Correct input data
Unsolvable

Primechanija

• Zadacha ocenivaetsja iz 40 ballov
• Ocenka osuschestvljaetsja, ishodja iz dvuh urovnej slozhnosti: dlja N=2 i dlja N=3.
• Vremja testirovanija programmy - ne bolee 1 min.

	Kollekcii
	Avtory: R.Prohorov

V gorode otkrylsja klub filatelistov, chlenami kotorogo stremjatsja stat' M chelovek. Na kazhdom zasedanii v klub prinimajut odnogo novogo filatelista. Chtoby byt' prinjatym, kazhdyj pretendent dolzhen pred''javit' svoju kollekciju marok, v kotoroj net odinakovyh jekzempljarov i kotoraja hot' chem-to otlichaetsja ot kollekcij chlenov kluba. Dlja jetogo kazhdyj novyj pretendent idet v magazin, gde prodajutsja N vidov pochtovyh marok (3< =N< =10000 po cenam X1< =X2 < =...< =XN (1< =Xi < =10000, i=1..N), i pokupaet sootvetstvujuschij nabor marok, starajas' potratit' minimal'nuju summu deneg.

Naprimer, pri assortimente iz 5 marok po cenam 3, 4, 6, 10, 15 kollekcionery budut pokupat' ih v predstavlennom nizhe porjadke:

Trebuetsja

Napisat' programmu, kotoraja po suschestvujuschim v magazine cenam na marki opredeljaet minimal'nye summy deneg, kotorye neobhodimo zatratit' kazhdomu kollekcioneru s uchetom porjadka vstuplenija ego v klub.

Vhodnye dannye

Vhodnye dannye zadajutsja v fajle INPUT.TXT v sledujuschem porjadke: v pervoj stroke - N, vo vtoroj - M, v posledujuschih N strokah ukazyvajutsja ceny marok v neubyvajuschem porjadke.

Vyhodnye dannye Rezul'tat reshenija zadachi zapisyvaetsja v fajl s imenem OUTPUT.TXT. Kazhdaja iz M strok jetogo fajla soderzhit sootvetstvujuschuju iskomuju summu zatrachennyh deneg dlja kazhdogo kollekcionera. Jeti M summ dolzhny raspolagat'sja v neubyvajuschem porjadke.

Primer vhodnogo fajla i sootvetstvujuschego emu vyhodnogo fajla priveden nizhe:

INPUT.TXT:

5 10 3 4 6 10 15  

OUTPUT.TXT:

3 4 6 7 9 10 10 13 14 15

Primechanija:

1. N, M, Xi - natural'nye chisla, N< =M< =2**N-1, M< =15000;
2. Testirovanie zadachi budet osuschestvljat'sja avtomaticheski, tak chto nikakih otstuplenij ot dannogo formata vvoda/vyvoda byt' ne dolzhno;
3. Vremja testirovanija ne bolee 30 sek;
4. Zadacha ocenivaetsja v 34 balla.

	Detskaja igra so spichkami
	Avtory: A.Ovsjannikov, T.Ovsjannikova

N spichek (N< =15) na ploskosti obrazuet figuru kak, naprimer, izobrazheno na ris.1:

ris.1

Nazovem figuru B simmetrichnoj figure A, esli suschestvuet takaja os' simmetrii, chto otobrazhaja otnositel'no ee ishodnuju figuru A, my poluchim figuru B. Ochevidno, dlja ljuboj zadannoj figury mozhno postroit' simmetrichnuju ej, perelozhiv nekotorye spichki. V processe perekladyvanija spichki lomat' nel'zja. Nakladyvanie spichek drug na druga ne privodit k narusheniju uslovija ih raspolozhenija na ploskosti. Naprimer, iz figury ris. 1. mogut byt' polucheny figury, izobrazhennye na ris.2 i ris.3:

ris.2	ris.3

Trebuetsja

Napisat' programmu, dlja opredelenija simmetrichnoj figury, poluchajuschejsja iz ishodnoj perekladyvaniem minimal'nogo kolichestva spichek.

Vhodnye dannye

Ishodnoe raspolozhenie spichek zadaetsja v fajle s imenem INPUT.TXT. Pervaja stroka fajla soderzhit chislo N, dalee sledujut N strok, soderzhaschih koordinaty koncov kazhdoj spichki: (x1,y1);(x2,y2).

Vyhodnye dannye

Rezul'tat raboty programmy zapisyvaetsja v fajl s imenem OUTPUT.TXT, soderzhaschij v pervoj stroke kolichestvo perelozhennyh spichek, dalee sledujut N strok s koordinatami koncov spichek v rezul'tirujuschej figure.

Naprimer, dlja figury na ris.1 resheniem javljaetsja figura na ris. 2. Sootvetstvujuschie im fajly INPUT.TXT i OUTPUT.TXT privedeny nizhe.

INPUT.TXT:

3
1 0 1 5
2 4 5 0
5 0 8 4

OUTPUT.TXT

1
9 0 9 5
2 4 5 0
5 0 8 4

Primechanija

1. Zavedomo izvestno, chto koordinaty koncov spichek ishodnoj i rezul'tirujuschej figury - celye chisla (-100< =x< =100, -100< =y< =100).
2. Vremja testirovanija ogranichenno 2 minutami.
3. Zadacha ocenivaetsja v 33 balla.

	Stena
	Avtory: A.Suhanov (S.-Peterburg), E.Andreeva (Moskva)

Stena dlja sostoit iz M rjadov po N odinakovyh kirpichej v kazhdom. Kazhdyj posledujuschij rjad smeschen otnositel'no predyduschego na 1/2 kirpicha (sm. ris. 1). Chetnye rjady sverhu smeschajutsja vlevo, a nechetnye - vpravo. Konfiguracija iz kirpichej javljaetsja ustojchivoj, esli kazhdyj kirpich opiraetsja, po krajnej mere, na odin kirpich v nizhelezhaschim rjadu. Ochevidno, chto iz zadannoj konstrukcii mozhno udalit' nekotorye kirpichi bez poteri ee ustojchivosti. Na ris. 2 izobrazhen primer vozmozhnoj konstrukcii dlja steny na ris. 1.

Trebuetsja

Napisat' programmu, kotoraja po zadannym M i N (0<M,N< =1000) i nahodit konstrukciju, poluchajuschujusja iz ishodnoj putem udalenija po vozmozhnosti maksimal'nogo kolichestva kirpichej, chtoby verhnij rjad ostalsja bez izmenenija, a konstrukcija ne poterjala ustojchivost'.

Vhodnye dannye

Vhodnoj fajl s imenem INPUT.TXT soderzhit kolichestvo rjadov M i shirinu steny N.

Vyhodnye dannye

V vyhodnoj fajl s imenem OUTPUT.TXT vyvesti kolichestvo ostavshihsja kirpichej i konfiguraciju steny. Ostavshiesja kirpichi perechisljajutsja nachinaja s verhnego rjada, sleva napravo v kazhdom rjadu (numeracija v kazhdom rjadu nachinaetsja s edinicy). Spisok kirpichej kazhdogo rjada dolzhen zakanchivat'sja chislom 0. Vse chisla v vyhodnom fajle dolzhny razdeljat'sja probelami i (ili) simvolami perevoda stroki.

Primer fajla ishodnyh dannyh INPUT.TXT dlja ris. 1:

4 5

Primer vyhodnogo fajla OUTPUT.TXT (sm. ris. 2):

13
1 2 3 4 5 0
2 4 5 0
2 3 5 0
3 5 0

ris.1	ris.2

Primechanija

• Zadacha ocenivaetsja v 33 balla.
• Programmy, vydajuschie pravil'nye, no ne optimal'nye reshenija takzhe budut ocenivat'sja.
• Vremja testirovanija ogranicheno 1 minutoj.