Завершилась 1-ая командная олимпиада на http://neerc.ifmo.ru/school/io/
Давайте тут обсуждать задачи.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Завершилась 1-ая командная олимпиада на http://neerc.ifmo.ru/school/io/
Давайте тут обсуждать задачи.
Название |
---|
Я H решал рекурсивно, причем, учитывая тот факт, что не может быть больше 2 итераций.
Тут напишу все решения:
Задача Б:Задача А:
Если точка 1 - ответ очевиден.
Если все на одной прямой, то ответа нету.
Отсортим все точки по х, в случае равенства, по у.
Проведем прямую между первой и последней точкой, теперь все что сверху последовательно соединим как отсортировали, а то что с низу в обратном порядке, это и будет ответом.
Возьмем ДП по параметрам F[mask,sum1,last] , mask - маска того что осталось на столе, sum1 - сумма у первого игрока, last - кто ходил первым на прошлом шагу, ответ - то сколько первый максимум наберет начиная с этого состояния. Теперь переходы:
mask = 0 - ответ sum1
иначе определим кто сейчас будет ходит первым, по этим параметрам, это не сложно, и теперь два варианта:
если 1м ходит 1й, то он берет печеньку, а 2й делает такой ход что-бы в результате 1й получил минимум, при этом 1й выберт максимум их всех этих минимумов, а в случае если 1й ходит 2м, то все наоборот, то есть ищем минимум из максимумов. Так-как состояний не много , то сложность выходит не большая, если делать рекурсивно с запоминанием.
Задача С:
Возьмем ДП от позиции И как кол-во дней, что-бы перекрасить весь отрезок [1;i] в цвет последней доски, очевидно что оно считается тривиально: это значение динамики там где стоит последняя доска такого цвета + кол-во дней что-бы покрасить отрезок между ними.
Теперь в конце переберем в какой цвет все будем красить , если доска такого цвета была, то возьмем последнюю доску с таким цветом и добавим к значению ДП кол-во дней что-бы перекрасить отрезок с (ее позиции +1) до конца. Если-же такого цвета не встречалось в последовательности, то посчитаем за сколько можно перекрасить весь отрезок в этот цвет.
Задача Д:
Алгоритм Флойда. Зададим кратчайшие расстояния между всеми парами вершин. А потом возьмем одну вершину и посчитаем максимум от нее до всех остальных, ответом будет вершина с таким минимумом.
Задача Е:
Если одна из вершин имеет номер 1, то ответ 1, иначе отними от непарных 1, и ответом будет минимум из этих, получившихся, значений.
Задача Ф:
ДП. Возьмем вершину i и есть вот такие переходы:
i = 1000 -> f[i] = 0
f[i] = min(f[i-1]+1,f[i*2]+1)
Я делал ленивой динамикой, не заходя в состояния 0 и числа больше 2000(хотя логично поставить 1050, наверное). И перед переходами поставил f[i] = inf что-бы не вышло цикла.
Задача G:
Сделаем все что просят, для каждого вида посчитаем кол-во с плюсом и минусом, и выведем чего не хватает, не забывая про знак.
Задача Н:
Посмотрим на суммы(1й ряд) и сколькими способами(2й ряд) их можно получить(a = 1, b = 4):
Задача I:
Для каждого места определим купе:
<=36 -> (num-1)div 4+1
>36 -> 9-(num-37)div 2
Потом переберем два места и проверим все что сказано в условии.
Надеюсь понятно расписал.
В С можно было по-другому. Просто отсортировать по цветам и, идя по массиву, просто для каждого цвета, который встретится, посчитать кол-во дней и выбрать самое оптимальное. А если какой-то цвет не встретился, то однозначно красим в него, так как оптимальнее варианта не будет.
А в F проходил обычный рекурсивный перебор.
к сожалению, нет
UPD: но будут доступны тесты и чекеры, можно воспользоваться тестирующей системой от хардфаер (я ею пользуюсь) или другими
Регистрируемся и отправляем
Уменьшаем N до максимальной степени 2-ки, потом эту степень домножаем до 128, вычитаем 3 и умножаем 3 раза на 2 и получаем 1000.
Невнимательность всегда наготове.
Там нигде не указано.
Зато решение выше правильно.
Худший случай - это 100.
Уменьшаем до 64 - 36 ходов
Множим на 2 - уже 37 ходов (128)
128 - 3 = 125 - 40 ходов
125 * 8 = 1000 - 43 хода
вот так было RE12, а так прошло
Мне тоже не понятно...
В задаче "G", где нужно было найти потерянное число, я делал xor-ом. (все числа брал по абсолютному значению). И выводил ответ в зависимости от количества отрицательных чисел. Почему-то тоже не проходило. Выводило ВА4...Потом просто все сложил, прошло...ну например на тесте
7
-1 -2 3 -4 2 1 -3
если у ты скажешь, что четное кол-во отрицательных, выведу с плюсом 4,
то на тесте
1
-1
у тебя упадет, если я не ошибаюсь