Завдання для підготовки учнів до ІІІ етапу

 Всеукраїнської учнівської олімпіади з інформатики

Задача 1. «Астролог» (20 балів)

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 1с

Один з астрологів визначає щасливі і нещасливі дні так: він виписує підряд число, номер місяця і рік. В отриманому числі додає всі цифри, в новому отриманому числі знову додає всі цифри і так далі, доки чергова сума цифр не стане однозначним числом. Це число і характеризує щасливість дня.

Формат вхідного файлу.

Дата вводиться в форматі ррррммдд.

Формат вихідного файлу.

Виведіть рядок, який містить одне число, яке визначає щасливість дати.

Приклади файлів

Задача 2. «Робочі дні» (20 балів)

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 2с

Місяцю з N днів відповідає лінійна таблиця елементів, в якій робочий день позначено 1, а неробочий – 0. Скласти алгоритм, який підраховує:

а) кількість тижнів в місяці;

б) кількість робочих днів в кожному з тижнів місяця.

Примітка: Тижнем будемо називати довільну не пусту множину одиниць між двома послідовними нулями або обмежену нулем праворуч (якщо місяць починається з робочого дня), або обмежену нулем ліворуч (якщо місяць не закінчується робочим днем).

 Формат вхідного файлу.

Перший рядок вхідного файлу містить ціле N – кількість днів, а внаступному рядку N чисел, які визначають робочі і неробочі дні (1≤N≤1000000).

Формат вихідного файлу.

Виведіть перший рядок, який містить одне число K, яке визначає кількість тижнів, в наступному рядку K чисел, які визначають кількість робочих днів.

Приклади файлів

Задача 3. «Обробка фотографій з космосу» (30 балів)

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 3с

Комп'ютер перетворив фотографiю частини поверхнi планети, зроблену з космiчного апарата, в двомiрну таблицю Map[1:M, 1:N], елементи якої - цифри 0 (суша) та 1 (вода).

Є 4 типи поверхнi сушi (материк, острiв, пiвострiв та берег) та 3 типи поверхнi води (море,  озеро та затока).  Тип  кожної  клiтини можна визначити в залежностi вiд того, до яких типiв було однозначно вiднесено ранiше деякi з чотирьох сусiднiх по горизонталi та  вертикалi клiтини:

Тип 2 - материк - клiтина сушi, оточена чотирма клiтинами сушi.

Тип 3 - острiв - клiтина сушi, оточена чотирма клiтинами води.

Тип 4 - пiвострiв - клiтина сушi, що має 3 сусiднiх клiтини води,

      або 2 сусiднiх клiтини води та >= 1 клiтини  пiвострова,

      або 1 сусiдню клiтину води та >= 2 клiтин пiвострова.

Тип 5 - берег - клiтина сушi, що не належить до типiв 2-4.

Тип 6 - море - клiтина води, що має хоча б одну сусiдню клiтину моря.

Тип 7 - затока - клiтина моря, що має 2 або 3 сусiднiх клiтини сушi,

      або 4 сусiднi клiтини затоки,

      або 1 сусiдню клiтину сушi та не менше 2 клiтин затоки.

Тип 8 - озеро - клiтина води, що не належить до типiв 6, 7.

Вважається, що двi клiтини типу 4 належать до одного  пiвострова, якщо мiж ними можна пройти по сушi, переходячи на сусiднi клiтини типу 4 по горизонталi або вертикалi.  Таким же чином двi  клiтини типу  7 належать до однiєї затоки,  якщо мiж ними можна пропливти по водi, перепливаючи на сусiднi клiтини типу 7 по горизонталi або вертикалi.  Двi клiтини типу 8 належать до одного озера,  якщо мiж ними можна пропливти по водi,  перепливаючи на сусiднi клiтини типу 8  по горизонталi або вертикалi.

Крайнi рядки та стовпчики таблицi займає море.

ЗАВДАННЯ: написати програму, яка для заданої таблицi-карти:

1. визначить номер типу кожної її клiтини;

2. обчислить кiлькість островiв, пiвостровiв,заток та  озер  на картi.

ТЕХНIЧНI УМОВИ:

1. Кожна "фотографiя" в файлi має таку структуру:

 – в першому рядку – число M,  кiлькiсть рядкiв таблицi Map,

 – в другому рядку – число  N, кiлькiсть  стовпчикiв таблицi Map,

 – в кожному з наступних M рядкiв – N цифр вiдповiдного рядка таблицi.

2. Результат для кожної "фотографiї" повинен складатися з:

 - кiлькостей  островiв, пiвостровiв, заток та  озер  в окремих рядках.

3. Програма повинна обробляти таблицi для 2≤ M ≤20, 2≤N ≤ 40.

Приклад файлів

Задача 4. «Зелена пляма» (30 балів)

Ім’я вхідного файлу: input.txt

Ім’я вихідного файлу: output.txt

Максимальний час роботи на одному тесті: 1с

Два  прожектори трикутної форми утворюють на стiнi двi плями, одну - блакитного, а  другу - жовтого  кольору.  Визначити площу плями зеленого кольору,  яка  утвориться  при накладаннi двох плям - блакитної i жовтої, та  форму (кiлькiсть вершин) зеленої плями.

Перший  рядок  файлу  мiстить цiлочисельнi координати однiєї плями: X1, Y1, X2, Y2, X3, Y3, а в другому рядку – такi ж координати вершин iншої плями. Всі числа по модулю менші 1000.

Вихiдний файл  повинен мiстити у першому рядку – кiлькiсть її вершин, у другому – площу зеленої плями (з двома  знаками  пiсля  коми).

Приклад файлів