a673. 河流污染 - Zero1 Online Judge System

Content

有一條發源於高山的河流，當這條河流流經一個谷地時，它分出了很多支流。每一次分支時會由一條分成兩條支流，這些支流隨後又會再分支，如此類推，直到流入大海。已知這些分支在流入大海前是不會合並。更加特別的一點是每條分支在流入大海前出現分流次數是剛好相同的。

由於這條河流對當地人非常重要，因此有很多關於它的調查報告存在。其中一項調查是關於每條支流分流的情況。這個調查對於該河的每個分流點 (河由一條分流為兩條支流的地點) 所做的，這個調查記錄了分支的水流比例，即有多少百分比的水流流了入左邊的分支，及多少百分比流了入右邊的分支，這兩個百分比的和必定是100%

某天，河流的源頭出現了一些不名的放射性的污染，當地政府希望預測一下這些污染到達每個出海口的比例，以便制定相關保救的政策。於是當地政府請了你來幫他們計算一下這些比例。

Input

輸入有兩行，第一行一個正整數N，它代表每條支流入海時所經歷分流的次數。而根據上面所述，每條支流在入海前所經歷的分流次數是剛好相同的。

在第二行上有 2^N - 1 個正整數，每個整數 A_i 代表在一個分流點上，分流到左邊支流的水量的百分比 (分流到右邊支流的百分比則是 (100 - A_i)% )。這些分流點資料的順序是首先是第一次的分流點，再列出所有第二次分流的分流點的資料 (以由左至右的順序列出)，再列出所有第三分流的分流點的資料 (亦是以由左至右的順序列出)。

Output

輸出應有 2^N 行，每行應該有兩個正整數 P Q，以一個空格分開，它們代表由左至右每個出海口所可能含有的污染的比例，其中 P Q 實際是代表分數 P / Q，且 P / Q 是最簡分數。已知在所有情況下 1 <= P, Q <= 2³¹ - 1

Sample Input #1

3
80 50 40 30 10 50 60

Sample Output #1

測資資訊：

記憶體限制： 64 MB
不公開測資點#0 (10%): 1.0s , <1K
不公開測資點#1 (10%): 1.0s , <1K
不公開測資點#2 (10%): 1.0s , <1K
不公開測資點#3 (10%): 1.0s , <1K
不公開測資點#4 (10%): 1.0s , <10M
不公開測資點#5 (10%): 1.0s , <1M
不公開測資點#6 (10%): 1.0s , <1M
不公開測資點#7 (10%): 1.0s , <1M
不公開測資點#8 (10%): 1.0s , <1M
不公開測資點#9 (10%): 1.0s , <1M

Hint ：

#非官方測試數據

Tags:

出處:

MOI 2021 [管理者：

lamkinun@gma... (Kinda Lam)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」