09.04.2013

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


Уважаемые участники олимпиады!

 

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

Вот небольшой список наиболее часто встречающихся ошибок:

 

  • Переполнение типа

Не стоит забывать про ограничения на диапазон переменных. Превысив максимальное значение типа, вы получаете вместо желаемого числа его остаток по модулю размер диапазона, теряя нужное значение.

Границы основных типов:
32-битный: -231..231-1 (231 2*109) - integer, longint (Delphi), int (C++, Java), НО integer во Free Pascal - 16-битный, то есть имеет диапазон -215..215-1 (215 = 32768), в качестве 32-битного типа используйте longint, или integer, но с директивой {$mode delphi} (ставится в начало программы).
64-битный: -263..263-1 (263 9*1018) - int64 (Delphi, FPC), long long (C++), long (Java).


  • Выход за границы массива

Случайно указав меньшие границы массива, вы рискуете получить Runtime Error (RE) за обращение в недопустимую область памяти, и даже если вам повезет, и ничего важного вы не сломаете, поведение того, что вы принимаете за ячейки массива за его границей, абсолютно непредсказуемо и с большой вероятностью даст вам невалидные данные, и, как следствие, WA или еще чего похуже. Не стоит так же забывать, что в языках с 0-нумерацией массивов (C++, Java) массив из n элементов содержит элементы с 0-го по (n - 1)-й, но не содержит n-й.

Отдельно речь о строках: тип string в Delphi, C++, Java - динамический, то есть строка при увеличении сама выделяет себе память без всяких ограничений (кроме внешних, вроде Memory Limit'а на тестируещей системе или размера оперативной памяти на вашем компьютере), НО длина string во Free Pascal ограничена 255 символами, снять это ограничение можно все той же директивой {$mode delphi}.


  • Крайние случаи

Тестируя программу, проверяйте крайние случаи, то есть минимальные и максимальные (по возможности, поскольку сгенерировать хороший максимальный тест иногда бывает сложнее, чем решить задачу) значения входных данных. Просто случайные тесты могут не выявить некоторых специфических ошибок. Например, вводится число n >= 1, у вас происходит деление на (n - 1); тесты с n = 2, 3, 4 работают, а n = 1 вы проверить забыли и получили законный RE из-за деления на ноль. Или, при входных данных 1, 2, 10, 100, 500 решение работает, а при 1000 происходит переполнение integer'а; не проверив максимальное значение, вы получите WA и возможно потратите много времени на поиск ошибки, которая в случае должного тестирования выявилась бы сама.


  • Ограничения по времени/памяти

Не забывайте про ограничения, указанные в условии. Обычно пары несложных арифметических действий достаточно, чтобы оценить время работы программы: если 107-108 операций в секунду можно сделать без проблем, то 109 разве что в случае очень простых операций, а 1010 и больше - совсем никак. Более того, произведя такие вычисления перед написанием программы, вы можете не только не получить штраф за решение с TL, но и сэкономить кучу времени, которое в противном случае вы бы потратили на реализацию заведомо медленного решения. И наоборот, можно потерять много времени, опрометчиво отбросив не очень быстрое, но верное решение, и начав реализовывать более эффективный, но и более сложный алгоритм. То же самое относится и к памяти: простая арифметика может сохранить вам много времени.

 

  • Ввод-вывод

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

 

  • Решения на Java

Когда вы отправляете на тестирующую систему решение на Java, главный класс должен называться Main (относится только к нашей тестирующей системе).


  • Условие

Самое главное в олимпиадном программировании - правильно прочитать условие. От неправильно/неточно понятого условия страдают программисты самого разного уровня, но за время и попытки, потраченные на реализацию решения "не той" задачи обидно всем одинаково. Перед тем как придумывать и реализовывать решение, убедитесь, что прочитаны все условия, а также формат входных и выходных данных. Также убедитесь, что никакая часть текста не вызывает у вас чувства непонимания/двусмысленности/противоречия с другими частями. Никогда не пренебрегайте возможностью задавать жюри вопросы по задачам: вещи, понятные с точки зрения авторов задач могут быть совсем не очевидны участникам.

 

Напоминаем, любые вопросы, связанные с олимпиадой, можно задавать по адресу permolymp@yandex.ru.

Адрес: 614039, г. Пермь, ул. Комсомольский проспект, 45
Телефон: +7 (342) 212-80-71
E-Mail: school9-perm@ya.ru
Вопрос администратору сайта