05.09.2017
Подготовка олимпиадных задач для ejudge / Alexey Nurgaliev

Краткое руководство по подготовке задач олимпиад по программированию для использования в системе ejudge.

В руководстве будут рассматриваться только задачи для олимпиад по правилам ACM ICPC или аналогичным.

Обычно в ejudge олимпиадная задача состоит из:

Условие

Условие задачи хранится в файле statement.xml. Примерное его содержание:

<?xml version="1.0" encoding="utf-8" ?>
<problem
        package="ru.codemore.contest"
        id="A"
        type="standard">

    <statement language="ru_RU">

        <title>...</title>

        <description>
            <p>...</p>
        </description>

        <input_format>
            <p>...</p>
        </input_format>

        <output_format>
            <p>...</p>
        </output_format>

        <notes>
            <p>...</p>
        </notes>

    </statement>

    <examples>

        <example>
            <input>...</input>
            <output>...</output>
        </example>

    </examples>

</problem>

Пример statement.xml реальной задачи:

<?xml version="1.0" encoding="utf-8" ?>
<problem
        package="ru.pskovedu.contest"
        id="rot13"
        type="standard">

    <statement language="ru_RU">

        <title>Шифр ROT13</title>

        <description>
            <p>
                Алгоритм шифрования ROT13 является вариацией шифра Цезаря.
            </p>
            <blockquote>
                Применение алгоритма ROT13 к части текста требует простой замены каждого
                буквенного символа на соответствующий ему со сдвигом на 13 позиций в алфавите.
                A становится N, B становится O, и т. д. до М, которое становится Z, а затем
                последовательно применяются буквы из начала алфавита: N становится A,
                O становится B, и так далее до Z, которая становится М. Затронуты лишь те буквы,
                которые используются в английском алфавите; цифры, символы, пробелы и все остальные
                символы остаются без изменений.
            </blockquote>
            <a href="https://ru.wikipedia.org/wiki/ROT13">https://ru.wikipedia.org/wiki/ROT13</a>
        </description>

        <input_format>
            <p>
                В первой строке дано целое число N (1&le;N&le;100) - длина строки.
            </p>
            <p>
                Во второй - строка состоящая из N символов - заглавных и строчных латинских букв,
                пробелов и знаков препинания ",.!?-" (не включая кавычки), зашифрованная по алгоритму ROT13.
            </p>
            <p>
                Гарантируется, что строка не начинается и не заканчивается пробелом.
            </p>
        </input_format>

        <output_format>
            <p>
                Расшифрованная строка.
            </p>
        </output_format>

    </statement>

    <examples>

        <example>
            <input>
13
Uryyb, jbeyq!
            </input>
            <output>Hello, world!</output>
        </example>

    </examples>

</problem>

Статья в ejudge wiki содержит описания и других тегов, которые можно включить в условие.

Решение жюри

Решение задачи, предоставленное жюри.

Должно проходить все тесты, соотвествовать ограничениям по времени и памяти, а также полностью соответствовать правилам олимпиады (если правилами накладываются какие-либо особые граничения).

Также рекомендуется, чтобы решение было написано на языке, разрешенном на олимпиаде.

Пример решения (для задачи, описанной выше):

package rot13;

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        in.nextLine();
        String s = in.nextLine();
        System.out.println(rot13(s));
    }

    public static String rot13(String s) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isAlphabetic(c)) {
                if (Character.isUpperCase(c)) {
                    c = (char)((c - 'A' + 13) % 26 + 'A');
                } else {
                    c = (char)((c - 'a' + 13) % 26 + 'a');
                }
            }
            sb.append(c);
        }

        return sb.toString();
    }

}

Набор тестов

Тест - это два текстовых файла, содержащих корректные входные и выходные данные задачи. Рекомендуется, чтобы:

Файлы тестов можно поместить в каталог tests, файлы входных данных назвать номером теста, файлы выходных данных - номером теста и расширением .a (расположение и наименование можно изменить в настройках контеста).

Чекер

Чекер - программа, проверяющая корректность решения участника, использующая три файла: входные данные, выходные данные жюри, выходные данные участника.

Проверка может закончиться с одним из результатов:

Для написания чекеров обычно используется библиотека testlib, предоставляющая многие полезные методы. При использовании библиотеки, нужно ее код (testlib.h) также включить в файлы задачи.

testlib предоставляет несколько стандартных чекеров, например:

Пример чекера для задачи, описанной выше (используется стандартный fcmp.cpp):

#include "testlib.h"
#include <string>
#include <vector>
#include <sstream>

using namespace std;

int main(int argc, char * argv[])
{
    setName("compare files as sequence of lines");
    registerTestlibCmd(argc, argv);

    std::string strAnswer;

    int n = 0;
    while (!ans.eof()) 
    {
        std::string j = ans.readString();

        if (j == "" && ans.eof())
          break;

        strAnswer = j;
        std::string p = ouf.readString();

        n++;

        if (j != p)
            quitf(_wa, "%d%s lines differ - expected: '%s', found: '%s'", n, englishEnding(n).c_str(), compress(j).c_str(), compress(p).c_str());
    }
    
    if (n == 1)
        quitf(_ok, "single line: '%s'", compress(strAnswer).c_str());
    
    quitf(_ok, "%d lines", n);
}

Настройки контеста

Каждой задаче соответствует раздел в настройках контеста (файл serve.cfg).

Для задания общих настроек для всех задач используются “абстрактные” задачи. Пример настройки такой задачи:

[problem]
abstract
short_name = "PskovGeneric"
use_stdin
use_stdout
use_corr
xml_file = "statement.xml"
test_pat = "%02d"
corr_pat = "%02d.a"
time_limit = 5
real_time_limit = 10
max_vm_size = 256M
max_stack_size = 256M
max_file_size = 256M
check_cmd = "check"

Здесь определены настройки:

Далее описываются настройки конкретных задач.

Пример настройки для задачи. описанной выше:

[problem]
super = PskovGeneric
internal_name = "rot13"
short_name = "B"
long_name = "Шифр ROT13"

Здесь определены настройки:

Статья в ejudge wiki содержит подробное описание настроек контеста.

Polygon

Задачи удобно готовить в системе polygon. Она поддерживает множество возможностей по организации работы над отдельными задачами и над контестом в целом.

Некоторые полезные возможности:

Существует возможность автоматизированной загрузки задач и контестов из polygon в ejudge. Однако на момент написания руководства условия не импортировались: polygon использует для оформления условий TeX, а ejudge HTML.

Лицензия Creative Commons
Code More Team - GitHub