National Olympiad in Informatics, China, 2011
Day 1, Problem 3 - Ali's Typewriter
Ali likes to collect all kinds of strange gadgets. Most recently, he's gotten his hands on an old-fashioned typewriter. The typewriter contains 28 keys, 26 of which are the lowercase alphabet, and the other 2 are the uppercase letters 'B' and 'P'.
Through further examination, Ali learned that the typewriter worked like this:
- Hitting a lowercase letter, the typewriter will append this letter onto a special groove. There will be at least one such letter before hitting '
P'. - Hitting the '
B' key, the typewriter will remove the last letter added to the groove. - Hitting the '
P' key, the typewriter will take all the letters currently on the groove and print them onto the paper, switching lines afterwards. However, the letters on the groove will not disappear nor change. There will be at least one letter on the grove for this operation.
For example, if Ali hits the keys aPaPBbP, then the following will be printed onto the paper:
a aa ab
We number the strings printed onto the paper from 1 to n. The typewriter has a very interesting feature – there exists a hidden numerical keypad where, if one were to input two numbers (x, y) (for 1 ≤ x, y ≤ n), the typewriter will display the number of times the x-th string appears in the y-th string.
Ali is very excited after discovering this feature. We wants to write a program to perform the exact same feature. Can you help him?
Input Format
The first line contains a single string, describing all of the keys that Ali presses on the typewriter.
The second line contains a single integer m, representing the number of queries.
For the following m lines, each line will describe a query on the hidden numerical keypad. The i-th of these lines will contain two integers x and y, indicating that the i-th query is (x, y).
Output Format
Output m lines, where the i-th line contains a single integer – the answer to the i-th query.
Sample Input
aPaPBbP 3 1 2 1 3 2 3
Sample Output
2 1 0
Constraints
The attributes of all the test cases are outlined below.
| Test Case | Range of n | Range of m | Length of Strings | Keypresses (Line 1 of input) |
|---|---|---|---|---|
| 1 | 1 ≤ n ≤ 100 | 1 ≤ m ≤ 1000 | / | ≤ 100 |
| 2 | ||||
| 3 | 1 ≤ n ≤ 1000 | 1 ≤ m ≤ 104 | Individual lengths ≤ 1000 Total length ≤ 105 | ≤ 105 |
| 4 | ||||
| 5 | 1 ≤ n ≤ 104 | 1 ≤ m ≤ 105 | Total length ≤ 105 | |
| 6 | ||||
| 7 | ||||
| 8 | 1 ≤ n ≤ 105 | 1 ≤ m ≤ 105 | / | |
| 9 | ||||
| 10 |
All Submissions
Best Solutions
Point Value: 30 (partial)
Time Limit: 1.00s
Memory Limit: 256M
Added: Aug 10, 2014
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...