問題一覧 > 通常問題

No.753 最強王者決定戦

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 41
作問者 : horiesinitihoriesiniti / テスター : はむこはむこ
0 ProblemId : 2156 / 出題時の順位表
問題文最終更新日: 2018-11-08 22:22:32

問題文

16人の格闘家が1対1のトーナメント形式で戦う。

格闘家には1~16までの番号が割り当てられている。

格闘家には相性があり、どの格闘家同士が対戦した時、どちらが勝つかは表で与えられる。

トーナメントは完全2分木である。

各人の勝率を図るためにシミュレーションをすることとなった。
全ての一回戦のありえる組み合わせにおいて全組み合わせで決勝戦終わりまで試した時、各格闘家が優勝する回数を格闘家1~16まで一行ずつ出力せよ。

組み合わせは一回戦での並びが違えば同じ対戦カードでも違うものと判断する。
つまり1回戦の組み合わせは全部で16!通り検討される。

入力

$a_{(1,1)}$ $\dots$ $a_{(1,16)}$
$\dots$
$a_{(j,1)}$ $\dots$ $a_{(j,16)}$
$\dots$
$a_{(16,1)}$ $\dots$ $a_{(16,16)}$

格闘家番号iと格闘家番号jが戦ったときどちらが勝つか見るには,表のj行目のi列目が1ならjが勝ち-1ならiが勝つ。 表の左下半分は入力をわかりやすくするためのダミーデータとして0で埋めてある。 つまり表はj < iの部分しか意味がない。 ansiは1回戦の全ての並びを試した時の格闘家番号iの優勝回数を答えよ。

出力

$ans_1$
$\dots$
$ans_i$
$\dots$
$ans_{16}$
最後に改行してください。

サンプル

サンプル1
入力
0 1 -1 -1 -1 1 -1 -1 1 1 -1 1 1 1 1 1
0 0 1 1 -1 1 1 -1 1 1 -1 -1 -1 1 1 1
0 0 0 1 -1 -1 -1 -1 -1 -1 -1 1 1 1 1 -1
0 0 0 0 -1 1 -1 1 -1 1 1 1 -1 1 -1 -1
0 0 0 0 0 1 -1 1 -1 -1 1 -1 -1 1 -1 -1
0 0 0 0 0 0 1 -1 1 -1 1 1 1 1 -1 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 -1 1
0 0 0 0 0 0 0 0 1 -1 -1 1 1 -1 1 -1
0 0 0 0 0 0 0 0 0 1 1 -1 -1 1 1 -1
0 0 0 0 0 0 0 0 0 0 1 -1 1 1 -1 1
0 0 0 0 0 0 0 0 0 0 0 1 1 -1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 -1 1 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 -1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
出力
1613069320192
2902313238528
119390961664
507047542784
1339820638208
1069828669440
7688706785280
1315405791232
367798026240
590398128128
1159765950464
311637147648
146366988288
7884701696
1659518025728
123837972480

一回戦の全組み合わせを試した時格闘家番号1は1613069320192回優勝する。 全員の優勝回数の合計は16!通りである。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。