Задача E. Лабиринт

@ivan_proger · Регистрация: 07.08.2018

Студворк — интернет-сервис помощи студентам

Робот находится в центре некоторого лабиринта. Лабиринт состоит из помещений и дверей:

https://ucarecdn.com/89b6a4d4-... a735e6f56/

На схеме изображены помещения, ограниченные радиальными и шестиугольными стенами. По краям лабиринта стены покрашены в красный цвет. В шестиугольных стенах смонтированы двери между помещениями. Радиальные стены соединены с красной стеной. Дверей в красной стене нет.

Каждое помещение имеет свой уникальный номер. Номер центрального помещения, из которого стартует робот, всегда равен 0. Ни один номер не повторяется дважды. Между помещениями установлены двери. Каждая дверь связывает некоторую пару помещений. Между двумя помещениями может быть не более одной двери. Нет ни одного помещения, в которое нельзя прийти из центра и из которого нельзя выйти к красной стене, двигаясь по направлению из центра. В радиальных стенах двери отсутствуют.

Задача робота добраться до красной стены. Робот в данном лабиринте ведет себя следующим образом: каждый раз он случайно (равновероятно) выбирает дверь, ведущую в сторону от центра. В каких помещениях робот будет заканчивать работу чаще? Определите вероятности попадания робота в помещения с красной стеной.

Формат входных данных

В первой строке программе подается целое число n (1≤n≤102) — количество дверей.

Далее в n строках через пробел записываются пары целых чисел a, b (0≤a, b≤n,a≠b) — номера помещений, которые соединены дверью.

Формат выходных данных

Для каждого помещения с красной стеной в отдельной строке выведите вероятность попадания робота в данное помещение в следующем формате:

номера помещений запишите в порядке возрастания;
после каждого номера поставьте двоеточие;
затем через пробел укажите вероятность попадания в указанное помещение. Если вероятность является целым числом, укажите это число. Если вероятность — дробное число, то запишите его в виде простой дроби x/y, где НОД(x,y)=1.
Система оценки

Баллы за задачу будут начислены, если все тесты будут пройдены успешно.

Sample Input:

23
0 1
0 2
0 3
0 9
1 16
1 17
16 15
15 14
15 13
17 21
17 18
18 19
18 20
2 4
2 5
4 6
4 7
5 8
3 22
9 23
9 10
10 11
10 12
Sample Output:

6: 1/16
7: 1/16
8: 1/8
11: 1/16
12: 1/16
13: 1/16
14: 1/16
19: 1/32
20: 1/32
21: 1/16
22: 1/4
23: 1/8

@siavash82ir · 09.11.2019, 14:05

Добавлено через 3 минуты
طراحی سایت ثبت دامنه بلیط هواپیما هاست لینوکس

вы заходите в комнату, а там 2 двери.
вероятность что вы пойдете в одну из них = 1/2

@liv · 09.11.2019, 14:11

siavash82ir, именно так

Только вот зачем было писать?
Вроде уже разобрались...

Я уже успел и забыть об этой программке...

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

@ivan_proger 3 / 3 / 2 Регистрация: 07.08.2018 Сообщений: 84

	Задача E. Лабиринт 05.11.2019, 13:03. Показов 7378. Ответов 21 Метки c++ (Все метки) Робот находится в центре некоторого лабиринта. Лабиринт состоит из помещений и дверей: https://ucarecdn.com/89b6a4d4-... a735e6f56/ На схеме изображены помещения, ограниченные радиальными и шестиугольными стенами. По краям лабиринта стены покрашены в красный цвет. В шестиугольных стенах смонтированы двери между помещениями. Радиальные стены соединены с красной стеной. Дверей в красной стене нет. Каждое помещение имеет свой уникальный номер. Номер центрального помещения, из которого стартует робот, всегда равен 0. Ни один номер не повторяется дважды. Между помещениями установлены двери. Каждая дверь связывает некоторую пару помещений. Между двумя помещениями может быть не более одной двери. Нет ни одного помещения, в которое нельзя прийти из центра и из которого нельзя выйти к красной стене, двигаясь по направлению из центра. В радиальных стенах двери отсутствуют. Задача робота добраться до красной стены. Робот в данном лабиринте ведет себя следующим образом: каждый раз он случайно (равновероятно) выбирает дверь, ведущую в сторону от центра. В каких помещениях робот будет заканчивать работу чаще? Определите вероятности попадания робота в помещения с красной стеной. Формат входных данных В первой строке программе подается целое число n (1≤n≤102) — количество дверей. Далее в n строках через пробел записываются пары целых чисел a, b (0≤a, b≤n,a≠b) — номера помещений, которые соединены дверью. Формат выходных данных Для каждого помещения с красной стеной в отдельной строке выведите вероятность попадания робота в данное помещение в следующем формате: номера помещений запишите в порядке возрастания; после каждого номера поставьте двоеточие; затем через пробел укажите вероятность попадания в указанное помещение. Если вероятность является целым числом, укажите это число. Если вероятность — дробное число, то запишите его в виде простой дроби x/y, где НОД(x,y)=1. Система оценки Баллы за задачу будут начислены, если все тесты будут пройдены успешно. Sample Input: 23 0 1 0 2 0 3 0 9 1 16 1 17 16 15 15 14 15 13 17 21 17 18 18 19 18 20 2 4 2 5 4 6 4 7 5 8 3 22 9 23 9 10 10 11 10 12 Sample Output: 6: 1/16 7: 1/16 8: 1/8 11: 1/16 12: 1/16 13: 1/16 14: 1/16 19: 1/32 20: 1/32 21: 1/16 22: 1/4 23: 1/8 0

@siavash82ir 0 / 0 / 0 Регистрация: 27.12.2018 Сообщений: 3
	09.11.2019, 14:05
	Добавлено через 3 минуты طراحی سایت ثبت دامنه بلیط هواپیما هاست لینوکس вы заходите в комнату, а там 2 двери. вероятность что вы пойдете в одну из них = 1/2 0

@liv 5120 / 4574 / 855 Регистрация: 07.10.2015 Сообщений: 9,462
	09.11.2019, 14:11
	siavash82ir, именно так Только вот зачем было писать? Вроде уже разобрались... Я уже успел и забыть об этой программке... 1