Sm. takzhe:


Rezul'taty olimpiady

  Sankt-Peterburgskie Olimpiady po Informatike

Zadachi komandnoj olimpiady shkol'nikov SPb 1994 goda

Zadacha A Zadacha B Zadacha C Zadacha D Zadacha E

Zadacha A

Imja fajla ishodnyh dannyh: A.IN
Imja vyhodnogo fajla: A.OUT
Kolichestvo testov: 1
Ogranichenie vremeni: 30 sekund

Chtoby avtomatizirovat' proverku kachestva programmnogo produkta, byli vyrabotany kriterii, po kotorym opredeljajutsja plohie i horoshie cherty programmy. Nekotorye kriterii kasalis' obschego stilja programmirovanija. V dannoj zadache trebuetsja najti znachenija dlja prostejshih iz jetih kriteriev.

Napishite programmu, kotoraja vvodit iz fajla ishodnyh tekst programmy na jazyke Pascal i opredeljaet:

Sledujuschaja informacija pomozhet vam vspomnit' strukturu programmy na jazyke Pascal. Tekst programmy zapisyvaetsja v svobodnom formate. Stroki mogut byt' proizvol'noj dliny. Tekst kommentarija nachinaetsja s simvola { i zakanchivaetsja simvolom }. Strokovaja konstanta nachinaetsja i zakanchivaetsja simvolom apostrofa '. Strokovaja konstanta ne mozhet raspolagat'sja na neskol'kih strokah. Dva apostrofa podrjad '' vnutri strokovoj konstanty oboznachajut odin simvol apostrofa i ne javljajutsja koncom ili nachalom strokovoj konstanty. Odnako pri podschete '' schitajutsja kak dva simvola. Figurnye skobki { i } vnutri strokovoj konstanty ne javljajutsja ogranichiteljami kommentarija, tak zhe, kak i apostrofy vnutri kommentarija ne javljajutsja ogranichiteljami strokovoj konstanty.

Fajl ishodnyh dannyh soderzhit pravil'nuju (ne soderzhaschuju sintaksicheskih oshibok) programmu na jazyke Pascal. Fajl ne soderzhit simvolov tabuljacii. Stroki mogut byt' skol' ugodno dlinnymi. Simvoly perevoda stroki pri podschete ne uchityvajutsja. Dlina fajla ishodnyh dannyh ne prevoshodit 64-h Kbajt.

Primer fajla ishodnyh dannyh:

program TEST;
    { razdel opisanija peremennyh:
    }
var i: integer;
    s: string;
begin
   s := 'Pechataem chislo '; {jeto kommentarij}
   for i := 1 to 5 do
      writeln (s, i);
   s := '{jeta stroka ne javljaetsja kommentariem}';
end.  {konec programmy TEST}

Primer vyvoda programmy


Kolichestvo strok v programme = 11
Obschee chislo simvolov v programme = 247
Kolichestvo pustyh strok v programme = 0
Kolichestvo kommentariev v programme = 3
Obschee chislo simvolov v kommentarijah = 73
Kolichestvo operatorov GOTO = 0

Zadacha B

Imja fajla ishodnyh dannyh: B.IN
Imja vyhodnogo fajla: B.OUT
Kolichestvo testov: 6
Ogranichenie vremeni: 60 sekund na ves' nabor testov

Dlja zadannogo N (1<=N<=1994) vychislit' znachenie vyrazhenija

1994**N

Fajl ishodnyh dannyh soderzhit odno ili neskol'ko chisel, razdelennyh probelami i (ili) simvolami perevoda stroki. Dlja kazhdogo takogo chisla vyvesti v vyhodnoj fajl s novoj stroki znachenie ukazannogo vyrazhenija.

Primer fajla ishodnyh dannyh

2 10

Primer vyvoda programmy

3976036
993691419595690831723569386546176

Zadacha C

Imja fajla ishodnyh dannyh: C.IN
Imja vyhodnogo fajla: C.OUT
Kolichestvo testov: 20
Ogranichenie vremeni: 30 sekund na ves' nabor testov

Dlja opredelenija togo, mogut li iteracii cikla vypolnjat'sja parallel'no (na vektornom komp'jutere) ispol'zuetsja analiz zavisimosti dannyh. Vasha zadacha provesti analiz zavisimosti dannyh dlja operatora cikla s operatorom prisvaivanija odnomernomu massivu.

Vo vhodnom fajle soderzhitsja nabor ciklov. Kazhdyj cikl soderzhit odin operator prisvaivanija, kotoryj vkljuchaet jelementy odnomernogo massiva A c linejnymi indeksami i schetchik cikla I. Dlja kazhdogo cikla trebuetsja opredelit' kakomu iz sledujuschih uslovij on udovletvorjaet:

Operator prisvaivanija zapisyvaetsja v vide

 A [expr] := expr2

gde v kachestve indeksov massiva A mogut byt' sledujuschie vyrazhenija:

n  I  I-m  I+m  n*I  n*I+m  n*I-m

Zdes' m i n - celye chisla v diapazone -32768..+32767. Vyrazhenie v pravoj chasti prisvaivanija javljaetsja arifmeticheskim vyrazheniem, zapisannym po pravilam jazyka Pascal. Vyrazhenie ne soderzhit strokovyh konstant i kommentariev. Vse vyrezki iz massiva A udovletvorjajut opisannym vyshe trebovanijam.

Operator cikla zadaetsja v vide LOOP mm,nn,pp. Cikl zadaet vypolnenie operatora prisvaivanija dlja kazhdogo I ot mm do nn s shagom pp. Esli pp ne zadano, to shag schitaetsja ravnym 1. Granicy i shag cikla javljajutsja celymi chislami v diapazone
-32768..+32767. Shag cikla pp<>0.

Operator mozhet byt' vypolnen parallel'no, esli posle prisvaivanija jelementu massiva A (levaja chast' prisvaivanija), ego znachenie ne ispol'zuetsja v pravoj chasti operatora. Analiz zavisimosti ne vypolnjaetsja, esli cikl rabotaet odin ili dva raza.

Ishodnye dannye

Fajl ishodnyh dannyh soderzhit odnu ili bolee strok, kazhdaja iz kotoryh soderzhit cikl s operatorom prisvaivanija v vide:

LOOP mm,nn,pp: A [expr] := expr2
ili
LOOP mm,nn: A [expr] := expr2

Dlina stroki fajla ishodnyh dannyh ne prevoshodit 80 simvolov.

Vyvod programmy

Dlja kazhdogo ishodnogo operatora cikla vyvesti v vyhodnoj fajl 2 stroki: sam operator i rezul'tat analiza zavisimosti dannyh:

Ne vypolnitsja ni razu
Vypolnitsja odin raz
Vypolnitsja dva raza
Parallel'noe ispolnenie
Trebuet posledovatel'nogo ispolnenija

Primer vyhodnogo fajla

LOOP 1,32767: A [I] := A [I]+1
Parallel'noe ispolnenie
LOOP 1,7: A [-2*I+50] := A [I-1]+A [I+40]
Trebuet posledovatel'nogo ispolnenija
LOOP 2,800,2: A [I] := -2.03E-17*A [2*I-1]+A [I]
Parallel'noe ispolnenie
LOOP 7,1,-1: A [I] := A [I+6]*3
Trebuet posledovatel'nogo ispolnenija
LOOP 2,-90,30: A [I] := 2
Ne vypolnitsja ni razu
LOOP 2,3: A [I] := A [I]*4.0
Vypolnitsja dva raza

Zadacha D

Imja fajla ishodnyh dannyh: D.IN
Imja vyhodnogo fajla: D.OUT
Kolichestvo testov: 4
Ogranichenie vremeni: 30 sekund na ves' nabor testov

Lentochnyj kletochnyj avtomat - jeto abstraktnaja vychislitel'naja mashina, na vhod kotoroj podaetsja skleennaja v kol'co lenta s simvolami. Jeta lenta javljaetsja takzhe edinstvennym zapominajuschim ustrojstvom avtomata. Avtomat rabotaet poshagovo soglasno tablice perehodov. Tablica perehodov opredeljaet mgnovennoe izmenenie soderzhimogo lenty za odin shag avtomata. Jelement tablicy perehodov zadaet novoe znachenie jachejki v zavisimosti ot ee soderzhimogo i soderzhimogo dvuh sosednih jacheek.

Zadano nachal'noe sostojanie lenty, kolichestvo shagov avtomata i tablica perehodov. Trebuetsja promodelirovat' rabotu zadannogo avtomata i opredelit' soderzhimoe lenty cherez zadannoe chislo shagov.

Fajl ishodnyh dannyh soderzhit odin ili neskol'ko naborov ishodnyh dannyh, razdelennyh pustoj strokoj.

V pervoj stroke nabora ishodnyh dannyh soderzhitsja nachal'noe sostojanie lenty (ishodnye dannye avtomata). Dopustimymi simvolami na lente javljajutsja bol'shie i malye latinskie bukvy, cifry i simvol podcherkivanija. Dlina lenty ne prevoshodit 20-ti simvolov i ne men'she 3-h simvolov.

Vo vtoroj stroke nabora ishodnyh dannyh soderzhitsja chislo shagov avtomata N. N - celoe chislo ot 0 do 100.

V sledujuschih strokah nabora ishodnyh dannyh soderzhitsja opisanie tablicy perehodov. Opisanie sostoit iz pravil, kotorye zapisyvajutsja na otdel'nyh strokah v vide:

iAj -> B

Takoe pravilo opredeljaet, chto esli jachejka soderzhit simvol A, sosednjaja jachejka sleva soderzhit simvol i, sosednjaja jachejka sprava soderzhit simvol j, to na sledujuschem shage znacheniem jachejki budet simvol B.

U pervoj jachejki sosedom sleva javljaetsja poslednjaja jachejka, a u poslednej jachejki sosedom sprava javljaetsja pervaja. Esli dlja jachejki i ee sosedej net podhodjaschego pravila, to ee soderzhimoe na dannom shage ne izmenjaetsja.

Dlja kazhdogo nabora ishodnyh dannyh vyvesti v vyhodnoj fajl s novoj stroki soderzhimoe lenty avtomata cherez zadannoe chislo shagov.

Primer fajla ishodnyh dannyh

100010011
2
101 -> 1
001 -> 1
010 -> 0
110 ->> 0

ABC
6
ADC -> Q

Primer vyvoda programmy

001001110
ABC

Primechanie

Vse ishodnye dannye korrektny i ih proverka ne trebuetsja. Dlina fajla ishodnyh dannyh ne prevoshodit 64-h Kbajt.

Zadacha E

Imja fajla ishodnyh dannyh: E.IN
Imja vyhodnogo fajla: E.OUT
Kolichestvo testov: 5
Ogranichenie vremeni: 30 sekund na ves' nabor testov

Zadano celoe chislo N (1<=N<=1000000). Trebuetsja najti naimen'shee natural'noe chislo s proizvedeniem cifr N.

Ishodnyj fajl soderzhit odno ili neskol'ko chisel, razdelennyh probelami i (ili) simvolami perevoda stroki. Dlja kazhdogo takogo chisla vyvesti v vyhodnoj fajl s novoj stroki iskomoe minimal'noe chislo. Esli takogo chisla ne suschestvuet, vyvesti 0.

Primer fajla ishodnyh dannyh

10
13

Primer vyvoda programmy

25
0
Используются технологии uCoz