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

Троицк, 23-28 марта 1995 года

Задачи

Задача 1. Рамки

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

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

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

Примечания:

Пример

входной файлoutput.txt
6 4
••••
•AAA
WWWA
WAWA
W•W•
WWW•
AW
AW

Система оценки

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

Задача 2. Что тут считать

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

Ввод чисел N и K осуществляется с клавиатуры, полученный результат выводится на экран. Корректность входных данных проверять не требуется.

Система оценки

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

Задача 3. Детектив

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

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

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

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

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

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

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

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

Длина имен не превышает 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 баллов.

Задача 4. Лягушка и комар

Лесное болото разделено на 8×8 одинаковых клеток. В некоторых клетках болота находятся кочки, а все остальные клетки с водой. На одной из кочек сидит лягушка, а над какой-то другой клеткой болота летает комар. Лягушка хочет съесть комара, а комар старается от нее улететь. Перемещаются лягушка и комар по очереди, первый ход - за лягушкой. За один прыжок лягушка перемещается на любую из кочек по горизонтали, вертикали или диагонали. Комар за один перелет перемещается на одну из 8 соседних клеток. Если лягушка в прыжке пролетает через клетку, над которой находится комар (или прыгает на клетку, над которой летает комар), то она съедает комара. Съев комара в последнем прыжке, лягушка может оказаться как в воде, так и на кочке

Требуется определить минимальное число прыжков для того, чтобы съесть комара, либо выдать сообщение, что комара съесть невозможно.

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

Входные данные программы расположены в текстовом ASCII-файле, имя которого вводится с клавиатуры.

В первых 8 строках файла находится матрица размером 8×8, задающая схему расположения кочек в виде нулей и единиц (0 - клетка с водой, 1 - кочка). Элементы матрицы в каждой строке записываются без пробелов. Далее содержится строка с координатами лягушки (x1, y1) и комара (x2, y2), где xi - номер строки, yi - номер столбца.

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

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

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

Выходной текстовый ASCII-файл с именем OUTPUT.TXT должен содержать сначала минимальное количество шагов, а затем первый возможный ход лягушки, задаваемый координатами кочки, на которую прыгает лягушка. Если комара съесть невозможно, то выходной файл должен содержать одну строку с сообщением "Невозможно".

Пример

входной файлвыходной файл
11111111
11111011
11101111
11111011
11110111
11011111
10111101
11111111
2 1 1 8  
2
2 7  

Примечания

  1. В выходном файле должен содержаться только один из возможных первых ходов лягушки.
  2. Лягушка перемещается только с кочки на кочку, т.к. при попадании в воду она теряет комара из вида.
  3. Исходные данные корректны, и их проверка не требуется.
  4. Решение задачи для случая, когда минимальное количество прыжков лягушки не превосходит трех, будет также оцениваться.
  5. Время тестирования каждого теста ограничено одной минутой.

Система оценки

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

Задача 5. Параллельные вычисления

Задана программа, состоящая из N операторов присваивания (1 ≤ N ≤ 15). Каждый оператор записывается в следующем виде: X=YopZ, где X, Y и Z - идентификаторы, состоящие из одной заглавной латинской буквы; op - символ одной из арифметических операций: "+" (сложение), "-" (вычитание), "*" (умножение) и "/" (деление).

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

Каждый оператор выполняется за один такт работы процессора. Чтобы синхронизировать работу процессоров введена команда "NOP", которая задерживает работу процессора на один такт. В процессе одновременной работы двух процессоров выполняемые операторы могут использовать только такие общие переменные, которые находятся в правых частях операторов присваивания (например, операторы "A=B+C" и "M=A+K" не могут выполняться одновременно).

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

Входные данные расположены в текстовом ASCII-файле, имя которго вводится с клавиатуры.

Каждый оператор находится на отдельной строке; файл не содержит пробелов и пустых строк; в конце последней строки файла символов конца строки нет.

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

Результат работы помещается в выходной текстовый ASCII-файл с именем OUTPUT.TXT.

В первую строку файла записывается искомое минимальное число тактов P.

Далее следуют P строк, в которых в две колонки выписаны программы для каждого процессора; колонки должны быть выровнены по левому краю.

Пример

входной файлвыходной файл
W=A+B
F=A+P
B=W/F
W=B*C
3
W=A+B   F=A+P
NOP     B=W/F
W=B*C   NOP       

Примечания

  1. Исходные данные корректны, и их проверка не требуется.
  2. Время тестирования каждого теста ограничено одной минутой.

Система оценки

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

Задача 6. Рандеву

Локаторы дальней космической связи замечают летящий в плоскости орбиты Земли неизвестный астероид с координатами (x, y). Астероид летит с постоянной скоростью, векторное значение которой равно (Vx, Vy). С Земли из точки с координатами (0, 0) немедленно стартует ракета с радиусом действия R (R > 0). Ракета летит по прямой с постоянной скоростью в пределах от 0 до W.

Требуется определить, может ли ракета подлететь вплотную к астероиду в пределах радиуса ее действия и найти вектор скорости ракеты, при котором время встречи ракеты с астероидом минимальное.

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

Входные данные расположены в текстовом ASCII-файле, имя которого вводится с клавиатуры.

В начале файла содержится число N - количество наборов исходных данных (тестов).

Далее расположены N наборов исходных данных; каждый набор - шесть вещественных чисел: X, Y, Vx, Vy, W, R.

Все числа в исходном файле разделяются пробелами и (или) символами перевода строки.

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

Результат работы помещается в выходной текстовый ASCII-файл с именем OUTPUT.TXT.

Для каждого набора исходных данных вывести с новой строки вектор скорости (Ux, Uy) и минимальное время встречи, либо сообщение "Встреча невозможна".

Пример

входной файлвыходной файл
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  
Встреча невозможна
3.0 -4.0 0.5  

Примечания

  1. Результат решения задачи должен быть вычислен с погрешностью не более 0.01.
  2. Влиянием Земли и всех космических объектов пренебречь.
  3. Ракета и астероид двигаются в одной плоскости.
  4. Исходные данные корректны, и их проверка не требуется.
  5. Общее время тестирования ограничено тремя минутами.

Система оценки

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