Имеется текстовый экран из 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 баллов.
Задано натуральное десятичное число N (N ≤ 109). Написать программу вычисления количества принадлежащих диапазону от 1 до N чисел, в двоичном представлении которых содержится ровно K значащих нулей. Например, для N = 18 и K = 3 таких чисел - 3 (8, 17, 18).
Ввод чисел N и K осуществляется с клавиатуры, полученный результат выводится на экран. Корректность входных данных проверять не требуется.
Максимальная оценка за задачу - 30 баллов.
Из городского музея был похищен крупный алмаз. Возглавивший следствие майор Пронин исследовал место преступления и выяснил следующее.
Музей состоит из цепочки залов с номерами от 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 баллов.
Лесное болото разделено на 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 |
Максимальная оценка за задачу - 40 баллов.
Задана программа, состоящая из 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 |
Максимальная оценка за задачу - 30 баллов.
Локаторы дальней космической связи замечают летящий в плоскости орбиты Земли неизвестный астероид с координатами (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 |
Максимальная оценка за задачу - 30 баллов.