← 返回题目列表

AtCoder · arc212_d

D. 两间房

中文机器翻译题面 查看原题

分数: 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

如果有空房间是可以接受的。