1. Problems
  2. classical
  3. HTML Formatting
  1. Status
  2. Ranking

FORMAT - HTML Formatting

no tags 

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
Submit solution!
hide comments
Satyaki Upadhyay: 2014-07-07 11:21:27

@Avinash The tags need to be properly nested. So the order in which you insert opening or closing braces is important.
Avinash: 2014-01-13 14:57:46

@Satyaki I'm also getting 8.
Satyaki Upadhyay: 2014-01-09 13:58:38

@nitish answer for176751 should be 8 right?
b_iu_/b_b_/i_/u_/b
the underscores indicate character positions

samfisher: 2013-11-19 22:22:37

@nitish I am getting 16 for your test case , any idea what i am doing wrong
nitish rao: 2013-11-11 16:35:02

Check this one : 176751. Ans:14.
@anirudh: i was also getting 16. Thats why no AC yet. :(

Last edit: 2013-11-21 15:50:00
Andrey Maksimenko: 2013-11-05 11:22:21

Mauro Persano: thank you, but this didn't help. Posted to forum. Will be appreciate for any ideas.
Mauro Persano: 2013-11-04 21:36:02

Andrey Maksimenko: I read the input with scanf, but got WA until I trimmed invalid characters (not 0-7) at the end of the input string. That could be your problem.
Andrey Maksimenko: 2013-11-04 17:17:16

I'm getting answer 54 for "12364012375303657213412303", but still WA, any tricky test cases please?
:D: 2013-10-31 21:20:51

Note it must be properly nested.
aman jain: 2013-10-29 21:02:11

how is the answer for case "12364012375303657213412303" is 54. I think it should be 44.

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.