"King Hugo II wants to state the number x in his recruitment order. The king needs as many soldiers as possible for his military campaign. However, if the recruitment takes more than t days, the enemy may learn about the imminent intrusion and strike first. Help Hugo II find the maximal possible value of x."
We must find "maximal possible value of x" with "if the recruitment takes more than t days, the enemy may learn about the imminent intrusion and strike first" without "The king needs as many soldiers as possible for his military campaign"!!!
Hi, 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.
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.