Правила проведения олимпиады Приведем и прокомментируем наиболее важные правила проведения Всероссийской олимпиады по информатике. Многие из этих правил справедливы также и для большинства региональных олимпиад
| Вид материала | Лекция |
- Правила проведения олимпиады, 138.29kb.
- Методические рекомендации по разработке заданий для школьного этапаВсероссийской олимпиады, 450.39kb.
- Методические рекомендации по разработке заданий для школьного и муниципального этапов, 455.04kb.
- Методические рекомендации по разработке заданий для школьного и муниципального этапов, 454.96kb.
- Методические рекомендации по разработке заданий для школьного и муниципального этапов, 197.9kb.
- Примерная программа проведения Олимпиады порядок заполнения и учета бланков дипломов, 495kb.
- Методические рекомендации подготовки и проведения школьного этапа всероссийской олимпиады, 323.11kb.
- Методические рекомендации по разработке требований к проведению школьного и муниципального, 455.01kb.
- Рекомендации для проведения Муниципального этапа Всероссийской олимпиады школьников, 538.45kb.
- Регламент проведения II (муниципального) этапа Всероссийской олимпиады школьников, 398.38kb.
Лекция 2.
Правила проведения олимпиады
Приведем и прокомментируем наиболее важные правила проведения Всероссийской олимпиады по информатике. Многие из этих правил справедливы также и для большинства региональных олимпиад.
- Олимпиада проводится в два тура. Продолжительность каждого тура 5 часов. На каждом из туров для решения задач участнику предоставляется персональный компьютер типа IBM PC со следующим программным обеспечением: Turbo Pascal 7.0, Borland C++ 3.1.
{комментарии}
Из первого пункта правил становится ясно, что, во-первых, оба тура олимпиады, так называемые, практические. Во-вторых, для решения задач предлагается использовать лишь один из двух языков программирования. Такое положение полностью соответствует международной практике, хотя на российских олимпиадах соблюдается не всегда строго. Basic исключен из числа официальных языков программирования олимпиады, так как желание программировать только на нем высказывают очень небольшое число участников олимпиад высокого уровня, при профессиональной разработке программ он практически не используется (в данном случае Visual Basic мы не рассматриваем), кроме того, решение задач с использованием этого языка иногда затруднено по сравнению с Pascal и C. На наш взгляд, заранее объявляя об ограничениях на использование программного обеспечения, жюри и оргкомитет олимпиады способствуют практике изучения тех языков программирования в российских школах, которые позволят ребятам добиваться не только успехов в различных соревнованиях, но и некоторым из них стать высокими профессионалами в области информатики и программирования. Мы считаем, что именно язык программирования Pascal, как никакой другой, позволяет за короткий срок отлаживать довольно сложные программы, что особенно важно в условиях практического тура любой олимпиады, но и не менее значимо при изучении информатики в школе. Использование языка C (C++) на олимпиаде стоит приветствовать лишь тогда, когда участник владеет им почти в совершенстве, практически не допуская ошибок при записи решения задачи на C, часть из которых невозможно обнаружить на этапе компиляции программы. Кроме того, при программировании на C могут возникнуть сложности с настройкой компилятора, а в режиме олимпиады даже минута, потраченная не на собственно решение задач, может сказаться на результатах участника. Хотя, справедливости ради стоит сказать, что на международной олимпиаде процент участников, использующих язык программирования C (C++) достаточно высок, причем многие из них выступают более чем успешно, что опять же свидетельствует о высокой квалификации таких школьников, а размер кода программ на C (не следует путать с размером исполняемого файла) часто меньше кода на языке Pascal. В заключение заметим, что предоставляемое на олимиадах программное обеспечение (операционная система, тип и версия компиляторов, среда программирования) со временем естественно может изменяться, как это и произошло на последней международной олимпиаде по информатике в Финляндии (см. №37/2001).
{\комментарии}
- На каждом из туров участникам будет предложено решить несколько задач. Вопросы по условиям задач можно задавать только в течение первого часа тура. Вопросы следует задавать только в письменном виде и формулировать их так, чтобы на них можно было ответить “да” или “нет”.
{комментарии}
Такая практика сложилась исторически и применяется на международных олимпиадах. Строгое соблюдение данного пункта правил иногда вызывает у ряда участников некоторые сложности. Так, школьникам зачастую тяжело именно в начале тура пытаться понять нюансы в формулировках сразу всех задач. Кроме того, часто вопросы по условию возникают лишь тогда, когда участник приступил к решению той или иной задачи. Поэтому немаловажным является умение с первого раза внимательно прочитать условие любой задачи, выделяя не ясные для себя места в тексте. Умение грамотно сформулировать вопрос, допускающий один из двух вариантов ответа, также зачастую у школьников отсутствует. Заметим, что при ответе на большинство задаваемых вопросов члены жюри используют фразу “без комментариев”. Это означает, что либо ответ на вопрос все же содержится в формулировке задачи и его следует искать самостоятельно, либо вопрос фактически касается уже способов ее решения и жюри не комментирует различные соображения участников по этому поводу.
{\комментарии}
- Во время тура не допускается использование личных дискет, калькуляторов, электронных записных книжек, пейджеров, мобильных телефонов, а также учебной литературы и личных записей, сделанных до начала тура1.
{сноска}
1Последнее ограничение применялось на Всероссийской олимпиаде по информатике 2001 года.
{\сноска}
{комментарии}
Подобные ограничения ставят всех участников олимпиады во время тура в равные условия и способствуют выявлению действительно наиболее талантливых ребят. Хотя на ряде соревнований использование специальной литературы допускается, что соответствует практике профессиональной работы ученого, инженера или программиста.
{\комментарии}
- Не забывайте периодически сохранять свои решения. В случае возникновения сбоев в работе компьютера и программного обеспечения необходимо срочно обратиться к дежурному преподавателю, который должен письменно зафиксировать сбой и сообщить о нем в жюри. По решению жюри вам может быть добавлено время, потраченное на восстановление работоспособности компьютера.
{комментарии}
Комментарии тут, как говорится, излишни. Справедливости ради следует заметить, что подобные ситуации на олимпиадах высокого уровня крайне редки и возникают, в основном, в результате ошибочных действий самих участников или же вызваны ошибками в их же программах, например, связанными с некорректным обращением к оперативной памяти.
{\комментарии}
- В решениях категорически запрещается:
- использовать расширенную память;
- использовать ассемблерные вставки;
- создавать файлы и каталоги во время работы программы;
- читать данные откуда-либо, кроме как из входного файла и записывать их куда-либо, кроме выходного файла;
- читать и записывать вектора прерываний;
- производить любые другие действия, нарушающие работу проверяющей системы во время тестирования.
{комментарии}
Собственно говоря, последнее из приведенных ограничений во многом объясняет и наличие всех остальных. Кроме того, в случае правильного решения задач, увеличивать скорость работы соответствующих программ путем использования ассемблера нет необходимости, то же самое касается и создания вспомогательных файлов.
{\комментарии}
- Для решения разных задач могут использоваться разные языки программирования. По каждой задаче на проверку должны быть сданы два файла — исходный текст решения и соответствующий ему исполняемый файл (файл с расширением exe). Если программа написана на языке C или C++, то она должна быть скомпилирована в модели памяти large. Ваша программа не должна использовать созданные вами внешние модули. После окончания тура и сдачи работы вносить какие-либо изменения в текст решения не допускается. Файлы с решениями могут быть скопированы на личную дискету участника дежурным преподавателем после окончания тура.
{комментарии}
Из данного правила следует, что проверка решения задачи производится в основном путем тестирования созданного участником во время тура исполняемого файла. Однако жюри оставляет за собой право перекомпилировать решения участников, в исключительных случаях это делается по просьбе школьников с разрешения жюри во время тестирования. Текст же решения с целью оценки используемых в нем алгоритмов жюри не анализируется, проверка осуществляется путем запуска программы на различных тестах. Так было далеко не всегда, однако в последнее десятилетие это стало нормой проведения всех практических туров олимпиад по информатике и программированию различного уровня2. Достаточно строгим является правило, согласно которому текст программы после окончания тура исправлениям не подлежит, даже если ошибки в программе незначительны (иногда требуется исправить всего один символ) или задача практически решена, но нарушен формат выходных данных. В противном случае довольно сложно определить, какие же именно исправления можно считать допустимыми. В последние годы такое правило неуклонно соблюдается и практически не вызывает возражений со стороны как участников, так и их руководителей. Ограничение же на модель памяти при использовании языка программирования C является довольно искусственным и введено лишь потому, что данная модель памяти наиболее близка к модели памяти языка Turbo Pascal, что опять же ставит участников в равные условия при решении задач. На международных олимпиадах такое ограничение отсутствует. Копирование решения участником на собственную дискету в ряде случаев позволяет ему вместе с руководителем найти ошибки и разобраться в особенностях работы программы до окончания олимпиады. Это существенно снижает количество подаваемых в жюри апелляций.
{сноска}
2О принципах оценки программ с помощью их тестирования можно прочитать в №34/2001.
{\сноска}
{\комментарии}
- Проверка решений осуществляется после окончания тура и проводится в присутствии участника (а по желанию и руководителя). По результатам тестирования заполняется лист проверки с результатами по каждому тесту. Ваша программа на одном и том же тесте должна всегда выдавать одинаковые результаты. Если с результатами проверки участник не согласен, то он вносит свои замечания в лист проверки.
{комментарии}
Проверка решения в присутствии участника говорит об открытости работы жюри на этапе тестирования. Такой подход снимает множество вопросов относительно полученных за решение той или иной задачи баллов. Поэтому его применение можно рекомендовать для олимпиад любого уровня, начиная со школьной. На последней, а также районной олимпиаде, участники зачастую получают за решение той или иной задачи нулевые баллы просто потому, что их решение просто не удалось запустить или файл с решением оказался не найденным. А ошибки в названиях файлов с решениями, входными и выходными данными, например на школьной олимпиаде, не должны оказаться для ребят фатальными. Но определить, что причины неработоспособности программы именно в этом, зачастую можно только лишь с помощью ее автора. Требование же стабильности работы программы имеет следующий смысл. Различные результаты работы программы на одном и том же тесте в большинстве случаев объясняются либо ошибками в ее работе (например, если значения каких-либо переменных в программе явным образом не проинициализированы, то работа исполняемого файла зависит от того, чем было заполнено содержимое используемой программой при запуске оперативной памяти), либо использованием датчика случайных (а на самом деле псевдослучайных) чисел. Причем правилами олимпиады использование случайных чисел как таковых не возбраняется. Просто программа должна применять датчик так, чтобы на одних и тех же входных данных, генерировалась последовательность из одних и тех же случайных чисел. Например, в языке Turbo Pascal этого легко добиться, если не использовать в программе процедуру randomize. Кроме того, генератор псевдослучайных чисел можно запрограммировать и самостоятельно. При нарушении указанного правила жюри оставляет за собой право запустить программу несколько раз и засчитать худший из показанных ею результатов.
{\комментарии}
- Ваши решения будут проверяться на компьютерах с одинаковой тактовой частотой, возможно не совпадающей с тактовой частотой компьютеров, предоставленных в ваше распоряжение на соревнованиях. При тестировании вам будет доступно не менее 350 килобайт динамической памяти. Для сравнения быстродействия тестирующего компьютера с вашим вам будет во время тура предоставлена специальная программа, которая на тестирующем компьютере работает ровно 5 секунд.
{комментарии}
Конечно, такое правило является вынужденным и объясняется лишь тем, что оргкомитету очень трудно предоставить участникам олимпиады порядка 150 одинаковых компьютеров. Хотя на международной олимпиаде такая задача решается. При отладке решения следует учитывать, что эталонная по времени работы программа позволяет лишь приблизительное оценить ожидаемое время работы программы участника на тестирующем компьютере. Но обычно время тестирования любой задачи как минимум в два раза превышает действительно необходимое время для работы программы с оптимальным решением этой задачи на любом из тестов. Напомним, что максимально допустимое время работы программы на одном тесте входит в текст условия задачи.
{\комментарии}
Порядок решения олимпиадных задач
Попробуем теперь сформулировать уже неформальные правила поведения на практически любой личной олимпиаде по информатике, которые могут помочь школьникам, особенно участвующим в ней впервые, показать максимально возможный результат. Большинство из предлагаемых советов не зависят от языка программирования, на котором школьник решает олимпиадные задачи, однако фрагменты программ будут приведены на языке Turbo Pascal, как наиболее распространенном среди участников российских олимпиад. Очевидно, что приведенные ниже “правила” несут под собой лишь рекомендательный характер, особенно это касается порядка в котором они перечислены, и могут быть переработаны как самим учеником, так и его руководителем.
- В самом начале тура полезно набить приведенную ниже универсальную заготовку для решения олимпиадной задачи (она представляет из себя работающую программу!!!), особое внимание следует обратить на директивы компилятора, приведенные в образце. С помощью команды
{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T+,V+,X+,Y+}
{$M 65520,0,655360}
var
i,j,k:longint;
procedure readdata;
begin
assign(input,'');
reset(input);
end;
procedure outdata;
begin
assign(output,'');
rewrite(output);
close(output)
end;
procedure initial;
begin
fillchar(i,?,0);{см. лекцию 3}
end;
procedure run;
begin
end;
begin
readdata;
initial;
run;
outdata
end.
Далее можно скопировать эту заготовку столько раз, сколько задач предложено на туре и сразу назвать каждый файл так, как это требуется по условиям олимпиады. В результате вам не придется при переходе от решения одной задачи к другой начинать работу с нуля (а попытка править текст с решением одной задачи для ускорения набора текста другой ведет только к порождению ошибок, на исправление которых будет потрачено гораздо больше времени). В разделе OPTIONS\enviroment\preferences среды программирования Turbo Pascal полезно установить параметр Auto save [X]Editor Files (автосохраниние редактируемых файлов). Это гарантирует автоматическое сохранение текста программы при каждом ее запуске. Таким образом, если, например, программа зависнет и среду программирования придется запускать заново, то результат последнего редактирования будет сохранен (к сожалению, во время тура школьники зачастую забывают самостоятельно время от времени запоминать сделанные ими изменения в тексте программ.
- Затем следует очень внимательно прочитать условия всех задач и постараться правильно (!!!) понять в чем заключается каждая задача. Если что-то непонятно, в том числе и в формате ввода и вывода, то лучше задать вопрос.
{комментарий}
Несмотря на очевидность данного правила, научить школьников его выполнять очень непросто. Иногда здесь просто нужна тренировка внимания и умения формально подходить к тексту условия задачи, то есть понимать условие буквально, а не так, как покажется при его поверхностном чтении. Если же с точки зрения формальной логики в условие все же можно трактовать неоднозначно, то тогда и следует задавать вопросы.
{\комментарий}
- Если вы приступили к решению конкретной задачи и основная структура данных для нее вам ясна, то можно описать основные глобальные переменные и набить процедуру readdata ввода данных, чтобы она считывала все параметры задачи так, как это указано в условии. Если не оговорено иное, то делать формальную проверку считанных данных, то есть проверять соответствие введенных значений переменных условию задачи не нужно (!!!). Объясняется это тем, что по правилам проведения большинства олимпиад последних лет считается, что все входные данные при тестировании будут корректны. Кроме того, заметим, что при считывании из файла чисел обычно следует использовать только процедуру read (а не readln), для случаев же считывания симовлов и строк (тип string) это не так. Если количество числе во входном файле неизвестно, то нужно использовать функцию seekeof вместо eof для проверки условия окончания считывания чисел. Для файлов, содержащих произвольный текст, это опять же уже не так.
{комментарий}
Проверка на корректность, несомненно необходимая в профессиональном программировании действительно в последнее время на олимпиадах практически не производится. Хотя на олимпиадах прошлых лет такая практика и существовала. Объясняется это тем, что количество предлагаемых на одном туре задач и их сложность со временем возрасли и во время олимпиады важнее определить не степень профессиональной пригодности участника как программиста, а его способность решать те или иные задачи. А отмена проверки входных данных позволяет участникам больше времени потратить на обдумывание алгоритмов решения задач и их реализацию. Что же касается приведеннных в данном пункте “технических” советов по организации ввода данных, то ниже будут даны различные рекомендации по технике и приемам программирования при решении олимпиадных задач, поэтому сейчас подробно обсуждать мы их не будем.
{\комментарий}
- В процедуре initial следует обнулить или присвоить соответствующие начальные значения всем (!!!) глобальным переменным, за исключением тех, которые будут использоваться в качестве параметров циклов. Затем запрограммировать вывод результата в процедуре outdata так, как это требуется в условии задачи. Это поможет дальнейшей отладке программы и в дальнейшем не потребуется “простой” вывод переделывать в “правильный”. Таким образом, к этому моменту у вас уже должна быть “работающая” программа. Она, по крайней мере, должна компилироваться, считывать данные и выводить результат, пусть и нулевой, но в нужном формате.
{комментарий}
Отсутствие привычки инициализировать все объявленные переменные можно отнести к небрежностям при программировании, в результате часть программ школьников, как уже упоминалось выше, не работают при тестировании именно по этой причине. Использование же отладочных форм выдачи результата во время олимпиады также вряд ли разумно. Так, если задача уже отлажена, на переделку формата вывода может просто не хватить времени. Или подобная работа, выполненная в последний момент, окажется сделанной с ошибками, то есть либо формат выходных данных будет не соблюден строго, либо дополнительно будет выводиться часть отладочной информации, а по правилам олимпиады даже в этом случае задача не будет зачтена. Еще одна типичная ошибка из данного класса — задание временных имен для входных и выходных файлов, и как результат, не работающая, с точки зрения автоматической системы проверки, программа.
{\комментарий}
- При выполнении пунктов 3, 4 данной памятки или после следует подумать над подходами к решению задачи, для чего ответить себе на ряд вопросов и проделать ряд действий.
1) Проверить данные на фактическую корректность, то есть всегда ли задача имеет решение для введенного набора данных, например, связан ли граф, нет ли деления на 0 и т.п., если только в условии не сказано, что все данные и в этом смысле корректны.
2) Определить, относится ли данная задача к знакомому вам классу или решение придется искать “с нуля”.
3) Попытаться найти на бумаге (!!!) точное решение, возможно только для малых размерностей. Такой подход зачастую позволяет обнаружить закономерности, которые затем можно попытаться распространить и на общий случай. Отобразить на бумаге принципиально различные случаи, в том числе и вырожденные. Это поможет при составлении тестов для самопроверки написанной программы.
4) Попробуйте сформулировать условие существования решения, пусть только необходимое или только достаточное.
5) Продумать и выпишите (!!!) достаточную систему тестов.
- Запрограммируйте решение задачи в виде вызовов процедур и функций, которые пока следует описать в виде “заглушек” (мнимого или пустого действия или имитации настоящего действия, которое должна выполнять ваша программа). Таким образом вы сможете отладить логику вашей программы, которая опять же должна оставаться “работающей”.
- Затем следует по одной набивать и отлаживать уже описанные процедуры и функции, добиваясь, чтобы свое действие каждая из них выполняла правильно в любом случае. например, поиск максимумов, сортировка массивов, комбинаторные подпрограммы и т.п. должны работать корректно при любых входных параметров, вне зависимости от программного контекста, из которого они будут вызываться3. Особое внимание следует уделять программированию вырожденных случаев. Так, если у вас в программе встречается деление, то сразу подумайте, не может ли делитель быть нулем и рассмотрите этот случай отдельно. При программировании циклов добивайтесь, чтобы зацикливания не происходило ни при каких начальных значениях переменных, использующихся в том или ином цикле, и т. д. и т.п.
{сноска}
3Создание программы по плану, описанному в пунктах 6 и 7 данных обычно называют методом программирования “сверху вниз”.
{\сноска}
- Если вы не придумали эффективного решения задачи, то запрограммируйте его по-простому: например, с помощью полного перебора или простой эвристики (приближенного решения в ряде случаев дающего точный ответ). Если и это сложно, то упростите себе задачу, то есть отбросьте условия, которые вам мешают или добейтесь, чтобы программа проходила на самых простых, например, вырожденных тестах (большинство параметров равны 0 или 1). Аналогично следует поступить с задачами, на решение которых у вас не хватило времени.
- Прежде, чем окончательно cоздавать exe-файл, замените ряд директив компилятора на следующие: D-,I-,L-,R-,Q- и отрегулируйте размер необходимого вашей программе стека.
- Постарайтесь запустить ваш exe-файл непосредственно в операционной системе хотя бы для одного теста, чтобы убедиться в его работоспособности и еще раз перечитайте условие.
{комментарий}
Причины, по которым работающая в среде программирования программа, может оказаться не работоспособной в виде исполняемого файла уже упоминались выше и заключаются, в основном, в неинициализации значений ряда переменных. Рекомендация же прочитать условие задачи еще раз уже после решения задачи, только на первый взгляд кажется парадоксальным. Часто оказывается, что школьники решали все же немного не ту задачу, какую требовалось. Например, находили минимум вместо максимума и т.п. Иногда даже в последний момент ошибки, связанные с подобной невнимательностью удается исправить.
{\комментарий}
Лекция 3.
Техника программирования олимпиадных задач
В предыдущей лекции был приведен возможный план решения олимпиадной задачи. Рассмотрим подробнее какие технические приемы в программировании позволяют реализовать его за достаточно короткое время.
Директивы компилятора
Как уже было показано выше, при программировании на языке Turbo Pascal практически необходимо вставлять директивы для компилятора в текст программы. В противном случае, при компиляции программы из командной строки (в этом случае используются те значения для ключей компилятора, которые установлены по умолчанию) или из среды программирования, в которой через меню были установлены не те значения для ключей, при которых отлаживалась программа, работа программы может не соответствовать ожиданиям. Напомним, что разместить директивы компилятора (значения ключей компилятора и характеристики оперативной памяти, выделяемой программе при ее выполнении) в тексте программы можно с помощью команды
{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,R+,S+,T+,Q+,P-,V+,X+}
{$M 65520,0,655360}
Собственно для отладки программы наиболее значимыми являются ключи D+ и L+. Именно благодаря им в исполнимый код программы вставляется отладочная информация и из среды программирования программу можно выполнять “по шагам”, просматривая значения тех или иных переменных на различных стадиях выполнения программы.
Еще одна пара ключей — E+ и N+ необходима, если программа использует вещественные числовые типы данных, арифметические и логические операции над которыми производятся с помощью сопроцессора, а именно: comp, single, double и extended. Без упомянутых ключей программа, использующая эти типы, просто не будет компилироваться. Строго говоря, ключ E+ был необходим лишь для компьютеров, сопроцессор в которых отсутствовал и операции над вещественными числами осуществлялись с помощью так называемого эмулятора — программы, реализующей эти операции только через команды процессора. Однако все процессоры класса Pentium, а именно ими и оснащено большинство современных компьютеров, содержат встроенный сопроцессор, который будет использоваться при выполнении программы, написанной на языке Turbo Pascal, в случае установки ключа компилятора N+. Заметим, что одновременное “включение” и эмулятора и сопроцессора приводит к использованию последнего при наличии сопроцессора и эмулятора при его отсутствии. То есть такая комбинация ключей делает программу “переносимой”, не зависящей от компьютера, на котором она исполняется.
Установка ключа I+ приводит к тому, что при работе программы строго контролируется соответствие поступающих на вход программы констант типам переменных, которым значения этих констант будут присвоены. В случае несоответствия типов, например, при вводе символа вместо числа или вещественного числа вместо целого, выполнение программы будет прервано.
Совершенно незаменима при отладке программы следующая установка ключей компилятора: R+ и Q+ (последний из двух ключей появился лишь в версии Turbo Pascal 7.0). Они позволяют контролировать во время выполнения программы “выход за границу массивов” и “выход за границу допустимого диапазона значений” при операциях над целочисленными переменными. То есть при попытке обращения к несуществующему элементу массива или если во время выполнения операции (арифметической или присваивания) над целыми числами результат, в том числе и промежуточный, не является допустимым для соответствующего типа, то выполнение программы прерывается. При этом ключ R+ отвечает за корректную работу с массивами и присваивание только допустимых значений переменным типа byte и shortint, а Q+ — за корректное выполнение арифметических операций над целыми числами в рамках соответствующих типов1. При отсутствии такого контроля поиск ошибки может быть затруднен тем, что промежуточные вычисления чаще всего производятся в целом типе наибольшего размера (обычно 32-разрядном) и лишь при присваивании полученного значения переменной меньшего размера лишние старшие разряды оказываются отброшенными. Как следствие, отладочная информация о значении арифметического выражения и его результат могут не совпадать.
{сноска}
1Подробнее об организации целочисленной компьютерной арифметики и возникающих при этом ошибках можно прочитать в гл. 6 книги Е.Андреева, И.Фалина. Системы счисления и компьютерная арифметика. М: Лаборатория базовых знаний, 2000.
{\сноска}
Рассмотрим это на примере следующей простой программы:
{$Q-}
var a:integer;
begin
a:=1*2*3*4*5*6*7;
writeln(7!=,a);
a:=a*8;
writeln(8!=,a)
end.
Если после получения переменной a своего первого значения, равного 7!, мы посмотрим в отладчике значение выражения a*8, то оно будет равно 40320, а в результате второго присваивания значение a окажется равным –25216.
Наконец, при установленном ключе компилятора S+ в программу вставляется код проверки стека на выполнение. Максимальный размер стека устанавливается директивой компилятора $M, речь о параметрах которой пойдет ниже. Заметим, что прерывание работы программы с диагностикой Stack overflow (переполнение стека) чаще всего означает, что в программе есть подпрограмма, использующая рекурсивные вызовы, работа которой в следствие ошибки завершиться не может.
После того как программа отлажена, то, как уже говорилось в п.9 порядка решения олимпиадных задач (см. лекцию 2), ряд ключей компилятора следует заменить на противоположные, а именно: сдавать программу на тестирование следует с ключами D-,I-,L-,R-,Q-. Объясняется это двумя причинами. Во-первых, при отмене ряда проверок и отсутствии отладочной информации программа будет выполняться быстрее. Во-вторых, если часть ошибок при отладке не устранена, но не является для работы программы фатальной (например, обращение к несуществующему элементу массива может не влиять на правильное формирование реальных его элементов), то программа может вполне успешно пройти процедуру тестирования. Если же проверка корректного обращения с данными в исполняемом коде остается, то скорее всего на большинстве тестов выполнение программы будет прервано досрочно и результат ее работы просто не будет получен.
Рассмотрим теперь на что влияет директива компилятора $M. В обычном режиме конфигурация памяти, отводимой для работы программы, характеризуется тремя числами. Первое число определяет максимальный размер в байтах для стека, который будет использоваться программой. Максимально возможный размер стека равен 65520 байтов, размер стека по умолчанию — 16384 байта, а минимально возможный — 1024 байта. Если в программе используется рекурсия, то скорее всего ей понадобится достаточно большой стек, вплоть до максимально возможного. Но и однократный вызов процедуры или функции требует наличия стека достаточного размера, особенно если в качестве параметра-значения в процедуру или функцию передается массив (по этой причине массивы и сопоставимые с ними по объему занимаемой памяти переменные рекомендуется передавать только по ссылке, в Паскале — с использованием ключевого слова var). Уменьшать размер стека с помощью директивы компилятора имеет смысл только в случае использования динамических переменных, применять которые при решении задач школьных олимпиад по информатике требуется достаточно редко. На размер памяти, отводимой под глобальные статические переменные повлиять практически невозможно, все вместе они не могут занимать более 64 килобайт памяти (например, один массив из 10000 чисел типа real занимает 60000 байт, то есть почти всю допустимую память). Данное ограничение является не естественным для современных компьютеров, следовательно системы программирования, его содержащие, будут вытеснены, как это уже произошло на международной олимпиаде по информатике 2001 года (см. №37/2001). Оставшуюся после размещения глобальных переменных и фиксации размера стека оперативную память можно использовать лишь для создаваемых во время работы программы динамических переменных. Показанные в нашем примере значения второго и третьего параметров в директиве $M как раз и позволяют использовать всю оставшуюся в распоряжении программы память. Ее размер в обычном случае работы DOS-приложения ограничен 640 килобайтами, часть из которых используют другие программы (командный процессор, драйвер русской клавиатуры и т.д.). В условиях олимпиады участникам обычно гарантируется наличие 350-400 килобайт свободной оперативной памяти для работы программы участника (конкретное значение оговаривается заранее) и именно на этот объем и следует ориентироваться при создании динамических переменных. К сожалению, каждая из создаваемых во время работы программы динамических переменных в отдельности не может занимать более все тех же 64 килобайт памяти. Примеры создания и использования динамических переменных будут приведены ниже.
В заключение рассмотрим директивы так называемой условной компиляции, которые иногда удобно применять при отладке олимпиадных задач. В зависимости от того была или нет определена с помощью директивы $define некоторая последовательность символов часть кода программы, ограниченная директивами $ifdef и $endif, может быть как включена, так и исключена из процесса компиляции. Если же два фрагмента программы являются альтернативными, то есть включен в программу должен быть строго один из них, то в дополнение к уже перечисленным можно использовать директиву $else. Рассмотрим это на примере организации ввода данных в программу или из файла или с клавиатуры (например, по условию задачи данные должны вводиться из файла, а при отладке входные параметры удобнее вводить с клавиатуры).
var n:integer;
begin
{$define debug}
{$ifdef debug}
assign(input,'con');
{$else}
assign(input,'input.txt');
{$endif}
reset(input);
read(n)
…
end.
Так как в приведенном фрагменте программы последовательность debug определена, то ввод данных будет осуществляться с клавиатуры, если же эту команду отменить (закомментировать или слово debug в ней заменить на, например, nodebug), то ввод данных будет производиться из файла input.txt.
Ввод и вывод данных
В большинстве олимпиадных задач ввод данных и вывод результатов работы программы предлагается производить из текстового файла. У ряда участников олимпиад такое техническое требование вызывает некоторое затруднение. Покажем, как можно быстро преодолеть все сложности работы с файлами и сделать при этом как можно меньше ошибок.
Как уже видно из примера, приведенного в конце предыдущего раздела, для организации ввода данных из текстового файла наличие файловой переменной типа text в программе вовсе не обязательно. Более того, перенаправление стандартного потока ввода input и потока вывода output в файлы является и более удобным при программировании и избавляет от ряда ошибок. Как это можно сделать видно из приведенного выше примера (см. также лекцию 2). После подобного перенаправления ввод данных из файла осуществляется с помощью обычных процедур read и readln, а вывод — с помощью write и writeln без указания в качестве первого параметра имени какой-либо файловой переменной. Такой подход избавляет от типичной ошибки при работе с текстовыми файлами, которая заключается в том, что в некоторых обращениях к процедурам ввода или вывода имя файловой переменной оказывается пропущенным. Это не нарушает работу программы в целом, так как часть информации может быть записана в файл, а часть — выведена на экран. Но так как проверке подлежит лишь создаваемый программой файл, то скорее всего оценить такую программу на олимпиаде будет невозможно. Вторая типичная ошибка при работе с файлом, открытым на запись — отсутствие в конце программы команды, закрывающей файл. В таком случае, создаваемый программой выходной файл скорее всего окажется пустым. Дело в том, что реальная запись данных на жесткий диск происходит или при выполнении уже упомянутой команды close или, если количество выводимой информации велико, в момент переполнения буфера оперативной памяти, предназначенного для ускорения работы с файлами. Но и от этой ошибки работа со стандартным потоком вывода спасает. Дело в том, что файл output закрывается при окончании работы программы автоматически, вне зависимости от наличия или отсутствия команды close(output).
Рассмотрим теперь полезные приемы программирования ввода данных различных типов. Начнем с описания считывания из текстового файла или консоли (клавиатуры), которая с точки зрения программы также является текстовым файлом, числовых данных. В условии задачи ввод большого количества чисел может быть задан двумя способами. В первом способе сначала предлагается ввести количество чисел, а уж затем сами эти числа. В данном случае при программировании сложности не возникают. Во втором же случае количество чисел приходится определять в процессе их считывания. Пусть, например, для каждой строки входного файла требуется найти среднее арифметическое для чисел, расположенных в ней, количество чисел в каждой из строк и количество строк при этом неизвестно. Наиболее простым и правильным будет следующее решение такой задачи:
while not seekeof do
begin
n:=0;
s:=0;
while not seekeoln do
begin
read(a);
s:=s+a;
n:=n+1
end;
{readln;}
if n>0 then writeln(s/n:0:2) else writeln
end;
Заметим, что обычно применяемые в таких случаях функции eof и eoln заменены на seekeof и seekeoln соответственно. Имя файловой переменной при этом опускается, что опять же возможно для стандартного потока ввода, даже после перенаправления его в файл. Только при показанном способе ввода чисел не возникают ошибки в работе подобной программы, связанные с наличием пробелов в конце строк и пустых строк в конце файла, так как для корректного использования функции eof требуется, чтобы признак конца файла стоял непосредственно после последнего числа в файле. То же требование относится к признаку конца строки при использовании функции eoln. Несмотря на то, что числа расположены в различных строках файла, процедуру readln при вводе именно чисел можно не использовать (в приведенном примере она взята в комментарий, снятие которого не изменит работу программы). Отметим, что техническую проблему, связанную с обработкой заранее неизвестного количества чисел в строке или в файле в целом, разрешить на языке программирования Си несколько сложнее.
Наоборот, если во входном файле находится текст, размер которого неизвестен, то поступать следует несколько по другому. Использование seekeoln может привести к ошибке, так как в тексте пробел уже является значимым символом. С другой стороны, служебные символы, обозначающие конец строки в файле и перевод на новую строку (их коды 13 и 10), не могут считаться частью текста и не должны анализироваться алгоритмом его обработки. Поэтому, если известно, что длина каждой строки текстового файла не превосходит 255 символов, то удобнее всего считывание производить с использованием переменной типа string:
while not eof do
begin
readln(S);
if s<>'' then {обработать строку S}
end;
В этом примере использование readln, а не read является уже принципиальным. Если же ограничения на количество символов в одной строке нет, то считывание следует производить посимвольно. Причем на Всероссийской или международной олимпиаде отсутствие такого ограничения означает, что при тестировании программы действительно будут тесты, содержащие очень длинные строки, а на школьной или районной олимпиаде, — что скорее всего такое ограничение просто забыли включить в текст условия, а все тесты будут состоять все-таки из коротких строк. Пример посимвольного считывания текста из файла:
while not eof do
begin
n:=0;
s:=0;
while not eoln do
begin
read(с);
{запись символа с в массив или его обработка}
n:=n+1
end;
readln;{!!!}
if n>0 then {обработка строки} else {строка пустая}
end;
Именно использование оператора readln позволяет и в данном случае автоматически исключить из рассмотрения символы перевода строки.
Последний вариант считывания данных относится к случаю смешанной информации, то есть в файле присутствуют как числа, так и символы или последовательности символов. Формат такого файла обычно определен заранее, поэтому считывание можно организовать сразу в переменные соответствующих типов. Наоборот, считывание информации в одну строковую переменную, а затем выделение из нее отдельных элементов и преобразование строкового представления данных в числовое, делает программу более громоздкой и зачастую требует отладки. Пусть, например, в каждой строке файла записана фамилия человека, затем через пробел его год рождения и, наконец, опять же через пробел — его пол, обозначенный одной буквой. Приведем фрагмент программы, считывающий данные описанного формата из файла сразу в переменные соответствующих типов:
while not seekeof do
begin
read(c);
S:='';
{формируем строку с фамилией}
while c<>' ' do
begin
S:=S+c;
read(с)
end;
read(n);{считываем год рождения}
readln(c,c);{считываем пол}
…{обработка считанной информации}
end;
При считывание символа, обозначающего пол человека, предварительно следует пропустить пробел, который ему предшествует. Именно поэтому считываются два символа, а не один, и значение первого символа (пробела) теряется при считывании второго (значения пола).
Во время записи результатов работы программы в файл обычно проблем практически не возникает. Ошибки в формате вывода могут быть связаны с отсутствием разделителей (пробелов или символов перевода строки) между выведенными в файл числами или с формой записи вещественного числа. Если вещественные типы данных используются для работы с целыми числами, а при выполнении над целыми числами только операций сложения и умножения это часто позволяет получить точный результат, по количеству значащих цифр более чем в два раза превосходящий максимальный целый тип, то выводить результат следует так:
writeln(x:0:0)
Если же результат работы программы представляет из себя произвольное вещественное число, то формат его вывода обычно оговорен в условии задачи. Так, если требуется получить в дробной части три цифры, то печать можно производить по формату x:0:3.
Инициализация данных и создание динамических переменных
Как уже говорилось в предыдущей лекции, одна из типичных ошибок при программировании в том числе и олимпиадных задач — неинициализация глобальных переменных. Нулевые значения всем статическим переменным в программе присвоить достаточно легко. Сделать это можно, например, так, как было показано в процедуре initial в “универсальной программе для решения олимпиадных задач” (см. лекцию 2), а именно:
fillchar(i,ofs(Last)-ofs(i)+sizeof(Last),0)
Здесь i — имя обязательно первой из описанных в программе переменных, Last— последней. Таким образом данная стандартная процедура заполнит нулями все байты памяти, которые используют статические переменные. После выполнения этой операции все числовые переменные, в том числе и элементы массивов, получат нулевые значения, всем символьным будет присвоен символ с кодом 0, а всем строковым — пустые строки, так как в байт, отвечающий за длину строки также занесен ноль и т.д. Если же количество глобальных переменных в программе невелико и не для всех из них ноль подходит в качестве начального значения, то инициализацию можно проводить для каждой переменной в отдельности. Для простых переменных это можно делать с помощью оператора присваивания или путем описания переменных как типизированных констант (в разделе описаний const, но с одновременным указанием и типа переменной и ее значения). Для массивов— с использованием все той же процедуры fillchar, но в пределах конкретного массива. Например:
var a:array[1..1000]of integer;
c:array[1..10000]of char;
begin
fillchar(a,sizeof(a),0);{заполняем массив a нулями}
fillchar(с,sizeof(с),'+');{заполняем символом плюс массив с}
…
end.
К сожалению, таким способом ненулевые значения можно присвоить лишь массивам, элементы которых по размеру не превосходят один байт (типы byte, shortint, char, boolean). Значения элементов массивов других типов задавать приходится в цикле. Однако, если два массива одного и того же типа требуется проинициализировать одинаково, то заполнить в цикле можно только один из них, а второму массиву просто присвоить первый (присваивание — единственная допустимая операция над составными переменными, такими как массив, как над целыми объектами). Иногда массивы удобно описывать и задавать в разделе констант путем непосредственного перечисления значений всех элементов массивов.
Как уже говорилось выше, для размещения всех глобальных переменных программе отводится не более 64 килобайт оперативной памяти. Однако при решении задач иногда требуется завести несколько массивов, размер каждого из которых не менее 32 килобайт. Покажем, как достаточно просто решить подобную проблему:
const n=150;
type aa=array[1..n,1..n] of integer;
var a:aa; {a - массив}
b:aa;{b - указатель на массив}
i,j:integer;
begin
fillchar(a,sizeof(a),0);
new(b);{создание динамического массива}
b:=a;{копирование массива a в динамический массив}
for i:=1 to n do
for j:=1 to n do
b[i,j]:=i+j;{обращение к элементам динамического массива}
…
end.
Из примера видно, что работа с динамическими массивами не намного отличается от работы со статическими. Причем использовать данный прием можно “по образцу”, не вдаваясь в механизм работы с указателями. Если же размер двумерного массива превосходит 64 килобайта, то создать его с помощью динамических переменных можно, например, следующим образом:
const n=500;
m=100;
type aa=array[1..n] of integer;
var b:array[1..m] of aa;
{b - массив указателей на одномерный массив}
i,j:integer;
begin
for i:=1 to m do
new(b[i]);{создание m динамических массивов}
for i:=1 to m do
for j:=1 to n do
b[i][j]:=i+j;{обращение к элементам двумерного массива}
…
end.
Таким образом, использование динамических переменных позволяет практически не изменять алгоритм решения задачи в случае, когда использование статических массивов уже невозможно. Использование же таких переменных требует лишь небольшой аккуратности в их создании и корректного обращения с уже созданными динамическими переменными.
Подсчет времени работы программы
На олимпиадах высокого уровня, к которым можно отнести и региональные соревнования, практически всегда в тексте условия задачи указано максимальное время работы программы на одном тесте. Поэтому писать программу, которая будет работать при каких-либо входных данных дольше этого времени, смысла нет. Если же выбранный участником алгоритм в отведенное для работы программы время не укладывается, то зачастую помогает прием, называемый — отсечение по времени. Применяется он в основном в задачах, решение которых производится с помощью перебора вариантов (а большинство олимпиадных задач в силу их дискретности можно решать с помощью полного перебора вариантов, правда лишь при небольших размерностях). Пусть в условии задачи требуется найти любой допустимый или даже оптимальный вариант, а при отсутствии допустимого варианта выдать сообщение, что решение отсутствует. Тогда работу программы следует организовать так, чтобы по истечении отведенного на ее выполнение времени выполнение программы заканчивалась и печаталось лучшее из рассмотренных к этому моменту решений или сообщение, об отсутствии решения. Если перебор в такой программе организовать “с предпочтением”, то есть сначала рассматривать наиболее вероятные варианты, то такая программа может работать правильно почти на всех входных данных, несмотря на возможную неэффективность заложенного в нее алгоритма. Так как правильно организованный перебор зачастую быстро находит решение задачи, а рассмотрение остальных вариантов необходимо в нем лишь для того, чтобы доказать оптимальность уже найденного. Поэтому, если за отведенное время не найден никакой вариант, то будем считать, что решение в задаче отсутствует (конечно, это не всегда оказывается справедливым), а если какой-то вариант найден, но перебор еще не закончен, то опять же можно надеяться, что этот вариант и есть искомый. В любом случае такая программа всегда результативно заканчивает свою заботу за время ее тестирования и баллы, полученные за нее могут быть весьма высокими (иногда такая программ получает полный балл за решение задачи).
Осталось показать, как программно реализовать описанный прием отсечения рассматриваемых вариантов по времени. Опытные участники олимпиад делают это так:
const timetest=10;{время тестирования программы}
var timer:longint absolute $40:$6c;
timeold:longint;
begin
timeold:=timer;
while true do
if timer-timeold>18.2*(timetest-0.5) then
begin
…{запись текущего результата в файл
или сообщение об отсутствии решения}
halt
end else {собственно работа программы}
end.
Данная программа использует тот факт, что к значению четырехбайтовой целой переменной, расположенной по абсолютному адресу $40:$6С, раз в 1/18.2 секунды аппаратно прибавляется единица. Поэтому, если мы опишем в нашей программе переменную, привязав ее к этому адресу, то легко сможем определить время работы программы. А именно, запомнив в самом начале программы значение этой переменной (в нашем примере это оператор timeold:=timer), в процессе работы определить время выполнения в секундах можно по формуле (timer timeold)/18.2. Поэтому, если время тестирования известно, то прерывать поиск решения следует за некоторое время до его окончания (в нашем примере это 0,5 секунды), для того, чтобы успеть вывести результат.
Лекция 4.