Давайте здесь обсуждать задачи.
Кто как делал J в усложненке?
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 01:39:46 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Расскажите СМС и Благовонное число, пожалуйста.
В SMS я писал динамику. f[i][j] = какое минимальное количество раз мы нажмем, если i-ая буква последняя на j-ой клавише. После этого делал восстановление ответа по динамике. Вот код — http://pastebin.com/qkmNipSA
В I (СМС) зашел простой перебор почти без отсечений.
В G нужно сначала определить длину палиндрома: заметим что кол-во палиндромов соответствующей длины
1 — 9
2 — 9
3 — 90
4 — 90
5 — 900
i — 9*10^((i+1)/2)
тогда будем идти и отнимать от числа кол-ва пока следующее можно отнять. Дальше получим номер числа нужной длины. Тут уже просто добавим к 10и в степени (длины+1)/2 номер и отнимем 1, а дальше просто скопируем в конец все что нужно, для получения длины.
Расскажите как Е в усложнённой решается?
Мы написали три разных решения и все падают на втором тесте!
Сам догадался в чём ошибка. Забыли учесть, что после 4-0 не может быть 4-1.
В J основная идея такая: если мы умеем разбивать для n, то умеем и для (n + 8). Как точно делать, не помню, решал сокомандник, но подобрать не сложно, я думаю. Теперь для всех маленьких n (<= 25 например) просто переберем все все разбиения, где не нашли — ну скажем что No :) . Вроде у нас по коду получилось что решение есть для n % 8 == 0, n % 8 == 1, (n — 12) % 8 == 0, (n — 13) % 8 == 0.
несложными арифметическими проверками можно убедиться, что если умеем решать для n — 1, то для следующих восьмых чисел тоже решим задачу. как это сделать написано во втором примере.
Интересно, каково решение задачи F? На контесте не смогли побороть WA8.
Задача сводиться к задаче поместить круг диаметром D в прямоугольник D*L А дальше каждая точка не даёт мячику находиться на отрезке, который считается по теореме Пифагора. Ну а там уже сканлайном пройти.
То же самое делали! То есть получается, мы рассматриваем оба прямоугольника, и "плохие" отрезки помещаем на одну и ту же прямую, а потом находим сканлайном на ней свободную точку? Может, из-за точности проблемы?
Не знаю, эту задачу не я писал. Архив с тестами уже выложен, можно посмотреть в чём ошибка.
А кто-нибудь знает идею на B?
Авторская идея решения использует паросочетание :) Далее предлагаю подумать самим — если не получится, расскажу!
В голову лезут только переборы с кучей отсечений. Хотя на контесте подумал что тут поток, но вот не особо понимаю как его тут прилепить.
Если я не ошибаюсь, то можно решать так: Переберем цвет левого верхнего угла. Теперь построем двудольный граф где вершины это диагонали. Один тип диагоналей будет в первой доле, второй соответственно во второй. Между вершинами будет ребро, если клетка в которой они пересекаются(если пересекаются) покрашена не в свой цвет. Ответом будет размер минимального вершинного покрытия, он вроде равен максимальному паросочетанию.
Спасибо.