Уважаемые форумчане! Может кто-нибудь объяснит подробно, как правильно решать эту задачу "Есть ли жизнь на Марсе" http://acmp.ru/index.asp?main=task&id_task=556. Я нашел ее решение, она проходит все тесты, но меня интересует, как строится динамика и делаются правильно переходы.Как надо рассуждать, чтобы получить эти формулы. Спасибо за помощь.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
21:34:20
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
21:34:20
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 20:00:40 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
Одно из самых простых состояний динамики dpi, j — вероятность узнать от i человека при j = 1 правду, при j = 0 ложь. Ответ будет в dpn, 1, а переходы будут такими:
Что это значит: если текущий человек соврал мы узнаем от него правду, только если предыдущий сказал ему ложь, если он не соврал, то мы узнаем от него правду, только если предыдущий сказал ему правду. Аналогично, для лжи.
Я понимаю так. Если у нас есть один человек, то он может сказать правду и вероятность будет равнв 1. Если же он солгал, то вероятность ровна 0. Потом смотрим ситуацию для двух человек. Вероятность будет равна предыдущей вероятности для одного человека сказавшего правду умножить на его теперешнюю вероятность при условии, что он сказал тоже правду + предыдущая вероятность для одного человека сказавшего ложь умножив на текущую его вероятность. Или я не так понимаю?
Не совсем, у каждого человека есть своя вероятность услышать от него правду или ложь. Рассмотрим двух человек. У первого вероятность сказать правду p1, а солгать — q1 = 1 - p1, у второго соответственно p2 и q2. Первому сообщили информацию, он передал ее второму, а второй нам. Какова вероятность, что мы получим правду? Если они оба сказали правду или оба солгали, то вероятность будет p1·p2 + q1·q2, а вероятность получить ложь p1·q2 + q1·p2.
Спасибо за помощь. Разобрался и все понял.