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

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

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

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

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

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

О чем речь?

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

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

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

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

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

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

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

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

Заранее уточните, на каком языке программирования вы сможете писать. Постарайтесь уговорить учителей, чтобы вам дали написать вашем любимом языке, будь то Free Pascal, PascalABC, Python, С++ c Code::Blocks или с MSVS или что угодно еще; если нужно, предложите, что вы сами установите нужные программы (компиляторы, среди разработки) на компьютер(ы), на которых будет олимпиада.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поэтому я настоятельно рекомендую школьникам младше 9 класса участвовать за 9 класс. Убедитесь, что вы выступаете за 9 класс и пишите по тем же задачам, что и 9-классники. Скажите учителям заранее, что вы хотите участвовать за 9-й класс. На самой олимпиаде тоже проверьте, что вы решаете задачи за правильный класс. Не бойтесь этого; как я уже писал, если у вас уровень 1В или выше, то вам эти задачи будут по силам. И даже если вы решите их плохо, все равно вы получите ценный опыт, который вам пригодится через год.

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

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

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

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

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

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

Возможно даже, что в принципе олимпиада будет как-то по-новому, я не искал детали организации в этом году.

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

Вообще, я думаю, что знаний уровней 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.

В C++ тоже есть аналогичный тип (long long int), но если вы пишете на C++, то скорее всего вы про него знаете.

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

Очень важная вещь на олимпиаде — аккуратно протестировать задачи. На эту тему есть мой длинный текст (ссылка на него также есть в уровне 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; самое главное — в разделе 4.1.3, про 100 миллионов действий).

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

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

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

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

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

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

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

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

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