Description

 Credit: KKOMDASTRO

Aria is an idol, but she's also a robot in disguise, so she don't know whether the audience is cheering for her or not. In order to do that, she need to use a Finite State Machine. Can you help her build one?

Finite State Machine

A finite state machine (FSM) is a simple model of computation that reads a sequence of inputs one at a time and moves between a fixed set of “states” based on what it reads. FSMs are used in linguistics, in regular expressions, and in many other areas to check whether a string follows a given pattern. You can think of it as a flowchart: you stand on one box (a state), read one symbol, and follow the arrow labeled with that symbol to the next box.

Components of the machine

• Initial state: The single state where the machine always begins, before any input is read.
• Accepting state: A state that signals “success.” If the machine finishes reading all of its input and is sitting on the accepting state, the input string is considered valid (matches the pattern). In this problem, there is exactly one accepting state.
• Intermediate states: All the remaining states that are neither the initial state nor the accepting state. They are “stepping stones”: the machine passes through them while reading input, but ending on one of them means the input was not accepted.
• Transitions: Each state has an alphanumeric ID and exactly 2 next states: one to move to when the input is 0, and one to move to when the input is 1.

Note: the initial state may also be the accepting state, and a state can be its own next state (a “loop”).

How the machine runs

1. Start at the initial state.
2. For each input symbol (0 or 1) in order, move to the next state corresponding to that symbol.
3. After the last input, check which state you are on:
   • If it is the accepting state, output 1.
   • Otherwise, output 0.

Visualization: https://www.automataaa.com/

Example input 1

Example input 2

Input

• First line: The number of states $n$
• Next $n$ line: Each line will contain $3$ parts, splitted by a whitespace:
  • 1st part: The state ID
  • 2nd part: Next state ID if input is 0
  • 3rd part: Next state ID if input is 1
• Next line: Contain 2 parts, splitted by a whitespace:
  • 1st part: The initial state ID
  • 2nd part: The accepting state ID
• Last line: The input string for the machine.

Output

• First line: The result of the machine
  • 1 if after all the input, the machine ends on a accepting state.
  • 0 if otherwise.
• Second line: The state after the final input.

Sample Input  Download

Sample Output  Download

Discuss