Давайте здесь обсуждать задачи.
Кто как делал J в усложненке?
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 142 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 135 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
Расскажите СМС и Благовонное число, пожалуйста.
В 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?
Авторская идея решения использует паросочетание :) Далее предлагаю подумать самим — если не получится, расскажу!
В голову лезут только переборы с кучей отсечений. Хотя на контесте подумал что тут поток, но вот не особо понимаю как его тут прилепить.
Если я не ошибаюсь, то можно решать так: Переберем цвет левого верхнего угла. Теперь построем двудольный граф где вершины это диагонали. Один тип диагоналей будет в первой доле, второй соответственно во второй. Между вершинами будет ребро, если клетка в которой они пересекаются(если пересекаются) покрашена не в свой цвет. Ответом будет размер минимального вершинного покрытия, он вроде равен максимальному паросочетанию.
Спасибо.