3928：Catch the Thief

题目描述

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.

输入解释

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.

输出解释

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

输入样例

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

输出样例

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

提示

Case 1: Only one guest there. So the thief must be him

Case 2: The data shows the timetable as below:
in time 1, #1 enter the house;
in time 2, #1 exit the house;
in time 3, #2 enter the house;
in time 4, #2 exit the house;
The cop will only ask #2. If he answer YES/YES, the thief must be him; If he answer NO/NO, the thief must be #1.

Case 3: There's a solution which cop only ask 2 times: The cop will ask #3 first, 
If he answer YES/YES, the thief may be #3 or #4, then ask #4 to know who is the thief;
If he answer NO/NO, the thief may be #1 or #2. then ask #2 to know who is the thief;
he can't answer YES/NO or NO/YES.

来自杭电HDUOJ的附加信息

Recommend

xubiao

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2011 Multi-University Training Contest 9 - Host by BJTU

源链接： HDU-3928

最后修改于 2020-10-25T23:08:24+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
2000/1000MS(Java/Others)	122768/62768K(Java/Others)