owned this note
owned this note
Published
Linked with GitHub
# Bài 1 - Tổng lẻ
n = 1 => 1 = 1
n = 2 => 4 = 1 + 3
n = 3 => 9 = 1 + 3 + 5
n = 4 => 16 = 1 + 3 + 5 + 7
n = 5 => 25 = 1 + 3 + 5 + 7 + 9
=> đáp án = n * n
# Bài 2 - Restangles
Chúng ta chỉ cần quan tâm tới nửa chu vi $p' = \left\lceil\dfrac{p}{2}\right\rceil$, từ đây suy ra yêu cầu đề là: **tìm số hình chữ nhật có tổng chiều dài + rộng $\ge p'$**
Ta thấy: trong một hình chữ nhật lưới $n \times m$, số hình chữ nhật có kích thước $d \times r$ bằng $(n-d+1) \times (m-r+1)$.
- Bước 1: $p' = (p / 2) + (p\%2)$
- Bước 2: Một hình chữ nhật bất kỳ có kích thước $d \times r$ được gọi là hình loại $d \times r$. Ta duyệt qua tất cả các loại $d \times r$, xem mỗi loại có bao nhiều hình trong hình chữ nhật gốc, và cuối cùng cộng tổng của các hình chữ nhật **có tổng $d+r \le p$**.
```python=
p = (p // 2) + (p % 2)
answer = 0
for d = 1 -> n:
for r = 1 -> m:
if (d + r) >= p:
answer += (n - d + 1) * (m - r + 1)
print(answer)
```
## Bài 3 - Chỉnh lý
### Cày trâu
Ưu tiên cộng 2 hơn cộng 1
```
while a < b:
if (a + 2) % c != 0:
a += 2
else:
a += 1
```
### Thuật chuẩn
Cố gắng cộng nhiều lần cùng một lúc.
**Nhận xét:** để không dính một số $A$ bất kỳ chia hết cho $c$, dãy cộng của chúng ta sẽ luôn có dạng: $\dots \rightarrow (A-1) \rightarrow (A+1) \rightarrow \dots$
Đầu tiên, ta tìm số A nhỏ nhất lớn hơn $a$ sao cho $A$ chia hết cho $c$.
Ta sẽ cộng $a$ liên tục cho 2, xem thử có dính phải $A$ hay không. Ta có các trường hợp sau:
1. Không dính $A$ $\Rightarrow$ kiểm tra có dính $A+c$ hay không.
- Nếu có, ta cho $+2$ liên tục tới $A+c+1$, rồi làm như mục 2 (reset đầu chu kỳ rồi làm như mục 2).
- Ngược lại, ta có thể chắc chắn không bao giờ dính các ước của $c$ ($a$ lẻ và $c$ chẵn) $\Rightarrow$ đáp án là $\left\lceil\dfrac{b-a}{2}\right\rceil$
2. Dính $A$ $\Rightarrow$ trước đó dính $A-2$ $\Rightarrow$ tới lúc này, muốn né $A$ thì buộc phải $+1$.
Dãy tăng lúc này trở thành: $a, a+2, \dots, A-2, A-1, A+1, \dots$
Lúc này, ta xét xem từ $A+1$ có khả năng chạm tới $A'=A+c$ hay không.
- Nếu $c$ lẻ $\Rightarrow$ luôn chạm được tới
- Xét chu kỳ cộng: $+2$ liên tục, tới lần cuối mới $+1$ rồi $+2$ lại $\Rightarrow$ số lượt cộng là $1 + \dfrac{c-1}{2} = \dfrac{c+1}{2}$
- Bước 1: cho số $a$ nhảy đến đầu chu kỳ thành số $A+1$.
- Bước 2: liên tục thực hiện chu kỳ $+c = +2 +2 \dots + 1$, và coi việc $+c$ là việc cộng $\dfrac{c+1}{2}$ lần cùng một lúc. dừng khi $a + c > b$, lúc này $a$ sẽ có dạng $A'-1$ (với $A'$ là một bội của $c$).
- Bước 3: $+2$ liên tục cho tới khi đến $b$ thì dừng.
- Nếu $c$ chẵn $\Rightarrow$ luôn né các bội của $c$ $\Rightarrow$ cộng một mạch tới $b$.
```python=
def step(dist):
return dist // 2 + dist % 2
def calculation(a, b, c):
ans = 0
A = (a // c + 1) * c
if (A - a) % 2 != 0: # không dính A
if c % 2 != 0: # không bao giờ dính bội của c
return step(b - a)
else:
# phase 1
ans += step(A+c+1 - a)
a = A+c+1
# phase 2 + 3 cóp ở dưới lên
solantang = (b - a) // c
ans += ((c + 1) // 2) * solantang
a += c * solantang
ans += step(b - a)
else:
# phase 1: reset chu kỳ
if b <= A+1:
return step(b - a)
ans = (A+1 - a) // 2
a = A+1
# phase 2: tăng chu kỳ liên tục
solantang = (b - a) // c
ans += ((c + 1) // 2) * solantang
a += c * solantang
# phase 3: hoàn thiện phép tính
ans += step(b - a)
return ans
```
## Bài 4 - Số hữu tỉ
![](https://hackmd.io/_uploads/r1oA5Yatn.png)
![](https://hackmd.io/_uploads/rJcgiF6Kh.png)
Lấy tập hợp danh sách các số dư $A$ và các chữ số tương ứng với đáp án $B$, theo công thức sau:
\begin{align}
A[1] &= x \ \text{mod}\ y \\
B[i] &= (A[i] \times 10)\ \text{div}\ y \\
A[i+1] &= (A[i] \times 10)\ \text{mod}\ y \\
\end{align}
Ta thấy đáp án ở $B$ tạo thành chu kỳ, khi trên dãy $A$ bị lặp phần tử đầu tiên.
Vì thế, ta tìm hai vị trí $i, j$ nhỏ nhất sao cho $A[i] = A[j]$. Khi đó, chu kỳ thập phân là $\sigma = j-i+1$, và đáp án có dạng $0.B_1B_2\dots B_{i-1}\overline{B_iB_{i+1}\dots B_j}$
## Subtask 1: $x, y \le 10^6$
Từ đó, ta sẽ có cách làm sau:
```python=
MAX = 10**6+10
A = [0] * MAX
B = [0] * MAX
vitri = [0] * MAX;
khongchuky = []; chuky = []
A[1] = x % y
for i = 1 -> ...
B[i], A[i + 1] = (A[i] * 10) // y, (A[i] * 10) % y
if vitri[A[i]] == 0:
vitri[A[i]] = i
else:
batdau = vitri[A[i]]
ketthuc = i-1
khongchuky = B[:batdau]
chuky = B[batdau:ketthuc + 1]
break
print phần khongchuky
if chuky != [0]:
print phần chuky
```
## Subtask 2: $x, y \le 10^{12}$.
**Nhận xét:** Khi tìm được vị trí bắt đầu $i$, thì ta thấy với mọi $i' \le i$, $A[i'] = A[i' + \sigma] = A[i' + 2\sigma] + \dots$ Tức là kể từ vị trí bắt đầu, các phần tử có vị trí hơn kém nhau $\sigma$ đều có $A$ (và $B$) bằng nhau.
**Idea:** Ta sẽ tìm một vị trí $i$ bất kỳ sao cho $A[i]=A[2i]$, bằng cách tạo ra hai con trỏ $i$ và $j$ chạy với hai tốc độ khác nhau: `i += 1`(rùa) và `j += 2`(thỏ)
![](https://hackmd.io/_uploads/B1dOe5pKh.png)
**Vấn đề 1:** Tuy nhiên, lúc này ta vẫn chưa tìm được chu kỳ chuẩn.
Ta có **nhận xét khác**: $(j-i)$ phải chia hết cho $\sigma$.
Lúc này, ta có thể tìm lại chu kỳ, bằng cách cố định rùa $i$, và cho thỏ $j$ đi từ từ từng bước 1.
![](https://hackmd.io/_uploads/HkU1ZcpY3.png)
**Vấn đề 2**: Đó cũng chưa chắc là vị trí bắt đầu.
Vì thế ta đi tìm lại vị trí bắt đầu, bằng cách cho rùa $i$ xuất phát tại $1$, thỏ $j$ xuất phát tại $\sigma + 1$, và hai con sẽ luôn giữ khoảng cách $\sigma$ với nhau, cùng nhau tiến 1 đơn vị, cho tới khi tìm được vị trí bắt đầu $(A_i = A_j = A_{i+\sigma})$.
![](https://hackmd.io/_uploads/ByhFbqat3.png)
Đây là Thuật toán Thỏ và Rùa của Floyd.
```python=
MAX = 2 * 10**7 + 10
A = [0] * MAX
B = [0] * MAX
# bước 1: khởi tạo mảng A và B thật nhiều số
A[1] = x % y
for i = 1 -> MAX - 1:
B[i], A[i + 1] = (A[i] * 10) // y, (A[i] * 10) % y
# bước 2.1: tìm một chu kỳ bất kỳ
rua = 1; tho = 2
while a[rua] != a[tho]:
rua += 1; tho += 2
# bước 2.2: cố định vt bắt đầu, tìm độ dài chu kỳ hạt nhân
tho = rua + 1
while a[rua] != a[tho]:
tho += 1
chuky = tho - rua
# bước 2.3: có độ dài chu kỳ, tìm vt bắt đầu
rua = 1; tho = rua + chuky
while a[rua] != a[tho]:
rua += 1; tho += 1
batdau = rua
khongchuky = ...; chuky = ...
print 2 phần.
```