Годинник | |
|
1999 год
|
| |
|
XII Всеукраинская олимпиада по информатике
|
|
XII Всеукраинская олимпиада по информатике
Первый тур
Конвейер
Для транспортирования материалов из цеху А в цех В используется конвейер. Материалы упаковываются в одинаковые контейнеры и размещаются на ленте один за другим в порядке изготовления в цеху А. Каждый контейнер имеет степень срочности обработки в цеху В. Для упорядочения контейнеров по степени срочности используют накопитель, находящийся в конце конвейера перед входом в цех В. Накопитель работает пошагово, на каждом шаге возможны такие действия:
- накопитель перемещает первый контейнер с ленты в цех В;
- накопитель перемещает первый контейнер с ленты в хранилище (в хранилище каждый следующий контейнер помещается на предыдущий);
- накопитель перемещает верхний контейнер с хранилища в цех В.
Задание: Написать программу PIPELINE, которая по последовательности контейнеров определит, можно ли упорядочить их по степени срочности с помощью описанного накопителя.
Входные данные: Входной текстовый файл PIPELINE.DAT в первой строке содержит количество тестов N. Далее следуют N строк, каждая из которых описывает отдельный тест и содержит целое число K (1£
K£
10000) - количество контейнеров в последовательности и K действительных чисел - степеней срочности контейнеров в порядке их поступления из цеха А.
Пример входных данных
2
2 2.9 2.1
3 5.6 9.0 2.0
Выходные данные: Каждая строка текстового файла PIPELINE.SOL должна содержать ответ для одного теста. Необходимо вывести 1, если необходимое упорядочение возможно, либо 0 в противном случае.
Пример выходных данных
1
0
Новости
В городе введено движение автобусов. Все автобусы имеют циклические маршруты. Некоторые маршруты имеют общие остановки. Когда два или больше автобусов встречаются на некоторой остановке, водители обмениваются всеми новостями, которые им известны на этот момент (после того как они выедут с остановки, все будут знать одинаковые новости). Водители начинают движение своих автобусов в одно время, и в это время каждый из водителей знает одну новость, которую не знает никто из других. Движение автобусов синхронизировано. Время, необходимое для переезда с одной остановки до следующей, одинаково для всех автобусов. Имеется D водителей (и, соответственно, D автобусов), которые занумерованы от 1 до D, и S остановок, имеющих номера от 1 до S.
Задание: Написать программу BUS, определяющую, может ли каждый водитель узнать все новости от своих коллег, если длительность нахождения на маршруте неограниченна.
Входные данные: Входной текстовый файл BUS.DAT в первой строке содержит количество тестов N. Далее следуют N блоков информации, каждый из которых соответствует одному тесту. Первая строка блока содержит два целых числа D (1£
D£
100) и S (1£
S£
250). Каждая из последующих D строк описывает маршрут одного из автобусов таким образом: первое число - количество остановок на данном маршруте Mi, после чего Mi различных целых чисел, задающих последовательность остановок маршрута. Движение автобуса начинается с остановки, указанной первой.
Пример входных данных
2
1 3
3 1 2 3
2 2
2 1 2
2 2 1
Выходные данные: Каждая строка текстового файла BUS.SOL должна содержать ответ для одного теста. Необходимо вывести 1, если каждый из водителей будет знать все новости, либо 0 в противном случае.
Пример выходных данных
1
0
Лото
Достаточно популярна лотерея, которая проводится по таким правилам: из набора N шариков случайно выбирается K шариков, которые считаются выигрышными. Выигрывают игроки, которые предусмотрели выбор именно этих шариков. Несложно вычислить количество C вариантов выбора K шариков из набора N шариков.
Задание: Написать программу LOTO, определяющую, сколько шариков нужно брать из набора N шариков, если количество вариантов выбора составляет C.
Входные данные: Входной текстовый файл LOTO.DAT содержит в единственной строке два числа - N и C (1£
N£
500000).
Пример входных данных
15 5005
Выходные данные: Единственная строка текстового файла LOTO.SOL должна содержать число K - количество шариков, которые необходимо брать.
Пример выходных данных
6
Второй тур
Парк
Накануне выборов мэр города решил основать парк отдыха. В центре города с этой целью была расчищена площадка, имеющая форму равностороннего треугольника. За победу в выборах борются N политических партий. Чтобы подчеркнуть свою независимость, мэр приказал посадить в парке деревья N разных цветов. Деревья должны быть размещены в узлах треугольной сетки (см. рисунок) на одинаковом расстоянии друг от друга. В каждом ряду, параллельном одной из сторон треугольника, должны расти деревья попарно различных цветов, внешние ряды площадки должны содержать ровно N деревьев, то есть деревья всех цветов.
Задание: Написать программу PARK, находящую одно з возможных размещений деревьев в парке.
Входные данные: Входной текстовый файл PARK.DAT в первой строке содержит количество тестов. Каждая последующая строка содержит одно целое число N - количество видов (цветов) деревьев, которые необходимо посадить в парке. (3£
N£
100).
Пример входных данных
2
3
4
Выходные данные: Выходной текстовый файл PARK.SOL должен содержать ответы для всех тестов из входного файла в том же порядке. Для каждого теста необходимо вывести либо единственную строку с числом 0, если размещение невозможно, либо N строк, первая из которых содержит одно число, вторая - два числа, N-я - N чисел - номеров цветов деревьев в размещении. Цвета нумеруются натуральными числами от 1 до N.
Пример выходных данных
2
3 1
1 2 3
0
Пещера
Гном Торин нашел план заброшенной пещеры, в которой жил горный король Норус. На плане обозначено место, где находится огромный клад. Горный король защитил свое богатство от кладоискателей, для чего разместил в пещере L каменных блоков, которые двигаются и могут раздавить кладоискателя, и которые останавливаются когда клад найден.
План задан в виде прямоугольной целочисленной матрицы MxN, элементами которой могут быть:-2 (клад), -1 (стена), 0 (пустое место), положительное число K (элемент K-го блока). K-ый блок состоит из всех элементов, обозначенных числом K. Блок не обязательно связный, но все его элементы двигаются синхронно. Нули в крайних строках или столбцах матрицы означают входы в пещеру. Отдельно указано начальное направление движение каждого блока (1 - вверх, 2 - вправо, 3 - вниз, 4 - влево). Гном занимает клетку-вход. После этого он двигается по таким правилам: на протяжении каждой секунды пеpвым перемещается гном на пустую клетку из 4-х соседних (вверх, вниз, влево или вправо) либо остается на месте. Затем на протяжении той же секунды перемещается каждый блок на одну клетку (вверх, вправо, вниз, влево): сначала первый, за ним второй и.т.д. Если перед любым из элементов блока в направлении его движения находится стена, край пещеры, клад либо другой блок, то на этом ходу блок не двигается, а направление его движения изменяется на противоположное. Если блок во время движения попал в клетку с гномом, то гном погибнет.
Задание: Написать программу CAVE для поиска безопасного пути, который приведет к кладу за наименьшее время, считая, что такой путь существует.
Входные данные: Входной текстовый файл CAVE.DAT в первой строке содержит числа M, N и L-количество блоков (3£
M£
75, 3£
N£
75, 3£
L£
1000). В последующих M строках содержится по N целых чисел - план пещеры. В следующих L строках заданы начальные направления движения блоков в порядке возрастания их номеров.
Пример входных данных
4 5 1
-1 -1 -1 -1 -1
-1 0 1 0 -1
0 0 0 -2 -1
-1 -1 -1 -1 -1
1
Выходные данные: Выходной текстовый файл CAVE.SOL в первой строке должен содержать число K - время пpохождения пути в секундах. В следующих K+1 строках - координаты положения гнома в каждую секунду (начиная с координат входа). Координаты должны быть представлены в порядке "строка - столбец". Если существует несколько путей, достаточно указать один из них.
Пример выходных данных
5
3 1
3 2
2 2
2 3
2 4
3 4 |
| | |
| |
