M - Does My Favored Team Have a Chance?
問題文
バスケットボールの ITF.リーグに $N$ チームが参加しており、各チームにはそれぞれ $1,2,3,\ldots,N$ という番号がつけられています。
各試合では $2$ チームが対戦し、引き分けでない場合勝った $1$ チームのみが $2$ ポイントを得ます。
引き分けの場合、対戦した $2$ チームはそれぞれ $1$ ポイントを得ます。
すべての試合が終わった後、得たポイントの合計が最大であるすべてのチームが優勝となります。
優勝となるチームは複数存在する場合があります。
また、優勝となるチームが $1$ チームのみである場合、そのチームは単独優勝となります。
チーム $i\ (1\leq i\leq N)$ の現時点のポイントの合計 $P_i$ がそれぞれ与えられます。
また、チーム $i\ (1\leq i\leq N)$ とチーム $j\ (1\leq j\leq N)$ が今後対戦する試合数 $G_{i,j}$ がそれぞれ与えられます。
$G_{i,i}=0\ (1\leq i\leq N)$ と $G_{i,j}=G_{j,i}\ (1\leq i\leq N,\ 1\leq j\leq N)$ が保証されます。
$i=1,2,3,\ldots,N$ の順に、チーム $i$ が単独優勝する場合があるかどうかと、優勝する場合があるかどうかを判定してください。
制約
すべてのテストケースについて、以下の制約を満たす。
- 入力はすべて整数
- $2\leq N\leq 300$
- $0\leq P_i\leq 10^{16}\ (1\leq i\leq N)$
- $0\leq G_{i,j}\leq 10^{13}\ (1\leq i\leq N,\ 1\leq j\leq N)$
- $\sum_{i=1}^N P_i$ は偶数
- $G_{i,i}=0\ (1\leq i\leq N)$
- $G_{i,j}=G_{j,i}\ (1\leq i\leq N,\ 1\leq j\leq N)$
部分点
入力
入力は以下の形式で標準入力から与えられる。
$N$
$P_1$ $P_2$ $\ldots$ $P_N$
$G_{1,1}$ $G_{1,2}$ $\ldots$ $G_{1,N}$
$G_{2,1}$ $G_{2,2}$ $\ldots$ $G_{2,N}$
$\ \ \ \vdots\ \ \ $ $\ \ \ \vdots\ \ $ $\ \ddots$ $\ \ \ \vdots\ \ \ $
$G_{N,1}$ $G_{N,2}$ $\ldots$ $G_{N,N}$
出力
$N$ 行出力せよ。
$i$ 行目 $(1\leq i\leq N)$ に、以下の形式で答えを出力せよ。
- チーム $i$ が単独優勝する場合があるならば
Yes - チーム $i$ が単独優勝する場合はないが、優勝する場合があるならば
Fat - チーム $i$ が優勝する場合がないならば
No
3
8 4 0
0 1 1
1 0 1
1 1 0
Yes
Fat
No
それぞれのチームの現時点のポイントは、チーム $1$ が $8$ ポイント、チーム $2$ が $4$ ポイント、チーム $3$ が $0$ ポイントとなっています。
今後の試合として、チーム $1$ と $2$ が対戦する試合、チーム $1$ と $3$ が対戦する試合、チーム $2$ と $3$ が対戦する試合が $1$ 試合ずつあります。
今後の $3$ 試合の結果によって、チーム $1$ は単独優勝できる場合があります。
チーム $2$ は今後の $3$ 試合の結果にかかわらず単独優勝はできませんが、優勝できる場合はあります。
一方、今後の $3$ 試合の結果にかかわらず、チーム $3$ は優勝できません。
この入力は、部分点 1. の制約を満たします。
5
10 10 9 8 3
0 1 1 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
Yes
Yes
Yes
Yes
No
チーム $5$ は今後のすべての試合に勝って $11$ ポイントを得た場合でさえ、優勝することはできません。
この入力は、部分点 1. の制約を満たします。
10
14000000000000 35000000000000 12000000000000 29000000000000 14000000000000 0 26000000000000 47000000000000 10000000000000 47000000000000
0 4000000000000 2000000000000 4000000000000 0 3000000000000 0 0 2000000000000 2000000000000
4000000000000 0 0 0 4000000000000 4000000000000 1000000000000 4000000000000 0 0
2000000000000 0 0 1000000000000 2000000000000 2000000000000 3000000000000 4000000000000 4000000000000 1000000000000
4000000000000 0 1000000000000 0 3000000000000 4000000000000 3000000000000 3000000000000 4000000000000 4000000000000
0 4000000000000 2000000000000 3000000000000 0 3000000000000 0 4000000000000 2000000000000 0
3000000000000 4000000000000 2000000000000 4000000000000 3000000000000 0 1000000000000 0 4000000000000 4000000000000
0 1000000000000 3000000000000 3000000000000 0 1000000000000 0 1000000000000 1000000000000 0
0 4000000000000 4000000000000 3000000000000 4000000000000 0 1000000000000 0 4000000000000 3000000000000
2000000000000 0 4000000000000 4000000000000 2000000000000 4000000000000 1000000000000 4000000000000 0 2000000000000
2000000000000 0 1000000000000 4000000000000 0 4000000000000 0 3000000000000 2000000000000 0
No
Yes
Fat
Yes
Fat
Fat
No
Yes
Yes
Yes
入力が 32bit 整数型の範囲に収まらない場合に注意してください。
この入力は、部分点 1. の制約を満たします。