THREECOL - Three-coloring of binary trees

A tree consists of a node and some (zero, one or two) subtrees connected to it. These subtrees are called children.

A specification of the tree is a sequence of digits. If the number of children in the tree is:

  • zero, then the specification is a sequence with only one element '0';
  • one, the specification begins with '1' followed by the specification of the child;
  • two, the specification begins with '2' followed by the specification of the first child, and then by the specification of the second child.

Each of the vertices in the tree must be painted either red or green or blue.
However, we need to obey the following rules:

  • the vertex and its child cannot have the same color,
  • if a vertex has two children, then they must have different colors.

How many vertices may be painted green?

Task

Write a program which:

  • reads the specification of the tree from the standard input,
  • computes the maximal and the minimal number of vertices that may be painted green,
  • writes the results in the standard output.

Input

The number of test cases t is in the first line of input, then t test cases follow in separate lines. Each test case consists of one word (no longer then 10000 characters), which is a specification of a tree.

Output

Your program should write for each test case exactly two integers separated by a single space, which respectively denote the maximal and the minimal number of vertices that may be painted green.

Example

Sample input:
1
1122002010

Sample output:
5 2

Added by:Piotr Ɓowiec
Date:2004-09-13
Time limit:7s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:6th Polish Olympiad in Informatics, stage 3

hide comments
2019-07-04 19:07:32
Easy One ;)
2017-12-18 16:45:32
easy one :)
2017-01-04 06:51:43
There's no empty line between test cases..
2016-09-30 08:58:40 ravi
nice and easy
2016-09-13 10:20:51
Solved a DP question almost after a month, AC in 1 go.... :)
2016-04-04 11:07:14
Its very easy DP for me .. AC in one go
DP on tree
2016-02-15 14:40:59 Sumit Vohra
DP on tree :)
2015-02-07 15:49:10 ANVER S R
the following are the output obtained while running the program in my laptop.
(snipped)

(Re)
Please see the Notes below:
3. For more discussion (hints, ideas, solutions) please visit our forum.

Last edit: 2015-02-07 15:58:07
2015-02-07 08:52:12 ANVER S R
check why i am getting wrong answer?
i used a stack to properly color the binary tree..
Checked it with many possible inputs
both brute force and my solution are giving the same results.
please give some example test cases where my solution fails.

Last edit: 2015-02-07 08:52:51
2009-03-17 16:13:14 mafo
Beware !
The test cases are of cause separated
by a newline-character and
NOT by an empty line.
Could the problem author please clearify this in the problem description.



Last edit: 2009-03-17 16:13:14
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.