/ 
Time Limit: 2 sec / Memory Limit: 2048 MB
配点 : 1000 点
問題文
N 個の、長さ N の 01 文字列 S_1,\ldots,S_N が与えられます。S_i の j 文字目を S_{i,j} と表します。ここで、S_{i,j}=\ 1 を満たす整数組 (i,j) が少なくとも一つ存在することが制約より保証されています。
高橋君と青木君が以下のようなゲームを行います。
- 高橋君が 1 \leq i,j \leq N, S_{i,j}=\
1を満たす整数組 (i,j) を 1 つ選ぶ。 - 0 回以上 N 回以下、青木君が高橋君に質問を行う。各質問では青木君が 1\leq i',j' \leq N を満たす整数組 (i',j') を選び、「i=i' と j=j' のうち少なくとも一方が成り立つ」の真偽を高橋君から教えてもらう。
- 青木君が (i,j) を予想する。予想が当たっていれば青木君の勝ち、そうでなければ負けとなる。
青木君は高橋君が選ぶ (i,j) の候補、すなわち S_1,\ldots,S_N を知った状態でゲームを行います。また、上記2では以前の質問に対する返事を聞いたうえで (i', j') を選ぶことができます。
青木君が適切な戦略を取った場合、高橋君の (i,j) の選び方や運によらず必ずゲームに勝てるかどうかを判定してください。
1 つの入力につきテストケースは T 個あります。
制約
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 500
- 1 つの入力の中のテストケースすべてにわたる N^2 の総和は 500^2 以下である
- S_i は長さ N の 01 文字列
- S_{i,j}=\
1を満たす整数組 (i,j) が少なくとも一つ存在する
入力
入力は以下の形式で標準入力から与えられる。
T case_1 \vdots case_T
各テストケースは以下の形式で与えられる。
N S_1 \vdots S_N
出力
各テストケースに対し、青木君が必ずゲームに勝てるならば Yes と、そうでなければ No と出力せよ。
入力例 1
3 2 01 11 2 11 11 10 0101011110 1100100001 1101100000 0111101010 1000011001 1110101010 1110110100 1110000110 0000001011 1001111100
出力例 1
Yes No Yes
1 番目のテストケースに対するゲームの一例を以下に示します。
- 高橋君が S_{i,j}=\
1を満たす (i,j) として (2,2) を選ぶ。 - 青木君が 2 回質問を行う。1 回目の質問では (i',j')=(1,1) として、高橋君から「i=1 と j=1 のうち少なくとも一方が成り立つ」が偽であると教えてもらう。2 回目の質問では (i',j')=(2,2) として、高橋君から「i=2 と j=2 の少なくとも一方が成り立つ」が真であると教えてもらう。
- 青木君が (i,j)=(2,2) と予想する。この予想は当たっているため、青木君の勝ちである。
これはあくまでゲームの一例であり、青木君の戦略が適切とは限りません。しかし、青木君が適切な戦略を取った場合には必ず青木君がゲームに勝つため、1 番目のテストケースに対する出力は Yes になります。
Score : 1000 points
Problem Statement
You are given N strings S_1, \ldots, S_N, each of length N, consisting only of 0 and 1. Let S_{i,j} denote the j-th character of S_i. It is guaranteed by the constraints that there exists at least one integer pair (i, j) satisfying S_{i,j} = 1.
Takahashi and Aoki play the following game:
- Takahashi chooses one integer pair (i, j) satisfying 1 \leq i, j \leq N and S_{i,j} =
1. - Aoki asks Takahashi at least 0 and at most N questions. In each question, Aoki chooses an integer pair (i', j') satisfying 1 \leq i', j' \leq N, and Takahashi tells Aoki whether "At least one of i = i' or j = j' holds" is true or false.
- Aoki guesses (i, j). If his guess is correct, Aoki wins; otherwise, he loses.
Aoki knows the possible choices of (i, j) that Takahashi can choose, that is, he knows S_1, \ldots, S_N before playing the game. Also, in step 2, Aoki can choose (i', j') based on the answers to previous questions.
Determine whether Aoki can always win the game regardless of Takahashi's choice of (i, j) and randomness, if he uses an appropriate strategy.
There are T test cases in each input.
Constraints
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 500
- The sum of N^2 over all test cases in each input is at most 500^2.
- S_i is a string of length N consisting of
0and1. - There is at least one integer pair (i, j) satisfying S_{i,j} =
1.
Input
The input is given from Standard Input in the following format:
T case_1 \vdots case_T
Each test case is given in the following format:
N S_1 \vdots S_N
Output
For each test case, print Yes if Aoki can always win the game, and No otherwise.
Sample Input 1
3 2 01 11 2 11 11 10 0101011110 1100100001 1101100000 0111101010 1000011001 1110101010 1110110100 1110000110 0000001011 1001111100
Sample Output 1
Yes No Yes
In the first test case, an example of the game is as follows:
- Takahashi chooses (i, j) = (2, 2) satisfying S_{i,j}=\
1. - Aoki asks two questions. In the first question, he chooses (i', j') = (1, 1). Takahashi tells him that "At least one of i = 1 or j = 1 holds" is false. In the second question, he chooses (i', j') = (2, 2). Takahashi tells him that "At least one of i = 2 or j = 2 holds" is true.
- Aoki guesses (i, j) = (2, 2). Since his guess is correct, Aoki wins.
This is just an example of the game, and Aoki's strategy might not be optimal. However, if Aoki uses an appropriate strategy, he can always win the game, so the output for the first test case is Yes.