本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1196. F. Camp Out


Description

Duke basketball is coming to Central Florida. It’s the biggest ticket available on campus this
year. UCF has immense school pride and wants to show other schools that whatever they do,
UCF can do it better. Duke has a long standing tradition of students camping out for important
basketball tickets. Students get in groups of 10 and man a tent for up to 168 hours straight before
the tickets are released for sale at midnight. At all times, at least two people must be at the tent
in order to secure the group’s place in line.
UCF has decided to utilize the same policy for selling tickets to its Duke game, except that it will
require three people to be present at each tent at all times for the whole week (168 hours). Also,
no individual may man a tent for more than 80 hours during the week, since that would take
away too much time from academic pursuits. You have gotten your 9 friends together to form
your group of 10 and have collected their schedules. You plan on manning the tent in four hour
shifts (12am-4am, 4am-8am, 8am-12pm, 12pm-4pm, 4pm-8pm, and 8pm-12am). Your goal will
be to figure out whether or not your group will be able to man the tent. Note that if a student in
the group is busy for part of a shift, they are not allowed to man the tent AT ALL for that
particular shift.
The Problem:
Given ten students’ schedules, determine if they can successfully man the tent with at least three
individuals for the 168 hours before the tickets for the Duke game go on sale.

Input

The first input line contains a single positive integer, n (1 < n ≤ 20), indicating the number of
groups of students to check. Each of the n input sets follows. Each set contains 10 lines of input,
one line per student in the group. Each line of input will contain a list of times that particular
student is busy. The format for each of these input lines is as follows:
The first positive integer, I (I < 20), on each line represents the number of intervals the student is
busy. (Thus, each student will be busy at least once during the week! There are no complete
slackers.) Each of the intervals follow and each piece of data on the line is separated by a single
space. Each interval is described with three integers, d, s and e, where d represents the day in the
week, s represents the start time, and e represents the end time of the interval. The days are
numbered 1 through 7, inclusive, and the start and end times are in military time in hours, in
between 0 and 24, inclusive. All intervals are guaranteed to be contained within a single day, no
intervals will end with 0 and no intervals will begin with 24. For example, the interval 13 to 17
on day 2 represents a four hour interval starting at 1pm and ending at 5pm on the second day of
the 168-hour week. All intervals will be at least one hour in duration.

Output

For each test case, first output “Case #i:” where i is the test case number, starting with 1.
Then, output the string “YES” or “NO”, depending on whether or not the group in question can
properly man the tent. Leave a blank line after the output for each test case. Follow the format
illustrated in Sample Output.

Samples

Input Copy
2
7 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24 7 0 24
6 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24
5 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24
4 1 0 24 2 0 24 3 0 24 4 0 24
4 1 0 24 2 0 24 3 0 24 4 0 23
1 1 0 24
2 1 10 12 2 3 7
7 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24 7 0 24
7 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24 7 0 24
7 1 0 24 2 0 24 3 0 24 4 0 24 5 0 24 6 0 24 7 0 24
7 1 0 1 2 0 1 3 0 1 4 0 1 5 0 1 6 0 1 7 0 1
7 1 1 2 2 1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 2
1 2 1 2
1 3 1 2
1 4 1 2
1 5 1 2
1 6 1 2
1 7 1 2
1 2 2 3
1 2 3 4
Output
Case #1: NO

Case #2: YES

Source

UCF2011
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 1 / 1
Tags:
Contests involved

1023. UCF 2011
My history solutions

You didn't submit any solution!
Submit your solution

Login Register