← 返回题目列表

AtCoder · cf_2015_relay_i

I. 排比赛

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

問題文

最近,某小镇的年轻人中流行了一款名为“排位赛”的高级游戏。 这是一项团体比赛,选手们携带水枪,穿着雨衣,在赛场上跑来跑去,看自己用水击中对手多少次。

详细规则如下所述。第一 N 参与者(不一定数量相等) 2 分成两队。所有玩家同时从各自队伍的指挥部出发,绕着准备好的场地移动,瞄准用水枪攻击敌方队伍成员。游戏过程中,被敌方队员用水枪射中的人会暂时离开游戏,立即返回己方总部,重新加入游戏。比赛结束时,每位参赛者自报自己被敌人射击的次数以及自己射击敌人的次数,从而决定比赛的胜负。

现在,您一直在保存以前排比赛的记录,但您忘记记录每场比赛的团队划分,因此您只知道每个参与者射击或被射击的次数。这个记录首先有意义吗?首先,您决定查看是否有一种团队安排可以实现每个参与者的记录表现。


入力

排比赛 1 游戏记录由以下格式的标准输入给出。

N
k1 d1
:
kN dN

N (2 \leq N \leq 200) 代表参与游戏的人数。ki 和 di (1 \leq i \leq N, 0 \leq ki, di \leq 200) 分别是 代表第 i 号参与者射击敌人的次数以及被敌人射击的次数。

出力

如果团队划分与每个人的既定表现不矛盾, valid ,否则 在 invalid 和 1 行输出。在输出末尾插入换行符。 第


入力例1

3
7 2
1 3
1 4

出力例1

valid

1 队参赛者 1 、 2, 3 队参赛者 2 ,不存在矛盾。 (参加者 1 是参与者 2 的 3 回、参加者 3 的 4 圆形镜头,参与者 2 和 3 是参与者 1 的 1 你可以把它想象成每次拍摄。 )

入力例2

3
2 5
3 2
4 2

出力例2

invalid

无论你如何划分团队,都会出现不一致的情况。

入力例3

3
4 1
2 1
1 1

出力例3

invalid

每个人被射击的次数总和与他们被射击的次数总和不匹配。

入力例4

4
0 0
0 0
0 0
0 0

出力例4

valid

无论怎么分队,都不会有矛盾。