|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Санкт-Петербургские Олимпиады по Информатике |
Задачи международной олимпиады 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" в первом столбце под картой островов означает, что первая вертикаль содержит три группы островов, в каждой из которых один остров, и т.д.
Постановка задачи
Написать программу, которая выполняет следующие действия (шаги) до тех пор, пока данный входной файл, содержащий несколько блоков информации, не будет прочитан полностью:
- Считывает очередной блок информации из входного ASCII файла (структура этого файла приведена в примере 1) и отображает его на экране. Каждый блок информации начинается с величины размера квадратной сетки, за которым следует кодовая информация о горизонтальном и вертикальном распределении островов. Код для каждой отдельной горизонтали и вертикали является отдельной строкой файла и представляет собой последовательность чисел, разделенных пробелами. Заканчивается каждая строка нулем. При этом сначала идет информация о всех горизонталях, а затем - о вертикалях.
- Восстанавливает карту (или все карты в случае не единственного решения как в примере 4) и отображает ее (их) на экране.
- Добавляет карту (карты) в конец выходного ASCII файла. Каждое пустое место в сетке должно быть представлено двумя пробелами, а каждый остров - символом "* " (звездочка и пробел). В случае неоднозначного решения различные карты должны быть отделены друг от друга пустой строкой. Если карту восстановить невозможно, в соответствующей строке выходного файла написать " no map ". Решения, относящиеся к различным блокам информации входного файла должны быть отделены в выходном файле строкой с надписью " next problem ".
Технические ограничения
- N должно быть не меньше 1 и не больше 8.
- Результирующая программа должна быть помещена в текстовый ASCII файл с именем "C:\IOI\DAY-1\413-PROG.xxx". Расширение .xxx для PASCAL - .PAS, для C - .C, для BASIC - .BAS, для LOGO - .LOG.
- Имя входного ASCII файла должно быть "C:\IOI\DAY-1\413-SEAS.IN".
Пример 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 0 1 2 0
Пример 2:
Блок входной Решение: информации 4 Столбцы 1 2 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 Этим данным удовлетворяют две различные карты.
|
Задача "Покорение вершины"
|
Клуб альпинистов состоит из P членов, с номерами от 1 до P. Каждый альпинист поднимается в гору с одной и той же скоростью, а скорость подъема не отличается от скорости спуска. Альпинист с номером i расходует C(i) единиц ресурсов в день как при подъеме, так и при спуске, и может нести в каждый момент времени не больше S(i) таких едениц. Все C(i) и S(i) - целые числа. Предполагается, что альпинист может достичь вершины за N дней при полной обеспеченности ресурсами как для подъема, так и для спуска. Гора может быть так высока, что один альпинист не может изначально нести все необходимые для подьема и спуска ресурсы. Поэтому группа альпинистов стартует в одном и том же месте и в одно и то же время, чтобы обеспечить восхождение. Альпинист может начать спускаться, не достигнув вершины, отдав при этом все ненужные ему для спуска ресурсы другим альпинистам, которые должны быть в состоянии их взять. Альпинисты не отдыхают в течение экспедиции. Задача состоит в составлении расписания восхождения для клуба альпинистов. По крайней мере один альпинист должен достичь вершины горы и все альпинисты, включенные в группу восхождения, должны возвратиться в начальную точку.
Постановка задачи
Написать программу, которая выполняет следующее:
- Вводит с клавиатуры число дней N, требуемое для достижения вершины горы, число P членов клуба и числа S(i), C(i), для всех i от 1 до P. Предполагается, что все входные данные целочисленные. Отвергнуть (повторить запрос) на ввод данных, которые не имеют смысла.
- Определяет расписание для восхождения, а также номера альпинистов a(1), a(2),..., a(k), образующих группу для восхождения, и числа M(j) (для всех j от 1 до k), которые обозначают количество единиц ресурсов, взятых каждым a(j) альпинистом на старте. Сообщает, если нельзя составить такого расписания для заданных N, S(i) и C(i).
- Выводит следующую информацию на экран:
a) число k альпинистов, действительно участвующих в восхождении (размер группы восхождения);
b) необходимое для этого общее количество единиц ресурсов;
c) номера участвующих в восхождении альпинистов a(1),a(2),..., a(k);
d) для каждого а(j) (1<=j<=k) какое количество единиц ресурсов он возьмет с собой со старта;
e) для каждого a(j) количество дней, через которое он начнет спускаться. - Пытается найти почти оптимальное расписание. Расписание является оптимальным, если:
a) число участвующих в восхождении альпинистов, необходимое для достижения вершины одним из них, минимально.
b) среди всех расписаний для групп, удовлетворяющих условию а), общее количество единиц ресурсов, взятых с собой со старта, - минимально.
Технические ограничения
- Поместите вашу результирующую программу в текстовый ASCII файл с именем "C:\IOI\DAY-2\422-PROG.xxx". Расширение .xxx для PASCAL - .PAS, для C - .C, для BASIC - .BAS, для LOGO - .LOG.
- Программа должна отвергать входные данные, если N<1 или N>100, а также если P<1 или P>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. До свидания.