Рамки

---

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

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

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

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

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

6 4
....
.AAA
WWWA
WAWA
WХWХ
WWW.  

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

AW
AW  

Что тут считать

---

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

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

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

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

• корректность входных данных не проверяется,
• время тестирования ограничено

Детектив

---

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

Музей состоит из цепочки залов с номерами от 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  

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

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

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

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

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

11111111
11111011
11101111
11111011
11110111
11011111
10111101
11111111
2 1 1 8  

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

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

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

2
2 7  

Примечания:

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

5. Время тестирования каждого теста ограничено одной минутой.

Параллельные вычисления

---

Задана программа, состоящая из N операторов присваивания (1<=N<=15). Каждый оператор записывается в следующем виде: X=YopZ

где X,Y,и Z - идентификаторы, состоящие из одной заглавной латинской буквы;

op - символ одной из арифметических операций: "+" (сложение), "-" (вычитание), "*" (умножение) и "/" (деление).

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

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

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

1. Входные данные расположены в текстовом ASCII-файле, имя которго вводится с клавиатуры.
2. Каждый оператор находится на отдельной строке; файл не содержит пробелов и пустых строк; в конце последней строки файла символов конца строки нет.

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

W=A+B
F=A+P
B=W/F
W=B*C  

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

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

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

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

3
W=A+B   F=A+P
NOP     B=W/F
W=B*C   NOP       

Примечания:

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

Рандеву

---

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

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

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

1. Входные данные расположены в текстовом ASCII-файле, имя которого вводится с клавиатуры.
2. В начале файла содержится число N - количество наборов исходных данных (тестов).
3. Далее расположены N наборов исходных данных; каждый набор - шесть вещественных чисел: X, Y, Vx, Vy, W, R.
4. Все числа в исходном файле разделяются пробелами и (или) символами перевода строки.

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

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  

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

1. Результат работы помещается в выходной текстовый ASCII-файл с именем OUTPUT.TXT.
2. Для каждого набора исходных данных вывести с новой строки вектор скорости (Ux,Uy) и минимальное время встречи, либо сообщение "Встреча невозможна".

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

Встреча невозможна
3.0 -4.0 0.5  

Примечания:

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