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

2005 рік

Задача 1. Множина чисел.

З клавіатури або файлу вказується ціле число з діапазону від 100 до 1000000. Вивести на екран монітора або у файл усі різні n-цифрові (n – кількість цифр у введеному числі) числа, які можна утворити з цифр введеного числа у порядку їх слідування у записі числа. Вважати, що за останньою цифрою введеного числа слідує перша цифра. Введене число не враховувати. Підрахувати суму отриманих чисел. Цифра нуль не може використовуватись, як перша цифра числа.

Вхідні дані. Ціле число з вище вказаного діапазону.

Результат. Перелік отриманих чисел у довільному порядку та сума цих чисел. Числа розділяються символом пробілу.

Приклад. Вхідні дані: 1203

Результат: 2031 3120 5151

Задача 2. Огинаюча прямокутників.

Кожен прямокутник з деякої множини прямокутників визначається за допомогою трьох параметрів: ширини (W), висоти (H) та розташуванням лівї нижньої вершини на координатній осі (S) (див. мал. 1). Усі параметри прямокутника –цілі числа з діапазону від 1 до 1000. Користувач вказує з клавіатури або з файлу параметри для N прямокутників (1<N<1000). Для отриманої множини прямокутників знайти сумарну довжину ламаних, що огинають усі прямокутники. Якщо на числовій осі є ділянки, які не належать жодному з прямокутників, то їхні довжини не потрібно враховувати (див. мал. 2).

Мал. 1 Мал. 2

Вхідні дані. З клавіатури або з файлу вказується спочатку кількість прямокутників а потім через пробіл трійки чисел, що визначають параметри кожного прямокутника: перше число з трійки – параметр S; друге – параметр W; третє – параметр H.

Результат. На екран монітора або у файл виводиться значення сумарної довжини усіх ламаних.

Приклад. Вхідні дані: 5 1 2 3 2 3 2 4 3 4 9 1 3 10 2 2

Результат: 25

Задача 3. Обхід фігури.

У масиві символів з M рядків та N стовпців (3<M<1000, 3<N<1000) за допомогою символу "*" закодовано певну фігуру, що не містить "отворів" і складається з одного "шматка". Елементи масиву, що не належать фігурі кодуються символом "0" (нуля). Кожен символ елементу масиву називатимемо точкою. Точка фігури вважається її вершиною, якщо вона межує лише з однією точкою, що не належитьфігурі або якщо на діагоналі точки існує точка, що не належить фігурі і, при цьому, зправа та знизу або зліва та знизу, або згори та зліва, або згори та зправа межує з точками, що теж не належать фігурі. Знайти номери стовпчиків та рядків тих точок фігури, які є вершинами і відобразити ці номери у порядку обходу контуру фігури, причому не суттєво з якої точки починати обхід. Контур фігури можна обходити лише у чотирьох напрямах: вліво, вправо, вгору, вниз. Відомо, що кожна точка фігури межує не менше ніж з трьома її іншими точками (включаючи діагональні елементи) і при цьому усі межові точки для деякої точки фігури не можуть розташовуватись на одній вертикалі чи горизонталі.

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

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

Приклад. Вхідні дані: 7 8 Мал. 3

00000000 00000000

000***00 000***00

00****00 00****00

0*****00 0*****00

0******0 0******0

0******0 0******0

00000000 00000000

Результат: 2 4 2 6 5 6 5 7 6 7 6 2 4 2 4 3 3 3 3 4 (див. мал. 3)

Оцінювання виконаних завдань

1. Задача "Множина чисел" – 15 балів

2. Задача "Огинаюча прямокутників" – 30 балів

3. Задача "Обхід фігури" – 30 балів

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

а) Задача "Множина чисел" – 2 бали

б) Задача "Огинаюча прямокутників" – 3 бали

в) Задача "Обхід фігури" – 5 балів

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

6. Максимальна кількість балів – 85

Технічні вимоги до виконання завдань

1. Усі програми-розв’язки задач повинні зберігатися за шляхом "Мої документи \ Olimp2005_*", де "*" – код учасника, який записується за наступним правилом. Прізвище учасника, потім символ підкреслення і код групи. Наприклад учасник Петренко є студентом 31МІ групи. Його результати виконання завдань олімпіади повинні бути збережені за шляхом: "Мої документи \ Olimp2005_Петренко_31МІ"

2. Папка з розв’язками задач повинна містити exe-файли і файли вхідних та вихідних даних (файли з текстами програм у цю папку можна не копіювати).

3. Файли вхідних даних та результатів повинні бути текстового формату.

4. Кожен файл-програму та файли вхідних-вихідних даних іменувати відповідно до наступних вимог.

Задача "Множина чисел": range.exe, rangeIn.txt (вхідні дані), rangeOut.txt (вихідні дані)

Задача "Огинаюча прямокутників": rl.exe, rlIn.txt (вхідні дані), rlOut.txt (вихідні дані)

Задача "Обхід фігури": run.exe, runIn.txt (вхідні дані), runOut.txt (вихідні дані)

5. Якщо не враховані технічні вимоги (збереження результатів не за вказаним шляхом і не під вказаними іменами), то робота учасника не розглядатиметься.