Реєстрація

Algomania – Змагання та приклади завдань

Завдання

Завдання задач, які доступні учасникам, можна подивитися у електронному вигляді. На умови можна подивитись, використавши меню (пункт “Завдання”). У кожній умові вказується обмеження по часу і пам’яті та посилання, по якому можна відіслати на перевірку розв’язок цієї задачі. Також задається формат вхідних та вихідних даних, їхні приклади. Формат вхідних та вихідних даних Вашого розв’язку повинен точно співпадати із даними в умові. Інакше система перевірки сприйме це як неправильну відповідь. Для того, щоб перевірити правильність формату даних, можна відіслати на перевірку лише на першому тесті.
Приклади завдань на сайті acm.lviv.ua та icpc.baylor.edu (pdf).

Надсилання розв’язків

Розв’язком вважається текст програми, написаний на одній з дозволених мов програмування, який у подальшому можна відкомпілювати відповідним компілятором та перевірити на всіх тестах.

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

Приклади розв’язків.

Умова: програма зчитує двоцифрове число і виводить через пробіл кожну цифру окремо.

Приклад розв’язку на мові програмування Pascal:

var 
a,b,c:integer;
begin 
read(a); 
b := a div 10; 
c := a mod 10; 
writeln(b,' ',c);
end.

Приклад розв’язку на мові програмування С++ (перший варіант):

#include <cstdio> 
int main(){ 
int a = 0; 
scanf("%d", &a); 
printf("%d %d\n", a/10, a%10); 
return 0;
}

Приклад розв’язку на мові програмування С++ (другий варіант):

#include <iostream>
using namespace std; 
int main(){ 
int a = 0; 
cin >> a; 
cout << a/10 << " " << a%10 << endl; 
return 0;
}

Лише перший тест

Якщо відправити розв’язок із відміткою «лише перший тест», то Ваш розв’язок буде протестовано лише на одному тесті (перший тест з умови, вказаний у прикладах вхідних та вихідних даних). Результати цієї перевірки ні на що не впливають. Це зручно використовувати для того, щоб перевірити правильність формату вихідних даних. Також, якщо у Вас виникають труднощі із компіляцією програми, то спочатку бажано спробувати відправити у цьому режимі, щоб побачити результат.

Перевірка розв’язків

  • Компілятори
    Для компілювання Ваших розв’язків використовуються наступні компілятори:
  • Pascal: Delphi7, консольний режим. Процес компілювання відбувається наступним чином: Dcc32.exe –CC source.pas.
  • С++: Microsoft Visual Studio C++ Express Edition. Процес компілювання відбувається наступним чином: cl.exe –I source.cpp –link –libpath шлях до бібліотек.

Автоматичне тестування

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

  • Введення / виведення
    Процеси введення / виведення відбуваються лише з екраном та клавіатурою. Потрібно виводити тільки ту інформацію, що вказана в умові і ніяких допоміжних символів, бо це призведе, до того, що Ваш розв’язок буде вважатися невірним. Програма після виведення результатів має завершувати свою роботу, а не чекати ще на якесь додаткове натиснення клавіш. Використовувати якісь файли категорично забороняється.
  • Лише перший тест
    Якщо необхідно перевірити правильність формату введення / виведення – можна перевірити розв’язок лише на першому тесті, це ніяк не вплине на місце в рейтингу.
  • Обмеження
    Для знаходження розв’язку на кожному тесті окремо задаються обмеження по часу та пам’яті.
  • Розмір тексту розв’язку
    Текст розв’язку до будь-якої задачі обмежується по розміру до 65535 байт. В іншому випадку система прийме лише перших 64Кб і Ви, швидше за все, отримаєте помилку компіляції.
  • Код завершення програми
    Після завершення програми повертається код завершення програми операційній системі. Якщо цей код буде не рівним 0 – це означає, що Ваш розв’язок завершився через якусь критичну помилку. У мові програмування С++ необхідно явно вказувати код завершення, інакше система сприйме не нульовий код завершення як помилку під час виконання. (необхідно писати int main(){… return 0;})
  • Результат тестування
    Якщо алгоритм складений правильно, то повідомляється додатково кількість використаної пам’яті, час затрачений на знаходження відповіді, а також кількість тестів для цього розв’язку. У випадку невдалої спроби надається додатково інформація в залежності від типу помилки.
  • Помилки, які розпізнає система:
    • Помилка компіляції (Compilation Error, CE) – Допущена синтаксична помилка в тексті алгоритму і система не змогла скомпілювати ваш розв’язок. Або Ваш розв’язок не відповідає стандарту компілятора, який використовується у нашій системі.
    • Помилка часу виконання (Runtime Error, RE) – Під час виконання алгоритму відбулася критична помилка, при якій подальше виконання неможливе. Типові помилки: ділення на 0 (нуль), доступ до неіснуючого елементу у масиві. Також можлива ця помилка у випадку, якщо код завершення програми не дорівнює нулю.
    • Невірна відповідь (Wrong Answer, WA) – Ваш алгоритм хоча б на одному з тестів подав неправильну відповідь, або формат виведення не відповідає умові.
    • Ліміт часу (Time limit, TL) – Ваш алгоритм не вклався у відведений для знаходження відповіді час. Цей ліміт подається в умові задачі і рахується для кожного тесту окремо. Час виконання програми – це загальний час від моменту запуску програми і аж до її повного завершення.
    • Ліміт пам’яті (Memory limit, ML) – Ваш алгоритм використовує більше пам’яті, ніж було для цього відведено.
    • Ліміт виведення (Output limit, OL) – Результат роботи вашого розв’язку, крім того що є неправильним, є занадто великим по розміру. Відведений об’єм результату не подається, але він завжди більший очікуваного результату.
    • Заборонена функція (DF) – При створенні алгоритму Ви використали функцію, яка є забороненою. Забороняється використовувати додаткові модулі, бібліотеки, експортувати зовнішні функції, використовувати ассемблерні вставки, користуватися файлами (якщо інше не зазначено в умові), викликати функції операційної системи. Якщо це буде повторюватись досить часто – Вас буде дискваліфіковано за порушення правил. Якщо Ви сумніваєтесь у тому, чи ви не використали якусь заборонену функцію, то можете спробувати «лише перший тест».

Рейтинг (монiтор)

Рейтинг працює наступним чином: Вище в рейтингу той, хто здав більшу кількість задач (написав правильно алгоритм для розв’язку задачі). При однаковій кількості зданих задач враховується кількість спроб: чим менше – тим вищий рейтинг. Спроби, які були здані з поміткою «лише перший тест», не враховуються.