分数: 600 点
问题陈述
有 N 人数 1,2,\ldots,N。对于 i\neq j,人与人之间的亲密程度 i 和 j is A_{i,j}.
对于每个 N 人,分配房间 X 或房间 Y。每个 N 人们搬到指定的房间。如果有空房间也是可以接受的。
人 i 位于 状态良好 如果满足以下条件:
(与人的亲密程度总和 i 与该人在同一房间的所有人 i) \geq (与人的亲密程度总和 i 与该人在不同房间的所有人 i).
输出一个房间分配,使得所有 N 人的状态很好。
可以证明这样的赋值总是存在的。
约束
- 2 \leq N \leq 50
- -50 \leq A_{i,j} \leq 50
- A_{i,j} = A_{j,i}
- A_{i,i}=0
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}
输出
输出一个满足条件的赋值。如果有多个解决方案,您可以输出其中任何一个。
用字符串表示赋值 S 长度 N。如果人 i 已分配给房间 X, i- 第一个字符 S 应该是 X;如果分配到房间 Y, i- 第一个字符 S 应该是 Y.
示例输入 1
4 0 4 -2 -1 4 0 -3 -5 -2 -3 0 2 -1 -5 2 0
示例输出 1
XXYY
假设人 1,2 被分配到房间 X 和人员 3,4 被分配到房间 Y.
对于人 1,与同一房间的人的亲密程度总和(人 2) 是 4,以及与不同房间中的人的亲密程度总和(人 3 和 4) 是 (-2)+(-1)=-3,所以他们的状态很好。
其他人的状态也都很好,所以这个作业满足条件。
输出 YYXX 也是正确的。
示例输入 2
3 0 0 0 0 0 0 0 0 0
示例输出 2
XXX
如果有空房间是可以接受的。