На схеме изображены помещения, ограниченные радиальными и шестиугольными стенами. по краям лабиринта стены покрашены в красный цвет. в шестиугольных стенах смонтированы двери между помещениями. радиальные стены соединены с красной стеной. дверей в красной стене нет.
каждое помещение имеет свой уникальный номер. номер центрального помещения, из которого стартует робот, всегда равен 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
procedure MatPrint(a:array[,] of integer);
begin
for var i:=0 to Length(a,0)-1 do begin
for var j:=0 to Length(a,1)-1 do Write(a[i,j]:4);
Writeln
end
end;
procedure MatReplaceOdd(a:array[,] of integer; value:integer);
begin
for var i:=0 to Length(a,0)-1 do
for var j:=0 to Length(a,1)-1 do
if a[i,j].IsOdd then a[i,j]:=value
end;
begin
var n,m:integer;
Write('Задайте число строк и столбцов матрицы: ');
Read(n,m);
var a:=MatrixRandom(n,m,-99,99);
Writeln('Исходный массив');
MatPrint(a);
MatReplaceOdd(a,26);
Writeln('Результирующий массив');
MatPrint(a)
end.
Тестовое решение
Задайте число строк и столбцов матрицы: 5 7
Исходный массив
-14 86 52 -85 -52 -79 78
20 -80 68 89 -45 -45 -36
-41 -60 96 43 16 56 -58
-39 81 1 26 -15 -98 89
57 -51 79 -28 -24 -63 -74
Результирующий массив
-14 86 52 26 -52 26 78
20 -80 68 26 26 26 -36
26 -60 96 26 16 56 -58
26 26 26 26 26 -98 26
26 26 26 -28 -24 26 -74