Сегодня в 20:00 по Москве состоится 1B Round. Не пропустите!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.12.2024 22:39:02 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
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. смог зайти