Programming exercise on 21 August

A

The value $ctz(n)$ can be obtained by performing the procedure operation for $i=1,2,…$ in order:

1. Refer to the $i$-th least significant digit in the binary representation of $n$.
2. Do nothing if it is $0$.
3. If it is 1, immediately terminate the procedure. The current value of $i$ subtracted by $1$ equals sought $ctz(n)$.

Here, the $i$-th least significant digit (0 or 1) in the binary representation of $n$ can be obtained by taking the logical product (AND) of $n$ shifted $(i−1)$ bits to the right. Since $n \le 10^9<2^{30}$, the iteration above is repeated at most $30$ times, which finishes within sufficiently short time. Therefore, the problem has been solved.

Alternatively, one can store the bit sequence in the binary representation of $n$ in an array of integers or booleans, or inspect the last bit while right-shifting $n$ one by one. These are all fast enough.

If you are not very used to handling bit sequences, you can regard each step as an operation against an integer. They can be regarded as:

• the $i$-th least significant digit in the binary representation of $n$ → remainder when $n$ is divided by $2$;
• shifting $n$ to the right by one bit → dividing $n$ by $2$ (with fractional part rounded down).

Thus, the effectively same operations can be achieved by combining these operations. Under the constraints of this problem, it is fast enough.

Intermediate and rather difficult problems sometimes require constant-factor optimization using say bitsets, which is based on bit operations which tend to be fast, so it may be good idea to learn bit operations.

Sample code in Python:

n=int(input())
for i in range(30):
    if n&(1<<i):
        print(i)
        break

B

The answer for this problem can be found by inspecting each of day $M$, day $M+P$, … to check whether it is within the first $N$ days, and add $1$ to the answer if it is, and terminating the loop if it is not. This can be implemented with a for statement. The following it

sample codes in Python:

n, m, p = map(int, input().split())
res = 0
while m <= n:
    res += 1
    m += p
print(res)

C

By the constraints of the problem, we do not need to consider the region outside $0 \le x \le 100$ and $0 \le y \le 100$. Also, for any pair $(i,j) (1 \le i \le 100,1\le j \le 100)$, the region within $i−1 \le x \le i$ and $j−1 \le y \le j$ is either entirely covered by a sheet or not covered at all. Therefore, it is sufficient to consider the following problem.

• There is a $100×100$ grid. Let us call the cell in the $i$-th row from the top and $j$-th column from the left cell $(i,j)$. Suppose that each cell is initially painted white.
• For each $1 \le k \le N$ in order, the $i$-th operation paints cell $(i,j)$ for all integer pairs $(i,j)$ with $A_k \le i \le B_{k−1}$ and $C_k \le j \le D_{k−1}$.
• Find the number of cells painted black after the $N$ operations.

The process can be actually simulated with for statements, and one can use for statements and if statements to count the cells ending up being painted black, in order to find the answer.

The simulation requires at most about $N \times (100 \times 100) \le 10^6$, which is fast enough even with a naive implementation. Therefore, the problem has been solved.

Sample code in Python:

n=int(input())
g=[[False for i in range(100)]for i in range(100)]
for k in range(n):
    a,b,c,d=map(int, input().split())
    for i in range(a,b):
        for j in range(c,d):
            g[i][j]=True
ans=0
for i in range(100):
    for j in range(100):
        if g[i][j]==True:
            ans+=1
print(ans)

D

We can sort $A_1,\cdots,A_N$ to assume $A_1<\cdots<A_N$ without changing the answer.

If two adjacent terms differ by two, the answer is between them. Since the Constraints guarantee that the answer is uniquely determined, such a position always occurs once.

The complexity of this problem is $\mathcal{O}(Nlog⁡N)$.

Sample code (Python):

N=int(input())
A=sorted(list(map(int,input().split())))
for i in range(N-1):
  if A[i+1]-A[i]==2:
    print(A[i]+1)