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.
The example earlier would be given as 333333220.
- 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
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 |