На сайте Яндекс тренировок есть NEERC 2011 Western Subregional Contest.
Кто решал, можете поделиться идеями по задачам B,E, F, I или J? :)
На сайте Яндекс тренировок есть NEERC 2011 Western Subregional Contest.
Кто решал, можете поделиться идеями по задачам B,E, F, I или J? :)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
Е: Считаем вероятность противоположного события (все джентльмены выбрали разные цвета), просто умножая 1 на (2*с-2*i)/(2*c-i), 1<=i<M. Как только вероятность стала меньше eps, выводим 1.
I: Находим компоненты связности. Если хотя бы одна содержит нечетное число вершин - impossible. Иначе строим искомый граф с нуля. В каждой компоненте начального графа пускаем дфс, для каждой вершины: если степень потомка в новом графе четная - добавляем ребро вершина - потомок в новый граф.
Остальные не решил, самому очень интересно)
А, туплю, всё ок, там строго меньше M.
G (Midsummer Fires):
Ключевой факт - что каждая тень - это такая бесконечная полоска с константной толщиной (короче, прямоугольную форму имеет).
Задача свелась к тому, что есть такие бесконечные полоски, и есть точки, и надо для каждой точки узнать, попала она хоть в одну полоску или нет.
Учитывая, что все эти полоски ориентированы по направлению от одной и той же точки - от точки источника света, можно сделать такое решение: отсортировать всё (и полоски, и точки) по расстоянию от источника света и обрабатывать в этом порядке. Мы поддерживаем все текущие полоски в отсортированном по углу порядке (в виде set, например), и тогда для ответа на запрос нам надо просто взять две полоски, соседние по полярному углу с текущей точкой-запросом (можно понять, что другие полоски, чем ближайшие по углу, нет смысла брать).
Ну и там у нас проблемы с точностью были, так что стараться как можно больше всего в целых числах делать.
P.S. Задача B тоже интересует, мы не сдали.
А там достаточно тупое решение.
Дело в том, что даже в худшем случае нам не придётся менять очень уж много элементов, потому что количество различных чисел (пусть даже и с константной суммой цифр) растёт весьма быстро.
Поэтому решаем так: перебираем, сколько цифр на суффиксе входного числа мы будем менять, и запускаем динамику с двумя состояниями (количество_цифр, сумма_цифр), которая возвращает нам количество таких чисел - и если это количество стало >= T, то мы останавливаемся и выводим ответ, восстанавливая его по динамике.
Точно асимптотику сложно оценить, но работает быстро.