A. Presents

This problem can be solved by starting from the 0-th day and implement the following operations.

For the i-th day (initially i=0), we check the next K days, i.e., from (i+1)-th to (i+K)-th day. If no holidays are included, we increase the number of presents by one and move to the (i+K)-th day; otherwise we add the number of holidays to the current number of presents and move to the last holiday. Note that if i+K>N, it is sufficient to only count the number of holidays from the i-th day to the N-th day, and add it to the number of presents.

B. Cutting Jigsaw Puzzle

The solution is straightforward but might be a little complicated to code.

At first, we should enumerate all the feasible sizes of pieces. A size with x*y is feasible if x and y are factors of A and B, respectively. For each feasible size x*y, we find out all the pieces and check if there exist any two pieces that are exactly the same. Any two pieces are exactly the same if at least one of the following conditions can be satisfied:

1) They are the same without any rotations;

2) They are the same if the second one is rotated with 180 degrees;

3) They are the same if the second one is rotated with 90 degrees;

4) They are the same if the second one is rotated with 270 degrees;

If there are not any two pieces that are the same, then this size x*y results in a good puzzle, and we should further record the minimum size according to the requirements.

C. First Digit Law

This problem can be divided into two subproblems.

Subproblem 1): given the interval [L,R], how to count the number of integers whose most significant digit is 1? Suppose that F(n) is a function which calculates the number of integers from 1 to n, and thus this subproblem can be solved by computing F(R)-F(L). To implement such a function, we can try 1,10,100,...,10^m, until 10^m<=n, and the answer will be 1+10+100+...+10^(m-1)+min(10^m, n-10^m+1). Moreover, we can immediately calculate the probability of selecting an integer whose most significant digit is 1 as (F(R)-F(L))/(R-L+1);

Subproblem 2): given N events and the probability that every event occurs, how to calculate the probability that at least K of them occur? A straightforward method that enumerates all the feasible combination may fail since the number is likely to be quite huge. However, we can use DP, like Pascal's Triangle, to avoid the above difficulty. We use D[n][m] to denote the probability that for the first n events, exactly m of them occur. One can check that D[n][m]=D[n-1][m-1]*p[n]+D[n-1][m]*(1-p[n]), where p[n] denotes the probability that the n-th event occurs, while the initialization is done by setting D[0][0]=1. Then, the answer is just D[N][K]+D[N][K+1]+...+D[N][N].