Consider the following case:

• You have 3 ten-yen coins and 14 one-yen coins.
• You are about to make purchases of 22 yen and then 13 yen.

There are two ways to make the 22 yen purchase. Which one will work better? Also, think about why the other method might not work.

• Use 2 ten-yen coins and 2 one-yen coins.
• Use 1 ten-yen coin and 12 one-yen coins.

Apply the thinking from Hint 1 to the following problem:

• You only have 1-yen and 10-yen coins.
• You will make purchases at \(N\) stores in sequence for \(X_1, X_2, ..., X_N\) yen.

Apply the thinking from Hint 2 when you have 1, 5, 10, 50, 100, and 500-yen coins.

Consider how to change the state from 00000 to 00010.

Consider how to change the state from 00000 to 01010. Which of the following two methods is easier?

• First change to 01000 and then aim for 01010
• First change to 00010 and then aim for 01010

Using the considerations from Hint 2, think about how to change the state from 0000000000 to 0100100100.

What about when 1s are consecutive? Consider how to change the state from 0000000000 to 0110001100.

Apply the considerations so far to a general case.

Try solving Example 1 by hand. It’s easier to solve if you consider Conditions 1 and 2 independently.

When only Condition 1 needs to be satisfied, think about how many repaints are necessary. As a hint, this problem can be reduced to a shortest path problem.

Poles that are \(H+1\) or more distance apart do not affect each other, so they can be considered separately. For example, in Sample 2, you can consider the following two groups separately:

• Group of pole 1 and pole 3
• Group of pole 2 and pole 4

Consider the example in the following diagram. What is the probability that all poles fall for the first time during the 64th earthquake (the pole in red in the diagram)?

Think about a method to quickly calculate the probability that all poles in a group fall for the first time at each time t.

Consider the following case:

• There are 3 problems in the contest.
• Contestant 1 solved problem 1.
• Contestant 2 solved problem 3.
• Contestant 3 solved problems 1 and 2.

Assume problem 1 is worth 1 point. When plotting problem 2’s points on the x-axis and problem 3’s points on the y-axis, consider how the relationship between points and rankings (such as contestant 3 ≥ 1 ≥ 2) appears.

In the case from Hint 1, you only need to consider the following two scoring schemes. Why is that?

• Problem 1 is 1 point, problem 2 is 1 point, problem 3 is 1 point
• Problem 1 is 1 point, problem 2 is 1 point, problem 3 is 2 points

Focus on the “intersection points” in the diagram you drew in Hint 1.

In fact, for any case with “3 problems,” you only need to consider the following two scoring schemes. Why is that?

• Problem 1 is 1 point, problem 2 is 1 point, problem 3 is 1 point
• Problem 1 is 1 point, problem 2 is 1 point, problem 3 is 2 points

Apply the considerations from Hint 3 to a case with 5 problems.

Consider a method to solve this problem using a dynamic programming approach with a space complexity of \(O(L^3)\).

In the dynamic programming approach from Hint 1, we calculated for \(O(L^3)\) states, but in reality, you only need to calculate for \(O(L \log^2 L)\) states. Which states can be eliminated?