Перший тур
25 березня 1994 року
ВЗАЄМНИЙ ЗАЛIК БОРГIВ
(20 балiв).
З-за економiчної кризи багато пiдприємств не можуть отримати
борги вiд покупцiв i розрахуватися з продавцями за свої борги. Банк
має намiр зменшити загальний борг своїх клiєнтiв, виконавши взаємний
залiк боргiв. Для цього банк може змiнювати борги клiєнтiв будь-яким
чином при умовi, що для кожного клiєнта лишиться незмiнним сальдо -
рiзниця мiж сумою боргiв йому та сумою його боргiв.
ЗАВДАННЯ: написати програму, що перерахує заданий список боргiв
в такий, що має якомога меншу загальну суму боргiв.
Технiчнi умови
- Ваша програма повинна прочитати вхiднi данi для декiлькох
тестiв з одного текстового ASCII-файлу DEBTS.DAT. Данi для рiзних
тестiв вiдокремлено порожнiм рядком. Кожен рядок файлу вiдповiдає од-
ному борговому зобов'язанню та мiстить 3 натуральних числа: номер
боржника, номер пiдприємства, якому вiн винен, та суму боргу. Сусiднi
числа вiдокремлено пропуском.
- Ваша програма повинна записати результати для всiх тестiв до
одного тестового ASCII-файлу DEBTS.SOL, вiдокремлюючи результати
рiзних тестiв порожнiм рядком. Результат кожного тесту має мiстити
список боргiв, що залишаться пiсля взаємних залiкiв. Цей список пови-
нен мати таку ж структуру, що й вхiдний. За ним треба вивести список
сальдо всiх клiєнтiв, що були боржниками або мали боржникiв. Кожен
рядок цього списку мiстить номер пiдприємства та його сальдо, вiдок-
ремленi пропуском. В кiнцi результатiв тесту треба в окремому рядку
вивести загальну суму боргiв.
- Кiлькiсть пiдприємств не перевищує 100, грошовi суми не пере-
вищують 30000 одиниць.
- Iм'я файлу з вихiдним текстом програми - DEBTS*.
Приклад вхiдного та вихiдного файлiв
Вхiднi данi (файл DEBTS.DAT):
1 2 100
2 3 50
3 1 75
1 2 15
2 3 11
4 1 14
Вихiднi данi (файл DEBTS.SOL) повиннi виглядати так:
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
ПОРIВНЯННЯ КОМПОСТЕРIВ
(20 балiв)
Компостер в автобусi робить у квитку отвори, що мiстяться у дея-
ких вузлах квадратної сiтки розмiром M*N вузлiв. Компостери вважа-
ються однаковими, якщо всi зробленi ними отвори в квитках можна
сумiстити, вiдобразивши один квиток на iнший комбiнацiєю паралельних
переносiв, поворотiв на прямий кут та симетрiй вiдносно горизонталь-
ної та вертикальної осей. Закомпостований квиток має принаймнi один
отвiр.
ЗАВДАННЯ: Написати програму, що визначить, чи однаковi два зада-
них компостери.
Технiчнi умови
- Ваша програма повинна прочитати вхiднi данi для декiлькох
тестiв з одного текстового ASCII-файлу COMPOST2.DAT. Данi для рiзних
компостерiв вiдокремлено порожнiм рядком. Кожен рядок файлу
вiдповiдає одному рядковi компостера та мiстить одиницi (отвори) та
нулi (вузли без отворiв). Сусiднi числа вiдокремлено пропуском.
- Ваша програма повинна записати результати для всiх тестiв до
одного текстового ASCII-файлу COMPOST2.SOL. Результат кожного тесту -
рядок з його порядковим номером та словом "Однаковi" або "Рiзнi".
- Розмiри сiтки не перевищують 15 вузлiв.
- Iм'я файлу з вихiдним текстом програм - COMPOST2.*
Приклад вхiдного та вихiдного файлiв
Вхiднi данi (файл DEBTS.DAT):
Вхiднi данi (файл COMPST2.DAT):
0 0 0 {перший тест, перший компостер}
0 0 1
0 0 0
0 1 0 0 {перший тест, другий компостер}
0 0 0 0 {хоч вiн i має iнший розмiр, нiж перший}
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
Вихiднi данi (файл COMPST2.SOL) повинен виглядати так:
1. Однаковi
2. Рiзнi
КIЛЬКIСТЬ КОМПОСТЕРIВ
(60 балiв)
ЗАВДАННЯ: Написати програму, що за умов попередньої задачi виз-
начить кiлькiсть рiзних компостерiв, якi можна утворити на сiтцi
розмiром M*N вузлiв.
Технiчнi умови
- Ваша програма повинна прчитати вхiднi данi для декiлькох
тестiв з одного текстового ASCII-файлу COMPOST3.DAT. Кожен рядок фай-
лу вiдповiдає одному тесту та мiстить числа M та N, вiдокремленi про-
пуском.
- Ваша програма повинна записати результати для всiх тестiв до
одного текстового ASCII-файлу COMPOST3.SOL. Результат кожного тесту -
рядок з його порядковим номером та кiлькiстю компостерiв.
- M та N не перевищують 15.
- Iм'я файлу з вихiдним текстом програми - COMPOST3.*
Приклад вхiдного та вихiдного файлiв
Вхiднi данi (файл COMPOST3.DAT):
1 1
2 2
Вихiднi данi (файл COMPOST3.SOL) повиннi виглядати так:
1 1
2 5
Другий тур
26 березня 1994 року
АРХIВАТОР
- Напишiть програму-архiватор, що перетворює вхiдний текстовий
файл у вихiдний (архiвний) файл якомога меншого розмiру, та програ-
му-дезархiватор, що вiдновлює за архiвним файлом початковий (50
балiв).
- Напишiть програму-архiватор, що перетворює всi текстовi файли
з iменами, вiдповiдними масцi "*.txt", що знаходяться в поточному ка-
талозi, в один вихiдний (архiвний) файл якомога меншого розмiру, та
програму-дезархiватор, що вiдновлює за архiвним файлом всi включенi
до нього текстовi файли (30 балiв).
- З рiзних причин iнформацiя в архiвних файлах може спотворюва-
тися. Додайте до дезархiватора засоби, що сповiщають користувача в
разi спотворення iнформацiї в архiвному файлi (20 балiв).
Технiчнi умови
- Вхiднi текстовi файли можуть мiстити великi та малi українсь-
ки, росiйськi та латинськi лiтери, цифри, крапки, коми, крапки з ко-
мами, двокрапки, знаки питання та оклику, тире, подвiйнi лапки,
круглi дужки, пропуски, символи повернення каретки (десятковий код -
10) та переведення рядка (код 13). Кожен файл завершується символом
кiнця файлу (код 26). Довжина рядкiв не перевищує 255 символiв. Вико-
ристовуйте кодування українських лiтер згiдно з наданим Вам драйвером.
- Архiвний файл повинен завершуватися символом кiнця файлу; в
серединi архiвного файлу цей символ мiститися не може.
- Програми повиннi запитувати необхiднi iмена текстових та
архiвних файлiв в дiалозi.
- Вiдкомпiльованi програми мають обробляти кожен набiр текстiв
не довше, нiж за 5 хвилин; програми, що iнтерпретуються - не довше,
нiж за 10 хвилин.
- Iмена файлiв з вихiдними текстами програм - ARC.* та UNARC.*
|
