| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 13364 | Mom, don't do that |
|
| 13708 | I want symmetry!!!! |
|
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
Mr.Moriya is a famous architect.
All the buildings he designs have one unique feature: they are symmetrical.
In fact, Mr.Moriya can't stand anything that is not symmetry, such as computers, clothes, photos, and anything he can see.
One day, when Mr.Moriya reads a book, he almost drives himself crazy because most strings in the books are not symmetry.
Can you help poor Mr.Moriya to partition the string into symmetry?
Given a string S, partition S such that every substring of the partition is a palindrome(symmetry), and output how many methods to partition S.
Example1: S = "aab" can be partitioned to ["aa", "b"], ["a", "a", "b"] these 2 conditions, so output is 2.
Example2: S = "c" can be partitioned to ["c"] 1 condition, so output is 1.
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 <= 40
Note that S only contains lowercase English alphabets.
Output
Output how many methods to partition S.
Remember to output '\n' at the end of each line.