|
Олимпиады прошлых лет
|
||||||||||||||||||||||||||||||||||||
|
I Всероссийская заочная олимпиада школьников по информатике, 2006/07 учебный год
Несколько советов участникам олимпиад
Прежде всего хотим отметить, что для участия в олимпиаде вы должны уметь работать с текстовыми файлами (считывать и записывать информацию): это не сложно - скорее всего, вы с легкостью разберетесь, как это делается, посмотрев приведенный ниже пример. Однако лучше всего попробовать работать с файлами до того, как вы придете на олимпиаду. Если вы участвуете в олимпиаде впервые, советуем вам также заранее посмотреть примеры предлагаемых на олимпиадах задач, например, в архивах олимпиад, представленных на нашем сайте.
На олимпиадах, если иное не указано в условии задачи, все входные данные считаются корректными, то есть файлы, которые подаются на вход вашей программе при проверке строго соответствуют описанным в условии форматам, а все значения - указанным ограничениям. Вы не должны в своей программе проверять корректность входных данных. С другой стороны, выходные данные (результат работы вашей программы) вы должны выводить в формате, описанном в условии задачи, не добавляя никаких посторонних комментариев. Все решения проверяются автоматически, и если выходной файл содержит постороннюю информацию или если его формат не соответствует описанному в условии, он будет признан неправильным.
Ваша программа не должна ничего выводить на экран (если это особо не оговорено в условии задачи), а также ждать какого-либа ввода пользователя. Распространенной ошибкой является ситуация, когда после окончания работы программа ждет нажатия какой-либо клавиши. При автоматической проверке никто эту клавишу нажимать не будет, и программа будет считаться превысившей предел времени (то есть зависшей или неэффективной).
Что делать, если ваше решение проходит не все тесты
Давайте для начала рассмотрим один простой пример. Решим следующую задачу. Во входном файле 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, а там это существенно).
Ваша программа всегда должна завершаться с кодом возврата 0. То есть функция main в C/C++ должна иметь тип результата int и всегда завершаться командой return 0, если вы используете в паскале процедуру выхода halt, то вы всегда должны делать halt(0) - другие значения недопустимы и диагностируются как Run-time error.
Если вы не знаете, как решать задачу
Если вы не знаете, как решать задачу при указанных ограничениях или в общем случае, но ваша программа работает в каких-то частных случаях, обязательно пошлите ее на проверку - быть может несколько тестов она все-таки пройдет, а любой положительный результат - это лучше, чем ничего.