owned this note
owned this note
Published
Linked with GitHub
## Đúng $s$ bước hay không?
Giả sử đây là trục tọa độ mà ta sử dụng.
![](https://hackmd.io/_uploads/SyJT0Kmoh.png)
Từ $(x, y)$, ta có thể:
- sang phải: $(x+1, y)$
- sang trái: $(x-1, y)$
- lên trên : $(x, y+1)$
- xuống dưới: $(x, y-1)$
Để đến điểm $(a, b)$:
1. Di chuyển trái/phải tới cột $a$
- Nếu $a > 0$, sang phải $a$ lần
- Nếu $a < 0$, sáng trái $-a$ lần
- Tóm lại, ta phải di chuyển $|a|$ lần
2. Di chuyển lên/xuống tới hàng $b$
- Tương tự, ta phải di chuyển $|b|$ lần
Tóm lại, ta cần tối thiểu $|a| + |b|$ lần di chuyển để tới điểm $(a, b)$.
> Để di chuyển được tới điểm $(a, b)$ trong vòng $s$ bước, ta phải thỏa mãn hai điều kiện sau:
> - $|a| + |b| \le s$, vì nếu $s$ nhỏ hơn, ta sẽ không tới được vị trí này
> - $|a| + |b|$ và $s$ phải cùng tính chẵn lẻ, vì sau khi đến điểm $(a, b)$, ta có thể dùng nốt $s - (|a| + |b|)$ bước còn lại bằng cách liên tục đi lên - đi xuống. (*)
(*) Ngoài ra ta có thể chứng minh điểm $(a, b)$ luôn có $a+b$ cùng tính chẵn lẻ với $s$.
## DS20
```
1 7 5 4 9 15 13 12 17 23 21 20 ...
+6 -2 -1 +5 +6 -2 -1 +5 +6 -2 -1
```
Tóm lại, ta thấy chu kỳ cộng của nó là: $+6 \rightarrow -2 \rightarrow -1 \rightarrow +5 \rightarrow \dots$
### Cày trâu
```python=
pos = 1; ans = 1
while pos < n:
pos += 1
if (pos % 4 == 2):
ans += 6
elif (pos % 4 == 3):
ans -= 2
elif (pos % 4 == 0):
ans -= 1
else: # (== 1)
ans += 5
print(ans)
```
### Thuật chuẩn
Sau mỗi chu kỳ cộng 4 lần, số của ta tăng thêm $8$ đơn vị.
Ta sẽ đếm số lần được cộng nguyên chu kỳ, sau đó cộng lẻ cho tới khi đủ $N$.
```
1 0
2 0
3 0
4 0
5 1
6 1
7 1
8 1
9 2
10 2
11 2
12 2
13 3
=> (n-1) // 4 chu kỳ
```
```python=
cycle = (n - 1) // 4
add = cycle * 8
pos = 1 + cycle * 4
ans = 1 + add
# đến đây, copy nguyên đoạn code ở trên vào
# vòng while này chạy tối đa 3 lần :))
while pos < n:
pos += 1
if (pos % 4 == 2):
ans += 6
elif (pos % 4 == 3):
ans -= 2
elif (pos % 4 == 0):
ans -= 1
else: # (== 1)
ans += 5
print(ans)
```
## CaiWinDao và 3 em gái
Đầu tiên, ta sẽ xem thử những bao nào chia hết cho 3, những bao nào chia 3 dư 1, những bao nào chia 3 dư 2.
```python=
candies = [[], [], []]
for baokeo in a:
candies[baokeo % 3].append(baokeo)
```
![](https://hackmd.io/_uploads/BJimV5mi3.png)
Ta thấy:
- Nếu tổng chia hết cho 3 $\Rightarrow$ ta lấy hết bao kẹo.
- Nếu tổng chia 3 dư 1, thì ta sẽ lấy bớt:
- Hoặc một bao kẹo từ nhóm $1$
- Hoặc hai bao kẹo từ nhóm $2$
- Nếu tổng chia 3 dư 2:
- Hoặc một bao kẹo nhóm $2$
- Hoặc hai bao kẹo nhóm $1$
Với hai trường hợp sau, hiển nhiên, ta sẽ bốc những bao kẹo **nhỏ nhất** trong nhóm, và ta sẽ chỉ chọn bốc trường hợp có tổng bao kẹo lấy đi **nhỏ hơn**.
```python=
for i = 0 -> 2:
candies[i].sort() # sắp xếp, để tí nữa lấy những bao kẹo nhỏ nhất
tong = sum(a)
if tong % 3 == 0:
pass
elif tong % 3 == 1:
case1 = 0; case2 = 0
if len(candies[1]) >= 1:
case1 = candies[1][0] # một bao kẹo nhỏ nhất nhóm 1
if len(candies[2]) >= 2:
case2 = candies[2][0] + candies[2][1] # hai bao kẹo nhỏ nhất nhóm 2
if case1 == 0: tong -= case2
elif case2 == 0: tong -= case1
else: tong -= min(case1, case2)
else: # (tong % 3 == 2)
làm tương tự, tính case1 case2 dựa vào kịch bản trên
copy lại ba dòng cuối (if - elif - else) của trường hợp ==1
print(tong // 3) # đến giờ chia kẹo rồi =))
```
## Vui vẻ
ở đây thống nhất mảng đếm từ 1, nên ta chèn vào một phần tử phía trước.
```python=
n, mod = map(int, input().split())
h = [0] + list(map(int, input().split())) # cho mảng đếm từ 1
```
### Subtask 1: $n=3$
không lẽ không làm được? <(")
### Subtask 2: $n = 300$
Duyệt hết tất cả bộ ba số
```python=
ans = 0
for i = 1 -> n:
for j = i+1 -> n:
for k = j+1 -> n:
ans += h[i] * h[j] * h[k]
print(ans % mod)
```
### Subtask 3: $n = 3000$
Ta thấy với mỗi cặp vòng for $i$ và $j$, vòng for $k$ chạy từ $j+1$ tới $n$.
Tổng ta tạo được là:
$h_ih_jh_{j+1} + h_ih_jh_{j+2} + h_ih_jh_{j+3} \dots + h_ih_jh_{n} = h_ih_j(h_{j+1} + h_{j+2} + h_{j+3} + \dots + h_n)$
Để tính cụm $(h_{j+1} + h_{j+2} + h_{j+3} + \dots + h_n)$, ta có thể sử dụng **mảng cộng dồn**.
```python=
sumH = [0] * (n + 1)
for i = 1 -> n:
sumH[i] = sumH[i - 1] + h[i]
ans = 0
for i = 1 -> n:
for j = i + 1 -> n:
ans += h[i] * h[j] * (sumH[n] - sumH[j])
print(ans % mod)
```
### Subtask 4+5: $n \le 10^5$
#### Bài toán nhỏ hơn
Vẫn là cho mảng $h$. Ta phải tính $\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n h_ih_j$, tức là tính tổng các bộ hai số, thay vì ba số như đề bài.
Cách giải của bài này na ná sub 3 ở trên, ta sẽ tính tổng một lượt $h_j$.
Để thuận tiện cho việc cài đặt sub này lẫn các sub sau, ta sẽ xây dựng mảng cộng dồn **ngược**.
```python=
sumH[0] = [0] * (n+2)
for i = n -> 1:
sumH[i] = sumH[i + 1] + h[i] # mảng cộng dồn ngược
for i = 1 -> n:
ans += h[i] * sumH[i + 1]
# -------------------
# các h[j]
```
#### Bài toán gốc
Ta sẽ thấy, với mỗi vòng for $i$, hai vòng for $j$ và $k$ tạo thành tổng các bộ hai số từ $i+1$ tới $n$.
Nếu xét vòng for ở trên theo thứ tự ngược lại $(i = n \rightarrow 1)$, ta sẽ thấy ở lượt thứ $i$ các bộ hai số từ $i$ tới $n$ đều **đã được dựng một cách đầy đủ**.
Gọi $sumH2[i]$ là tổng tất cả bộ hai số trong khoảng $i \rightarrow n$, tức ở đây cũng là **mảng cộng dồn ngược** như ở bài toán nhỏ.
```python=
for i = n-1 -> 1:
sumH2[i] = sumH2[i + 1] + h[i] * (sumH[i + 1])
ans = 0
for i = n-1 -> 1: # 1 -> n-1 cũng được
ans += h[i] * sumH2[i + 1]
print(ans % mod)
```
##### code mẫu:
```python=
n, M = map(int, input().split())
h = [0] + list(map(int, input().split()))
sumH = [[0] * (n + 2) for i in range(2 + 1)]
for i in range(n, 1 -1, -1):
sumH[1][i] = sumH[1][i + 1] + h[i]
for i in range(n, 1 -1, -1):
sumH[2][i] = sumH[2][i + 1] + h[i] * sumH[1][i + 1]
ans = 0
for i in range(1, n + 1):
ans += h[i] * sumH[2][i + 1]
print(ans % M)
```
#### Mở rộng
Nếu bài toán tính tổng các bộ $k$ số bất kỳ,
gọi $sumH[k][i]$ là tổng các bộ $k$ số bất kỳ trong đoạn từ $i \rightarrow n$
Đáp án là $sumH[k][1]$.
```python=
sumH = [[0] * (n + 2) for i in range(k + 1)]
for i = n -> 1:
sumH[1][i] = sumH[1][i + 1] + h[i]
for kk = 2 -> k:
for i = n -> 1:
sumH[kk][i] = sumH[kk][i + 1] + h[i] * sumH[kk-1][i + 1]
```
## Đếm số ODD
Đầu tiên, ta biến đổi bài toán đếm số lượng số từ $L$ tới $R$, thành $f(N) =$ số lượng số từ $1$ tới $N$. Đáp án là $f(R) - f(L - 1)$
Tiếp theo, ta xem thử có bao nhiêu số ODD có $K$ chữ số. Rõ ràng, đáp án là: $g(k) = 5^k$
Để tính $f(N)$, ta làm như sau:
1. Xem thử $N$ có bao nhiêu chữ số. Ta gọi là $K$.
2. Tính tổng $g(1) + g(2) + \dots + g(K-1)$, tức là các số có $<K$ chữ số.
3. Lần lượt tách nhóm theo các chữ số của $N$, và lập công thức
4. Cộng các kết quả tính được ở bước 2 và 3
Ví dụ tách nhóm:
```
N = 3456
- 1xxx
- 3xxx
- 31xx
- 33xx
N = 3179
- 1xxx
- 3xxx
- 31xx
- 311x
- 313x
- 315x
- 317x
- 3171, 3173, 3175, 3177, 3179
N = 3147
- 1xxx
- 3xxx
- 31xx
- 311x
- 313x
công thức số lượng mỗi nhóm:
g(số chữ số còn lại)
```
```python=
def g(k: int) -> int:
return 5 ** k
def f(n: int) -> int:
digits = [];
while n > 0:
digits.append(n % 10)
n //= 10
length = len(digits)
ans = 0
for i = 1 -> length - 1:
ans += g(i)
for i = length-1 -> 0:
for d in range(1, digits[i] + 1, 2):
if d == digits[i]: continue # tách thành nhóm nhỏ hơn
ans += g(i)
if digits[i] % 2 == 0: # nếu là số chẵn, dừng
break # vì đã lấy đủ số
l = int(input())
r = int(input())
print(f(r) - f(l-1))
```
## Đếm số đối xứng lẻ
Có thể làm thử bài này trước
https://lqdoj.edu.vn/problem/15thtbdna4
---
![](https://hackmd.io/_uploads/Hkj2UjXsh.png)
Ta sẽ gọi mỗi khối xanh là một khối **hạt nhân**, và số lượng số hồi văn độ dài $k$ bất kỳ sẽ bằng số lượng hạt nhân có thể tạo được, mà ở đây là **số lượng số ODD** độ dài $\left\lfloor\dfrac{k+1}{2}\right\rfloor$
Cách làm:
1. Tách $N$ thành mảng các chữ số, gọi $K$ là độ dài của $N$.
2. Tính số lượng tất cả số đối xứng lẻ độ dài **nhỏ hơn $K$**.
```
N = 7654321
-> 7653
N = 7654999
-> 7654
N = 1000000
-> không có hạt nhân nào
```
3. Tìm số hạt nhân lớn nhất có thể tạo được, ở đây gọi là $X$
4. Đếm số lượng hạt nhân nhỏ hơn $X$ và là số ODD.
```python=
def getNuclear(N: int) -> int:
digits = [];
while n > 0:
digits.append(n % 10)
n //= 10
length = len(digits)
nuclearLength = (length + 1) // 2
for i = 0 -> (length-1)//2
digits[i] = digits[length - 1 - i] # cho nửa sau bằng nửa trước
sohoanchinh = (ráng ghép cả digits lại thành số đi hihi)
hatnhan = (ráng ghép từ digits[0 -> nuclearLength - 1])
if sohoanchinh <= N: return hatnhan
else: return hatnhan - 1
def f(N: int) -> int:
digits = [];
while n > 0:
digits.append(n % 10)
n //= 10
length = len(digits)
ans = 0
for i = 1 -> length - 1:
ans += g((i+1) // 2)
if (N == 10**(length - 1))
return ans;
N = getNuclear(N)
copy lại dòng 20-24 của hàm này
đếm số lượng số ODD có length chữ số, nhỏ hơn N
copy lại bài trên, chắc là dòng 14-20?
return ans
```