June 14, 2017
На примере задачи Эния разберём, что вообще представляет из себя ACM-задача. Отметим, что решением задачи является программа на некотором языке программирования, и проверяются решения автоматически. Ниже мы обсудим это подробнее, а пока стоит это просто запомнить, потому что на этом основана некоторая специфика задач по сравнению с математическими олимпиадами, например.
Здесь содержится постановка самой задачи, то есть объясняется, что нужно делать. Эта часть слабо отличается от других олимпиад. Иногда даётся сразу математическая формулировка задачи, но обычно авторы стараются придумать некоторую легенду, сделать задачу жизненной.
В задаче Эния математическая формулировка — Посчитайте сумму удвоенных площадей $N$ прямоугольников $A \times B$. Легенда — Найдите необходимую для обработки панелей массу сульфида.
Здесь чётко специфицируется, что и в каком порядке будет подано на вход программы.
В задаче Эния на вход подается три целых числа ($N$, $A$, $B$), записанных в одной строке через пробел.
Это какие-то условия, которые точно будут выполнены на всех входных данных.
Типичные ограничения:
Обычно разделы “входные данные” и “ограничения на входные данные” объединяют, но есть исключения.
В задаче Эния все числа на входе лежат в диапазоне $[1;100]$
Здесь чётко специфицируется, что и в каком порядке должно выдать решение.
В задаче Эния нужно выдать одно число: массу сульфида.
Решение будет запущено в некоторой песочнице, и ему будет выделено определённое количество времени и памяти. Если решение будет использовать больше времени или памяти, то оно будет признано неверным. Соответствующие ограничения времени и памяти указываются в условии.
В задаче Эния ограничение по времени составляет 1 секунду, ограничение по памяти — 64 МБ.
Почти всегда в задачах приводят примеры валидных (удовлетворяющих всем ограничениям) тестов и правильных ответов на эти тесты. Это является важной частью условия. Иногда описать вид входных данных словами намного сложнее, чем показать на примере. Цельь примеров не в том, чтобы дать участникам тест для проверки своей программы, а в том, чтобы показать формат ввода и вывода и проверить понимание условия.
В задаче Эния тест “5 2 3” является валидным, и правильный ответ на него — 60.
Решение задачи — это программа на одном из поддерживаемых на соревновании языке программирования. Стандартом де-факто является поддержка C++ и Java, многие участники используют Python, остальные языки используются намного реже.
Пример решения задачи Эния на C++:
1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
int main()
{
int N, A, B;
cin >> N >> A >> B;
cout << 2 * N * A * B << endl;
return 0;
}
Есть исключения: на некоторых соревнованиях, в том числе очень престижных Google Code Jam и Facebook Hacker Cup, участнику высылается тест, а он должен прислать ответ на этот тест. Впрочем, обычно вся разница в том, что тестирование происходит на компьютере участника, и ограничение по памяти примерно равно объёму оперативной памяти.
Для проверки есть заранее подготовленный набор тестов, одинаковый для всех участников. Решение участника автоматически запускается на тесте, затем, в случае успешного завершения в пределах отведённых времени и памяти, вывод программы проверяется на правильность.
И это очень важная специфика соревнований по программированию: чтобы сдать (решить) задачу, не нужно уметь доказывать своё решение. Более того, решение может быть неверным; необходимо и достаточно, чтобы оно проходило все тесты из заранее подготовленного набора. Конечно, обычно тесты участникам неизвестны, однако сам факт того, что их конечное количество, говорит о том, что покрыть все возможные случаи обычно невозможно. Количество тестов обычно не сильно больше 100, и почти наверное не больше 500.
Есть задачи, в которых ответ определяется однозначно, тогда для проверки нужно просто сравнить ответ с правильным. Однако иногда ответ неоднозначный. В таких случаях авторы задачи пишут специальную программу, которая проверяет ответ участника на правильность.
Некоторые тестирующие системы не сообщают номер теста, который решение не прошло.