2. Як перевіряються розв'язки задач олімпіади Печать
Добавил(а) Administrator   
03.10.12 08:36

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

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

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

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

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

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

Програми-розв'язки рекомендується перевіряти за системою тестів. До кожної задачі необхідно підготувати набір тестових даних, які б дозволяли розрізнити правильні та неправильні розв'язки, а серед правильних - більш та менш ефективні.

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

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

Рекомендована кількість тестів в наборі для однієї задачі - 10. Для більш складних задач це число можна збільшити до 20. Серед тестів повинні бути: декілька тестів невеликого розміру, виконання яких свідчить про правильність запропонованого алгоритму; тести, що перевіряють коректність роботи програми у спеціальних випадках (вироджені випадки, відсутність розв'язку); тести великого розміру, виконання яких свідчить про ефективність запропонованого алгоритму.

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