编程介的小学生 2017-12-09 13:31 采纳率: 20.5%
浏览 640
已采纳

Catch the Thief

Problem Description
A thief stole a big diamond in a party. The diamond was in the door of the house. So everyone can tell if there is a diamond when he enter and exit the house.

The cop think that the thief must be one of the guests. So they have got the timetable of the entrance time and exit time of everyone. They are arranging how to ask them to know who is the thief. When ask somebody, the cop could know if the diamond was still being there when they entering and exiting.

Of course, thief will tell lie. To simplify the problem, the thief will always tell you that the diamond was there. To simplify the problem, we assume that the thief stole the diamond when he exit.

The cop want to ask as few people as possible. Please help them to find the minimum number of guests they have to ask.

Input
The first line contains a single positive integer T( T <= 100 ), indicates the number of test cases.
For each test case: First line contains an integer N(1<=N<=25), indicates the number of Guests
The Timetable of the party - 2N numbers, 1-N each one twice, the first appearance means he enter. the second appearance means he exit.

Output
For each test case: output the case number as shown and the minimum number of guests they have to ask.

Sample Input
4
1
1 1
2
1 1 2 2
4
1 1 2 2 3 3 4 4
5
1 4 4 2 5 5 3 3 2 1

Sample Output
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 2

  • 写回答

1条回答 默认 最新

  • threenewbee 2018-04-05 15:51
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥20 Python安装cvxpy库出问题
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥15 python天天向上类似问题,但没有清零
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题