SRM 495 will be held at 27 january 16:00 GMT. Good luck, have fun!
And may The Force be with you.
And may The Force be with you.
→ Обратите внимание
До соревнования
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.10.2026 23:26:55 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Неудачно совпало со временем поезда ... - Петрозаводск.
Наоборот, надо запускать из всех вершин, независимо посетили их или нет. Иначе такой тест, граф:
1-2
3-4
В итоге у тебя ответ - 4. Т.к. из вершин 2 и 4 ты не будешь запускаться и у тебя буду одни 2.
Еще тест:
1-2
2-3
4-2
5-3
Здесь ответ по твоему алгоритму - 3. Хотя на самом деле достаточно заглянуть в 2 коробки - 1 и 4 (или 5).
Я вот щас поигрался на дорешке - можно решать и так, как ты описал.
Я решал так: закреплял что выкидывать, затем находил транзитивное замыкание, а потом добавлял вершины жадно, каждый раз добавляя ту, которая закрашивает максимум из непокрашенного.
Чтобы прошла не хватало при вычислении транзитивного замыкания не учитывать выкинутую вершину.
И Petr'а с очередной победой! :)
И снова здравствуй, Div. 1.
До скорой встречи, Div. 2. Не скучай сильно.
Генерим строку из n символов соответственно простым и непростым числам.
Находим первое возможное вхождение данной строки в результирующую. За линию. :)
Находим последнее возможное вхождение. Аналогично.
Пересекаем. Если не совпадают => -1.
Эта та же задача, что 250 Div 1.
А решается она следующим образом. Для каждой позиции проверим какие числа на ней могут стоять. А именно:
Так определяем что может стоять на i-ой позиции ответа. И однозначность его.
Сложность O(N^2 * длинну строки)
Ну я исходил из следующей идеи. Построим граф в котором вершинами будут коробки, а ребра будут соответствовать тому, что открытие этой коробки влечет знание, того что в другой коробке. После построения такого графа сожмем все сильно связные компоненты и получим ациклический граф в котором есть вершины в которые ничего не входит (пусть их q щтук). Т.е. мы точно определим коробку которая пустая не более чем за q открытий коробок, и не менее чем за q-1 в худшем случае. Теперь осталось определить когда мы можем получить q-1. Это значит, что после открытия всех остальных q-1 коробок у нас осталась ровно одна про которую ничего не известно. А тогда ответ q-1 если можно выбрать q-1 коробку из оставшихся, так чтобы ровно 1 была не использована (это можно сделать например проверкой есть ли такая коробка, из которой можно попасть только в вершины, которые покрыты, оставшимися).
Ну как-то так. Надеюсь более менее понятно.
Объясните кто-нибудь как Div 2 1000 решается. :)
Решение.
Строим граф. Вершины - клетки, соединяем вершины ребром, если они лежат в каком-то незаблокированном треугольнике. Далее пускаем dfs по графу и ищем количество вершин в каждой компоненте связности. Если их a1, a2, ..., ak, то ответом будет число f(a1)*f(a2)*...*f(ak), где f(x)={x!/2 при x>=3, 1 иначе}.
Это был мой первый tc и div2 меня разочаровал - из 20 участников комнаты 9 не пришли, 9 решили только первую задачу, а последний 1 и 2, но вторую у него сломали в первую же минуту => челленджить было просто некого.