Вроде бы контест уже совсем закончился
Кто-нибудь умеет вторую решать? Я послал наивное решение, которое в худшем случае работает за 22n, но придумать для него контртест не смог.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Просто чтобы "проэмулировать" какое-то развитие игры
Там получается, что, когда мы думаем куда бы походить на первом шаге, мы не знаем куда будет ходить Бесси; когда мы думаем о втором ходе мы уже точно знаем первый шаг Бесси и никак не знаем последующих. Стратегия должна быть такая, чтобы Джон рассуждал именно исходя из этих знаний, и ходил в гарантированно выйгрышную позицию.
Можем, мы переходим в состояние которые либо мы проверили на корректность (случай bottom) либо потому что нам обещали корректность, а раз bottom не обязательно корректен, то top должен быть :)
Но чтобы узнать, куда делать первый ход, мы для начала должны проверить на корректность bottom. Т.е. сделать 4n - 1 раундов, нет? Или мы "предположим" корректность и что-нибудь случится?
ПС. разумеется что решение как у Egor :)
Я тоже так считал. Судя по ограничению K <= floor(M/2), это должно быть правильно, иначе зачем оно вообще нужно.
О, спасибо, но для этого как минимум надо быть зарегистрированным :)
<offtopic> Серега это ты? Что у тебя с ником :) </offtopic>
o_O Cherry tree это маленькая девочка?
Пойду английский поучу, что ли :)
</offtopic>
Во второй dp[i][j]...это можем ли мы собрать сумму i в 1-ый ангар, и сумму j во 2-ой ангар...Дальше вроде понятно, как делать :)
Ну не знаю, может у нас разные понимания слова "медленный".
Я неправильно понял условие :(
Не знаю правильно или нет . результатов ещё нет . Но я решал 2 задачу так :
находил все возможные суммы и брал первую большую (s/3), если нацело не делится то добавлял 1.
Третью то-же жадным, а первую не придумал.
А кто знает когда результаты будут. Я на новом их сайте первый раз участвую. Раньше в среду уже на почту присылали , а в пятницу на сайте было. Сейчас зашел, ничего нет.
Ask msg555 - it's his task.
Edit:
Writing handles doesn't work...Edit2: Ok, thx
Первый раз участвую в обновленной usaco и она мне явно уже не нравится :) Фишка с подсвечиванием условий цветом дивизиона, помоему была отличной, хотя это мелочи.
Колстадукакому-то новому чуваку с подписями, пускай Гена на IOI передаст ему лично и пожурит за урезаный функционал ;)2. Последовательность ходов Бесси не важна, надо сгенерировать лексикографически минимальную последовательность ходов фермера, которая выигрывает в любом случае.
3. Ответ = произведение ответов по каждой связной компоненте: если компонента дерево, то ответ количество вершин в ней (я этого не заметил и писал ДП, мне после контеста сказали), если в компоненте ровно один цикл - то ответ для нее равен двум, иначе ответ равен нулю.
Как-то так.
У меня похожая идея, может у вас опечатка где-то, так как это набирает несколько больше.
По-моему, во второй задаче, у вас:
У меня зашла рекурсия.
P.S : Авторское решение можно найти здесь.