ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1018. Двоичная яблоня

The description of this problem is not full... (+)
Послано SPb SU #3 - 1 14 июн 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 (-)
Послано Andrey Popyk (popyk@ief.tup.km.ua) 14 июн 2002 22:05
Re: The description of this problem is not full... (+)
Послано Maigo Akisame 11 июн 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... (+)
Послано tests 19 сен 2004 08:57
I THINK THE ANSWER TO TEST 1 IS "1",AND THE SECOND IS "2"