Олимпиады по программированию

olympiads.ru

Московская олимпиада
Новости
Ссылки на странички разных лет
2006/07 учебный год
2005/06 учебный год
2004/05 учебный год
2003/04 учебный год
2002/03 учебный год
Московская городская олимпиада по программированию 2002/03
Доска объявлений олимпиады
Материалы олимпиады
Призеры олимпиады
Полная таблица результатов
Заочный тур
Информация о заочном туре
Задачи заочного тура
Об использовании тестирующей системы
Результаты заочного тура
Несколько советов
Задать вопрос оргкомитету

Несколько советов

Давайте для начала рассмотрим один простой пример. Решим следующую задачу. Во входном файле a.in записаны два натуральных числа, каждое из которых не превышает 32000. Числа во входном файле разделяются пробелами и (или) символами перевода строки. В выходной файл a.out вывести сумму этих двух чисел.

Кажется, что это даже не задача, и любой знакомый с программированием школьник с легкостью может написать ее решение:

var a,b,c:integer;
    f,g:text
begin

  assign(f,'a.in');  {Связываем переменную f с файлом a.in}
  reset(f);          {Открываем файл, связанный 
                      с переменной f для чтения}
  read(f,a,b);       {Считываем данные из файла, связанного с f}
  close(f);          {Закрываем файл}

  c:=a+b;            {Решаем задачу :-) }

  assign(g,'a.out'); {Связываем переменную g с файлом a.out}
  rewrite(g);        {Открываем файл, связанный 
                      с переменной g для записи}
  writeln(g,c);      {Записываем данные в файл} 
  close(g);          {Закрываем файл}
end.

Кажется, что все правильно. На всякий случай запустим нашу программу, чтобы еще раз убедиться, что она работает правильно. Посылаем ее на проверку, и получаем неожиданный результат - несколько тестов прошло, но на некоторых тестах происходит ошибка во время исполнения (или неверный ответ - это зависит от ключей компилятора). Давайте еще раз внимательно прочитаем условие, и особо остановимся на ограничениях. Числа натуральные, не превышающие 32000. У нас для хранения чисел заведены переменные типа integer, диапазон значений переменных этого типа - от -32768 до 32767, так что кажется, что тут все правильно. Однако условию удовлетворяет тест, в котором оба числа равны 32000. Конечно, они входят в тип integer, чего нельзя сказать об их сумме! Меняя в нашей программе тип integer на тип longint получаем уже действительно полное решение задачи (замечание: оказывается, если сделать тип переменной c - longint, а a и b оставить типа integer, то программа работать все равно не будет - подумайте почему).

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

Ограничения важны еще с одной точки зрения. Задумайтесь - а сколько действий выполнит ваша программа в самом худшем случае. Успеют ли все эти действия выполниться за время, отведенное на работу программы на одном тесте? Если ответ заведомо отрицательный - попытайтесь как-то улучшить свой алгоритм, или даже придумать новый.

Обязательно перед сдачей решения проверьте его самостоятельно, введя тесты, приведенные в условиях задач, и придумав свои. Хорошо бы потестировать задачу не только на маленьких тестах, но и на максимальных, удовлетворяющих ограничениям. Это позволит найти ошибки, приводящие к переполнению типов, выходу индекса за границы массива. Эти же тесты дают возможность проверить, укладывается ли ваше решение в ограничения по времени, указанные в условии задачи.

Если вы осуществили все такие проверки, а задача все равно не проходит какие-то тесты, подумайте, быть может, вы не учли какой-то из частных случаев задачи.

Если вы послали решение, которое у вас работает, а оно не прошло ни одного теста, проверьте, правильно ли в вашем решении называются входной и выходной файлы, соблюдены ли форматы входных и выходных данных, заканчивает ли ваша программа свою работу (например, не ждет ли она нажатия клавиши "Enter")? Обратите внимание, имена входного и выходного файла должны писаться маленькими буквами (под Windows это не имеет значения, однако ваши решения проверяются под Linux, а там это существенно).

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

Удачи!