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

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

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

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

((848266) 3-14-42

e-mail: nel_shkola_4@mail.ru

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

Русский язык

г. Бонн, Германия,

12—21 июля 1992 г.

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

"ОСТРОВА В МОРЕ"

Расположение островов в море представлено с помощью сетки размером N*N. Каждый остров обозначается символом "*" в узле этой сетки. Задача заключается в том, чтобы восстановить карту морских островов по закодированной информации о распределении островов по горизонталям и вертика­лям. Для иллюстрации принципа кодирования рас­смотрим следующую карту и соответствующие ей коды:

* _ * * _ _     1  2

_ * * * _ *     3  1

* _ * _ * _     1  1  1

_ * * * * *     5

* * _ * _ *     2  1  1

_ _ _ * _ _     1

1 1 4 2 2 1

1 2    3    2

1  

Числа справа от карты на этом рисунке явля­ются кодами и представляют порядок и размер групп островов в соответствующих горизонталях сетки.

Например, цифры "1 2" в первой строке означают, что первая горизонталь содержит группу из одного острова, за которой следует группа из двух остро­вов. Слева и справа от каждой группы островов рас­положено море произвольной протяженности. Ана­логично, последовательность "1 1 1" в первом столбце под картой островов означает, что первая вертикаль содержит три группы островов, в каждой из которых один остров, и т. д.

Постановка задачи

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

1. Считывает очередной блок информации из входного ASCII файла (структура этого файла при­ведена в примере 1 и отображает его на экране.

П р и м е р 1

6

1  2  0   - строка для первой горизонтали

3  1  0

1  1  1  0

5  0

2  1  1  0

1  0

1  1  1  0  - строка для первого стобца

1  2  0

4  0

2  3  0

2  3  0

2  0

1  2  0

П р и м е р 2

Блок входной

информации                    Решение

4                                        Столбцы  12 3 4

0                                        Строка 1

1 0                                     Строка 2        *

2 0                                     Строка 3        * *        

0                                        Строка 4

0

1 0

2 0

0

П р и м е р 3

2

0

0

2 0

2 0

Для этих данных не существует карты.

П  р и м е р 4

2

1   0

1   0

1   0

1   0

Этим данным удовлетворяют две различные карты.

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

2.  Восстанавливает карту (или все карты в слу­чае не единственного решения,  как в примере 4) и отображает ее (их) на экране.

3.  Добавляет карту (карты) в конец выходного ASCII файла. Каждое пустое место в сетке должно быть представлено двумя пробелами, а каждый ост­ров — символом "* " (звездочка и пробел). В случае неоднозначного решения различные карты должны быть отделены друг от друга пустой строкой. Если карту восстановить невозможно, в соответствую­щей строке выходного файла написать "nо mар". Ре­шения, относящиеся к различным блокам информации входного файла, должны быть отделены в выходном файле строкой с надписью "next problem ".

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

1.   N должно быть не меньше 1 и не больше 8.

2.    Результирующая  программа  должна  быть  по­мещена   в   текстовый   ASCII  файл   с   именем C:\IOI\DAY- l\413-PROG.xxx.    Расширение   .ххх для PASCAL - .PAS, для С - .С, для BASIC -.BAS, для LOGO - .LOG.

3.   Имя    входного   ASCII   файла    должно    быть C\IOI\DAY-1\413-SEAS.IN.

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

"ПОКОРЕНИЕ ВЕРШИНЫ"

Клуб альпинистов состоит из Р членов, с номе­рами от 1 до Р. Каждый альпинист поднимается в гору с одной и, той же скоростью, а скорость подъе­ма не отличается от скорости спуска. Альпинист с номером i расходует C(i) единиц ресурсов в день как при подъеме, так и при спуске,  и может нести в каждый момент времени не больше S(i) таких еди­ниц.

Предполагается, что альпинист может достичь вершины за N дней при полной обеспеченности ресур­сами как для подъема, так и для спуска. Гора может быть так высока, что один альпинист не сможет изначально нести все необходимые для подъема и спуска ресурсы. Поэтому группа альпинистов стар­тует в одном и том же месте и в одно и то же время, чтобы обеспечить восхождение. Альпинист может начать спускаться, не достигнув вершины, отдав при этом все ненужные ему для спуска ресурсы другим альпинистам, которые должны быть в со­стоянии их взять. Альпинисты не отдыхают в тече­ние экспедиции.

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

Постановка задачи

Написать программу, которая выполняет сле­дующее:

1.   Вводит с клавиатуры число дней N, требу­емое для достижения вершины горы, число Р членов клуба и числа S(i), C(i) для всех i от 1 до Р.

Все входные данные целочисленные, вещественные данные вводиться не будут. Повторить запрос на ввод данных, не имеющих смысла.

2.    Определяет расписание для  восхождения,   а также номера альпинистов а(1), а(2), ..., а(к), об­разующих группу для восхождения, и числа M(j) (для всех j от 1 до к), которые обозначают количество единиц ресурсов,   взятых  каждым   альпинистом  на старте.

Сообщает, если нельзя составить такого распи­сания для заданных N, S(i) и C(i).

3.   Выводит следующую информацию на экран:

а)  число k альпинистов, участвующих в восхож­дении (размер группы восхождения);

б)  необходимое для этого общее количество еди­ниц ресурсов;

в)  номера участвующих в восхождении альпини­стов a(1), a(2), ..., а(k);

г)  для каждого a(j) — какое количество единиц ресурсов он возьмет с собой со старта;

д)   для каждого a(j) —  количество дней,   через которое он начнет спускаться.

4.   Найденное расписание должно быть близким к оптимальному.   Расписание является  оптимальным, если:

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

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

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

1.  Поместите вашу результирующую программу в  текстовый  ASCII файл  с  именем   C:\IOI\DAY-2\422-PROG.xxx.  Расширение  .ххх для  PASCAL   -.PAS, для С - .С, для BASIC - .BAS, для LOGO -.LOG.

2.  Программа не должна воспринимать входные данные,  если  N<1  или N>100,   а  также  Р<1  или Р>20.

 Пример

Возможен следующий  диалог с вашей програм­мой:

Число дней, необходимое для достижения вершины   —  4

Число альпинистов в клубе                                                 —  5

Максимальный ресурс для альпиниста 1                        —  7

Ежедневный расход ресурса для альпиниста 1               —  1

Максимальный ресурс для альпиниста 2                         —  8

Ежедневный расход ресурса для альпиниста 2                —  2

Максимальный ресурс для альпиниста 3                          — 12

Ежедневный расход ресурса для альпиниста 3                 —  2

Максимальный ресурс для альпиниста 4                           — 15

Ежедневный расход ресурса для альпиниста 4                 —  3

Максимальный ресурс для альпиниста 5                            —  7

Ежедневный расход ресурса для альпиниста 5                  —  1

2 альпиниста требуются для покорения вершины.

10 единиц ресурса в целом для этого необходимо.

Взбираться будут альпинисты 1, 5.

Альпинист 1 возьмет 7 единиц ресурса и начнет спускаться через 4 дня.

Альпинист 5 возьмет 3 единицы ресурса и начнет спускаться через 1 день.

Хотите спланировать восхождение для другого альпинистского клуба? (Y/N)      — Y

Число дней, необходимое для достижения вершины          — 2

Число альпинистов в клубе                                                       —  1

Максимальный ресурс для альпиниста 1                               —  3

Ежедневный расход ресурса для альпиниста 1                      — 1

Восхождение невозможно.

Хотите спланировать восхождение для другого альпинистского клуба? (Y/N)       — N

До свидания.

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

участники

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

Начало