|
|
"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"!!! I got WA at #4 by using int type but got AC by using long long I don't understand... I think the max of date is 1e6(maybe n=1e4 and every ti=100, in this way the sum time is 1e6 and it's max) Am I wrong? Who can tell me plz Edited by author 15.03.2015 21:47 Give some tests, please... I keep getting WA for test #7, any tips? Sorry, my fault - I was handling input data incorrectly, hoping on certain nodes order. Got AC after fix :) Edited by author 27.09.2011 20:37 Edited by author 27.09.2011 20:38 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. please, give me any hint on this problem. Edited by author 29.03.2011 20:27 Try to think about how the answer for every node (and for the whole tree) depends on x? Use dichitomy (binary search), Luke! О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) 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. Maybe, someone can help with test? =) In test #6, a nobelman might have some vassals, whose numbers are greater than himself. Good luck. We do apologize for this error. The runs from the contest are rejudged. No :D Should be 100.00000000 Bad checker... I've got so much penalty time... I write in Java, I know that answer for test 1 is 50, and even when I add following lines to my code: if (Math.abs(l - 50) > 1e-4) { while (true); } out.printf("%.9f", l); I recieve WA. What can be wrong? Same strange thing. I AC'eed this problem several days ago from 2nd try. But there is something... strange. Great, it's not only me. Can admins make some statement about this problem? Can you at least show me what my program outputs at test #1 ? Is the 1st test equal to the sample? I'm not sure, first two numbers in test 1 are "6 3", but I was lazy to check it further. Most probably, 1st test is sample. test 1 is same as sample checker is wrong seems it compares answers as strings Edited by author 19.03.2011 16:40 Thanks a lot. For all who wants to solve this problem right now: output your answer with exactly 8 digits after decimal point. Edited by author 19.03.2011 16:36 |
|
|