Description

Recently, Mr. ATH's hard disk is almost full so his computer crashes often. He decided to clean up his hard disk by
uninstalling some programs. Currently his computer is running under an operation system called SOD, which is an
operation system that has similar commands to DOS.

To remove a program, he needs to change his working directory to the directory of the program.
After typing "uninstall" in the directory, then the program will be automatically uninstalled.

However, unlike DOS, this operation system's command of changing directory is fairly limited.
The command "cd" has the following usage:

1. cd [directory_name]
   This command would allow user to swap his directory exactly one level down in the hierarchy.
   For example, if the current directory is "/tmp", the command "cd aaaa" would change the directory to "/tmp/aaaa"
   However, "cd aaaa/bbbb" does not work.
    
2. cd ..
   This command would allow user to move his directory one level up in the hierarchy.
   For example, if the current directory is "/tmp/aaaaa", the command "cd .." would change the directory to "/tmp"

Note that in the SOD operation system, the root directory is "/" and he started at root directory initially.

Now Mr. ATH has listed the directories of the programs that he wanted to delete IN ORDER,
because violation of the order would cause his computer to crash.

Since the function of executing a batch file is not even implemented in SOD operation system (what a bad OS),
Mr. ATH would have to type these commands by hand.
Besides, because Mr. ATH is lazy, he wanted to type as few lines of commands as possible.

You going to write a program that will generate minimum lines of commands that Mr. ATH could use to
delete all program he listed.

Input

The input may contain many cases (Mr. ATH need to clean his hard disk very often).
The first line of each case contain exactly one integer n (1<=n<=50) indicating the number of program that Mr. ATH wanted to delete.
Then the following n lines consist of strings without any spaces that describe the directories of the programs.
The names of adjacent directories are separated by a slash "/", and there is no slash succeeding the last directory name.
There will be no same strings appear in the same case. Besides, he will not uninstall his root directory "/".

The name for each directory has length at least 1 and at most 32 and consist of
only letters (a-z, A-Z), digits (0-9) and underscores "_".
Moreover, the SOD operation system can only allow the depth of hierarchy to at most 10 levels.
That is, "/1/2/3/4/5/6/7/8/9/10" is valid, while "/1/2/3/4/5/6/7/8/9/10/11" is not a valid directory.
You should also note that the names are case sensitive, that is, "/Aaaa" is a directory different from "/aaaa".

Output

For each case, output "Case x:" in the first line, where x is the number of case, starting from 1.
Then output the commands, each in a line, which can be "cd ..", "cd [directory_name]", or "uninstall".
Note that he always starts at root directory "/" in every case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Stepmania is a widely played game among otakus. Mr. SuBaRaSi has always wanted to become an otaku.
So he wanted to be a maestro in Stepmania. However, it would take a lot of time to practice.

For each song, some parts are difficult while other parts are easy. For example, the chorus at the middle part of the song
might be hard that he need to practice 25 times in order to get familiar. On the other hand, the intro part might be easy that he
only need to practice 5 times.

He found it is NOT efficient to always practice from the start all the way to the end of the song. As in the previous example,
he can start at the chorus part till the end for 20 times, and from intro to the end 5 times, which might be more efficient.
However, since is not good for him to interrupt at too many different parts, he can ONLY start or stop at the breakpoints settled.

Given a song that contain n parts that numbered from 1 to n, and the difficulty of every part (number of times 
needed to practice). Now he has inserted k breakpoints on k different points between two adjacent parts of the song.
Then for each practice, he can start at the beginning or any of the breakpoints, and stop at the end
or any of the breakpoints. The time needed for each practice is exactly the number of parts practiced.
For example, if he started at part 3 and ended at part 7, then the time needed is (7-3+1) = 5.

You are to write a program that help SuBaRaSi to arrange his practice so that the total sum of his
practice time is minimum. In this way, he will thank you because he can then achieve his otaku's dream
more quickly.
 

Input

The input may contain many cases. In each case, the first line contain 
two integers n, k (0<=k<n<=500) representing the number of parts in the song
and the number of breakpoints SuBaRaSi has set. In the following n lines, the i'th line
contain exactly one integer d_i (0<=d_i<=1000) denoting the difficulty of part i.
Then, in each of the following k lines contains an integer p_i (1<=p_i<n) representing the breakpoint
has been inserted between part p_i and part p_i+1. Note that these k integers are all distinct.

Output

For each case, print exactly one integer on a line representing the minimum time needed for SuBaRaSi to
become proficient in this song.

In the first case of the sample input, he can practice from beginning to the end once.
Then he practices part 2 to part 5 twice. Finally, he practices from part 2 to part 3 twice.
Therefore, the total time used is 18.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

One day, Mary told you that she really liked someone in your class.
However, Mary is so shy that she won't tell who it is.
But curiosity has driven you to try pumping more information from Mary.
For example, you might write to Mary the following:

• You questioned: 
• "Is he rich?"
• "Is he handsome?"
• "Is he humor?"
• "Is he an otaku?"
   
• Mary replied:
• "No."
• "No."
• "No."
• "Yes."

Then you suddenly realized who it is.

But, the above is an ideal scenario. Because Mary is shy, she is so reluctant that she will not answer too many questions.
Since you know the characteristics of everyone in the class, you are going to ask as few questions as possible from Mary.
No matter who is the person Mary likes, you have to ensure that you will know the answer after asking these questions.
Note that you will write all the questions you are going to ask to Mary before getting any replies from her.
You are going to write a program that determines what the minimum number of question needed is.
 

Input

The input may contain many cases. In each case, there are 2 numbers, n and m (1<=n<=10000, 0<=m<=12) that
describe the number of students in your class and the number of possible characteristics.
Then the following are n lines, where in each line there is a string denote the name of the student.
Then the following describe the characteristics of people.  For each characteristic, there is a string describing
the characteristic followed by an integer k_i (1<=k_i<=n) denoting the number of people who has this characteristic.
The next line contains exactly k_i strings separated by a space which represent the people who have this characteristic.

 All the strings in the input only contain "_", digits or upper-case letters and have length at most 24.

Output

For each case, you should output exactly one non-negative integer in a line representing the minimum number of
questions needed to get the answer regardless of who it is. If there is a possibility that you will never know
who it is then output -1.

In the sample input, you can choose to ask "Is he smart?", "Is he handsome?", and "Is he an unicorn?".
Then no matter who is it, you can recognize him from the answers responded by Mary.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a grid which represents a circuit, the current passing each grid point has its direction which can either 
be north, east, south, or west. According to the right hand rule, if the current formed a closed loop then
a magnetic field is generated inside the loop. A closed loop is defined as follow:

If you started at some point and keep follow the arrow and finally go back to the point, the path you traversed
is a closed loop. In addition, the loop must consists of at least four arrows. Therefore, a right followed by a left
does not account for a closed loop. Note that it is not guranteed that every point lies on a closed loop.

The direction of the magnetic field depends on whether the current loop is clockwise or counter-clockwise.
If the loop is clockwise, then magnitude of -1 is generated. If it is counter-clockwise, +1 is generated.
In addition, the magnitudes are cumalaitve. For example, if there is a clockwise loop A and a counter-clockwise
loop B. If B is inside A, then the magnetic field inside B has magnitude of 0.

In this problem, you have to find the greatest absolute value of the magnetic field magnitude in the circuit.

Input

The input may consist of many cases. In each case, the first line are two integers n, m (1<=n, m<=1000) indicating
the size of the grid circuit. The followings are n lines describing the circuit, and in each line there are m integers.
The integers can be 0, 1, 2, 3 representing north, east, south, west respectively.

Output

In each case, you should output exactly one integer in one line which indicates the greatest absolute value
of magnitude induced by the circuit.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Dr. SiRaBaSu always has trouble memorizing large numbers. To remember a number x, he will need | x | units of energy.
As a programmer and a notorious problemsetter who enjoy setting very hard problems, he often needs to memorize a
lot of number sequences. Fortunately, he invented a mnemonic to help himself memorize better.

When a sequence of numbers is given, instead of memorizing each number in the sequence, now he memorizes
several consecutive segments and their sum instead. For example, in the sequence <a_i> = <1, -3, 2, 4>, he would memorize
the following:
a₁ = 1
a₂ + a₃ = -1
a₂ + a₃ + a₄ = 3
a₃ = 2

Then, he is able to reconstruct the original sequence from the information he just memorized.
For example, he can retrieve a₄ by using the third equality to minus the second equality.
As mentioned, the total energy needed for him is | 1 | + | -1 | + | 3 | + | 2 |  = 7, which is less than
10 units of that in the straightforward way.
(Note that this strategy is not the best in this case. The minimum energy he needed can be 6 here. )

You are going to write a program that helps Dr. SiRaBaSu to determine the best strategy to memorize
the sequence using minimum energy, so he can set more hard problems.
 

Input

The input may contain no more than 50 cases. In each case, there is an integer n (1<=n<=500) denoting the length of the sequence.
The following n lines describe the sequence, where the i'th line contains an integer representing a_i (-10000 <= a_i <= 10000).

Output

For each case, please output exactly one integer in a line representing the minimum energy SiRaBaSu
can use to memorize the sequence.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Tom's girlfriend, Enigma, is a very mysterious person. When answering a question, she sometimes tell the truth
but sometimes don't. For example, "yes" might actually means "no", and "no" might actually means "yes". It could be very
dangerous to Tom if he didn't get the actual meaning.
Tonight, Tom want to ask his girlfriend whether she want to watch a movie or not.
Tom: "Enigma, would you like to watch a movie tonight?"
Enigma: "No."
Tom: "Was your last answer correct?"
Enigma: "Yes."
Tom: "Was your last answer correct?"
Enigma: "No."
....
Enigma always answered "no" to the first question which is actually meaningless.
Then Tom will ask n more "Was your last answer correct?" before he gets tired or... fired.
Fortunately, there is a way for Tom to get the true meaning of Enigma. He knows that although Enigma is
very strange, however, she still has a principle: At any moment, the number of times she lied will not be greater than
the number of times she said the truth plus k. Therefore, the number of strategy that Enigma can use is limited.
Note that the number of times she told a truth or a lie includes the answer of the first question.

Besides, Tom is very smart, Enigma is so afraid that he will understand her true meaning.
So Enigma turned to you, a nice man programmer, and begged for your help. She wanted to know how
many different strategies she can use to answer these n questions so that (1)Tom will be still confused whether
she want to see the movie or not. (2)Her principle is not violated.
 
The following example illustrate a strategy that would fail when n = 2 and k = 1

Since in Possibility 1, at the moment when the first "Was your last answer correct?" is answered, Enigma has told 2 lies 
while 0 truth is told. Therefore, Tom knows that Possibility 2 is the only possibility that Enigma really
don't want go to the movie. So, the strategy "yes, no" does not work for Engima.
However, as you can verify, "no, yes" works well in this case.

Input

The input consists of many cases. In each case, two integers n, k (1<=n, k<=1000) are given
in a line, separated by a space. The number n indicates how many "Was your last answer correct?" will Tom ask
after he ask "Enigma, would you like to watch a movie tonight?". The number k is the maximum number of lies could be
more than truths told by Enigma at any moment.

Output

For each case, output x % 100000007, where x is the number of strategies that Enigma
can use that (1)confuse Tom, (2)does not violate her principle.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Davidku and Otasu are brothers who love ACG(Anime, Comic and Game) very much.  Due to their professional skills and
knowledge on ACG, everybody called them  "Super OTAKU brothers".

One day, an new video game, "Tales of KoKuHaKu in the end of century" is published.   The game is a typical love simulation
game that you have to interactive with each girls in the games and make decisions in the conversation.
For the relationships between you and each girls, there are numerical values representing how good it is and how the girl likes
you, called L-value.    Some events would arise depending on your conversation decisions and therefore it matter the L-values of
girls and the ending of story.   So if you like some girls, you may try raising the L-values with them.

 To live up to their reputation, the name of  "Super OTAKU brothers", this time they  also want to write the playing guide
of  the game to other video game players on internet.  
Now they want to make a section in the guide talking about "What events must arise to maximize the L-values of the girls?".

After disassembling the game and tracing the code, they know the rules about the changing of L-values.
For every event E, there is a corresponding set S(E) consisting of elements indicating how it affects the L-values of girls.
Every element is a pair of value (N, V) repsenting the name of girl and the variation of L-value.
For example, let S(E) = {(Raou, 5), (Kenshirou, -2)}. Then if you arise the event E, Raou's L-value would increase by 5 and Kenshirou's L-value would decrease by 2. 
In addition, when you arise two events E and F, for this two events, if the number of girls who participates in exactly
one of the two events is a prime number more than 2(excluded), these girls would be resentful and their L-values would decrease 
by the square of the prime number (what a geek design).   
For example, suppose there are two events E and F, and S(E) = {(Raou, 10), (Kenshirou, -10), (Toki, -5)},   S(F) = {(Kenshirou, 20), (Yuria, 5)}.   
Then if you arise both the events, The variation of L-values is the following result.

Kenshirou: -10 + 20 = +10
Raou: +10 - 3 * 3 = +1
Toki: -5 - 3 * 3 = -14
Yuria: 5 - 3 * 3 = -4 

Now they want someone to help them. You are to write a program that they can import the event data and indicate
which girls they want to maximize the L-value. Then the program would find out what events should arise to maximize the sum of L-values of the indicated girls .

Input

Output

For each case,  output a single line containing the maximum L-value they can achieve.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

After many years of discipline and persistent practices, SuBaRaSi has almost become an otaku that
play Stepmania really well. However, to play even better, he needs to analyze the songs.

Many of rhythms have specifics patterns that SuBaRaSi can perform much easier because he is familiar with those patterns.
Note that he played Stepmania using his computer keyboard with both hands because it looks more like an otaku.
Since SuBaRaSi has learned the "technique of alternating left-right hands" from the "old-stubborn child", Zhou Buotong,
now he can play the songs using two hands independently without interfering other hand.

Patterns are described by strings consist of 0, 1, and 2. A zero means no taps, a one means a single tap on any 
of the arrows, and a two means two taps simultaneously on any of two distinct arrows. For each pattern, either of his
hand could recognize it independently and apply it for playing more easily. Depending on the cost of the patterns, you
are going to help SuBaRaSi to develop an analysis such that he can use as small cost as possible to play the
song without any single miss or any extra taps.

Note that, the pattern with a single "0", "1" or "2" and their costs will be given in the input so that it is guaranteed that he can 
perfectly play the song. The following is an example:

P₁ = "0", cost 0
P₂ = "1", cost 1
P₃ = "2", cost 2
P₄ = "121212", cost 2
P₅ = "1012", cost 1

After the analysis:


Therefore, the cost for right hand is  2 + 1 + 0 + 2 = 5, and the cost for left hand is 1 + 0 + 1 + 1 + 0 = 3.
He needs totally 8 cost to play this song in this analysis.
 

Input

The input may consist of many cases. For each case, there are two integers p, l (3<=p<=20, 1<=l<=200) denoting
the number of patterns SuBaRaSi could recognize and the length of the song. In the each of following p lines, there
are a string P_i and an integer c_i representing the patterns and cost of the patterns. Each P_i is consisted of digits 0, 1 or 2
and has length at most 10. The values of c_i are all non-negative and less than 1000.

The following four lines describe the left, down, up, right arrows of the song. Each line is a string with length l and consisted
of 0 and 1. A 0 means the arrow does not appear, a 1 means the arrow is there.
 

Output

For each case, output exactly one number denoting the minimum cost SuBaRaSi can perform the song under any analysis.

Sample Input  Download

Sample Output  Download

Tags

Discuss