【NOIP模拟赛】世界人民大团结

2014年11月2日1,5840

现在,世界的主题是和平与发展。社会学博士老Z认为,要实现和平发展,首先要实现世界人民大团结。

世界上有n个人。他们胸前和背后各有一个自然数,大于或等于0且小于或等于6。两个身上带有某个相同数字的人把身上相同的数字合在一起,就实现了团结。比如,(0,1)(1,2)就实现了团结,而(0,1)(2,1)和(0,0)(1,2)都不是团结。把数合在一起的方法,是胸靠胸、背靠背、背靠胸或胸靠背。

请判断世界人民能否实现大团结。如果能,请输出大团结的实现方案。

【输入】

第一行,一个正整数n,表示世界上有n个人。

剩余n行,每行是用空格隔开的两个自然数,大于等于0且小于等于6,第(1+i)行表示第i个人胸前和背后的数字。

【输出】

如大团结可以实现,输出n行,每行两个空格隔开的数字。第一个是人的编号(同输入);第二个是“-”或“+”,“+”表示这个人胸在前,背在后,“-”反之。人们按照你输出的顺序和面对的方向从前到后站立。具体参见样例。

如大团结不能实现,输出一行“No Solution”(不含引号)。

【样例输入】

5

1 2

2 4

2 4

6 4

2 1

【样例输出】

2

5 +

1 +

3 +

4

【数据规模】

对于100%的数据,1<=n<=100

题解

现在,世界的主题是和平与发展。社会学博士老Z认为,要实现和平发展,首先要实现世界人民大团结。

世界上有n个人。他们胸前和背后各有一个自然数,大于或等于0且小于或等于6。两个身上带有某个相同数字的人把身上相同的数字合在一起,就实现了团结。比如,(0,1)(1,2)就实现了团结,而(0,1)(2,1)和(0,0)(1,2)都不是团结。把数合在一起的方法,是胸靠胸、背靠背、背靠胸或胸靠背。

请判断世界人民能否实现大团结。如果能,请输出大团结的实现方案。

【输入】

第一行,一个正整数n,表示世界上有n个人。

剩余n行,每行是用空格隔开的两个自然数,大于等于0且小于等于6,第(1+i)行表示第i个人胸前和背后的数字。

【输出】

如大团结可以实现,输出n行,每行两个空格隔开的数字。第一个是人的编号(同输入);第二个是“-”或“+”,“+”表示这个人胸在前,背在后,“-”反之。人们按照你输出的顺序和面对的方向从前到后站立。具体参见样例。

如大团结不能实现,输出一行“No Solution”(不含引号)。

【样例输入】

5

1 2

2 4

2 4

6 4

2 1

【样例输出】

2

5 +

1 +

3 +

4

【数据规模】

对于100%的数据,1<=n<=100

现在,世界的主题是和平与发展。社会学博士老Z认为,要实现和平发展,首先要实现世界人民大团结。

世界上有n个人。他们胸前和背后各有一个自然数,大于或等于0且小于或等于6。两个身上带有某个相同数字的人把身上相同的数字合在一起,就实现了团结。比如,(0,1)(1,2)就实现了团结,而(0,1)(2,1)和(0,0)(1,2)都不是团结。把数合在一起的方法,是胸靠胸、背靠背、背靠胸或胸靠背。

请判断世界人民能否实现大团结。如果能,请输出大团结的实现方案。

【输入】

第一行,一个正整数n,表示世界上有n个人。

剩余n行,每行是用空格隔开的两个自然数,大于等于0且小于等于6,第(1+i)行表示第i个人胸前和背后的数字。

【输出】

如大团结可以实现,输出n行,每行两个空格隔开的数字。第一个是人的编号(同输入);第二个是“-”或“+”,“+”表示这个人胸在前,背在后,“-”反之。人们按照你输出的顺序和面对的方向从前到后站立。具体参见样例。

如大团结不能实现,输出一行“No Solution”(不含引号)。

【样例输入】

5

1 2

2 4

2 4

6 4

2 1

【样例输出】

2

5 +

1 +

3 +

4

【数据规模】

对于100%的数据,1<=n<=100

以自然数0至6为顶点,以每个人为边,建图。求出图上的欧拉回路或欧拉路即可。

欧拉回路存在的充要条件(在连通图中) 每个点的度为偶数(无向图) 每个点的入度出度相等(有向图) 欧拉路存在的必要条件: 有且仅有两个点的度为奇数(无向图) 总的入度和等于总的出度和,有且仅有两个点的入度、出度差为1,其他点相等(有向图)