Почему в олимпиадных задачах не надо проверять входные даннные на корректность

18.05.2019

В типичной олимпиадной задаче (и, соответственно, в типичной задаче на алгопроге) в условии четко оговариваются максимальные допустимые значения для переменных или другие ограничения на входные данные. Например, так:

В единственной строке входных данных вводятся два числа K и T, разделенные пробелом. Оба числа натуральные и не превосходят 1 000 000 000.

В результате у многих людей возникает желание в решении такой задачи проверить, правда ли, что эти числа удовлетворяют этим ограничениям, написать так называемую «защиту от дурака»:

if k <= 0 or k > 1000000000 or t <= 0 or t > 1000000000:
    print("Неправильные числа")
    sys.exit(0)  # или sys.exit(1)

Или что-нибудь еще более жесткое, типа бесконечного цикла «пока пользователь не введет корректные данные».

Так вот, ничего этого делать не надо!

Если в условии задачи написано некоторое ограничение, то подразумевается, что все тесты в этой задаче будут этим ограничениям удовлетворять. Вашу программу-решение никто не будет пытаться запускать на тестах, которые не удовлетворяют этим ограничениям. В примере выше никто не будет вам вводить числа больше миллиарда, и т.п.

Почему? На то есть несколько причин.

Проверить все невозможно

Во-первых, вы не можете проверить абсолютно все. Вы думаете, что код выше достаточен для проверки? Вы уверены? А если вам введут вещественные числа? А если два числа будут на разных строках? А если вам введут три числа или, наоборот, одно? А если вам введут буквы вместо цифр?

Это точно такие же нарушения формата входных данных, как и ввод чисел больше миллиарда. Но приведенный выше фрагмент кода их не заметит. Конечно, возможно, что программа как-то отреагирует на это — например, выдаст какую-нибудь ошибку (исключение) или т.п. А возможно (зависит в первую очередь от языка программирования), никакой ошибки и не будет, программа просто считает эти числа как попало, и выдаст какой-то ответ, вовсе не обязательно правильный (хотя что такое правильный ответ в такой ситуации — вообще не понятно, см. про это еще ниже).

Вы думаете, что вы сможете написать код, который все эти проблемы учитывает? Это уже далеко не так просто. Но более того, некорректные входные данные — это далеко не единственное проявление «дурака», которое тут возможно. Если уж писать «защиту от дурака», то можно писать ее по максимуму, защищаясь от всех возможных проблем с окружающей средой, а не только от некорректных входных данных. Вдруг такой «дурак» захочет вашу программу, написанную под Python 3, запустить под Python 2? Надо от этого писать защиту? Если уж он «дурак» и может ввести некорректные числа, то почему он не может перепутать версию языка? А если вашу программу на C++ скомпилируют под линукс, после чего попробуют запустить под Windows? Или попробуют скомпилировать под один процессор, а запустят на другом, на котором она не заработает (если сильно постараться, то это можно сделать)? А если процессор окажется бракованным и неправильно выполняет сложение (кстати, это тоже бывает)? А если вашу программу вообще захотят запустить на утюге?..

В общем, вы не можете написать 100% защиту от дурака. Абсолютно любую программу можно сломать (в смысле, добиться незадуманного поведения), если специально подготовить внешние условия (входные данные, среду работу и т.д.) Поэтому надо где-то остановиться и решить: вот эти ситуации мы пытаемся обрабатывать, а эти нет. Вот фраза «Оба числа натуральные и не превосходят 1 000 000 000» и проводит эту границу: ваша программа должна корректно обрабатывать натуральные числа до миллиарда, а другие случаи программа не обязана как-то поддерживать, она может делать что угодно вообще.

Условие должно быть строгим

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

Что же вы тогда хотите делать, если введенные числа больше миллиарда? Код выше выводит на экран строку «Неправильные числа», но с чего вы взяли, что именно это — правильный ответ на такой тест? Ваша программа будет проверяться автоматически, и тестирующая система не знает русского языка, поэтому если вы выведете такую строку, то почти наверняка проверяющая программа сочтет, что ваш ответ неправильный. Поэтому у вас все равно нет хорошего варианта обработки чисел больше миллиарда. Даже если вы захотите что-то в таком случае сделать, поставить «защиту от дурака», вы все равно не знаете, какую именно «защиту» от вас ожидает тестирующая программа.

С другой стороны, если бы авторы задачи хотели бы, чтобы вы поставили такую «защиту», они бы явно это написали в условии, например, как-то так: «Вводятся два натуральных числа. Если оба введенных числа не превосходят миллиарда, выведите ответ на задачу, иначе выведете -1». Здесь явно указано, что на не-натуральность числа проверять не надо, а вот на превышение миллиарда — надо. Очень похожая ситуация имеет место в задачах, где надо найти какое-то решение, причем это решение существует не всегда. Тогда если в условии написано «если решений не существует, выведите NO SOLUTION» — это одно дело, а если в условии написано «гарантируется, что решение будет всегда существовать» — это совсем другое дело. (Фраза «гарантируется, что» — это по сути те же ограничения, просто заданные не так явно.)

(На самом деле, даже если бы решения проверялись вручную, не автоматически, все равно условия должны были бы быть строгими. Даже если решения проверяет человек, не программа, почему вы уверены, что его устроит фраза «Неправильные числа»? Вдруг он хотел бы видеть фразу типа «Числа больше 1000000000 не поддерживаются»? По условию задачи вы не можете угадать, чего захочет проверяющий. Поэтому даже если проверка идет вручную, условие все равно должно быть строгим, в нем должно быть четко указано, что когда делать.)

«Защита от дурака» — не олимпиадное дело

Третья причина состоит в том, что задачи на олимпиаде должны быть интересными и нетривиальными. «Защита от дурака» в большинстве разумных случаев делается довольно тупо и, после определенного опыта, не требует особого размышления. Можно один раз написать достаточно мощную такую «защиту» и переиспользовать во всех дальнейших решениях. (На самом деле такая «защита», в плане входных данных, уже давно написана, называется testlib, и используется в самих проверяющих программах — когда надо быть готовым к тому, что решение участника выведет какую-нибудь ерунду.) Но зачем тогда это требовать на олимпиаде? Олимпиада все-таки проверяет, кто из участников лучше думает, лучше умеет программировать, а не кто просто один раз написал и умеет воспроизвести или заиспользовать конкретный код.

Аналогично, задачи на алгопроге нужны на отработку определенных алгоритмов, на изучение тех или иных приемов программирования — зачем же тогда там требовать «защиту от дурака», если она не имеет никакого отношения к основной теме задачи?

С другой стороны, если какая-то проверка, какая-то «защита от дурака» действительно нетривиальна и интересна, то никто не запрещает потребовать такую проверку в задаче, или даже сделать отдельную задачу «проверить входные данные на корректность». Но тогда это всё должно быть четко описано в условии — вот, например, задача «IP-адрес». Здесь четко описано, какая проверка должна быть сделана, и, конечно же, описано, до какого предела надо делать проверку, а что можно и не проверять — например, в этой задаче гарантируется, что во входных данных есть только цифры и точки, причем точек ровно три, а цифр не более 12.

Расширение области деятельности программы

Еще одна причина, почему не стоит писать «защиту от дурака», состоит в том, что никогда не хуже сделать программу, которая корректно работает в максимально широком спектре случаев. Вот в примере выше у вас числа не больше миллиарда. Как вы думаете, если вы не напишете в программе никакой «защиты от дурака», и введете число 1000000001, что выдаст ваша программа? Думаю, что абсолютно правильный ответ. Конечно, если вы введете очень большое число, то, скорее всего, ваша программа не заработает, но, скорее всего, числа, несильно превышающие ограничения, ваша программа переварит. Аналогично, хотя и сказано, что числа натуральные, но вполне возможно, что число ноль в качестве входных данных ваша программа тоже обработает (все это зависит от конкретной задачи и конкретной программы, конечно).

Такое расширение области деятельности программы обычно полезно, ну или по крайней мере не вредно. Во-первых, вы можете аккуратно потестировать программу на этих тестах. Тестировано на слишком больших числах обычно не имеет особого смысла, а вот на нуле нередко бывает полезно. Я всегда советую при тестировании начинать с самых маленьких тестов — и тест «ноль» вам в определенных ситуациях может быть очень полезен.

Наконец, бывают и ошибки в тестах к задаче. Если вдруг в тестах случайно встретится число чуть больше миллиарда, то скорее всего проверяющая программа будет ожидать честный ответ, а не какую-то строку. Конечно, ошибок в тестах в идеале быть не должно, и вообще они очень редки, но всякое бывает. Не написав «защиту от дурака», вы имеете неплохой шанс пройти некорректные тесты, если они вдруг будут; с «защитой» же вы их почти наверняка не пройдете. Так зачем писать лишний код, если он не улучшает, а возможно только ухудшает вашу программу?

Вообще, «защита от дурака» — это лишний код. В нем всегда можно ошибиться. Так зачем его писать?

Реальная жизнь

Кто-то может сказать, что все это чушь и олимпиадные заморочки, и что в реальной жизни (c) программисты должны писать всю возможную защиту. Но нет, это не так. В любой ситуации в любой программе программисты должны понимать, могут ли тут быть ошибочные данные и какие, и писать только те проверки, которые нужны. Когда программист пишет код, он всегда явно или неявно понимает, какие «защиты» он должен написать.

Если вы пишете, например, сайт, то вы, конечно, должны тщательно проверять все данные, полученные от пользователя, потому что среди пользователей могут быть хакеры, которые пытаются взломать сайт. Но если тот же сайт читает из локальной базы данных информацию, которую сам же сайт туда когда-то писал, то проверок можно делать меньше (зависит от того, что за данные, конечно) — предполагается, что база данных недоступна извне и хакер не может там испортить данные, поэтому там будет то, что сайт записал туда раньше. (Конечно, тут много оговорок, но в любом случае доверия данным из базы намного больше, чем данным от пользователя.)

Если же вы пишете, например, программу физического моделирования какой-нибудь системы, которую будут запускать только опытные пользователи, понимающие, что они делают, то вы можете делать намного меньше проверок. Во-первых, если пользователь сам ввел какие-то нереалистичные данные, то он сам и виноват, можно выдать абсурдный результат; во-вторых, если ваша программа будет работать с некорректными данными, то в принципе ничего сверх-страшного не случится (в отличие от сайта, где некорректные данные легко могут привести к взлому сайта или аккаунтов других пользователей, утечке личной информации и т.д.) Конечно, если пользователи вашей программы физического моделирования скажут вам «мы часто делаем такую-то ошибку, это приводит к пустой трате нескольких суток машинного времени, добавьте такую-то проверку на старте программы» — вы ее добавите. Но вот вам и строгая формулировка.

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

…Я недавно наткнулся на обсуждение разработчиками браузера Chrome одного бага в этом браузере. Всё обсуждение свелось к тому, что баг происходит только в случае какой-либо аппаратной ошибки (например, полетевшего жесткого диска). И разработчики решили, что эту проблему они фиксить не будут, т.к. Chrome не рассчитан на работу в таких ситуациях.

В общем, даже в реальной жизни вы почти никогда не ставите полную «защиту от дурака».


Мой курс по алгоритмическому программированию (и подготовке к олимпиадам) для школьников, студентов и всех желающих — algoprog.ru