VII Всеукраїнська олімпіада з інформатики
Перший тур
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.*
|
