Книжная полка

Оформление условий задач

Александр Ипатов, Михаил Рубинчик

Рекомендации были написаны во время подготовки осенних соревнований 2013 года

Многие участники соревнований одновременно являются и авторами задач. Поэтому, думаю, данная тема найдёт широкий отклик.

В известной статье «Как стать чемпионом Урала по программированию» написано «Постарайтесь писать одинаковые вещи АБСОЛЮТНО одинаково». Некоторые тренеры трактуют этот тезис следующим образом: исходник решения должен быть написан так, чтобы по нему невозможно было понять, кем из участников команды он написан. Аргументация простая: когда ты ищешь ошибку в распечатке чужого исходника, то чем больше взгляд цепляется за что-то, написанное не так, как делаешь ты, тем сложней тебе будет найти ошибку.

Теперь представим себе, что мы работаем в программном комитете – т.е. в команде, которая не решает задачи во время пяти часов соревнования, а готовит эти задачи. В частности, наша команда должна написать несколько условий задач (10-12) и вылизать их до безупречного состояния. Вычитывание условий задач не сильно отличается от вычитывания исходника, и если бы все условия были оформлены по одинаковым стандартам, то вычитывать их было бы проще.

Стандарты оформления условий задач на соревнованиях, проходящих в Уральском федеральном университете, существуют в виде устного народного творчества, то есть передаются из уст в уста, постепенно обрастая новыми. Мы попытались задокументировать эти стандарты, дополнив их несколькими полезными советами по подготовке условий задач.

Опыт показывает, что если придерживаться всех приведённых правил, то можно застраховаться от большого количества ошибок в задачах.

Текст подразумевает, что условия задач пишутся на русском и английском языках и оформляются в TeX-е с применением стилевого файла olymp.sty (в частности, одна из версий этого стилевого файла используется в системе Polygon).

1. Название задачи должно быть оригинальным и иметь отношение к тому, что происходит в задаче. Название – это идентификатор задачи, и через несколько лет после контеста вспомнить задачу «Тилимилитрямдия» обычно проще, чем задачу «Строка» или «Дерево». Если условие не даёт шанса придумать к нему нормальное название (скажем, целиком состоит из математической постановки), можно, не переделывая условие, добавить в него персонажей и/или одно вводное предложение. Скажем, заменить Васю и Петю на Холмса и Ватсона, и тогда, возможно, название придумается само.
2. Сэмпл должен по возможности что-то демонстрировать. Обычно единственный сэмпл, в котором на вводе число 1 (а случай n = 1 является частным в задаче) не помогает лучше понять, что нужно сделать в задаче. Если ответ на сэмпл нетривиален, имеет смысл пояснить, почему он такой, или в основной части условия, или в хинте после сэмпла. Обратное тоже верно – если в основной части условия описывается какая-то ситуация, хорошим тоном является дать сэмпл именно на эту ситуацию. Если в задаче предполагается несколько принципиально разных ситуаций на выводе (скажем, вывести решение / сказать, что их много / сказать, что их нет), то желательно на каждую из этих ситуаций сделать отдельный сэмпл.
3. Сэмпл должен помогать лучше понять условие задачи, но не должен подсказывать, как она решается. Например, если нетривиальным фактом является то, что задача всегда имеет целое решение, то лучше придумать сэмпл, для которого также существует оптимальное нецелое решение (и дать это нецелое решение в качестве ответа).
4. В тех случаях, когда входные данные содержат строку с двумя равнозначными переменными (количество строк и столбцов матрицы или размер чего-нибудь по X и по Y), имеет смысл в сэмпле сделать эти величины различными, чтобы застраховать себя и участников от путаницы в них. Очень распространены ошибки в задачах, когда первая строка по условию содержит n и m, а по факту m и n.
5. Хорошим тоном является считать количество сэмплов в задаче и использовать из команд olymp.sty \Example, \Examples правильную. Впрочем, если вы используете Polygon, он сделает это за вас.
6. Условия должны быть написаны так, чтобы оставаться корректными независимо от того, какой ввод/вывод используется (потоки или файлы). В частности, они не должны содержать сочетаний «входной/выходной файл», «input.txt/output.txt», «стандартный входной поток» и т.п. Как показывает практика, этого можно добиться всегда.
7. Нужно избегать в условии термина «натуральное число», заменяя его на «целое положительное» или просто «целое» (в таком случае то, что оно не меньше единицы, вносится в ограничения). Также в выражениях типа «Первая строка содержит число n» лучше всегда вместо «число» писать «целое число», даже когда то, что оно целое, очевидно из контекста (пояснено, что это количество чего-то).
8. Если у одной из величин в условии указана размерность (скажем, метры в секунду), то нужно проверить, чтобы она была указана и у всех остальных величин на вводе и выводе, связанных с нею (то есть метры и секунды, соответственно). Альтернатива – не указывать размерность ни у одной величины.
9. Не нужно давать в задаче заведомо невозможные ограничения. Например, это касается случая, когда стоит ограничение снизу n ≥ 0, но n = 0 явно или неявно противоречит условию задачи (при этом оно могло не противоречить мат.модели, которая была до написания литературной сказки). Другой пример: «n ≥ 1; n чётно» – вместо этого нужно написать, «n ≥ 2; n чётно».
10. Если подряд даётся несколько ограничений на переменные, эти ограничения нужно разделять точкой с запятой, а не запятой. Пример: ограничение a ≤ b, c ≤ d можно понять как двойное неравенство на b и c и как два не связанных неравенства. Во втором случае вместо запятой должна стоять точка с запятой.
11. Желательно избегать термина «запятая» у действительного числа. То есть вместо «выведите ответ с точностью столько-то знаков после запятой» лучше писать «после десятичной точки», а ещё лучше просто «с точностью такой-то» (например, 10⁻⁵). В последнее время стало принято вместо стандартного чекера float использовать чекер rfloat, проверяющий и относительную, и абсолютную погрешность ответа. Если используется он, в формате вывода вместо «Выведите число с точностью 10⁻⁵» нужно писать «Выведите число с абсолютной или относительной погрешностью не более 10⁻⁵».
12. Тонкий момент – когда решение неоднозначно, а вывод содержит действительные числа, округлённые до скольки-то знаков. Формально в данном случае требовать ответ с какой-то точностью нельзя, потому что чекер при проверке ответа будет выполнять какие-то вычисления и сравнивать с эпсилоном их результат, а не выходные данные участника. В таких случаях бывает уместно написать в формате вывода что-то про то, как именно чекер будет проверять ответ участника (пример – задача 1757 с Тимуса. Если это невозможно, то допустимо написать в формате вывода «Выведите ответ с максимальной возможной точностью». Мотивация – если в формате вывода написано «Выведите ответ с точностью 10⁻⁵», то при правильном ответе 0 решение участника, выводящее 0.00005, не должно быть засчитано (даже если чекер при вычислениях считает такую погрешность допустимой).
13. Если в задаче возможно несколько решений, то нужно явно писать фразу типа «Если задача имеет несколько решений, выведите любое из них». Если задача всегда имеет решение, но ещё нужно додуматься, что это так, лучше написать «Гарантируется, что задача всегда имеет решение».
14. Знаки препинания и типографика:
    • В русских условиях нужно использовать кавычки <<a>>, в английских – кавычки ``a''.
    • В качестве тире во всех местах нужно использовать одинаковое: или везде длинное (---), или везде короткое (--), но уж точно не дефис. Пробел перед тире должен быть неразрывным (~).
    • Все сокращения окончаний числительных и переменных в русском языке должны быть записаны через дефис: n-й, n-я, n-е, n-го, n-му, n-м, n-й, n-ю, n-х, n-ми. Неправильно начинать сокращение с гласной, если за гласной что-то ещё есть (n-ый, n-ую, n-ому)! В английском языке лучше писать сокращение через апостроф, а не через дефис (n'th).
    • В английском условии стоит избегать тире. В конструкциях вида «The first line contains an integer n – the number of kittens» нужно заменять тире на «that is» или менять порядок слов. Если тире всё же есть, нужно писать его или без пробелов, или с короткими пробелами (\,). Прямая речь и диалоги в английском языке оформляются с кавычками, но без тире!
    • Длинные числительные (не менее пяти разрядов) лучше разбивать по разрядам – 10 000. В числительных с четырьмя разрядами можно по желанию также ставить короткий пробел после первой цифры, но тогда надо следить, чтобы это правило выполнялось повсеместно (а не так, что в одной задаче 1000, а в другой 1 000)!
    • Желательно избегать в предложениях написания коротких числительных цифрами там, где они не являются частью ограничений или формул: вместо «На столе лежало 2 предмета: 1-й и 2-й» нужно писать «На столе лежало два предмета: первый и второй».
15. Строки и символы в формате ввода/вывода в большинстве случаев надо писать в кавычках. Обычно в основном техе пишется \newcommand{\s}[1]{\mbox{<<\texttt{#1}>>}} (кавычки приведены для русского условия) и далее в условиях «выведите ответ \s{No solution}». Мотивация – фразы на вводе/выводе могут содержать знаки препинания, и без кавычек не всегда ясно, являются они частью фразы или нет. Это не означает, что вместо кавычек, выполняющих в условии роль знаков пунктуации, нужно писать \s{}!
16. Следует избегать излишеств в формулировках:
    • Не нужно писать в формате ввода, сколько величин дано в очередной строке входных данных, если далее перечислены их обозначения. Пример: вместо «В первой строке входных данных записаны три целых числа a, b, c» нужно писать «В первой строке входных данных записаны целые числа a, b, c». Надо думать, что участники в состоянии сами посчитать до трёх, если захотят.
    • В формате вывода в конструкциях вида «Выведите в единственной строке целое число x – сколько мышат ребята несут в Ленинград» следует опускать то, что строка единственная, сколько величин в ней надо вывести и обозначения этих величин, если они несущественны. Правильная формулировка: «Выведите, сколько мышат ребята несут в Ленинград» Но если в первой строке нужно вывести число n, а во второй – ещё n чисел, то опускать обозначение n нельзя.
17. Условия всех задач должны быть оформлены одинаково. Примеры, как не должно быть:
    • В одной задаче все числа на вводе обозначаются маленькими латинскими буквами, а в другой – большими.
    • В одной задаче ограничение 10⁵, а в другой 100000.
    • В одной задаче в качестве Ё используется Ё, а в другой Е (ещё хуже, когда в одном тексте только в части слов стоят Ё!)
    • Знаки ≤, ≥ в одной задаче записаны с горизонтальной нижней чертой, а другой – с наклонной.
    • В одной задаче ограничение 1 < n < 100, а в другой 2 ≤ n ≤ 99. Вообще лучше всегда, когда это возможно, использовать нестрогие неравенства.
    • В формате ввода в одном месте ограничения на переменную следуют до пояснения, что она означает, а в другом – после. Пример: «n (1 ≤ n ≤ 100) – количество попугаев» и «m – количество удавов (1 ≤ m ≤ 100)». Предлагаем все ограничения писать после пояснения (как в примере с удавами).

Эту страницу можно найти на сайте Уральские олимпиады по адресу http://sp.urfu.ru/library/statements.html