730 участников представили хотя бы одно решение.
Всего за раунд было отправлено 4793 решения, из них 1531 правильное.
Наибольшее количество решений в GNU C++ — 1786. В Python 307 решений, 86 из них правильные.
В PHP 93 решения, 15 из них правильные.
В Perl есть 6 решений, 2 из которых правильные.
Первым задачу А решил Дмитрий Филиппов (DimaPhil) за 2:42 минуты, а задачу Б он первым решил за 12:09. Задачи C и D впервые решил Александр Обедников (AOb) на 12:25 и 37:44 минутах соответственно.
Первым, кто решил задачу Е, стал Фефер Иван (Fefer.Ivan) на 45:22 минуте.
Также Иван первым выполнил все задания за 1 час 8 минут. Всего 5 задач решили 12 человек.
10 участников были дисквалифицированы судьями.
Всего за 4 отборочных тура в отборочный тур прошли 802 участника, которые сразятся друг с другом в финале 8 июня.
Проблема А .
Социальный опрос Идея: Андрей Станкевич Реализация: Николай Ведерников Анализ: Николай Ведерников Задача требует найти минимальное и максимально возможное количество участников, которые решат задачу.
Если общее количество участников н , из них способны решить задачу а , А б Участники находят задание отвратительным.
Поскольку по условиям задачи ее решат только те, кому она не противна и кто знает, как ее решить, то число тех, кто попытается решить задачу, будет равно или меньше н − б .
То есть, если среди всех, кто пытается решить задачу, есть те, кто умеет это делать, то это будет максимум тех, кто ее решит. Это мин( а , н − б ).
Минимум достигается, если каждый, кому задача противна, сможет решить задачу, тогда ответ max(0, а − б ).
Проблема Б .
Сто Идея: Виталий Аксенов Реализация: Павел Кротков Анализ: Павел Кротков Решением проблемы является программа, внимательно рассматривающая несколько простых случаев.
Самый простой случай, когда количество цифр в числе Икс равно к +1. В этом случае вам нужно вывести −1, если число не содержит ни одного нуля, и ноль, если число содержит хотя бы один ноль.
Если количество цифр в числе Икс превышает к хотя бы три, к этой ситуации нужно относиться более осторожно.
Найдем второй ноль с конца в числе.
Давайте убедимся, что за этим не стоит ничего, кроме к +1 цифра.
Вычеркнем из числа все ненулевые цифры после предпоследнего нуля, а также вычеркнем необходимое количество цифр непосредственно перед предпоследним нулем.
Обратите внимание, что первая цифра никогда не зачеркивается, а это значит, что в конечном числе не будет ведущих нулей.
Важно было не забывать, что операцию зачеркивания цифры не следует выполнять на длину числа — решения с такой ошибкой получали превышенный лимит времени на третьем тесте.
Проблема С .
Собираюсь в гости Идея: Георгий Корнеев Реализация: Борис Минаев Анализ: Борис Минаев Для решения проблемы необходимо тщательно сымитировать процесс, описанный в условии.
При реализации удобно использовать встроенные инструменты ведения очереди.
В самих очередях можно хранить, например, номер человека, купившего соответствующий подарок.
Затем следующий визит происходит следующим образом.
Возьмем из очереди элемент, соответствующий человеку, пришедшему в гости.
Если его очередь пуста, то будем считать, что из очереди был взят элемент, соответствующий этому человеку.
После этого мы добавим этот элемент в очередь, соответствующую человеку, к которому мы пришли в гости.
Если значение добавленного элемента равно номеру очереди, в которую он был добавлен, то должно быть выведено ДА, в противном случае НЕТ.
Задача Д .
СНМ Идея: Артем Васильев Реализация: Артём Васильев Анализ: Артем Васильев Задача описывала реализацию системы непересекающихся множеств с эвристикой ранга, но без эвристики сжатия пути.
Решим задачу для каждого укорененного дерева самостоятельно; следует также рассмотреть случай наличия циклов.
Даже массив классифицировать и не был указан во входных данных, легко понять, что без сжатия пути классифицировать я — высота поддерева с вершиной я в корне.
Также отметим, что алгоритм устроен таким образом, что классифицировать я каждый раз увеличивается не более чем на единицу, а после подвешивания вершины к другой ее родитель И классифицировать не меняйте, поэтому вы можете строить от листьев к корням.
Рассмотрим поддерево с корнем в вершине ты .
Если классифицировать ты = р , затем вверху ты должны быть дети с рангом 0, 1, .
, р -1. Легко показать, что это условие является достаточным: если выполнить операции союз в порядке повышения ранга сына все операции будут проходить корректно.
Это приводит к решению для одного дерева:
- Давайте рекурсивно построим решение для всех дочерних элементов корня дерева.
- Давайте проверим это для всех час от 0 до классифицировать корень - Существует 1 сын с рангом час .
- Давайте проведем операции союз ( корень , ребенок я ) в порядке возрастания ранга ребенок я .
Время выполнения решения: О ( н бревно( н )).
Задача Е .
Нанороботы Идея: Виталий Аксенов Реализация: Андрей Комаров Анализ: Андрей Комаров Задача требует за минимальное количество ходов или разбиения на две части перенести всех нанороботов из левого верхнего угла в правый нижний.
Эту проблему мы решим с помощью динамического программирования.
Обозначим через дп [ ш ][ Икс ][ й ] минимальное количество шагов, за которое можно довести робота массой ш из клетки ( Икс , й ) до последней ячейки ( н , м ).
Начальные значения дп [ ш ][ н ][ м ] = 0 означает, что из целевой ячейки никуда выходить не нужно.
После дп будет рассчитано, ответ будет содержаться в ячейке дп [ ш ][1][1].
Давайте научимся считать дп .
Считать дп [ ш ][ я ][ дж ], мы сделаем одно из двух:
- Давайте доберемся до финиша, не разбивая робота на части.
Для этого с помощью обхода в глубину найдем кратчайший путь к финишу по уцелевшим клеткам.
- Либо мы дойдем до какой-то ячейки, разделимся на две части и воспользуемся ими, чтобы добраться оттуда.
Итоговая сложность алгоритма: О ( ш 2 н 2 м 2 ).
Теги: #программирование #спортивное программирование #rcc #rcc #rcc #кубок России по коду 2014
-
Примите Участие В Благотворительном Флешмобе
19 Oct, 24 -
Вконтакте Запустил Видеорекламу
19 Oct, 24 -
Моральное Измерение Венчурных Инвестиций
19 Oct, 24 -
Сборка Мини-Куба Бедлама
19 Oct, 24 -
Шпаргалки По Интернет-Сервисам
19 Oct, 24
