Блог пользователя SummerSky

Автор SummerSky, 7 лет назад, По-английски

80A - Panoramix's Prediction

As the range is quite small, we can directly calculate the next prime integer and check whether it is the same as the given one or not.

80B - Depression

At first, we should note that if the hour is larger than 12, we can decrease it by 12, since they will form exactly the same angles. For instance, 13:26 is equivalent to 01:26. Then, we calculate the angles of minute and hour, respectively. As 60 minutes are equal to 360 degrees, its angle is just M × 6. For the hour, 1 hour or 60 minutes is equal to 360/12 degrees. Thus, the angle of hour is H × 30 + M × 0.5.

80C - Heroes

A little complicated but not quite difficult problem. Enumerate all the feasible divisions of the heroes, and find out first the minimum difference and then the maximum liking.

80D - Falling Anvils

This is a pure mathematical problem. We use f(p) and f(q) to denote the probability density function (pdf) of p and q, respectively. For normal distribution with range [x, y], the pdf is written as . Then, we derive the formula as follows:

We first deal with the first term.

.

Then, it comes to the second term. This should be solved based on the following two cases:

1) 4b < a:

2) 4b ≥ a:

Therefore, for a ≠ 0 and b ≠ 0, we can calculate the answer according to the above formula. For the other cases, the rules are:

1) a = b = 0, the answer should be 1;

2) a = 0, b ≠ 0, the answer is ;

3) a ≠ 0, b = 0, the answer is 1.

80E - Beavermuncher-0xFF

I think this is a nice problem to practice dp based on trees. We use dp[n] to denote the maximum number of beavers that it can eat, under the condition that all the child nodes of node n have been processed and it returns back to node n. Furthermore, we use left[n] to denote the number of beavers that are still at node n, under the above same condition. We need another array beaver[n] to denote the number of beavers at each node at the beginning.

Now, we start implementing DFS from the given root node s. To calculate dp[n], we assume that all the child nodes of n, i.e., dp[m], have been computed (they are obtained when the DFS function returns). Then, we sort all the dp[m] in a decreasing order. If we use M to denote the number of its child nodes that have at least one beaver, then . Moreover, note that we might still have beavers left at both node n and its child nodes, and we should take them into consideration as well. Thus, we should further update .

Be careful that when we call DFS to deal with any child node, we should decrease beaver[m] by 1, since we need at least one beaver to return back!! Also remember to update left[m] with correct values. The DFS function trivially returns when it is a leaf node or it has no beavers at all. Finally, we can output dp[s] as the required answer.

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится