VII Всеукраинская олимпиада по информатике
Певый тур
25 марта 1994 г
Взаимозачет долгов
(20 баллов).
Из-за экономического кризиса многие предприятия не могут получить долги от покупателей и рассчитаться с продавцами за свои долги. Банк намерен уменьшить общий долг своих клиентов, выполнив взаимозачет долгов. Для этого банк может изменять долги клиентов любым образом при условии, что для каждого клиента останется неизменным сальдо - разница между суммой долгов ему и суммой его долгов.
ЗАДАНИЕ: Написать программу, которая преобразует заданный список долгов в имеющий как можно меньшую общую сумму долгов.
Технические условия
- Ваша программа должна прочитать входные данные для нескольких тестов из одного текстового ASCII-файла DEBTS.DAT. Данные для различных тестов отделены пустой строкой. Каждая строка файла соответствует одному долговому обязательству и содержит 3 натуральных числа: номер должника, номер предприятия, которому он должен, и сумму долга. Соседние числа отделены пробелом.
- Ваша программа должна записать результаты для всех тестов в один текстовый ASCII-файл DEBTS.SOL, отделяя результаты различных тестов пустой строкой. Результат каждого теста имеет содержать список долгов, оставшихся после взаимозачетов. Этот список должен иметь такую же структуру, что и входной. За ним надо вывести список сальдо всех клиентов, которые были должниками или имели должников. Каждая строка этого списка содержит номер предприятия и его сальдо, отделенные пробелом. В конце результатов теста надо в отдельной строке вывести общую сумму долгов.
- Количество предприятий не превышает 100, денежные суммы не превышают 30000 единиц.
- Имя файла с исходным текстом программы - DEBTS.*.
-
Пример
Входные данные (файл DEBTS.DAT):
1 2 100
2 3 50
3 1 75
1 2 15
2 3 11
4 1 14
Выходные данные (файл DEBTS.SOL) должны выглядеть так:
1 2 25
3 2 25
1 -25
2 50
3 -25
50
1 2 1
4 2 4
4 3 11
1 -1
2 4
3 11
4 -14
15
Сравнение компостеров
(20 баллов)
Компостер в автобусе делает в билете отверстия, что содержатся в некоторых узлах квадратной сетки размером M*N узлов. Компостеры считаются одинаковыми, если все сделанные ими отверстия в билетах можно совместить, отобразив один билет на другой комбинацией параллельных переносов, поворотов на прямой угол и симметрий относительно горизонтальной и вертикальной осей. Закомпостированный билет имеет по крайней мере одно отверстие.
ЗАДАНИЕ: Написать программу, определяющую, одинаковы ли два заданных компостера.
Технические условия
- Ваша программа должна прочитать входные данные для нескольких тестов из одного текстового ASCII-файла COMPOST2.DAT. Данные для различных компостеров отделены пустым строкой. Каждый строка файла соответствует одному строке компостера и содержит единицы (отверстия) и нули (узлы без отверстий). Соседние числа отделены пробелом.
- Ваша программа должна записать результаты для всех тестов в один текстовый ASCII-файл COMPOST2.SOL. Результат каждого теста - строка из его порядковым номером и словом "Одинаковые" или "Разные".
- Размеры сетки не превышают 15*15 узлов.
- Имя файла с исходным текстом программы - COMPOST2.*.
Пример
Входные данные (файл COMPOST2.DAT):
0 0 0 {первый тест, первый компостер}
0 0 1
0 0 0
0 1 0 0 {первый тест, второй компостер}
0 0 0 0 {хоть он и имеет не такой размер, как первый}
0 0 0 0 {но считается одинаковым с ним}
1 0 0 0 0 0 {второй тест, первый компостер}
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
1 0 0 0 0 1 {второй тест, второй компостер}
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Выходные данные (файл COMPOST2.SOL) должны выглядеть так:
1 Одинаковые
2 Разные
Количество компостеров
(60 баллов)
ЗАДАНИЕ: Написать программу, которая при условии предыдущей за- дачи определит количество различных компостеров, которые можно образовать на сетке размером M*N узлов.
Технические условия
- Ваша программа должна прочитать входные данные для нескольких тестов из одного текстового ASCII-файла COMPOST3.DAT. Каждая строка файла соответствует одному тесту и содержит числа M и N, разделенные пробелом
- Ваша программа должна записать результаты для всех тестов в один текстовый ASCII-файл COMPOST3.SOL. Результат каждого теста - строка с его порядковым номером и количеством компостеров.
- M и N не превосходят 15.
- Имя файла с исходным текстом программы - COMPOST3.*.
Пример
Входные данные (файл COMPOST3.DAT):
1 1
2 2
Выходные данные (файл COMPOST3.SOL) должны выглядеть так:
1 1
2 5
Второй тур
27 марта 1994 г
Архиватор
- Напишите программу-архиватор, преобразующую входной текстовый файл в выходной (архивный) файл как можно меньшего размера, и программу-дезархиватор, восстанавливающую по архивному файлу исходный (50 баллов).
- Напишите программу-архиватор, преобразующую все текстовые файлы с именами, соответствующими маске "*.txt", находящиеся в текущем каталоге, в один выходной (архивный) файл как можно меньшего размера, и программу-дезархиватор, восстанавливающую по архивному файлу все входящие в него текстовые файлы (30 баллов).
- По разным причинам информация в архивных файлах может искажаться. Добавьте в дезархиватор средства, предупреждающие человека в случае искажения информации в архивном файле (20 баллов).
Технические условия
- Входные текстовые файлы могут содержать большие и малые украинские, русские и латинские буквы, цифры, точки, запятые, точки с запятой, двоеточия, вопросительные и восклицательные знаки, тире, двойные кавычки, открывающие и закрывющие круглые скобки, пробелы, символы возврата каретки (десятичный код - 10) и перевода строки (код 13). Каждый файл завершается символом конца файла (код 26). Длина строк не превосходит 255 символов. Используйте кодировку украинских букв, соответствующую предоставленному Вам драйверу.
- Архiвний файл повинен завершуватися символом кiнця файлу; в серединi архiвного файлу цей символ мiститися не може.
- Архивный файл должен заканчиваться символом конца файла; в середине архивного файла этот символ находиться не может.
- Программы должны запрашивать необходимые имена текстовых и архивных файлов в диалоге.
- Откомпилированные программы должны обрабатывать каждый набор тестовых текстов не дольше, чем за 5 минут; интерпретируемые - не дольше, чем за 10 минут.
- Имена файлов с исходными текстами программ - ARC.* и UNARC.*
|
