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

Discussion of Problem 1822. Hugo II's War

any hint?
Posted by Pavel 29 Mar 2011 20:18
as I understand, this is a problem on dynamic programming. I see only one solution - go through the whole tree and compute the values for each node from the leaves up to the root of the tree.
And on each level the full search should be done. For example, if we want to compute value for a node with p childs with already computed x_1, x_2, .., x_p values, then try 1/p, 2/p, ... p/p as a possible solution for this node.

please, give me any hint on this problem.

Edited by author 29.03.2011 20:27
Re: any hint?
Try to think about how the answer for every node (and for the whole tree) depends on x?
A hint
Posted by Artem Khizha [DNU] 1 Apr 2011 02:13
Use dichitomy (binary search), Luke!
Re: A hint
Posted by bsu.mmf.team 26 Apr 2011 17:49
ОK, what answer to this test:
106 10
1 1
1 5
1 5
1 5
1 5
2 1
2 1 (70 times: 2 1)
2 100
2 100 (30 times: 2 100)
Re: A hint
Posted by bsu.mmf.team 12 Sep 2011 14:25
The answer is 80.0000000, but I think, it's incorrect a little bit. Because it is said in the condition "the king needs as many soldiers as possible". If x = 80, then the king will have only 4 soldiers, while if x = 70, the king will have 74 soldiers. So I thought binary search doesn't work there, i.e. the numebr of soldiers is more important, than the total time of preparing to the war (the only thing is necessary is the total time should be not greater than max allowed time). But it's not true. The most important is to maximize the percent in the answer.