Муниципальное общеобразовательное учреждение

средняя общеобразовательная школа №4 

(территориальный ресурсный центр)

 Тверская область, г. Нелидово, ул. Карбышева 14А

((848266) 3-14-42

e-mail: nel_shkola_4@mail.ru

Международная олимпиада по информатике 1990 года

Русский язык

г. Минск, СССР,

15—21 июля 1990 г.

ЗАДАЧА ПЕРВОГО ТУРА

 "ИГРА 14"

Задана таблица размером 4*4, в каждой клетке которой, кроме двух, содержится одно из чисел от 1 до 14 (все числа разные). Оставшиеся две клетки — пустые. (Пример — таблица 5).

         Таблица 5                                                     Таблица 6

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

Цель. Необходимо с помощью указанного правила выполнять по шагам преобразование произвольной исходной таблицы в конечную таблицу 6.

Задание. Написать программу, которая:

1) осуществляет ввод с клавиатуры исходной таблицы и вывод ее на экран (пустые клетки могут быть закодированы нулями);

2)  выполняет преобразование введенной таблицы в таблицу 6;

3)  на каждом шаге выдает на экран слева матрицу до хода, справа — матрицу после хода и указывает номер хода (1, 2, 3 и т. д.) так, что в конце работы программы будет показано полное число сделанных ходов;

4) минимизирует число ходов, требуемых для решения задачи.

ЗАДАЧА ВТОРОГО ТУРА

"КАРТИННАЯ ГАЛЕРЕЯ"

В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи называется множество пар [T1(I), T2(I)] — моментов начала и конца дежурства 1-го сторожа из интервала [0, EndTime].

Для заданного расписания стражи требуется:

а) проверить, в любой ли момент в галерее нахо­дится не менее двух сторожей;

если условие пункта а) не выполняется, то:

б)  перечислить все интервалы времени с недостаточной охраной (менее двух сторожей);

в)  добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства так,   чтобы  получить правильное расписание (удовлетворяющее условию пункта а);

г)  проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать время дежурства   каждого   сторожа   с  сохранением   длительности его дежурства;

д)  при положительном ответе на пункт г) составить расписание с наименьшим числом сдвигов.

Входные данные (все моменты времени задаются в целых минутах):

EndTime — момент окончания стражи ( момент начала — 0);

N — число сторожей;

Т1(1), Т2(1), I=1,...,N — моменты начала и окончания дежурства 1-го сторожа;

Length — длительность дежурства каждого дополнительного сторожа.

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

1)  ответ на пункт а) в форме да/нет;

2)  при ответе "нет" на пункт а) — список пар (k,l) — начал и концов всех малоохраняемых интерва­лов с указанием числа сторожей в каждом (0 или 1);

3)  число дополнительных сторожей и моменты начала   и   окончания  дежурства  каждого  дополнительного сторожа;

4)  ответ на пункт г) в форме да/нет; если "да", то номера сторожей, смена которых сдвигается, и значения сдвигов;

5)  ответ на пункт д) — наименьшее число сторожей, смена которых сдвигается, их номера и значения сдвигов.

Примечание. Программа должна допускать независимое тестирование пунктов в), г), д).

Место проведения и

участники

Скачать задания в Word

Начало