CDC12_F - Forbidden Machine

Finally Ronny could make it to the safe place, he left his family there and decided to go to this new planet and talk to their King. Ronny know that he can’t do this by himself, so he called every army of the Earth to have a backup in case that things turn out bad.

They made it to the new planet, and realize that it was like only rainbows and teddy bears, and just at the entrance there was a sign that said: ”Welcome to Rainbowland”. Ronny and his army went through this planet directly to their castle. At the entrance, a guard wearing a hat colored with rainbow colors, stopped Ronny. He said that Ronny could pass if and only if he could solve a puzzle: The Forbidden Machine Puzzle.

This puzzle consists on a machine that takes strings, and then says if the strings are correct. A string is considered correct if it follows the rules of the machine. This rules consists on a sequence of state transitions. Each transition tells the machine that if it was in a state X, it can go to a state Y with a character Z on the string. The machine starts reading from the first position of the string, and each transition move the string one position to the left, so the next position to read it’s the second one. It is important to add that the machine always start on an initial state and a string follows the rules of the machine if and only if this can made it to a final state of the machine, and the string has been read completely. Ronny has a hard time understanding this machine, so he would like you to simulate it, in order to have the correct answer for the guard.

Please note that a single state-character combination can lead to several different states.

Input

The first line contains an integer T, which specifies the number of test cases. Then, will follow the descriptions of T test cases.

Each test case will contain a line with 4 integers, N, M, F and Q. N is the number of states of the machine, M is the number of transitions, F is the number of final states of the machine, and Q it’s the initial state. Then F lines will follow with a single integer E on it, representing that the state E it’s a final state. Then M lines will follow, with 2 integers I and J and a character C; this represents that there exists a transition that goes from state I to state J reading the character C. Then will be a line with an integer S, that indicate the number of strings to process, and S lines will follow, each one with a string A that has to be evaluated by Ronny.

Output

For each input case you must "Scenario #i:" where i is the number of the test case that you are evaluating (Starting by 1). Then S lines, with the string and the answer of the machine for that string, if the string is correct, you should output "Accepted", and if it’s not, you should output "Rejected" (Quotes for clarity).

Sample

Input
2
4 8 1 0
0
0 1 a
1 0 a
1 2 b
2 1 b
0 3 b
3 0 b
3 2 a
2 3 a
3
ababbaa
abababab
aaaabbbb
6 8 2 0
2
5
0 0 a
0 1 a
1 1 b
1 2 c
1 3 c
3 4 d
4 4 d
4 5 d
5
aaabcccc
aabbbbcdc
abbcdddcc
acdddddd
abc

Output
Scenario #1:
ababbaa Rejected
abababab Accepted
aaaabbbb Accepted
Scenario #2:
aaabcccc Rejected
aabbbbcdc Rejected
abbcdddcc Rejected
acdddddd Accepted
abc Accepted

Constraints

  • 1 ≤ T ≤ 100
  • 1 ≤ N ≤ 100
  • 1 ≤ F, Q, I, J, E ≤ N
  • 1 ≤ S ≤ 100
  • 1 ≤ |A| ≤ 1000

Added by:Venezuelan Programming League
Date:2012-10-27
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for UCV-CEIDEC contest.

hide comments
2013-04-22 12:25:18 Jacob Plachta
Though the samples suggest that the states are numbered 0..N-1, it looks like they can rather be numbered as high as N (as the problem statement says).
2012-12-12 08:04:07 :D
There are two things here. Aman was asking if we can pass a few states using one character in the input string. The answer to that is NO.

The second is that one character can lead to multiple states and you must check all the resulting paths. If any valid path leads to an end state, string is accepted. In that sense you can say it represents an non-deterministic decision program.
2012-12-09 03:33:29 Rocker3011
i got quite confused by :D comment, does his comment means that the machine is a deterministic one? or just that you have a transition and then you move the index of the string
2012-12-08 20:38:02 :D
Re: Aman Gupta
abcd would be rejected. Exactly one transition for each letter, as for your regular state machine.

All character data in the input are in lowercase letters. I assert checked it.

Last edit: 2012-12-08 20:38:32
2012-11-28 19:50:15 Rocker3011
this problem has a very tricky test case, cant find it yet T_T
2012-11-28 11:10:57 Aman Gupta
While reading a character, can we make more than one transition? For example, is abcd Accepted for scenario 2 in the example?

Also, are strings always lowercase?

Last edit: 2012-11-28 11:26:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.