신호 강도

Net Profits Incorporated는 장거리에서도 즉시 재구성할 수 있는 초고속 네트워크를 지원하는 새로운 세대의 네트워크 스위칭 장치를 발표했다.

이 네트워크는 새로운 종류의 스위치로 구성된다. 각 스위치는 여러 입력 회선을 감시하다가 그중 가장 강한 신호에 고정(lock-on)하고, 그 신호를 자신의 출력 포트에 연결된 모든 출력 회선으로 내보낸다.

연결 회선이 길기 때문에 신호 손실이 큰 문제이며, 스위치 자체도 추가 손실을 일으킨다. 두 손실을 모두 보완하기 위해 일부 스위치에는 증폭기가 달려 있다. 파괴적인 피드백을 막기 위해, 증폭기가 달린 스위치는 자신의 출력이 (간접적으로라도) 자신의 입력에 다시 도달할 수 있는 순환(cycle)에는 절대 연결되지 않는다.

네트워크의 한 지점에서 시작한 신호가 다른 지점에 도달했을 때 기대되는 유효 신호 강도를 예측하는 프로그램을 작성하라. 스위치 $N$개로 이루어진 네트워크가 주어지며($1 \le N \le 1000$), 스위치에는 $0$번부터 번호가 매겨진다. 각 스위치에는 배율이 하나 주어지는데, 이는 그 스위치에 들어오는 가장 강한 입력의 강도에 비해 출력이 얼마나 약해지거나 강해지는지를 나타낸다. 증폭기가 없는 스위치는 신호 강도에 $0.1$ 이상의 배율을 곱한다. 증폭기가 있는 스위치는 최대 $5.0$까지의 배율을 곱할 수 있다.

또한 네트워크 안의 연결 회선에 대한 정보도 주어진다. 각 회선에는 신호가 회선에 들어올 때보다 회선 끝에서 얼마나 약해지는지를 나타내는 배율이 주어지며, 이 값은 $0.1$ 이상 $1.0$ 이하이다.

입력은 하나 이상의 네트워크로 구성된다.

각 네트워크는 스위치의 개수 $N$을 담은 한 줄로 시작한다. 스위치에는 $0$번부터 번호가 매겨진다. $N$이 양수가 아니면 입력의 끝을 의미하며, 그 줄 자체는 네트워크가 아니다.

이어지는 $N$개의 줄이 스위치를 순서대로 설명한다. 각 줄은 그 스위치의 강도 배율을 나타내는 실수로 시작하고, 그 뒤에 그 스위치의 출력에 연결된 회선의 개수 $k$가 정수로 온다. 그다음에는 출력 회선마다 하나씩, 총 $k$개의 수 쌍이 온다. 각 쌍의 첫 번째 수는 그 회선을 입력으로 받는 스위치의 번호이고, 두 번째 수는 그 회선에서의 신호 손실 배율을 나타내는 실수이다.

각 네트워크마다 다음 형식으로 한 줄을 출력한다.

Network M: X

여기서 $M$은 네트워크 번호($1$부터 시작)이고, $X$는 강도 $1.0$인 신호가 $0$번 스위치의 (모든) 입력에 주어졌을 때 $N-1$번 스위치의 출력에서 기대되는 신호 강도이다. 그 신호가 $N-1$번 스위치의 출력에 전혀 도달하지 못하면 $X$는 $0$이다. $X$는 소수점 아래 두 자리로 출력한다.