Что же касается выступления, то здесь главное не победа, а участие и набор опыта. Всего на олимпиаде участвовало 53 команды. Это и студенты с разных специальностей, и школьники, тоже разных мастей.
За час до конца мероприятия перестаёт обновляться статистика, где отображается условное название команды и решённые задачи с количеством попыток, группа 09КЗОИ была на 7 месте, а наша, 08КЗОИ, только на 20. У предпоследних было верно решено 3 задачи, у нас же только одна прошла проверку.
Самое что интересное, так это то, что ответы были под самым носом. А всего-то надо было вспомнить вычислительную математику и ещё 3-4 задачи были у нас в кармане. Додумать в одной оптимизацию, в другой не упустить важную мелочь, в третьей нужно было правильно считать данные из файла и тогда ещё на 3 задачи было бы решено больше. Но, случайности не случайны.
А теперь по-подробнее. Если Вы уже ознакомились с задачами, то могли догадаться, что задача J ("Всемогущие короли") была самой простой. С ней по статистике справилось около половины всех участников. Может чуть меньше. Было команд 15-20, у которых ни одной задачи верно решено не было. Может кто-то смылся через ближайшие 40 минут после начала, может ещё чего произошло, но 10-15 команд даже ни одну задачку не пригубили.
Задача G ("Неопытный/Начинающий водитель") можно было решить верно, если не забыли бы учесть ситуацию, когда водитель едет из двора во двор напрямик, когда расстояние от начала до пункта назначения всего две условные единицы. Возможно сказалось то, что засмотрелись на неё только ближе к концу.
Задача E ("Задача Лейбница") была решена верно. Только проверку по скорости выполнения не прошла. Вся загвоздка была в том, что нужно было искать двоичный код не от квадрата заданного числа, а от самого числа. Далее уже в двоичном коде возводить его в квадрат. Таким образом получается быстрее, если делать в обоих случаях через массив.
Задача A ("Индекс Хирша") оказалась малость на смекалку. Смысл: посчитать количество цитирований, выстроить их в порядке убывания и посчитать количество статей, у которых количество цитирований больше или равно их порядкового номера упорядоченной последовательности. В результате выдать как раз это число. Всё! Однако с этой задачкой справились от силы команд 7-8.
Задача B ("Касательные"), аналогично "Индексу Хирша", тоже решается до боли просто - нужно было вспомнить геометрию или наглядно проиллюстрировать 4 различные ситуации. А дальше работаем с радиусами. Если некоторая переменная, скажем "L", - расстояние между центрами окружностей - равна сумме радиусов, тогда касательных три. Если "L" равна больше суммы двух радиусов, тогда касательных четыре. Если "L" равна или больше по модулю разности двух радиусов окружностей (две окружности пересекаются в двух точках), тогда общих касательных две. А в последнем случае, одна окружность внутри другой, "L" меньше по модулю разности двух окружностей, тогда ни одной общей касательной. С этой задачей справилось примерно столько же команд, сколько и с задачей A.
Задача C ("Функция Смарандаша") решается аж тремя способами/методами. Их можно узнать через поисковик. Так я Вам уже и не скажу, в чём смысл. Но тоже до боли простой алгоритм. По крайней мере первый, когда и в числителе и в знаменателе сокращаем всё это дело до простых чисел. И если в знаменателе останется единица, тогда в числителе и будет искомое число. Кажется так. Но этот вопрос лучше уточнить в интернете. С данной задачей справилось 2-3 команды.
Задача D ("Автобус") решается как обход графа в глубину или ширину. Главное на бумаге проиллюстрировать все возможные ситуации на примере двух пассажиров и тогда всё встанет на свои места. Только с этой задачей справилась всего одна команда. Не с первого раза - это точно. А сколько именно попыток было - врать не буду.
Дальше по списку задача F ("Холодильник"). Здесь нужно отсортировать все имеющиеся толщины листов бумаги, не теряя первоначальных индексов, и подобрать равное значение нужной толщины или близкое к ней, но не более. Первый встретившийся вариант и будет искомым, с наименьшим количеством листов. Так как если во всей последовательности не найдётся нужной толщины из одного листа, тогда придётся суммировать и искать. Довольно долго, но нужно грамотно организовать выход из циклов, чтобы уложиться во время. Если мне не изменяет память, то с этой задачкой также как и с "Автобусом" справилась одна команда. Или две - точно не помню.
Так, что там у нас осталось? Ах да, "Фонари" (задача H). здесь простой поиск интеграла методом прямоугольников. Конкретный метод на ваш выбор. Главное правильно подобрать точность, чтобы пройти по времени. В случае нескольких длин линий от разных окружностей по одной координате х нужно их просто просуммировать. В итоге должна получиться искомая площадь покрытия. Конкретно станет понятно также при иллюстрации на бумаге. Здесь уже и не скажу, сколько точно команд справилось. Кажется 6. Но это только догадки.
И, на конец, задача I ("Разлив нефти"). Здесь справилось около 2-3 команд. Основное: вода восьми-связная, а нефть - четырёх. Что суша, что вода - одно и тоже: огораживаем везде. И тупо считаем по контуру количество заграждений. Следует обратить внимание на одну деталь: если внутри самого пятна есть суша или вода - огораживаем только снаружи. В исходную карту разлива нефтяного пятна следует по контуру добавить воду, чтобы верно посчитать количество заграждений. А далее наглядные иллюстрации. Здесь можно реализовать либо в виде обхода графа, либо простое чтение с файла или массива и сразу подсчёт в зависимости от некоторых условий проверки - что окружает вокруг точку с нефтью.
Думаю, на этом всё. Оказывается всё гениальное - просто. Надо только взглянуть под нужным углом зрения. Недаром почти все лавры достались математикам.
