[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

#### Source

UCF2011

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.

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.

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.

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

Time Limit: | 1000MS (C/C++,Others×2) |

Memory Limit: | 128MB (C/C++,Others×2) |

Special Judge: | No |

AC/Submit: | 1 / 1 |

Tags: |