# Đề HSG 9 năm 2025

## Bài 1

Nhiều cách:
- for từng kí tự c trong bảng chữ cái. check xem c có xuất hiện trong s không?
- dùng thêm vòng for (vẫn okay)
- dùng CTDL
- dùng `set` của Python

## Bài 2:


**Tư tưởng Prefix-Sum:**
- Các bài toán đếm trong đoạn $[L,R]$ --> Đưa về bài toán đếm từ 1 tới $n$. Tạo hàm $f(n)$ là đáp án đếm từ $1$ tới $n$.
- Kết quả: $f(r) - f(l-1)$

- Tính f:
"Từ 1 tới n có bao nhiêu số tròn chục - chia hết cho 10?"
`n div 10`

" lớn hơn L và nhỏ hơn R"
từ L+1 tới R-1
Đáp án: `(R-1) div 10 - L div 10`

đếm >=, trừ L-1

## Bài 3:

### Cách 1

`f(p+k-1) - f(p-1)`
Với $f(x)$ là tổng từ vị trí $1$ cho tới vị trí $x$.

Tính $f$ như thế nào?

**Quy tắc tính:**
Cứ $n$ số liên tiếp thì dãy số lại lặp lại.
Tổng được tính bằng:
- Số lần lặp lại hoàn chỉnh
- Cộng với: Phần thêm vào/ thừa ra

Cụ thể là bao nhiêu?
- Lặp lại `k div n` lần
- Phần dư ra: `k mod n`. Bắt đầu từ `a[1]` (a[0] luôn)

**Lưu ý:** Vừa cộng, vừa `mod`

### Cách 2
Đếm trực tiếp?

Dùng cùng quy tắc
Cứ $n$ số liên tiếp thì dãy số lại lặp lại.
Tổng được tính bằng:
- Số lần lặp lại hoàn chỉnh
- Cộng với: Phần thêm vào/ thừa ra

**Phải tính vị trí bắt đầu** (vì lấy mốc là $p$ - ở lưng chừng)

## Bài 4:

How to cày trâu?

1. Nhập vào n,k
2. Khai báo mảng a[k + 5] (lưu được a[1], a[2], .. a[k+1]) là số lượng từng cấp độ
3. a[1] = n
4. BythonC

for i từ 1 tới k {
    1. Tuyển lính mới
    mới = 0
    for j từ 1 tới k+1:
        mới += a[j] * j
    2. Tăng cấp độ
    for j từ k+1 xuống 2:
        a[j] = a[j-1]
    a[1] = mới
}

**Print cày trâu ra để quan sát**

.
n 1

.
n 1 mới
n 2

.
3n 1 
 n 2
 n 3

X lính
Y 

.
8n 1
3n 2
 n 3
 n 4

.
21n 1
 8n 2
 3n 3
  n 4
  n 5

Chứng minh:

Tại mỗi thời điểm:
Đặt $n$ là tổng số lượng lính.
- $a_i$ là số lượng lính cấp độ $i$

Đặt $T$ là khả năng chiêu mộ lính mới của toàn bộ $n$ lính (tính bằng số lính mới chiêu mộ vào thời điểm ngày tiếp theo)

Theo đề bài:
$T = 1 \cdot a_1 + 2\cdot a_2 + 3\cdot a_3 + \dots + i\cdot a_i + \dots$

Quan sát quy luật:
- Ngày 0: $a = [1], n = 1, T = 1$
- Ngày 1: $a = [1, 1], n = 2, T = 3$
- Ngày 2: $a = [3, 1, 1], n = 5, T = 8$
- Ngày 3: $a = [8, 3, 1, 1], n = 13, T = 21$
- Ngày 4: $a = [21, 8, 3, 1, 1], n = 34, T = 55$
- Ngày 5: $a = [55, 21, 8, 3, 1, 1], n = 89, T = 120$

Ta có một số quan sát, biến đổi như sau:
1. Quy luật: số lượng lính sau ngày $k$ chính là số Fibonacci thứ $2k+1$ (với $F_1 = F_2 = 1$) **(*)**
Với quan sát này, đã có thể code AC được bài toán. Để chặt chẽ hơn, mời bạn đọc xem chứng minh công thức toán
2. $a_1 \text{ next day}=T$
3. $\Rightarrow n \text{ next day} = n + T$
4. $T \text{ next day} = T + 2 \cdot a_1 + 3\cdot a_2 + 4\cdot a_3 + \dots + (i+1)\cdot a_i + \dots = T + a_1 + 2\cdot a_2 + 3\cdot a_3 + \dots + i \cdot a_i + \dots + (a_1 + a_2 + \dots + a_i) = 2T + n$
5. Tới đây chúng ta đã rút gọn công thức xuống còn hai biến, có thể cài đặt cách khác.
6. Nếu thích, có thể rút gọn công thức này chỉ còn một biến $n$, nhưng *chưa cần thiết*. [Spoiler](https://oeis.org/A001519)