ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1018. Binary Apple Tree

The description of this problem is not full... (+)
Posted by SPb SU #3 - 1 14 Jun 2002 21:07
1) There are some branches which have 0 apples. Every such branch
does NOT contain any non-zero branch - this test is impossible:
5 2
1 2 1
1 3 0
3 4 0
3 5 1,
because branch 3 (with 0 apples) contains branch 5 (with 1 apple).

2) If there are some branches with 0 apples, we should IGNORE them
and left from other branches (q - number of zero branches) ones. See
also 1).
For example,
7 5
1 2 1
1 3 0
3 4 0
3 5 0.
2 6 0
2 7 1
There are 4 zero branches. Ignore them - you'll get 2 branches.
1 2 1
2 7 1
From these branches you should left 5(q) - 4(number of zero
branches) = 1 branch. Remove 2 7 1 and you'll get answer: 1.

3) All tests are correct now, but for this problem sometimes I had
Wrong Answer, but it should be Runtime Error.
I solved it with DP and get AC (-)
Posted by Andrey Popyk (popyk@ief.tup.km.ua) 14 Jun 2002 22:05
Re: The description of this problem is not full... (+)
Posted by Maigo Akisame 11 Jun 2004 04:55
Why is the answer to 2) 1? Why mustn't I remove the zero-apple branches?
Re: The description of this problem is not full... (+)
Posted by tests 19 Sep 2004 08:57
I THINK THE ANSWER TO TEST 1 IS "1",AND THE SECOND IS "2"