| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 1000 | The A+B Problem |
|
| 1001 | Simple Relation |
|
| 1002 | String Reverse |
|
| 1003 | OTAKU |
|
| 1004 | Toy |
|
| 1005 | How Many Trees? |
|
Description
Given two integer sequences A, B. Add them in some specific order O.
O is described via a representation of the location relationship from input.
For example, O = 100101 means A[i] + B[i+2] write to result C[i+1];
O = 111 means A[i] + B[i] write to C[i].
Note that if index is out of the length of B or C, imagine that B,C are circular.
Input
N
L
A
B
O
N is the number of total test data.
L is the number of element in A,B.
A,B sequences have the same number of elements, each element e:
0< e < 1000000
1<= num. of A,B <= 1000
O is the description of the order
3 <= length of O < 1000
there are exactly three ones in O, and the leading one is always happen!
Output
Output your result by the same format of input sequence.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
"Otaku" is a Japanese term used to refer to people with obsessive interests, particularly anime,
manga, and video games. Otaku usually has much features such that you can recognize someone as
a otaku with those features.
Dr.Davidsu now want to do a research about Otaku. First he wants a program to help him.
The program should read the list of characteristics of many people and to determine how possible
they are Otaku.
Although Dr.Davidsu is a great programmer, but since he realizes so much knowledge about Otaku
with his research, now he also becomes a OTAKU!! So he only plays games day and night and could
not write program anymore. Please help the great Ota.. uh.. great Dr. Davidsu!!
Input
There are two positive integer N, M in the first line of input following N lines of the features of Otaku.
Each line has a distinct string describes the feature. And then there are M people's describing below.
In each people's data, first line there is a positive integer K which is the number of the people's characteristics
and K lines below are the K features of the people.
Limits
1 <= N <= 10000
1 <= M <= 1000
1 <= K <= 1000
the string describes the feature of otaku or people is consecutive characters only contains uppercase
letter or underline char "_" and no more than 16 characters.
Output
For each people, if more than half of its characteristics is a feature of OTAKU, then output 'Y'.
Otherwise output 'N' on each line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Jasio is a little boy - he is only three years old and enjoys playing with toy cars very much. Jasio has n different cars. They are kept on a shelf so high, that Jasio cannot reach it by himself. As there is little space in his room, at no moment may there be more than k toy cars on the floor.
Jasio plays with one of the cars on the floor. Jasio's mother remains in the room with her son all the time. When Jasio wants to play with another car that is on the floor, he reaches it by himself. But when the toy is on the shelf, his mummy has to hand it to him. When she gives Jasio one car, she can at the same time pick any car from the floor and put it back on the shelf (so that there remains sufficient space on the floor).
The mother knows her child very well and therefore can predict perfectly which cars Jasio will want to play with. Having this knowledge, she wants to minimize the number of times she has to hand Jasio a toy from the shelf. Keeping that in mind, she has to put the toys off on the shelf extremely thoughtfully.
Write a programme that:
- reads from the standard input the sequence of toy cars in order in which Jasio will want to play with them,
- calculates the minimal number of times the mother has to pick cars from the shelf,
- writes the result to the standard output.
Input
In the first line of the standard input there are three integers: n, k, p (1 <= k <= n <= 100,000, 1 <= p <= 500,000), separated by single spaces. These denote respectively: the total number of cars, the number of cars that can remain on the floor at once and the length of the sequence of cars which Jasio will want to play with. Each of the following p lines contains one integer. These integers are the numbers of cars Jasio will want to play with (the cars are numbered from 1 to n ).
Output
In the first line of the standard output one integer should be written - the minimal number of times his mother has to pick a car from the shelf.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A binary search tree is a binary tree with root k such that any node v in the left subtree of k has label (v) <label (k) and any node w in the right subtree of k has label (w) > label (k).
When using binary search trees, one can easily look for a node with a given label x: After we compare x to the label of the root, either we found the node we seek or we know which subtree it is in. For most binary search trees the average time to find one of its n nodes in this way is O(log n).
Given a number n, can you tell how many different binary search trees may be constructed with a set of numbers of size n such that each element of the set will be associated to the label of exactly one node in a binary search tree?
Input
The input will contain a number 1 <= i <= 1000 per line representing the number of elements of the set.
Output
You have to print a line in the output for each entry with the answer mod 32767 to the previous question.