B - Binary Alchemy

Contest Duration: 2024-09-07(Sat) 12:00 - 2024-09-07(Sat) 13:40 (local time) (100 minutes) Back to Home

B - Binary Alchemy Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $200$ 点

問題文

$N$ 種類の元素があり、元素には $1, 2, \ldots, N$ の番号が付けられています。

元素どうしは合成させることができ、元素 $i$ と元素 $j$ を合成すると $i \geq j$ のとき元素 $A_{i, j}$ に、 $i < j$ のとき元素 $A_{j, i}$ に変化します。

元素 $1$ に対して元素 $1, 2, \ldots, N$ をこの順に合成したとき、最終的に得られる元素を求めてください。

制約

$1 \leq N \leq 100$
$1 \leq A_{i, j} \leq N$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

 $N$ 
 $A_{1, 1}$ 
 $A_{2, 1}$   $A_{2, 2}$ 
 $\vdots$ 
 $A_{N, 1}$   $A_{N, 2}$   $\ldots$   $A_{N, N}$

出力

最終的に得られる元素の番号を出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

元素 $1$ と元素 $1$ を合成すると、元素 $3$ が得られます。
元素 $3$ と元素 $2$ を合成すると、元素 $1$ が得られます。
元素 $1$ と元素 $3$ を合成すると、元素 $3$ が得られます。
元素 $3$ と元素 $4$ を合成すると、元素 $2$ が得られます。

したがって、出力するべき値は $2$ です。

入力例 2Copy

Copy

出力例 2Copy

Copy

入力例 3Copy

Copy

6
2
1 5
1 6 3
2 6 1 4
2 1 1 1 6
5 6 1 2 2 5

出力例 3Copy

Copy

Score : $200$ points

Problem Statement

There are $N$ types of elements numbered $1, 2, \ldots, N$ .

Elements can be combined with each other. When elements $i$ and $j$ are combined, they transform into element $A_{i, j}$ if $i \geq j$ , and into element $A_{j, i}$ if $i < j$ .

Starting with element $1$ , combine it with elements $1, 2, \ldots, N$ in this order. Find the final element obtained.

Constraints

$1 \leq N \leq 100$
$1 \leq A_{i, j} \leq N$
All input values are integers.

Input

The input is given from Standard Input in the following format:

 $N$ 
 $A_{1, 1}$ 
 $A_{2, 1}$   $A_{2, 2}$ 
 $\vdots$ 
 $A_{N, 1}$   $A_{N, 2}$   $\ldots$   $A_{N, N}$

Output

Print the number representing the final element obtained.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

Combining element $1$ with element $1$ results in element $3$ .
Combining element $3$ with element $2$ results in element $1$ .
Combining element $1$ with element $3$ results in element $3$ .
Combining element $3$ with element $4$ results in element $2$ .

Therefore, the value to be printed is $2$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

6
2
1 5
1 6 3
2 6 1 4
2 1 1 1 6
5 6 1 2 2 5

Sample Output 3Copy

Copy