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

2006 рік

Задача 1. "Слово"

Кожна клітинка таблиці, що складається з m рядків та n стовпців (m, n – натуральні числа із діапазону від 5 до 1000000) містить деяку літеру латинського алфавіту. Необхідно знайти у такій таблиці певне слово. Літери слова мають бути розташовані у сусідніх комірках, що межують між собою ліворуч, праворуч, знизу або зверху. Кожна комірка з літерою, що входить до слова, використовується один раз.

Вхідні дані: кількість рядків та стовпців таблиці, символи таблиці, символи слова, яке необхідно знайти в таблиці.

Результати: пари чисел, що задають номер рядка та стовпця клітини таблиці у якій знаходиться літера слова (нумерація рядків та стовпців починається з нуля).

Приклад вхідних даних:

6 8

afghklmo

srpqiypo

tbufqagf

buycogdl

lildinog

mikjuotw

building

Приклад результату:

2 1 3 1 4 1 4 2 4 3 4 4 4 5 3 5

Задача 2. "Ламані"

На площині розташовано масив прямокутників зі сторонами паралельними координатним осям. Кожен прямокутник визначається цілочисельними координатами верхнього лівого та нижнього правого кутів. Перший прямокутник з масиву вважається головним. Потрібно визначити координати вершин ламаних, що поділяють головний прямокутник на частини. До певних частин належить хоча б одна точка прямокутника, що не є головним. Інші частини складаються лише з точок головного прямокутника. Несуттєво з якої вершини ламаної починається обхід усіх її вершин. Значення координат вершин прямокутників знаходяться у межах від -10000 до 10000. Кількість прямокутників не менша від 3 і не перевищує 1000000.

Вхідні дані: кількість прямокутників, координати вершин прямокутників.

Результати: кількість ламаних, кількості вершин кожної
ламаної, координати вершин ламаних

Приклад вхідних даних

11

-4 9 13 -2

3 1 11 -4

4 4 8 -1

-6 13 1 6

-1 12 7 7

11 14 14 3

6 6 9 3

3 14 5 5

-2 4 -1 -1

-3 2 2 1

10 12 15 8

Приклад результату

2

28

12

-4 6 1 6 1 7 3 7 3 5 5 5

5 7 7 7 7 9 10 9 10 8 11 8

11 3 13 3 13 -2 11 -2 11 1

8 18 3 9 3 9 6 6 6 6 4 4 4 4 1

3 1 3 -2 -4 -2 -2 2 -2 4

-1 4 -1 2 2 2 2 1

-1 1 -1 -1 -2 -1

-2 1 -3 1 -3 2

Задача 3. Отвір.

На площині задано два опуклі многокутника, причому вершини другого багатокутника належать внутрішній області першого. Другий многокутник визначає контур отвору, який необхідно побудувати у першому. Отвір будується за наступним алгоритмом. Для кожної вершини першого многокутника будується вершина, що належить його внутрішній області і знаходиться на відстані, що не перевищує 1/5 найменшої із відстаней від вершин першого до вершин другого многокутника (див. мал.). За отриманими точками будується многокутник, який називатимемо внутрішнім контуром. Відповідні точки першого многокутника і точки внутрішнього контура з’єднуються відрізками. З довільної внутрішньої точки другого многокутника, назвемо її S-точкою, проводяться промені через його вершини. Називатимемо такі промені S-променями. Далі знаходяться точки перетину S-променів зі сторонами внутрішнього контура. У результаті таких побудов отримується множина опуклих многокутників (називатимемо їх елементарними), які утворюють геометричну фігуру з отвором.

Нумерація точок, що отримуються у результаті вищеописаних побудов здійснюється наступним чином. Спочатку вказуються у порядку обходу проти годинникової стрілки номери точок першого многокутника (від 0 до n-1, де n – кількість вершин першого многокутника). Потім також проти годинникової стрілки визначаються номери вершин другого многокутника (від n до n+m-1, де m – кількість вершин другого многокутника). Після чого вказуються номери вершин внутрішнього контура (від n+m до 2n+m-1). В останню чергу вказуються номери вершин, що є точками перетину променів із сторонами внутрішнього контура (від 2n+m до 3n+m-1).

Необхідно вказати у порядку обходу проти годинникової стрілки номери вершин кожного елементарного багатокутника. При цьому несуттєво з якого елементарного багатокутника починати їх перелік та з якої вершини кожного багатокутника починати обхід його контура.

Зауваження. У процесі побудови алгоритму може виявитися ситуація, при якій певний елементарний багатокутник потрібно поділити на кілька частин.

Вхідні дані: кількість вершин першого та другого багатокутників, пари номерів вершин внутрішнього контура, що перетинаються S-променями, починаючи з S-променя, що проходить через першу вершину внутрішнього багатокутника.

Результати: кількість отриманих елементарних багатокутників, номери вершин цих багатокутників у порядку обходу їх контура проти годинникової стрілки.

Приклад вхідних даних

5 5 13 14 14 10 10 11 12 13 12 13

Приклад результату (взагалі кажучи, правильний результат не єдиноможливий)

10

0 1 11 17 10

1 2 12 11

2 3 13 9 8 12

3 4 14 13

4 0 10 16 14

5 15 14 16 6

6 16 10 17 7

7 17 11 12 18 8

8 18 19 9

9 19 13 15 5

Технічні вимоги.

Для збереження результатів роботи у папці "Мої документи" створити папку "Olimp2006_*", де * – прізвище виконавця та код групи. Наприклад – "Olimp2006_Петренко31МФ". У папках з виконаними завданнями, крім файлів з вихідним кодом, повинні знаходитися відкомпільовані ехе-файли програм.

Задачу "Слово" зберегти у папці з іменем "Word"; задачу "Ламані" – у папці "BreakLines"; задачу "Отвір" – у папці "Whole".

Якщо передбачається реалізація підтримки роботи з файлами, то необхідно дотримуватись наступних вимог щодо форматів файлів та їх назв.

Усі файли мають бути текстовими. Файли з вхідними даними повинні мати назви "*_In.txt", файли з результатами – "*Out.txt", де * – назва папки задачі. Наприклад, для задачі "Ламана" відповідні файли повинні мати назви "BreakLines_In.txt" та "BreakLines_Out.txt".

Щодо структури подання даних у файлах необхідно дотримуватися таких вимог.

Задача "Слово". Перший рядок файлу із вхідними даними містить кількості рядків та стовпців таблиці, розділені символом пробілу. Наступні рядки файлу містять літери, що відповідають кожному рядку таблиці. Останній рядок файлу із вхідними даними містить слово, яке потрібно знайти у таблиці. Файл з результатом містить номери стовпців та рядків клітин таблиці, що відповідають літерам шуканого слова, розділені символом пробілу або табуляції, або символом переходу на наступний рядок.

Задача "Ламана". Перший рядок файлу із вхідними даними містить кількість прямокутників. У наступних рядках (рядку) містяться координати верхнього лівого та нижнього правого кутів прямокутників розділені символом пробілу або табуляції або символом переходу на наступний рядок. Перший рядок файлу з результатом містить кількість знайдених ламаних. У наступних рядках мають зберігатися кількості вершин для кожної ламаної. Після цього вказуються координати вершин ламаних у порядку їх обходу, розділені символом пробілу або табуляції або символом переходу на наступний рядок.

Задача "Отвір". Єдиний рядок файлу з вхідними даними містить кількості вершин першого та другого багатокутників та номери сторін внутрішнього контура, розділені символом пробілу. Перший рядок у файлі з результатом містить кількість знайдених елементарних багатокутників. У наступних рядках вказуються номери вершин цих багатокутників, розділені символом пробілу.

Оцінювання результатів розв’язування задач

Задача "Слово"

Перший тест – 3 бали; другий тест – 5 балів; третій тест – 7 балів.

Підтримка роботи з файлами – додатково 2 бали

Налаштування візуального інтерфейсу користувача – додатково 3 бали.

Максимальна кількість балів – 20

Задача "Ламані"

Перший тест – 5 балів; другий тест – 8 балів; третій тест – 12 балів.

Підтримка роботи з файлами – додатково 2 бали

Налаштування візуального інтерфейсу користувача – додатково 3 бали.

Максимальна кількість балів – 30

Задача "Отвір"

Перший тест – 10 балів; другий тест – 15 балів; третій тест – 20 балів.

Підтримка роботи з файлами – додатково 2 бали

Налаштування візуального інтерфейсу користувача – додатково 3 бали.

Максимальна кількість балів – 50

Максимальна кількість балів за усі задачі – 100