Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
RSI
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 439Accepted: 195

Description

You have the goal of becoming the world’s fastest two-fingered typist. In this problem, your goal is to optimize the movement of your fingers when typing numeric values in order to ensure that you finish typing a number in the shortest amount of time possible. Your numeric keyboard has the following layout:

For convenience, we refer to the cells above according to their row and column; hence, the “5” key is at position (2, 2), and the “0” key takes up both positions (4, 1) and (4, 2). At time 0, your left pointer finger is on the “4” key and your right pointer finger is on the “5” key. During each time interval, each finger may press the key underneath it, move vertically one position, or move horizontally one position. Although both fingers may move simultaneously within a single time interval,

  • at most one key may be pressed during any given time interval,
  • the left pointer finger’s column must always be less than the right pointer finger’s column at the end of each time interval, and
  • both fingers must always be above one of the 10 keys in the diagram at the end of each time interval (e.g., neither finger cannot hover over position (4, 3)).
  • The “0” key may be pressed by a finger at either positions (4, 1) or (4, 2).

Examples

  • Typing “56” takes three time units. At time 1, both left and right fingers have moved one position to the right and are on keys “5” and “6” respectively. Then, each key is pressed sequentially.
  • Typing “71” takes five time units. During the first two time units, the left finger moves up to the “7” and presses the key. However, the right finger is not allowed to be in the same column as the left finger, and hence the left finger takes two time units to get to the “1” key and one time unit to press it.

Input

The input test file will contain multiple test cases. Each test case consists of a single line containing a string of between 1 and 100 digits. The end-of-file is marked by a line containing the word “eof” and should not be processed.

Output

For each input case, output the minimum number of time units required to type the given digits.

Sample Input

56
71
902
eof

Sample Output

3
5
6

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator