SummerSky's blog

By SummerSky, 6 years ago, In English

215A - Bicycle Chain

Exhaustive enumeration.

215B - Olympic Medal

According to the definition, we have , which gives . Thus, we should find the maximum r1 and p1, and minimum p2.

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) ti < Ti: At first, we should note that if there are more than one buses which satisfy mj + ti > Ti, where mj 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 mj + ti > Ti and mk + ti > Ti, , the compensation fees will be xi(mj + mk), while if we move mk + ti - Ti students to the j-th bus, the fees are reduced to xi(mj + mk + ti - Ti). Therefore, there can be either one single bus with mj + ti > Ti or no bus at all. We can compute the maximum Y satisfying m > Y(Ti - ti), where Y means that if the number of buses is less than or equal to Y, then every bus should take Ti - ti 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)(Ti - ti))xi + y × costi, 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 × costi and the minimum value is (Y + 1)costi. Therefore, the global minimum value should be min(m × xi + costi, (m - (Y - 1)(Ti - ti))xi + Y × costi, (Y + 1)costi).

2) ti ≥ Ti: for this case, the total cost is always m × xi + y × costi, and thus the minimum value is m × xi + costi.

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 2d - 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 2d - 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 2d - 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 a1a2...ad, where ai = 0, 1. Note that a1 = 1 always holds, and thus we can always have a2a3...ad - 1 different feasible answers. Be careful that we should check whether a2a3...ad can serve as an extra answer or not. We can simply repeat a1a2...ad with d times and see if it is less than or equal to x. If yes, we in fact have a2a3...ad - 1 + 1 feasible answers. Similarly, we should decrease a2a3...ad - 1 or a2a3...ad - 1 + 1 when we compute for d'.

  • Vote: I like it
  • 0
  • Vote: I do not like it