Robotics Event - 2
All submissions for this problem are available.
Again we have an event designed by our robotic group of our college. In this contest the participants are expected to collect balls from source buckets and dump it into the target bucket. There are K number of source buckets numbered from 1 to K and only one target bucket. The bucket ‘i’ contains infinite number of balls of colour ‘i’ only. All the balls used in the event are of the same diameter ‘d’.
The participating team needs to design a robot which has a cylindrical container of diameter ‘d’ such that ball just fits into the container. The container is of infinite length. The container operates in LIFO style. It is used to hold the ball temporarily before being dumped into the target bucket.
The robots are remote controlled and the team gives a sequence of command ‘S’ according to which the robot performs the action. The command is of two type
Pi – picks the ‘i’ coloured ball and stores it into the cylindrical container
Di – drops the top most ball from the container which is of colour ‘i’ into the target bucket.
Now due to some problem few of the commands from the sequence is lost. You are given an incomplete sequence where the missing command is represented by ‘?’, your task is to find out how many valid sequence can be generated from the given incomplete sequence.
A valid sequence means for every ‘Di’ command the robot drops the top most ball from the container which is of colour ‘i’.
Note: The cylindrical container is operated in ‘Last-In-First-Out’ more often we say it to be LIFO style.
The first line of input consist of two space separated integers N and K, where N is the number of the command in sequence ‘S’, followed by the sequence ‘S’ in the next line which is command separated by single space. Every ‘P’, ‘D’, is followed by the colour of the ball on which the operation is to be performed.
Output the total number of valid sequence that can be constructed. The output can be very large so print answer modulo 1000000007.
1 ≤ K ≤ 9
2 ≤ N ≤ 100
P1 P2 D2 ?
Explanation of first input
The robot first picks the ‘1’ coloured ball and puts it into the cylindrical container then puts the ‘2’ coloured ball into the container then dumps the ‘2’ coloured ball into the target bucket and then dumps the ‘1’ coloured ball into the target bucket. No other valid sequence is possible.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.