Сегодня в 20:00 по Москве состоится 1B Round. Не пропустите!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
SpeedCoder2014 1B. Уж насколько хороша система оценки на ТС, но сегодня на каждую сотую балла по 5 мест. Задача B короткая, понятная, интересная, но у половины участников, по-видимому, вообще нет идей, что с ней делать.
Идея одна — перебирать две битмаски долго, надо перебирать одну. Дальше вот что?
Перебрали, проверили, можно ли с ней вообще получить ответ. Если да, то жадно строим вторую маску.
Переберем, например, битмаску горизонтальных заборов. Теперь все наше поле поделилось на секторы. Будем обходить поле слева направо и смотреть на все секторы. Если хоть в каком-то секторе после просмотра очередного столбца появилась пара "овца — волк", ставим перед этим столбцом забор. Очевидно, раньше нам ставить не имеет смысла, а позже ставить нельзя, иначе какой-то волк доберется до какой-то овцы.
а если в одном секторе такая картина:
W....
....S
то что делать?
Тогда маска не годна.
Говорим, что жизнь нас к такому не готовила и бросаем спортивное программирование.
А ты сам-то пробовал?) Не так это просто как кажется
Пробовал что? :)
Я чувствую, что туплю, но почему мы не поставим забор перед 4-ым (в 0-индексации) столбиком?
я неправильно Вас понял, сейчас все встало на свои места, спасибо!
Как решать 900?
Посчитаем динамику — какая вероятность найти свободную вершину в поддереве i, если в него уже заходило k орлов. Пересчет — Если k=1 то 1, иначе /* p=1/edges[i].length — вероятность выбрать конкретное ребро */ d[i][k]=sum(p * sum(d[j][k1] * c[k-1][k1] * p^k1 * (1-p)^(k-1-k1), k1=0..k-1), j in edges[i])
Посчитаем сначала p_go[i] — вероятность того, что мы попадем в i-ую клетку, случайно выбираю детей на пути от корня о нее.
Теперь посчитаем динамику dp[i][j] — вероятность того, что i-й орел будет сидеть в j-й клетке. Имеем формулы
Мы перебираем орла, который находится в родителе. Коэффициент (1 - p_go[j])(j - l - 1) при значении динамики показывает вероятность того, что орлы с номерами c l + 1 по i - 1 не попали в клетку j (или, что то же самое, что клетка j не занята). Ответом будет
.
dp[i][j] еще нужно домножить на p_go[j] и при возведении в степень возводить в i - l - 1, а не j - l - 1.
Никто раньше не встречался с невозможностью открыть задачу для взлома? А то висит такая единственная 900, сданная на последних минутах, в комнате, а ни двойным кликом, ни через правую кнопку -> Source открыть не получается.
На этом контесте некоторое время не открывалось решение, но потом всё стало норм.
В нашей комнате участник T-30 сдал по второй и третьей задаче заглушки, в итоге подбросив двух синих, хотя они и так прошли бы квалификацию. Чем он руководствовался не понятно. Это считается нарушением?
Нет, не считается. Можно посылать хоть пустой файл — это уже задача "Быстро найти таких в своей комнате и забить тест."
Нужно посылать код который скомпилировался.
Кто собирался участвовать в раунде 1С, у кого работает Арена? Меня выкинуло потому что пропало соединение, теперь не могу подключиться по тайм-ауту. http://www.topcoder.com/tc тоже не открывается.
Не работает. Сайт топкодера тоже лежит
UPD. смог зайти