Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2013
Frustrated Queue
fq.c, fq.cpp, Fq.java
The toilet in Freddy's garden is broken, so his only chance are public toilets nearby. One day,
there is a long queue of people in front of the toilets. Freddy is in a big need and so he desperately
wants the queue to be served as quick as possible.
To use the toilets, you need to pay 5 crowns. Half of the people in the queue have a 5-crown
coin and the other half only have a 10-crown coin. Initially, the toilet operator has no coins,
thus, the people in the queue have to reorganize so that whenever someone wants to pay with
a 10-crown coin, the operator has at least one 5-crown coin available from previous customers.
The issue is that some of the people in the queue are unwilling to give up their spot. Determine
in how many ways can the people willing to change their position rearrange themselves in the
queue so that the operator always has change available. The positions of those unwilling cannot
change (they cannot be moved to a later but also to an earlier spot in the rearranged queue).
Furthermore, among those willing to change the position, the relative order of those with the
same coin must be preserved.
Input Specification
The input contains several test cases. Each test case consists of one line containing a non-empty
string of parentheses and dots of length n ≤ 1 000. A dot indicates a person willing to change
their position in the queue, an opening parenthesis indicates a person unwilling to change the
position who has a 5-crown coin, and a closing parenthesis indicates a person unwilling to change
the position who has a 10-crown coin.
You may assume that n is even and that the string contains at most n/2 opening parentheses
and at most n/2 closing ones.
Output Specification
For each test case, compute the number of ways the queue can be rearranged so that the
conditions described in the statement of the problem are satisfied. Since this number may be
too large, you are only required to print a single line containing one integer equal to the last 6
digits (in the decimal representation) of the number.
Sample Input
Output for Sample Input
....
2
.(..
1
)...
0
.....)......................
68484
