MOZSATSK - Sharmeen and the strange keyboard

no tags 

Sharmeen’s grandfather had a strange long keyboard. The keyboard is so long that standing on a key of the keyboard sharmeen can only reach it’s adjacent at most two keys. You can think the keyboard as a string and every character in the string a key of the keyboard. So if she is now in position i of the string she can be able to reach only the positions i-1,i-2,i+1,i+2 if there exist such position of the string. The string contains only digits from ‘0’ to ‘9’ and any of these digits can appear more than once in this string. Though in real world there is no existence of such keyboard, you can think it is imaginary and just for solving problem with fun.

Sharmeen has a limitation that she forget quickly and continuously. If now she know digit x , in the next minute she know only digit x , x-1 , x+1. If x = 0 then she know 0 , 9 , 1 in the next minute and if x = 9 , then she know 9, 8, 0 in the next minute. You can assume that she never press any key if she doesn’t know the digit of that key. She always know the first character of the string.

After pressing a key she can press the next key exactly one minute later and pressing any key takes no time.

You have to print ‘yes’ if she will be able to press the last key of the keyboard and minimum minutes required to press it. Otherwise print ‘no’ without quotes.

Input

A string S consists of only digits from ‘0’ to ‘9’ of length n( 1 <= n <= 10^5 ).

Output

Output your answer as mentioned above.

Constrain:

1 <= n <= 10^5

See the sample input output for better understanding.

Example

Input:
5495

Output:
yes
2

Explanation:

At the beginning sharmeen presses S[0], it takes no time.
In the next minute Sharmeen can press S[1].
In the second minute Sharmeen press S[3].
Thus able to press the last key in 2 minutes.


hide comments
nadstratosfer: 2020-02-22 12:02:22

The problem asks whether it's possible to traverse the string of digits, being allowed to move at most 2 positions back or forth and only move between "neighboring" digits as described. Such traversal in this case is probably best implemented with Breadth-First Search (BFS).

Nice problem, Tutorial would perhaps be a better place for it.

negiji: 2020-02-18 14:48:18

can some one give algorithm for this?

mujahid_3732: 2019-12-06 20:58:28

very Good problem


Added by:Mozahid
Date:2019-09-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All