Про ННОИ
Провели — 4 дня назад — седьмую нижегородскую городскую олимпиаду школьников по информатике. Все материалы .
в этом году, по моим ощущениям, намного более плотные по сложности, чем в прошлые годы. Не было откровенных халяв, и не было откровенных гробов. Впервые за последние несколько лет у меня до олимпиады была уверенность в том, что будет результат за 500 баллов, и я даже думал, что есть небольшая вероятность, что кто-нибудь получит максбалл. Но с другой стороны, в общем-то, было ясно, что простых задач тоже нет, и потому было логично ожидать не самые высокие результаты в середине-нижней половине таблицы.
это и подтвердили. Максбалла, конечно, нет, и результат за 500 один — но больше ста баллов набрали лишь 16 человек — с огромным запасом антирекорд за последние несколько лет. В общем-то, плохо, по-моему, и то, и другое. И даже у меня есть соображения, почему так получилось. Надо будет постараться в следующем году этих проблем избежать. (Конечно, еще и отсутствие Сарова в этом году ощутимо сказалось на результатах.)
Кстати, который год одна из причин, почему у нас так много нулей — это то, что многие школьники получают ноль из-за тупости типа неправильного названия файла или чтения с клавиатуры. Надо будет таки через год организовать возможность проверки задачи на тестах из условия по ходу олимпиады. Хоть у нас, видимо, наладить сеть всем участникам — это нетривиальная задача, но поэтому надо будет просто сделать возможность локальной проверки, расписав всем по компам микро-тестирующую систему.
Задача 1. Тупики в городе.
Дано клетчатое поле, каждая клетка может быть или проходима, или нет. По полю можно двигаться, переходя с клетки на соседнюю по стороне, но запрещается делать два хода подряд в противоположных направлениях. Ясно, что в результате можно застрять в тупике. Надо пометить все тупики, т.е. все такие клетки, куда, раз зайдя, дойдешь до тупика.
Задача придумалась год назад, когда я писал программу на мерский конкурс стратегий. Там надо было написать искуственный интеллект для игры а-ля пакман: игрок управлял одним пакманом и двумя приведениями; одновременно на поле выпускали четырех игроков, т.е. 12 персонажей. В процессе пробных игр я обнаружил, что мои пакманы часто попадают в тупики, где их зажимают чужие приведения, поэтому пришлось писать отдельный кусок кода, который детектировал подобные тупики. Я написал первое, что пришло в голову — поиск в глубину, — но в процессе написания обнаружил, что это не так просто: моя программа заработала не с первой попытки. Понял, что это вполне годится на задачу, добавил в репозиторий задач.
Когда этой осенью мы стали выбирать задачи для дальнейшей проработки и обсуждали эту задачу, Антон вдруг оборонил какую-то фразу про очередь, и до меня дошло, что и правда, эту задачу еще проще решить не поиском в глубину, а просто очередью клеток-кандидатов на пометки. (Аналогично топсорту, не использующему поиск в глубину.) Это меня еще больше обрадовало. В итоге по этой задаче я написал нормальное решение с очередью, а потом нашел-таки тот код, который я посылал в Меру, и выдрал оттуда свое старое решение. Первый раз за все города у меня получилось одно из решений — на сях.
Долго думал, какую придумать легенду, чтобы не писать явно, что именно надо сделать ("удалить все вершины степени 0 и 1, потом еще раз и так до тех пор, пока таких вершин не останется"), чтобы надо было хоть немного об этом подумать, но чтобы все было достаточно четко и строго. Изначально я, конечно, хотел придумать легенду типа погони, но в итоге написал легенду с запретом разворота, поскольку она, в общем-то, мне показалась более понятной.
В этой же задаче довольно быстро стало понятно, что в условиях 16-битных компиляторов невозможно дать эту задачу так, чтобы она не решалась за четвертую степень. Пришлось давать ограничения такие, что на BP задача не решается — о чем мы честно и предупредили в условиях.
А вообще, пожалуй, из всех задач олимпиады лично мне больше всего нравится именно эта задача.
Задача 2. Калитка в заборе.
На отрезке [L,R] отмечено несколько точек. Надо стереть минимальное количество так, чтобы на этом отрезке образовался интервал ширины как минимум W, не содержащий точек вообще.
Довольно стандартная задача на сортировку + два указателя; желающие могли так
Добавить комментарий