VIII обласна олімпіада учнів 9-11 класів з інформатики Хмельницький, 30 січня 1994 р. Задачі 1 туру. 1.Нова історія одного міста (30 балів) Новий градоначальник міста Глупова вирішив з метою поповнення бюджету та економії пального провести компанію боротьби з лівим ухилом та лівими рейсами. Для цього він заборонив водіям виконувати ліві повороти, встановивши штраф за кожен поворот наліво в розмірі 1 мільйон та наказавши встановити систему тотального стеження за автомобілями, яка слідкує за кожним автомобілем і заносить його координати в пам'ять комп'ютера на початку та в кінці руху, а також в ті моменти, коли він виконує будь-який поворот. Від важкого минулого Глупову лишилися вулиці, що можуть перетинатися під будь-якими кутами. Рух у зворотньому напрямку градоначальник не заборонив. ЗАВДАННЯ: написати програму, що для заданої послідовності координат автомобіля обчислює штраф водія. ТЕХНЧНІ УМОВИ: 1.Імена файлів програми, вхідних та вихідних даних -FEE. 2.Кожен тест - послідовність пар координат для одного водія. Кожна пара координат (дійсних чисел) міститься в окремому рядку. 3.Сумарний штраф для кожного теста (водія) в мільйонах (без 6 нулів) записується в окремому рядку. В кінці треба вивести суму штрафів всіх водіїв. 2.ОБРОБКА ФОТОГРАФІЙ З КОСМОСУ (70 балів) Комп'ютер перетворив фотографію частини поверхні планети, зроблену з космічного апарата, в двомірну таблицю Map[1:M, 1:N], елементи якої - цифри 0 (суша) та 1 (вода). Є 4 типи поверхні суші (материк, острів, півострів та берег) та три типи поверхні води (море, озеро та затока). Тип кожної клітини можна визначити в залежності від того, до яких типів було однозначно віднесено раніше деякі з чотирьох сусідніх по вертикалі та горизонталі клітин: Тип 2 - материк-клітина суші, оточена чотирма клітинами суші. Тип 3 - острів-клітина суші, оточена чотирма клітинами води. Тип 4 - півострів-клітина суші, що має 3 сусідніх клітини води, або 2 сусідніх клітини води та >=1 клітини півострова, або 1 сусідню клітину води та >=2 клітин півострова. Тип 5 - берег-клітина суші, що не належить до типів 2-4. Тип 6 - море-клітина води, що має хоча б одну сусідню клітину моря. Тип 7 - затока-клітина моря, що має 2 або 3 сусідніх клітини суші,або 4 сусідні клітини затоки, або 1 сусідню клітину суші та не менше 2 клітин затоки. Тип 8 - озеро-клітина води, що не належить до типів 6, 7. Вважається, що дві клітини типу 4 належать до одного півострова, якщо між ними можна пройти по суші, переходячи на сусідні клітини типу 4 по горизонталі або вертикалі. Таким же чином дві клітини типу 7 належать до однієї затоки, якщо між ними можна проплисти по воді, перепливаючи на сусідні клітини типу 7 по горизонталі або вертикалі. Дві клітини типу 8 належать до одного озера, якщо між ними можна проплисти по воді, перепливаючи на сусідню клітину типу 8 по горизонталі або вертикалі. Крайні рядки та стовпчики таблиці займає море. ЗАВДАННЯ: написати програму, що для заданої таблиці-карти: 1. Визначить номер типу кожної її клітини. 2. Обчислить кількості островів, півостровів, озер та заток на карті. ТЕХНІЧНІ УМОВИ: 1. Імена файлів програми, вхідних та вихідних даних - MAP. 2. Кожна "фотографія" в файлі має таку структуру: - в першому рядку - число М, кількість рядків в таблиці MAP, - в другому рядку - число N, кількість стовпчиків в таблиці МАР, - в кожному з наступних М рядків - N цифр відповідного рядка таблиць. 3. Результат для кожної "фотографії " повинен складатися з: - номера фотографії в окремому рядку; - М рядків, у кожному з яких має міститися N цифр (без пропусків), що позначають тип поверхні планети у відповідних клітинах; та - 4 рядки з кількостями півостровів, островів, озер та заток. Сусідні фотографії відокремлюйте порожнім рядком. 4. Програма повинна обробляти таблиці для 1 < M <= 20, 1 < N <= 40. 2 тур. БАРТЕР (100 балів) В умовах інфляції багато підприємців віддають перевагу обміну своєї продукції на необхідні товари (бартеру), а не продажу продукції. Припустимо, що кожне підприємство може обміняти деяку кількість своєї продукції та визначає її ціну. Для кожного підприємства визначено множину підприємств, в продукції яких воно зацікавлене. Підприємство може передати іншим будь-яку кількість свого товару в межах наявного, але не може пропонувати чужу продукцію. Біржа може виступати посередником в бартері між виробниками товарів, організуючи не тільки попарні обміни, а й більш складні, з дотриманням єдиної умови: кожен клієнт повинен отримати необхідні йому товари з такою ж сумарною вартістю, на яку він надав продукції іншим, наприклад: підприємство А надає підприємству В товару на 90 млн, В надає С та D товару відповідно на 70 та 20 млн, а С та D надають підприµмству А товари на такі ж суми. ЗАВДАННЯ: Написати програму, що для заданих пропозицій та запитів товарів запропонує таку комбінацію бартерних угод, щоб сумарна вартість обміняних була якомога більшою. ТЕХНІЧНІ УМОВИ. 1. Імена файлів програми, вхідних та вихідних даних - BARTER. 2. В кожному тесті спочатку перераховано пропозиції товарів, а потім, після рядка з символом '-' - запити товарів. Кожен рядок пропозиції містить 2 натуральних числа: номер підприємства та загальну вартість продукції, запропонованої ним до обміну. Кожен рядок запиту містить 2 натуральних числа: номер підприємства, що запитує товар, та номер підприємства-виробника товару. Пропозиції впорядковано за зростанням першого числа. Запити впорядковано за зростанням першого числа, а при однакових перших - за зростанням другого. 3. Результат для кожного тесту - список угод, кожен рядок якого містить 3 числа: номер підприємства-виробника, номер підприємства, що отримує товар, та загальну вартість товару. Далі треба вивести список результатів бартеру для всіх учасників обміну, кожен рядок якого містить 3 числа: номер підприµмства та загальні вартості наданих та отриманих ним товарів. Списки впорядковуйте таким же чином, як у вхідних даних. В кінці треба вивести загальну вартість всіх обміняних товарів. 4. Номери підприємств не перевищують 15, грошові суми - 30000.