О школьной олимпиаде

Эта информация касается школьной олимпиады в Нижегородской области. В других регионах могут быть отличия.

Краткое содержание того, что ниже

• В школьной олимпиаде стоит участвовать как минимум всем, у кого уровень 1В и выше
• Участвовать надо по задачам за 9-11 класс, даже если вы в младших классах
• Заранее выясните, где и когда будет олимпиада, и попросите вам дать возможность писать на том языке, на котором вы хотите.
• На самой олимпиаде:
• Тщательно тестируйте свои задачи, жюри будет проверять их только после олимпиады и второй попытки у вас не будет!
• Неполные решения также оцениваются
• Прочитайте все задачи сразу, не тратьте всё время на одну задачу.
• Регулярно сохраняйте решения
• Не бойтесь задач, самые сложные обычно примерно соответствуют уровню 1Г-2А, и не обязательно решать всё, чтобы пройти дальше.
• Если что-то забыли, ищите обходные пути
• Ищите закономерности
• Применяйте здравый смысл
• Как только узнаете свой результат, скажите его мне
• (Только нижегородцы) По любым вопросам, а особенно если что-то идет не так, сразу и в любое время звоните мне!

О чем речь?

Школьная олимпиада по информатике в Нижнем Новгороде состоится, видимо, в конце сентября — начале октября; сроки могут быть разными в разных районах. Уточните сроки заранее в своей школе. (Школьники не из Нижнего Новгорода — тоже уточняйте у себя в школе).

Говорят, что в некоторых школах олимпиада будет аж 19 сентября! Это очень рано, конечно. Но это обозначает, что обязательно поторопитесь и выясните всё заранее!

Школьная олимпиада — это первый этап в системе Всероссийской олимпиады школьников. Победители школьной проходят на районную олимпиаду, с районной — на областную и далее на собственно всероссийскую и международную, поэтому это — самая важная последовательность олимпиад в году, и школьная олимпиада является "входом" в нее. Не пропустите.

Кому стоит участвовать?

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

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

Что надо сделать, чтобы участвовать?

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

Если вы младше 9 класса, то обязательно скажите, что вы хотите писать задачи за 9 класс (см. про это подробнее ниже). (В лицее 40 я сам это проконтролирую.) Младше 9 класса могут быть очень странные задачи, очень странная организация и т.д. — ни в коем случае не соглашайтесь участвовать по задачам младше 9 класса, даже если вы сами намного младше :)

Заранее уточните, на каком языке программирования вы сможете писать. Постарайтесь уговорить учителей, чтобы вам дали написать вашем любимом языке, будь то Free Pascal, и PascalABC или Python или что угодно еще; если нужно, предложите, что вы сами установите нужные программы (компиляторы, среди разработки) на компьютер(ы), на которых будет олимпиада. (В лицее 40 я постараюсь заранее это все обсудить, но на всякий случай можете и сами уточить.)

Если возникают какие-то проблемы, обязательно пишите или даже звоните мне (только нижегородцы)! Я не уверен, что смогу чем-то помочь, но вдруг. Не тяните с проблемами до последнего.

Как проходит олимпиада

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

Но есть важное отличие — на сайте результат проверки задачи сообщается вам сразу же, и вы можете сдавать одну и ту же задачу несколько раз. На олимпиаде ваши задачи будут проверяться только после тура, и у вас уже не будет возможности исправить никакие ошибки. Поэтому тщательно проверяйте свои решения, про это еще см. ниже.

Олимпиада длится ограниченное время (скорее всего, два урока, но уточните заранее), поэтому внимательно контролируйте время. Не зависайте над одной задачей; если что-то не получается, то подумайте, может быть, стоит переключиться на другую задачу?

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

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

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

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

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

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

Имейте в виду, что вам не обязательно решать всё. Чтобы пройти на районную олимпиаду, часто достаточно набрать половину баллов, поэтому не бойтесь, если у вас не получается решить самую сложную задачу (или две самых сложных, если задач много). (Но все равно постарайтесь по ним хоть что-то написать.) Для 11-классников порог прохода на район может быть выше.

О задачах за разные классы

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

При этом формально может быть сказано, что олимпиада проходит только для определенных классов, как правило — для 9-11 классов. Но это вовсе не значит, что младшеклассники не могут в ней участвовать — даже если вы младше 9 класса, вполне можете писать за 9 класс.

Но помимо этого, я иногда слышал, что в некоторых школах бывают какие-то отдельные задачи для более младших (например, 7-8 классов). Это довольно странно; в лицее 40 я никогда про такое не слышал. Возможно, это инициатива отдельных школ или районов. В любом случае, это не то: по этим задачам вы в лучшем случае пройдете на район и дальше никуда, в худшем случае вам скажут, что "района по вашим классам не бывает" (знаю реальный такой случай). Задачи на этих олимпиадах могут иметь мало общего с тем, что мы тут проходим, организация может быть хуже (например, вам могут предложить писать программу на бумажке (!)) — в общем, если вы младше 9 класса, убедитесь, что вы выступаете за 9 класс и пишите по тем же задачам, что и 9-классники. Для этого может быть полезно заранее сказать, что вы хотите участвовать за 9-й класс. Не бойтесь этого; как я уже писал, если у вас уровень 1В или выше, то вам эти задачи будут по силам. И даже если вы решите их плохо, все равно вы получите ценный опыт, который вам пригодится через год.

О результатах

Как только будут известны ваши результаты, сообщите их мне. Результаты — это общее число набранных баллов (а хорошо бы и распределение баллов по задачам) и проходите вы на район или нет. Про район иногда сообщают сразу, иногда не сразу — если вы пока знаете только баллы, то сообщите мне только баллы, потом как будет известно про район, сообщите мне.

Какие будут задачи?

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

Какие знания могут потребоваться?

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

int64

В паскале есть очень полезный тип данных, про который вы, возможно, не знаете. Это int64 — 64-битное целое число. Он может хранить числа от (примерно) -2⁶³ до 2⁶³; это примерно от -9e18 до 9e18. Он полезен, если значения, которые вам нужны в вашей программе, не влезают в integer.

var a:int64;
begin
a:=1000000000;
a:=a*1000000000;
writeln(a); // выведет 1000000000000000000
end.

Тестирование задач

Очень важная вещь на олимпиаде — аккуратно протестировать задачи. На эту тему я недавно написал длинный текст (ссылка на него также есть в уровне 1В). Прочитайте его и следуйте его рекомендациям. Конечно, вам пока не обязательно использовать совсем уж продвинутые вещи типа стресс-тестирования или assert'ов, но практически весь остальной текст вам будет полезен. Не жалейте времени на аккуратное тестирование.

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

Работа с файлами

Ниже — про паскаль; про работу с файлами в питоне см. текст на уровне 2А.

На школьной олимпиаде, вполне возможно, вам придется вводить данные не с клавиатуры, а из указанного в условии задачи файла, и аналогично выводить данные не на экран, а в файл. В паскале это делается это так: вы заводите переменную специального типа text, а потом командами assign и reset/rewrite "открываете" файл на чтение/запись соответственно. Далее в командах read/readln и write/writeln первым аргументом указываете файл (переменную), откуда читать или куда выводить. После работы с файлом "закрываете" его командой close. При этом тогда ваша программа не должна ничего вообще читать с клавиатуры! Т.е. по нажатию Ctrl-F9 черное окошко должно мелькать на мгновение, после чего должно возвращаться синее окошко паскаля.

Пример кода, который читает из файла input.txt два числа и выводит в файл output.txt их сумму:

var f,g:text;
    a,b:integer;
begin
assign(f,'input.txt');reset(f); // "открыли" файл input.txt для чтения
read(f,a,b); // из файла f прочитали числа a и b
close(f); // "закрыли" файл
assign(g,'output.txt');rewrite(g); // "открыли" файл output.txt для записи
writeln(g,a+b); // вывели сумму чисел в файл g
close(g); // "закрыли" файл
end.

Как тестировать такую программу? В оболочке паскаля вы можете открыть несколько окон (через меню File - Open). В одном набираете программу (и сохраняете файл как чтонибудь.pas), в другом редактируете входной файл (и сохраняете как требуется по условию), в третьем открываете выходной файл.

Переключаться между окнами можно, нажав Alt-0 — будет окошко со списком всех открытых файлов. Можно также заметь в правом верхнем углу каждого окошка цифру (1, 2, 3 и т.д.) и переключаться в это окошко, нажав Alt-1, Alt-2 и т.п. Я, например, предпочитаю иметь в окошке "1" исходный текст программы, в окошке "2" входной файл, в окошке "3" выходной файл. Я не советую вам иметь много открытых окон — оставляйте открытыми только те окна, которые нужны для текущей задачи. Когда переключаетесь на новую задачу, закрывайте все окна от старой задачи и открывайте окна для новой задачи.

Соответственно, теперь вводите тест в окошко с входным файлом, не забываете его сохранить (!), и запускаете программу. Если в одном из окон у вас открыт выходной файл, то после запуска программы паскаль вам будет выводить диалоговое окно вида "File output.txt has changed on disk. Reload?" ("Файл output.txt изменился на диске. Перезагрузить?"; точный английский текст я не помню.) Нажмите "yes" — и в окошке с выходным файлом его содержимое автоматически обновится.

Тестировать программу так даже удобнее, чем при вводе с клавиатуры: если вы отлаживаете программу на конкретном тесте, то вам не надо его вводить заново при каждом запуске.

Обязательно попробуйте работать с файлами до олимпиады!. Если на олимпиаде у вас не получается быстро наладить работу с файлами, то лучше попросите разрешения работать по старинке — с клавиатуры и на экран. Не теряйте время на то, чтобы разобраться с файлами на олимпиаде!

Алгоритмы

В основном большинство задач на школьной олимпиаде вряд ли будут требовать специальных знаний, особенных алгоритмов. Задачи, скорее всего, будут требовать только аккуратного размышления и аккуратной реализации; ничего такого, что мы с вами не проходили, не потребуется. Возможно, придется пописать что-то на бумажке, сделать какое-то моделирование и т.п. Все будет довольно похоже на задачи уровней 1В и 1Г.

В наиболее сложных задачах, возможно, потребуются алгоритмы, обсуждаемые в уровнях 2А и 2Б — в первую очередь НОД, сортировки, простые числа и разложения на множители, может быть ДП. Если у вас уже решено хотя бы задач 10-15 уровней 1В/1Г, можете переключиться на эти темы на уровне 2, но не тратьте много времени — лучше порешайте еще задач с уровней 1В/1Г и научитесь тестировать задачи. Конечно, если у вас уже много задач уровней 1В/1Г решено и вы уже находитесь на уровне 2, то изучите эти темы.

Сложность алгоритмов

Важной вещью может оказаться определение того, насколько долго работает придуманный вами алгоритм на больших входных данных. Это обязательно стоит проверить, в идеале — еще до написания программы. Для этого существует понятие сложности алгоритма, про нее можно почитать тут (в первую очередь читайте часть 1; самое главное — в абзаце, который на стыке страниц 2 и 3, про 100 миллионов действий).

Используйте компьютер по полной

Помните, что вы можете на компьютере не только писать программы-решения задач. Если вы, например, думаете над задачей, и вам стало важно узнать, чему равно 163*634, то не надо умножать числа в столбик. Воспользуйтесь калькулятором на компьютере или напишите отдельную программу из одного writeln/print. Если у вас в задаче описан какой-то процесс (есть N бактерий, они размножаются по каким-нибудь правилам, или что-нибудь подобное), не бойтесь написать отдельную программу, которая промоделирует этот процесс, выведет что вам надо, чтобы вы могли поискать какие-нибудь закономерности. И так далее. Не бойтесь писать вспомогательные программы.

Ищите закономерности

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

Знакомые задачи

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

Если чего-то не знаете, ищите обходные пути

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

Здравый смысл

Ну и главное. Применяйте здравый смысл. Думайте головой, постоянно думайте над тем, что вы делаете, и помните, что ваша цель на олимпиаде — как можно лучше выступить по сумме заданий.

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