215A - Bicycle Chain

Exhaustive enumeration.

215B - Olympic Medal

According to the definition, we have , which gives . Thus, we should find the maximum r₁ and p₁, and minimum p₂.

215C - Crosses

At first, note that the rextangulars can only have size (2a + 1) × (2b + 1) and (2c + 1) × (2d + 1), where a, b, c, d starts from zero. Then, there are two cases that we should take into consideration.

1) One rectangular is completely contained by the other one. Without loss of generality, we assume that a ≥ c and b ≥ d. For a rectangular with size a × b, there are (n - (2a + 1) + 1) × (m - (2b + 1) + 1) different positions to put it within the board. The inner rectangular can have (a + 1) × (b + 1) different sizes. As we can swap these two rectangulars, there are in fact 2 × (a + 1) × (b + 1) feasible answers. Furthermore, when a = c, b = d, the “swapping operation” gives the same answer, and thus we have 2 × (a + 1) × (b + 1) - 1 different answers. Taking the different positions into consideration, the final answer is (n - (2a + 1) + 1) × (m - (2b + 1) + 1) × (2 × (a + 1) × (b + 1) - 1).

2) Two rectangulars form a “crossing”. We enumerate a, b, c and calculate d based on the target area size s. The remaining work is similar to case 1).

215D - Hot Days

The main idea is greedy algorithm, and as each interval is independent, we only focus on one single interval.

1) t_i < T_i: At first, we should note that if there are more than one buses which satisfy m_j + t_i > T_i, where m_j denotes the number of students in the j-th bus, we can always achieve a better result by moving all the “extra” students to one single bus. For instance, if there are two buses with m_j + t_i > T_i and m_k + t_i > T_i, , the compensation fees will be x_i(m_j + m_k), while if we move m_k + t_i - T_i students to the j-th bus, the fees are reduced to x_i(m_j + m_k + t_i - T_i). Therefore, there can be either one single bus with m_j + t_i > T_i or no bus at all. We can compute the maximum Y satisfying m > Y(T_i - t_i), where Y means that if the number of buses is less than or equal to Y, then every bus should take T_i - t_i students except for one single bus taking all the remaining students. For any y ≤ Y, the total cost can be written as (m - (y - 1)(T_i - t_i))x_i + y × cost_i, which is a monotonic function. Thus, the minimum value is obtained either at y = 1 or y = Y. For any y ≥ Y + 1, the total cost is y × cost_i and the minimum value is (Y + 1)cost_i. Therefore, the global minimum value should be min(m × x_i + cost_i, (m - (Y - 1)(T_i - t_i))x_i + Y × cost_i, (Y + 1)cost_i).

2) t_i ≥ T_i: for this case, the total cost is always m × x_i + y × cost_i, and thus the minimum value is m × x_i + cost_i.

215E - Periodical Numbers

The main framework is “prefix” idea, i.e., we define a function f(x) to denote the number of feasible integers less than or equal to x. Thus, the required answer is f(r) - f(l - 1).

Suppose that we write x in a binary form, and it has length len. For instance, len = 3 when x = 7. Then, all the feasible answers must have a binary length ilen ≤ len, which gives the following two cases.

1) ilen < len: any periodic integer y satisfies the requirements, and thus contributes a feasible answer, since y < x always holds. For a given ilen, we find all its divisors. For instance, for a divisor d, it means the binary sequence should have a cycle of length d. As the head digit is always 1, we have 2^d - 1 feasible integers. However, for any divisor d' > d of ilen, if d' is a multiple of d, i.e., ilen%d' = 0, d'%d = 0, all the 2^d - 1 sequences will be counted again. The reason is that as long as the current sequence has a cycle of length d, then it also has a cylce of length d'. Therefore, we should decrease 2^d - 1 when we calculate for d'.

2) ilen = len: different from case 1), only those periodic integers less than or equal to x should be considered. We still consider each divisor d of ilen, and find out the leftmost d binary digits, written as a_1a2...a_d, where a_i = 0, 1. Note that a₁ = 1 always holds, and thus we can always have a_2a3...a_d - 1 different feasible answers. Be careful that we should check whether a_2a3...a_d can serve as an extra answer or not. We can simply repeat a_1a2...a_d with d times and see if it is less than or equal to x. If yes, we in fact have a_2a3...a_d - 1 + 1 feasible answers. Similarly, we should decrease a_2a3...a_d - 1 or a_2a3...a_d - 1 + 1 when we compute for d'.