1031 . Jinyuetuan Puzzle
Description
JinYueTuan(按：勁樂團) is a famous online game which has been
in vogue for a long time. Large number of players put
themselves in it day after days…
JinYueTuan is a simple game with these rules:
Only seven keys on the keyboard will be used in games,
each key are assigned to one of the seven sound tracks.
During the game, a series of notes may fall in each
sound track irregularly. When notes fall down in one
sound track, player should press the assigned key at
once. If so, then got a “Cool”, or get “Miss” otherwise.
There are two types of “Note”: “single note” and
“strip note”. Just as the name implies, “single note”
means a single note, press right key at the right time
once, then you can get a “Cool”, otherwise “Miss”;
“strip note” needs you keeping press the corresponding
key from the start time to the end time of the note.
Press key at the begin time you may get a “Cool”, and
release at the end time to get another “Cool”, you will
“Miss” either early or late. If “Miss” at the begin
time, then “Miss” the other (the end time) immediately.
But you can get the first “Cool” if you pressed at the
begin time even though you may release too early or late to fail to get “Cool”
for the second one.
People lament about the fact that such an easy game is limited by the hardware
design, the so-called “keys confliction”. “keys confliction” means some key
combinations cannot be pressed. For example, when Track 1,4,5,6 fall a note at
the same time respectively, we should press the four keys at the same time, but
now, keys confliction may happen, and cause this to fail, then you will “Miss”
all these four notes. Keys confliction meets the relation of inclusion, in other
words, if keys set S would cause the confliction, so would keys set T when S is
included in T. Note that, if at a certain moment in time, some keys should be
pressed and some pressing keys should be released, then you can release and press
at the same time, and released keys won’t cause any keys confliction at all.
Because of the keys confliction, we have to give up some notes to save as more
other notes as possible. More details will be explained in the sample data.
Now you know the falling time and type (single or strip) of each note in each
sound track, and all keys-assembling that may cause confliction. Your task is
to calculate the maximum number of “Cool” that player can get.
Input Format
There are multiple test cases, the number of them T is given in the very first
line, followed by T cases.
For each test case:
First line contains an integer N, the length of the music (1≤N≤1000).
The next 7 lines will contain description of each sound track. The first number
in each line, C, denote the number of notes in that sound track. Following C
description of each note: A single number “A” denotes an single note at Time A(1≤A≤N);
A pair of integers separating by ‘-’,”A-B” denotes a strip note start at Time
A and end at Time B(1≤A<B≤N). In each sound track, no superposition exists, no
strip starts at another’s end time, no single notes puts in a strip(includes begin
and end point).
The next line contain a single integer K (0≤K<27
), denotes K descriptions of
Keys Confliction are following.
Each description is a single line containing a string of seven characters
S0S1S2…S6, if Sk1,Sk2,…,Sks were character ‘1’ and others were ‘0’, that means
key combination Sk1Sk2…Sks may cause Keys Confliction.
Output Format
For each test case, output one line containing integer P with case number,
the maximum number of “Cool” players can get.
Sample Input 1
3 6 3 1 3 4 2 1 2-5 2 3 6 0 0 0 0 1 1110000 6 3 1 3 5 2 1 2-5 2 5 6 0 0 0 0 1 1110000 6 1 1 1 1-3 1 1 0 0 0 0 1 1110000
Sample Output 1
Case #1: 7 Case #2: 8 Case #3: 3
Hints
Problem Source
Migrated from old NTUJ.
2009Shanghai
Subtasks
| No. | Testdata Range | Score |
|---|