VII Всероссийская олимпиада школьников по информатике

г. Троицк Московской области, 23-28 марта 1995 года

 

Задача 1

РАМКИ

Имеется текстовый экран из M строк и N столбцов (3? M,N? 100). Первоначально экран заполнен символом "•" (ASCII-код 249). На этом экране одна за другой рисуются прямоугольные рамки толщиной в один символ. Каждая рамка рисуется при помощи своего символа, являющегося заглавной буквой латинского алфавита. При рисовании рамки ее символы замещают на экране ранее изображенные. Рамки нарисованы таким образом, что у каждой рамки видна хотя бы одна пара противолежащих углов. Требуется по данному изображению на экране определить, возможно ли однозначно восстановить последовательность рисования рамок и 1) если восстановление однозначно, определить требуемую последовательность; 2) если восстановление неоднозначно, определить две различные возможные последовательности рисования рамок.

Исходные данные программы расположены в текстовом ASCII-файле, имя которого вводится с клавиатуры. Первая строка исходного файла содержит размеры экрана M и N. Далее расположено M строк по N символов в каждой, задающих изображение на экране.

Результат работы программы выводится одновременно на экран и в текстовый ASCII-файл с именем OUTPUT.TXT. Первая строка содержит одну из возможных последовательностей рисования рамок, заданную перечислением имен рамок без пробелов. Вторая строка повторяет первую, если восстановление однозначно, либо содержит другую возможную последовательность, если восстанвление неоднозначно.

Примечания: Заданное во входном файле изображение заведомо можно получить последовательным рисованием рамок. Каждая сторона рамки состоит не менее, чем из 3 символов. Рамки не могут рисоваться за пределами экрана. Исходные данные корректны, и их проверка не требуется.

Пример файла исходных данных:

6 4

• • • •

• A A A

W W W A

W A W A

W • W •

W W W •

Пример выходного файла OUTPUT.TXT для приведенного примера:

AW

AW

Максимальная оценка задачи - 30 баллов

Задача 2

ЧТО ТУТ СЧИТАТЬ?

Задано натуральное десятичное число N (N? 1.000.000.000). Написать программу вычисления количества принадлежащих диапазону от 1 до N чисел, в двоичном представлении которых содержится ровно K значащих нулей. Например, для N=18 и K=3 таких чисел - 3 (8, 17, 18).

Технические требования:

- ввод чисел N и K осуществляется с клавиатуры,

- полученный результат выводится на экран.

Технические ограничения:

- корректность входных данных не проверяется,

- время тестирования ограничено

Максимальная оценка задачи - 30 баллов

 

 

Задача 3

ДЕТЕКТИВ

Из городского музея был похищен крупный алмаз. Возглавивший следствие майор Пронин исследовал место преступления и выяснил следующее.

Музей состоит из цепочки залов с номерами от 1 до n (n? 10). Алмаз находился в зале k. Посетители (их не более 10) проходили по залам в соответствии с их номерами, не возвращаясь назад. Размеры залов таковы, что посетитель затрачивал на проход зала не меньше минуты. В некоторых залах находились смотрители (их не более 10), которые не могли похитить камень. В зале, где находился алмаз, смотрителя не было. Смотрители замечали не всех посетителей, которые проходили по залу, но уж если смотритель заметил посетителя, то он обязательно запоминал время, когда он его увидел, с точностью до минуты. Посетители музея, разглядывая экспонаты, не всегда обращали внимание на остальных посетителей, но уж если посетитель обращал на кого-то внимание, то он запоминал время и место (номер зала) его нахождения.

Предварительное расследование позволило майору Пронину определить промежуток времени, когда мог быть похищен алмаз. Он также установил, что преступник действовал в одиночку, мог совершить кражу, только если находился в этот момент в зале один, и на допросе мог дать ложные показания. Осталось выяснить имя преступника.

С этой целью майор Пронин допросил смотрителей и посетителей и составил протокол, содержащий информацию о том, кто, кого, когда и где видел.

Требуется написать программу, которая по всей имеющейся у майора Пронина информации определяет круг посетителей, которые могли совершить преступление.

Входные данные

Входные данные вводятся из файла в следующей последовательности:

n k - количество залов, номер зала, где был алмаз

t1 t2 - промежуток времени, когда произошло похищение

m - число смотрителей

имя_смотрителя_1

имя_смотрителя_2

...

имя_смотрителя_m

p - число последующих строк в файле

кто_1 кого_1 когда_1 номер_зала_1

кто_2 кого_2 когда_2 номе_рзала_2

...

кто_p кого_p когда_p номер_зала_p

Имена смотрителей и посетителей записываются русскими буквами.

Длина имен не превышает 20 символов.

Пример файла

4 2

9:20 10:30

1

БабаНастя

5

БабаНастя ПоручикРжевский 10:15 1

АгентСидоров ИностранныйШпион 11:21 1

АгентСидоров ИностранныйШпион 11:22 2

АгентСидоров ИностранныйШпион 11:22 3

АгентСидоров ИностранныйШпион 11:24 4

Программа должна запрашивать имя входного файла с клавиатуры.

Максимальная оценка задачи - 40 баллов

 

Caaa?a 4.

Eyaooea e Eiia?

Eaniia aieioi ?acaaeaii ia 8? 8 iaeiaeiauo eeaoie. A iaeioi?uo eeaoeao aieioa iaoiayony ei?ee, a ana inoaeuiua eeaoee n aiaie. Ia iaiie ec ei?ae neaeo eyaooea, a iaa eaeie-oi a?oaie eeaoeie aieioa eaoaao eiia?. Eyaooea oi?ao nuanou eiia?a, a eiia? noa?aaony io iaa oeaoaou. Ia?aiaua?ony eyaooea e eiia? ii i?a?aae, ia?aue oia - ca eyaooeie. Ca iaei i?u?ie eyaooea ia?aiauaaony ia e?ao? ec ei?ae ii ai?eciioaee, aa?oeeaee eee aeaaiiaee. Eiia? ca iaei ia?aeao ia?aiauaaony ia iaio ec 8 ninaaieo eeaoie. Anee eyaooea a i?u?ea i?ieaoaao ?a?ac eeaoeo, iaa eioi?ie iaoiaeony eiia? (eee i?uaaao ia eeaoeo, iaa eioi?ie eaoaao eiia?), oi iia nuaaaao eiia?a. Nuaa eiia?a a iineaaiai i?u?ea, eyaooea ii?ao ieacaouny eae a aiaa, oae e ia ei?ea.

O?aaoaony ii?aaaeeou ieieiaeuiia ?enei i?u?eia aey oiai, ?oiau nuanou eiia?a, eeai auaaou niiauaiea, ?oi eiia?a nuanou iaaicii?ii.

Aoiaiua aaiiua

1. Aoiaiua aaiiua i?ia?aiiu ?aniiei?aiu a oaenoiaii ASCII-oaeea, eiy eioi?iai aaiaeony n eeaaeaoo?u.

2. A ia?auo 8 no?ieao oaeea iaoiaeony iao?eoa ?acia?ii 8? 8, caaa?uay noaio ?aniiei?aiey ei?ae a aeaa ioeae e aaeieo (0 - eeaoea n aiaie, 1 - ei?ea). Yeaiaiou iao?eou a ea?aie no?iea caienuaa?ony aac i?iaaeia. Aaeaa niaa??eony no?iea n eii?aeiaoaie eyaooee (X1, Y1) e eiia?a (X2, Y2), aaa Xi - iiia? no?iee, Yi - iiia? noieaoa.

I?eia? oaeea enoiaiuo aaiiuo:

11111111

11111011

11101111

11111011

11110111

11011111

10111101

11111111

2 1 1 8

Auoiaiua aaiiua

Auoiaiie oaenoiaue ASCII-oaee n eiaiai OUTPUT.TXT aie?ai niaa??aou nia?aea ieieiaeuiia eiee?anoai oaaia, a caoai ia?aue aicii?iue oia eyaooee, caaaaaaiue eii?aeiaoaie ei?ee, ia eioi?o? i?uaaao eyaooea. Anee eiia?a nuanou iaaicii?ii, oi auoiaiie oaee aie?ai niaa??aou iaio no?ieo n niiauaieai "Iaaicii?ii".

I?eia? auoiaiiai oaeea OUTPUT.TXT aey i?eaaaaiiiai i?eia?a:

2

2 7

I?eia?aiey:

1. A auoiaiii oaeea aie?ai niaa??aouny oieuei iaei ec aicii?iuo ia?auo oiaia eyaooee.

2. Eyaooea ia?aiauaaony oieuei n ei?ee ia ei?eo, o.e. i?e iiiaaaiee a aiao iia oa?yao eiia?a ec aeaa.

3. Enoiaiua aaiiua ei??aeoiu, e eo i?iaa?ea ia o?aaoaony.

4. ?aoaiea caaa?e aey neo?ay, eiaaa ieieiaeuiia eiee?anoai i?u?eia eyaooee ia i?aainoiaeo o?ao, aoaao oae?a ioaieaaouny.

5. A?aiy oanoe?iaaiey ea?aiai oanoa ia?aie?aii iaiie ieiooie.

Iaeneiaeuiay ioaiea caaa?e - 40 aaeeia

 

Caaa?a 5.

Ia?aeeaeuiua au?eneaiey

Caaaia i?ia?aiia, ninoiyuay ec N iia?aoi?ia i?enaaeaaiey (1? N? 15). Ea?aue iia?aoi? caienuaaaony a neaao?uai aeaa:

X=YopZ

aaa X, Y, e Z - eaaioeoeeaoi?u, ninoiyuea ec iaiie caaeaaiie eaoeineie aoeau;

op - neiaie iaiie ec a?eoiaoe?aneeo iia?aoee: "+" (nei?aiea), "-" (au?eoaiea), "*" (oiii?aiea) e "/" (aaeaiea)

O?aaoaony ?ani?aaaeeou iia?aoi?u caaaiiie i?ia?aiiu ia?ao aaoiy iaeiaeiauie i?ioanni?aie n iauae iaiyou? oae, ?oiau iauaa a?aiy auiieiaiey auei ieieiaeuiui, a niune i?ia?aiiu ia eciaieeny.

Ea?aue iia?aoi? auiieiyaony ca iaei oaeo ?aaiou i?ioanni?a. ?oiau neio?iiece?iaaou ?aaioo i?ioanni?ia aaaaaia eiiaiaa "NOP", eioi?ay caaa??eaaao ?aaioo i?ioanni?a ia iaei oaeo. A i?ioanna iaiia?aiaiiie ?aaiou aaoo i?ioanni?ia auiieiyaiua iia?aoi?u iiaoo eniieuciaaou oieuei oaeea iauea ia?aiaiiua, eioi?ua iaoiayony a i?aauo ?anoyo iia?aoi?ia i?enaaeaaiey (iai?eia?, iia?aoi?u "A=B+C" e "M=A+K" ia iiaoo auiieiyouny iaiia?aiaiii).

Aoiaiua aaiiua

1. Aoiaiua aaiiua ?aniiei?aiu a oaenoiaii ASCII-oaeea, eiy eioi?ai aaiaeony n eeaaeaoo?u.

2. Ea?aue iia?aoi? iaoiaeony ia ioaaeuiie no?iea; oaee ia niaa??eo i?iaaeia e ionouo no?ie; a eiioa iineaaiae no?iee oaeea neiaieia eiioa no?iee iao.

I?eia? oaeea enoiaiuo aaiiuo:

W=A+B

F=A+P

B=W/F

W=B*C

Auoiaiua aaiiua

1. ?acoeuoao ?aaiou iaycaoaeuii iiiauaaony a auoiaiie oaenoiaue ASCII-oaee n eiaiai OUTPUT.TXT.

2. A ia?ao? no?ieo oaeea caienuaaaony eneiiia ieieiaeuiia ?enei oaeoia P.

3. Aaeaa neaao?o P no?ie, a eioi?uo a aaa eieiiee auienaiu i?ia?aiiu aey ea?aiai i?ioanni?a; eieiiee aie?iu auou au?iaiaiu ii eaaiio e?a?.

4. I?eia? auoiaiiai oaeea OUTPUT.TXT aey i?eaaaaiiiai i?eia?a:

W=A+B F=A+P

NOP B=W/F

W=B*C NOP

I?eia?aiey:

1. Enoiaiua aaiiua ei??aeoiu, e eo i?iaa?ea ia o?aaoaony.

2. A?aiy oanoe?iaaiey ea?aiai oanoa ia?aie?aii iaiie ieiooie.

Iaeneiaeuiay ioaiea caaa?e - 30 aaeeia

Caaa?a 6.

?aiaaao

Eieaoi?u aaeuiae einie?aneie nayce caia?a?o eaoyuee a ieineinoe i?aeou Caiee iaecaanoiue anoa?iea n eii?aeiaoaie (x,y). Anoa?iea eaoeo n iinoiyiiie nei?inou?, aaeoi?iia cia?aiea eioi?ie ?aaii (Vx, Vy). N Caiee ec oi?ee n eii?aeiaoaie (0,0) iaiaaeaiii noa?ooao ?aeaoa n ?aaeonii aaenoaey R (R>0). ?aeaoa eaoeo ii i?yiie n iinoiyiiie nei?inou? a i?aaaeao io 0 ai W.

O?aaoaony ii?aaaeeou, ii?ao ee ?aeaoa iiaeaoaou aieioio? e anoa?ieao a i?aaaeao ?aaeona aa aaenoaey e iaeoe aaeoi? nei?inoe ?aeaou, i?e eioi?ii a?aiy ano?a?e ?aeaou n anoa?ieaii ieieiaeuiia.

Aoiaiua aaiiua

1. Aoiaiua aaiiua ?aniiei?aiu a oaenoiaii ASCII-oaeea, eiy eioi?iai aaiaeony n eeaaeaoo?u.

2. A ia?aea oaeea niaa??eony ?enei N - eiee?anoai iaai?ia enoiaiuo aaiiuo (oanoia).

3. Aaeaa ?aniiei?aiu N iaai?ia enoiaiuo aaiiuo; ea?aue iaai? - oanou aauanoaaiiuo ?enae: X, Y, Vx, Vy, W, R.

4. Ana ?enea a enoiaiii oaeea ?acaaey?ony i?iaaeaie e (eee) neiaieaie ia?aaiaa no?iee.

I?eia? oaeea enoiaiuo aaiiuo:

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

Auoiaiua aaiiua

1. ?acoeuoao ?aaiou iiiauaaony a auoiaiie oaenoiaue ASCII-oaee n eiaiai OUTPUT.TXT.

2. Aey ea?aiai iaai?a enoiaiuo aaiiuo auaanoe n iiaie no?iee aaeoi? nei?inoe (Ux,Uy) e ieieiaeuiia a?aiy ano?a?e, eeai niiauaiea "Ano?a?a iaaicii?ia".

I?eia? auoiaiiai oaeea OUTPUT.TXT aey i?eaaaaiiiai i?eia?a:

Ano?a?a iaaicii?ia

3.0 -4.0 0.5

I?eia?aiey:

1. ?acoeuoao ?aoaiey caaa?e aie?ai auou au?eneai n iia?aoiinou? ia aieaa 0.01.

2. Aeeyieai Caiee e anao einie?aneeo iauaeoia i?aiaa?a?u.

3. ?aeaoa e anoa?iea aaeaa?ony a iaiie ieineinoe.

4. Enoiaiua aaiiua ei??aeoiu, e eo i?iaa?ea ia o?aaoaony.

5. Iauaa a?aiy oanoe?iaaiey ia?aie?aii o?aiy ieiooaie.

Iaeneiaeuiay ioaiea caaa?e - 30 aaeeia