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

2004 рік

Перетин відрізків

1. На площині задано координати двох відрізків AB і CD. Знайти спільну частину проекцій цих відрізків на вісь абсцис.

Вхідні дані: з клавіатури вводяться 8 цілих чисел – координати точок A, B, C, D. Кожне число не перевищує за абсолютною величиною 1000.

Результат: на екран виводиться одне число – довжина спільної частини проекцій. Якщо спільна частина– порожня множина, вивести -1, якщо це одна точка – вивести 0.

Приклад вхідних даних та результатів

Введення: 2 2 7 5 3 4 8 1

Результат: 4

Кількість балів – 10

Найбільше і найменше число

2. Задано натуральне число N. Знайти найменше та найбільше число, яке складається з тих самих цифр та у такій самій кількості, що і N.

Вхідні дані : вводиться з клавіатури число N (1< N <200000000000000).

Результат : на екран виводиться в одному рядку найменше і через пропуск - найбільше число.

Приклад вхідних даних та результатів

Введення: 7051

Результат: 1057 7510

Кількість балів – 15

Шаховий слон

3. На шаховiй дошцi розмiрами М*N клiтинок стоїть слон (фiгура, що ходить по дiагоналi). З'ясувати, чи може слон дiйти до поля (x,y) Якщо може, то за яку найменшу кiлькiсть ходiв. Якщо кiлькiсть ходiв бiльша за 1, то вказати, через якi промiжнi клiтинки повинен пройти слон (якщо таких маршрутiв кiлька, вказати будь-який один з них). Поля шахової дошки кодуються парою натуральних чисел 1..М, 1..N, де перше число - номер горизонталi, а друге– номер вертикалi (1<=М, N<=1000).

Вхідні дані: з клавiатури вказуються через пропуск числа М, N, а далi координати початкового та кiнцевого полiв бажаного маршруту слона.

Результат: на екран виводиться число k (мiнiмальна кiлькiсть ходiв), а далi в k-1 рядках
по 2 числа через пропуск – координати вiдвiданих полiв. Якщо розв'язкiв немає, вивести 0

Приклад вхідних даних та результатів

Введення: 10 10 1 1 1 7

Результат: 2

4 4

Кількість балів – 30

Точка багатокутника

4. На площині задано багатокутник без самоперетинів координатами своїх вершин у порядку обходу цих вершин. Перевірити чи належить точка з координатами (x, y) багатокутнику. Вважати, що точка належить багатокутнику, якщо вона лежить у частині площини, обмеженої багатокутником або на одній з його сторін.

Вхідні дані: з клавіатури вказується через пропуск:

а) кількість вершин багатокутника – число в межах від 3 до 1000;

б) пари координат вершин багатокутника у порядку їх обходу – дійсні числа, модуль яких не перевищує 1000;

в) координати точки (x, y) для якої перевіряється її належність багатокутнику

Результат: на екран виводиться слово "ТАК" у разі належності точки багатокутнику або "НІ" у протилежному випадку.

Приклад вхідних даних та результатів

Введення: 5 1 1 7 1 7 5 4 2 1 5 2 3

Результат: ТАК

Кількість балів – 35

Технічні вимоги та зауваження щодо виконання завдань олімпіади.

1. У папці "Мої документи" створити папку "Олімп2004_*_#" для збереження виконаних розв’язків задач. Тут "*" – прізвище та ініціали виконавця олімпіади, "#" – номер групи. Наприклад, назва папки може бути така "Олімп2004_ПетернкоПІ_21Мі" (Петренко Петро Іванович з 21-шої МІ групи).

2. Тексти програм кожної задачі зберігати у окремій папці:

а) задачу "Перетин відрізків" – у папці "CrossLine";

б) задачу "Найбільше і найменше число" – у папці "MaxMinNumber";

в) задачу "Шаховий слон" – у папці "CheckEliph";

г) задачу "Точка багатокутника" – у папці "PsetInPoly"4

3. При наявності підтримки роботи з файлами для вхідних та вихідних даних до кількості балів кожної задачі буде нараховано додатково п’ять балів. Таким чином максимальна кількість балів для задач становитиме:

а) задача "Перетин відрізків" – 15 балів;

б) задача "Найбільше і найменше число" – 20 балів;

в) задача "Шаховий слон" – 35 балів;

г) задача "Точка багатокутника" – 40 балів.

4. Технічні вимоги щодо підтримки роботи з файлами:

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

б) імена файлів повинні починатися з префіксів "In" (для вхідних даних) та "Out" (для результатів) і закінчуватися назвою папки та мати розширення ".txt". Наприклад, для задачі "Перетин відрізків" імена файлів з вхідними даними та результатами мають бути такими: "InCrossLine.txt", "OutCrossLine.txt";

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