FORMAT - HTML Formatting

Description

You have been given formatted text and asked to converted it HTML.
Each character may be formatted as bold, italic, underlined, or some combination.
In HTML, content between <b> and </b> tags is bold. Content between <i> and </i> tags is italic. Content between <u> and </u> tags is underlined.
What is the minimum number of properly nested HTML tags needed to produce a given format?
For example, say we wanted to format <i><b>LookAt</b>Me</i>!
  • <b><i>LookAt</b>Me</i>! has incorrectly nested tags.
  • <b><i>LookAt</i></b><i>Me</i>! has correctly nested tags, but is longer than necessary.
  • <i><b>LookAt</b>Me</i>! is the shortest and uses the fewest number of tags.

Input

There will be a sequence of 1 to 20,000 numerals. Each numeral denotes the formatting at that position.
  • 0 - no formatting
  • 1 - bold
  • 2 - italic
  • 3 - bold and italic
  • 4 - underlined
  • 5 - bold and underlined
  • 6 - italic and underlined
  • 7 - bold, italic, and underlined
(There is no need to actually specify the content, since that will not affect the answer.)
The example earlier would be given as 333333220.

Output

The minimum number of <b>, </b>, <i>, </i>, <u>, and </u> tags required.
Input Input Input Input
01
333333220
00110066
12364012375303657213412303
Output Output Output Output
2
4
6
54

Added by:BYU Admin
Date:2013-10-18
Time limit:1s-2.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2013-10-25 00:01:04 Mitch Schwartz
Moved to classical.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.