Давайте здесь обсуждать задачи.
Кто как делал J в усложненке?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Название |
---|
Расскажите СМС и Благовонное число, пожалуйста.
В 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?
Авторская идея решения использует паросочетание :) Далее предлагаю подумать самим — если не получится, расскажу!
В голову лезут только переборы с кучей отсечений. Хотя на контесте подумал что тут поток, но вот не особо понимаю как его тут прилепить.
Если я не ошибаюсь, то можно решать так: Переберем цвет левого верхнего угла. Теперь построем двудольный граф где вершины это диагонали. Один тип диагоналей будет в первой доле, второй соответственно во второй. Между вершинами будет ребро, если клетка в которой они пересекаются(если пересекаются) покрашена не в свой цвет. Ответом будет размер минимального вершинного покрытия, он вроде равен максимальному паросочетанию.
Спасибо.