I Интернет – олимпиада по кибернетике и информатике
29.09.2007 г.
Задача 1. Электрик.
По дну реки поперек проложен кабель. Под его наружной оболочкой скрыто 49 изолированных проводов. Все провода имеют изоляцию одного цвета, поэтому определить по цвету изоляции, какой из концов проводов, торчащих из кабеля на одном берегу реки, соответствуют тому или иному концу провода на другом берегу реки, невозможно. Электрик должен, определив концы проводов, прикрепить к ним бирки и соответствующие концы перенумеровать одинаковыми числами. Для этого в его распоряжении имеются проходящая вдоль берега реки линия электропередач, пробник (пробник позволяет определить, находится ли данный провод под напряжением) и лодка. Сколько раз придется электрику переправиться через реку, чтобы решить задачу?
Примечание: река довольно широкая и электрик вряд ли захочет много раз переправляться через нее.
Задача 2. Блины.
На столе стоит блюдо со стопкой блинов, смазанных маслом. Диаметры всех блинов различны.
С помощью лопатки Вы можете разделить стопку блинов на 2 части. Верхнюю часть можно перевернуть и положить обратно на нижнюю.
Распишите Ваши действия, которые позволят расположить блины в стопке в порядке убывания их диаметров. Оценить число требуемых переворотов.
Задача 3. Тележка.
Необходимо перевозить груз из одного конца извилистого туннеля (тупика) в другой конец (тупик). Программа движения тележки записывается в ее память, состоящей из 25 строк, которые выполняются последовательно, кроме случаев, когда указан конкретный номер строки. Каждая строка имеет свой номер и может содержать одну из следующих команд:
- продвинуться вперед на 1 метр ‑ F;
- повернуть направо на 90о – R;
- повернуть налево на 90o – L;
- взять груз – U;
- положить груз – D;
- продолжить выполнение программы со строки с номером N – G N;
- если впереди стена, то продолжить выполнение программы со строки с номером N – IF N,
где N – номер строки, с которой следует продолжить выполнение программы.
Напишите программу, с помощью которой тележка будет брать груз в первом тупике, перевозить его по туннелю, оставлять груз во втором тупике, возвращаться в первый тупик, брать там груз и т. д.
В начальный момент времени тележка находится в первом тупике. Все изгибы туннеля имеют угол 900. Расстояние между изгибами кратно одному метру. Удар тележки в стенку приводит к поломке тележки.
Задача 4. Электронная схема.
Электронная схема состоит из элементов И и НЕ.
Элемент НЕ имеет один вход и один выход. Принцип его работы следующий: Если на входе появится сигнал 0, то через 1 мс на выходе установится сигнал 1, а если на входе 1, то через 1 мс на выходе установится сигнал 0.
Элемент И имеет два входа и один выход. Если на обоих его входах появится сигнал 1, то через 1 мс на выходе установится сигнал 1. Если хотя бы на один из входов поступает 0, то через 1 мс на выходе устанавливается сигнал 0.
Все точки подсоединения элементов пронумерованы. Если в точку поступает сигнал с выходов нескольких элементов, то в этой точке сигнал равен 0 тогда, когда со всех выходов поступает сигнал 0. Если с одного или нескольких выходов, подсоединенных в одной точке, поступает сигнал 1, то в этой точке устанавливается сигнал 1. В последних двух случаях сигнал устанавливается мгновенно (без задержки).
Известно состояние (сигнал 0 или 1) каждой точки в момент включения схемы. Необходимо выдать состояние некоторой указанной точки К в течение первых T мс с момента включения схемы.
В точках, которые соединены только с входами элементов, сигнал остается неизменным с момента включения схемы до окончания ее работы.
Исходные данные находятся в текстовом файле INPUT. TXT.
Файл состоит из некоторого количества строк. Каждая строка содержит несколько целых десятичных чисел, отделенных друг от друга одним или несколькими пробелами. Первое число в строке показывает, что именно описывают оставшиеся числа данной строки:
0 - описание точки соединения;
0 m n - точка с номером m имеет в момент включения состояние n (0 или 1)
1 - описание элемента НЕ;
1 x y - элемент НЕ, вход которого соединен с точкой под номером x, а выход - с точкой под номером y
2 - описание элемента И;
2 x y z - элемент И, один вход которого соединен с точкой под номером x, второй вход соединен с точкой под номером y, а выход - с точкой под номером z
3 - описание задания.
3 K T - необходимо выдать состояние точки K в течение первых T мс с момента включения схемы.
Пример
Пусть имеется схема, приведенная на рисунке. Необходимо выдать состояние точки 3 в течение 5 мс с момента включения схемы.
 |
Исходный файл:
0 1 1 точка 1, в момент включения сигнал 1
0 2 0 точка 2, в момент включения сигнал 0
0 3 0 точка 3, в момент включения сигнал 0
1 2 3 элемент НЕ, вход соединен с точкой 2, выход - 3
элемент И, один вход - точка 1, другой - 3, выход - 2
3 3 5 задание: выдать состояние точки 3 в течение 5 мс
Результат необходимо вывести в текстовый файл OUTPUT. TXT, который содержит T строк: первая строка ‑ состояние точки K в первую мс, вторая строка ‑ состояние точки K во вторую мс, и так далее до T мс.
Для приведенного примера результат будет следующий:
1
1
0
0
1
Примечание. Количество элементов И и НЕ конечно и составляет от 0 до 20 каждого из элементов. В задании количество мс не может превышать 50.
Задача 5. Лифт.
В четырехэтажном здании имеется один лифт, вмещающий 3 человека. Некоторое время не было напряжения, и лифт не работал. На этажах собрались люди (их количество не более 25), желающие переместиться на другие этажи. Наконец лифт включили. Необходимо перевезти всех людей за наименьшее количество остановок лифта.
Исходные данные хранятся в файле INPUT. TXT. Данный файл состоит из 5 строк. В первых четырех строках записано по четыре целых числа отделенных друг от друга одним или несколькими пробелами. Указанные числа имеют следующий смысл: Akn - количество желающих уехать с этажа k на этаж n (k ‑ номер строки исходного файла, n ‑ номер столбца). В последней (пятой) строке записано целое число, соответствующее номеру этажа на котором находится лифт в момент включения напряжения.
Результат необходимо записать в файл OUTPUT.TXT. Файл состоит из М+1 строки.
В первой строке записано число М ‑ количество остановок лифта. В каждой из М оставшихся строк записано по 5 целых чисел отделенных друг от друга пробелами. Первое число означает номер этажа на который поедет лифт, второе ‑ количество человек, вошедших в лифт на текущем этаже и желающих попасть на первый этаж, третье ‑ количество человек, вошедших в лифт на текущем этаже и желающих попасть на второй этаж, четвертое ‑ количество человек, вошедших в лифт на текущем этаже и желающих попасть на третий этаж, пятое ‑ количество человек, вошедших в лифт на текущем этаже и желающих попасть на четвертый этаж.
Пример
Исходный файл
на первом этаже 4 желающих уехать на второй этаж
на 2-ом этаже 2 желающих уехать на 3-й этаж
на 3-ем этаже 1 желающий уехать на 4-й этаж
на 4-ом этаже 1 желающий уехать на 1-й этаж, 2 ‑ на 2-ой этаж
3 лифт стоит на 3-ем этаже
Результат:
6 всего 6 остановок лифта
4 0 0 0 1 с текущего (3-го) этажа перевезти на 4-ый 1-го желающего уехать на 4-й этаж
1 1 2 0 0 с текущего (4-го) этажа на 1-й этаж 1 желающего уехать на 1-й этаж и 2 желающих уехать на 2-й этаж
2 0 3 0 0 с текущего (1-го) этажа на 2-й этаж 3 желающих уехать на 2-й этаж
3 0 0 2 0 с текущего (2-го) этажа на 3-й этаж 2 желающих уехать на 3-й этаж
1 0 0 0 0 переместить лифт с текущего (3-го) этажа на 1-й этаж
2 0 3 0 0 с текущего (1-го) этажа на 2-й этаж 3 желающих уехать на 2-й этаж.
