Давайте здесь обсуждать задачи.
Кто как делал J в усложненке?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3845 |
2 | jiangly | 3707 |
3 | Benq | 3630 |
4 | orzdevinwang | 3573 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3532 |
8 | ecnerwala | 3501 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 163 |
2 | adamant | 163 |
4 | maroonrk | 152 |
5 | nor | 151 |
5 | -is-this-fft- | 151 |
7 | TheScrasse | 147 |
7 | atcoder_official | 147 |
9 | Petr | 145 |
10 | pajenegod | 144 |
Название |
---|
Расскажите СМС и Благовонное число, пожалуйста.
В 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?
Авторская идея решения использует паросочетание :) Далее предлагаю подумать самим — если не получится, расскажу!
В голову лезут только переборы с кучей отсечений. Хотя на контесте подумал что тут поток, но вот не особо понимаю как его тут прилепить.
Если я не ошибаюсь, то можно решать так: Переберем цвет левого верхнего угла. Теперь построем двудольный граф где вершины это диагонали. Один тип диагоналей будет в первой доле, второй соответственно во второй. Между вершинами будет ребро, если клетка в которой они пересекаются(если пересекаются) покрашена не в свой цвет. Ответом будет размер минимального вершинного покрытия, он вроде равен максимальному паросочетанию.
Спасибо.