多米诺难题
   
　　
　　在一个多米诺骨牌集合里，每个骨牌以两位1到6的数字标记。有些多米诺骨牌集合中的所有骨牌可以按首尾数字相同排成一行，但有些不能，例如集合中包含5块骨牌： (1, 5), (1, 6), (5, 5)和两张(2, 4)，不能按首尾数字相同排成一行。 然而，如果我们加了一张（2，5）骨牌，则我们就可以将排成如下的一行。

　　　　

　　但是，更感兴趣的是这样的一行的骨牌上的数字总和是否最小。在上面的例子中，加入的牌为（2，5），它上面的数字和为7；而如果我们加入两块（1，2）骨牌，则它们上的数字总和却只有6，而且仍然可以使所有骨牌按首尾数字相同排成如下的一行。

　　　　

　　你的任务是写一个程序，对于给定的一个多米诺骨牌集合，找出一个具有最小的数字和的额外骨牌集合（也可能是空集），使得加上这个集合的骨牌后所得骨牌能按上面规则排成一行。

　　输入

　　输入文件的第一行包含一个整数N N (2≤N≤100) ，代表多米诺集合中牌的总数。接下来N行分别是每张骨牌上的两个1-6的数字。骨牌上的两个数字顺序是任意的。

　　输出

　　在输出文件的第一行为额外骨牌集合中所有骨牌上面最小的数字和（额外集合为空时则为0）。第二行输出额外骨牌集合中的骨牌数（空集时为0）。然后按输入文件的格式输出每一块这些骨牌。如果存在多种解，则只要输出其中任意一种即可。

　　Sample input #1

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

　　Output for the sample input #1

　　0
　　0

　　Sample input #2

　　5
　　1 5
　　6 1
　　5 5
　　2 4
　　2 4

　　Output for the sample input #2

　　6
　　2
　　1 2
　　1 2

　　

    

 
网站导航 | 关于曙光 | 联系我们 | 请提意见
Copyright © FuJian Sunshine Educational Info. Co.,Ltd.
福建曙光教育资讯有限公司 版权所有