Сайт підготовки до олімпіади з інформатики

Готуємось до олімпіади з інформатики

1. Що таке олімпіадна інформатика?

Що потрібне для успішної участі в олімпіадах по інформатиці? Як показує практика, тільки знання мови програмування для цього явно не достатньо. Взагалі, виявляється, що олімпіадні задачі по інформатиці лежать десь на стику математики і програмування. І дуже часто виявляється, що розв’язуючи задачі школярі не тільки вчаться програмувати, але і освоюють нові розділи математики.

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

Перші олімпіади 1934 рік. Олімпіади з інформатики насправді дуже відрізняються від олімпіад з інших предметів:

-                             По-перше, всі учасники (і 8, і 11 класи) розв’язують одні і ті ж задачі (як правило – 3-4) 

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

Якщо з вивченням мови програмування у вас не повинно виникнути складнощів (величезна кількість книг по цій темі), то ось з алгоритмами доведеться складніше. Книг по цій темі теж немало, але вони, частіше всього, дуже переобтяжені теорією, а на олімпіадах потрібна тільки практика. З електронних джерел по алгоритмах можу порадити книгу С.М.Окулова і сайт algolist.manual.ru , який менш націлений на вивчення "олімпіадної інформатики", ніж книга Окулова, але містить велику кількість алгоритмів, яких немає в книзі, але які було непогано б знати.

Звикайте працювати в режимі: написання + відладка на Borland Pascal/Borland C++. Нові 32-бітові компілятори не мають жорсткого обмеження в пам'яті і працюють істотно швидше (особливо помітна різниця в швидкості виконання 16 і 32-бітових програм на P4). Така хитра тактика пояснюється відсутністю пристойного відладчика в нових платформах і їх практично повною сумісністю з компіляторами фірми Borland.

2. Як перевіряються розв’язки задач олімпіади

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

Програма повинна виводити відповідь строго в описаному в умові форматі (тобто, наприклад, якщо програма раптом виведе у відповідь два числа в переплутаному порядку або замість числа-відповіді надумає написати слово "відповідь" і потім вже сама відповідь, перевіряючим комп'ютером це буде сприйнято як повністю неправильний розв’язок - він не зможе, та і не намагатиметься шукати, а в чому ж ви помилилися).

Другий наслідок з автоматичної перевірки - як правило, тести по задачі складаються так, щоб "покрити" всі можливі випадки. У тому числі і максимальні. Тобто якщо, наприклад, в умові написано, що "у вхідному файлі записано N чисел і N не перевищує 1000", то тест на N=1000 (або дуже близьке до нього число) майже напевно буде.

Ще одна традиція олімпіадних задач, коректність вхідних даних. Тобто, якщо це особливо не написано в умові, не вимагається перевіряти коректність вхідних даних - вхідні дані повністю відповідатимуть описаному в умові формату і задовольнятимуть всім вказаним обмеженням.

Ваш розв’язок повинний читати вхідні дані з вхідного файлу (його ім'я звичайно вказано в умові задачі) в описаному форматі, розв’язати задачу, і виводити результат у вихідний файл (його ім'я теж звичайно вказується в умові). Програма повинна завжди завершуватися з кодом 0 (інакше тестуюча програма вважає, що в ході роботи відбулася помилці) - тобто командою halt(0); або просто дійти до кінця на Паскалі.