Informatica Online Judge

  결정 유한 상태 오토마타 [0625 / 0271]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 190   Total Tried : 164


The Champion of this Problem (C++) : gs17018 - ms / 194byte
My Best Submission (C++) : N/A

[]

Background

아래 그림과 같이 결정 유한 상태 오토마타가 주어졌다.



이 오토마타는 6개의 state들과 {0,1}의 알파벳으로 이루어져 있고 시작 state는 시작이 없는 화살표로 표시 되어 있는 A이다.

final state는 그림 1에서 빨간색으로 표시된 {A}이며 transition function 은 아래표와 같다.



이 오토마타는 {0,1}의 알파벳으로 이루어진 주어진 입력 문자열 x에 대하여 다음과 같이 동작한다. 시작 state에서 시작하여 입력 문자열 x의 왼쪽부터 순서대로 문자를 하나씩 사용 하면서 transition function에 따라 현재 state를 next state로 옮긴다. 이와 같이 입력 문자를 하나씩 사용하면서 state를 옮기는 작업을 반복하여 입력 문자열 x의 모든 문자를 사용하였을 때 현재 state가 final state 집합 {A}에 포함되어 있는지 검사하여 포함되어 있다면 yes 포함되어 있지 않다면 no를 반환한다.

예를 들어, 입력 문자열 x가 010010으로 주어졌을 때 주어진 유한 상태 오토마타는 순서대로 표 2와 같이 동작한다.



최종적으로 오토마타는 A에서 멈췄으며 A는 final state에 원소이므로 yes를 반환한다.

입력 문자열 x가 주어졌을 때 주어진 오토마타가 반환하는 결과가 무엇인지 출력하는 프로그램을 작성하시오.

Input

첫째 줄에 길이 1,000,000 이하의 0과 1로 이루어진 입력 문자열 x가 주어진다.

Output

첫째 줄에 주어진 오토마타에 입력 문자열 x를 입력하였을 때 반환되는 결과를 출력한다.

IO Example

입력
010010

출력
yes

입력2
010001

출력
no

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]