| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13364 | Mom, don't do that |
|
| 13709 | I want symmetry quickly!!!! |
|
Description
"Mom, don't do that."
You have some secret folders which store a lot of videos about algorithm.
However, you do not want your mom know that you are interested in CS (she wants you to become a doctor).
Thus, you use a special trick to rearrange the original directory and sub-directory so it's difficult to directly access the folder.
Also, you make some fake directories, trying to make your mom more confused.
Although you think it's safe enough, your mom wrote a super program to check whether the decoded directory is valid or not.
Orz.
In order to figure out how your mom does that, you are going to design a similar program.
Given testcases T, each with two strings, O (origin directory) and D (decoded directory), please print "valid" if you can rearrange D into a sub-directory of O; if it's not possible, print "not valid".
Next time, remember to lock your room before leaving home.
hint. You can use string.h to make the problem easier.
Input
The first line of the input is an intger T, denoting the number of testcases. 1<= T <= 100
Next 2*T lines contain information of T pairs of O and D.
O is a directory, composed of a sequence of folders separated by a "/", e.g. "/home/hii/it/is/a/folder".
D is a decoded directory, which may be a sub-directory of O or an invalid directory:
example 1: "/hii/home/it", which is valid because you rearrange it into "/home/hii/it".
example 2: "/hii/it/home/nooo", which is invalid because "nooo" is not a part of folders of O.
1 <= length of O or D <= 5000
1 <= number of folders in O <= 50
Note that O and D must start from a "/", and there is no "/" in the end and each folder may appear more than once.
Output
For each testcases, if D may be valid, print "valid".
Otherwise, print "not valid".
Note that you have to print "\n" after each answer.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Although you have helped Mr.Moriya to partition the string, he doesn't think it is enough.
He wants everything to become symmetry faster and faster!
You should help Mr.Moriya partition the string to symmetry by minimal cut.
Otherwise, he will use the boom to destroy the world.
Given a string S, partition S such that every substring of the partition is a palindrome (symmetry) and outputs the minimal cuts needed for a palindrome (symmetry) partitioning of S.
Example1: S = "aab" can be partitioned to ["aa", "b"], ["a", "a", "b"] these 2 conditions, ["aa", "b"] condition can be produced with a minimal cut: 1 in all conditions(["a", "a", "b"] needs 2 cuts).
Example2: S = "c" can be partitioned to ["c"] 1 condition, so ["c"] condition can be produced with a minimal cut: 0 in all conditions.
Input
The first line of the input is an integer T, denoting the number of testcases. 1<= T <= 10
Next T lines indicate T strings S to partition
1 <= length of S <= 1000
Note that S only contains lowercase English alphabets.
Output
Output how many methods to partition S.
Output the minimal cut to partition S.
Remember to output '\n' at the end of each line.