# Hướng dẫn giải bài các bài tập trên lqdoj

Tài liệu học:
https://drive.google.com/drive/folders/1MO_VgOLymvcHbrubuKH7YD7hEhthQFp3?usp=sharing

---

## [Chia Cặp 1](https://lqdoj.edu.vn/problem/pair1)

Chia cặp là một bài toán trên trang web LQDOJ: Le Quy Don Online Judge. Bài toán yêu cầu tìm độ chênh lệch lớn nhất x sao cho khi ghép 2 số trong một mảng lại thành một cặp, ta có ít nhất k cặp và chênh lệch giữa 2 số trong một cặp bất kỳ không vượt quá x.

### Mô tả bài toán

- **Input**: Một mảng gồm n số nguyên và một số nguyên k.
- **Output**: Giá trị x là độ chênh lệch lớn nhất thỏa mãn yêu cầu của bài toán.

### Hướng giải quyết

Để giải quyết bài toán, ta sử dụng kỹ thuật chặt nhị phân. Ta xây dựng một hàm kiểm tra để kiểm tra xem với một giá trị x nhất định, ta có thể ghép được ít nhất k cặp hay không. Sau đó, ta áp dụng kỹ thuật chặt nhị phân để tìm giá trị x lớn nhất thỏa mãn yêu cầu.

### Thuật toán

1. Xây dựng hàm kiểm tra:
- Hàm này nhận vào một giá trị x là độ chênh lệch bất kỳ.
- Kiểm tra xem x có thỏa mãn yêu cầu của bài toán hay không.
- Trả về true nếu có thể ghép được ít nhất k cặp với độ chênh lệch không vượt quá x, ngược lại trả về false.

2. Áp dụng kỹ thuật chặt nhị phân:
- Khởi tạo đoạn ta xét là [0, 1e9] (l = 0, r = 1e9), vì chênh lệch nhỏ nhất giữa 2 số là 0 và lớn nhất chỉ có thể nhỏ hơn 1e9.
- Thực hiện vòng lặp while để thu hẹp dần đoạn tìm kiếm với điều kiện l <= r.
- Đoán một giá trị chênh lệch bằng cách lấy trung bình cộng của l và r.
- Kiểm tra xem với giá trị chênh lệch này, ta có thể ghép được ít nhất k cặp hay không bằng cách sử dụng hàm kiểm tra đã xây dựng ở bước 1.
- Nếu thỏa mãn, lưu lại giá trị x đã đoán vào biến kết quả và dời đoạn tìm kiếm sang phía bên phải để tìm kiếm những giá trị lớn hơn.
- Ngược lại, dời đoạn tìm kiếm sang phía bên trái để xét những giá trị nhỏ hơn.
- Kết thúc vòng lặp, in ra giá trị x là kết quả.

Đây là cách giải quyết bài toán Chia Cặp 1 trên trang web LQDOJ: Le Quy Don Online Judge.

## [Đường dây điện (THTA Sơn Trà, Đà Nẵng 2024)](https://lqdoj.edu.vn/problem/24stra4)

### Mô tả bài toán
- Bài toán yêu cầu tính tổng độ cao của các cột mốc từ cột mốc l đến cột mốc r trên một đường dây điện.
- Cột mốc được xây dựng theo quy tắc sau:
- Các cột mốc chẵn có độ cao là 0.
- Các cột mốc chia hết cho 4 có độ cao là 1.
- Các cột mốc chia hết cho 8 có độ cao là 2.
- Và tiếp tục theo quy luật tương tự.
- Yêu cầu: In ra tổng độ cao từ cột mốc l đến cột mốc r.

### Hướng làm bài
- Để nhận biết quy luật xây dựng các tầng đèn trên các cột mốc, chúng ta thay đổi góc nhìn:
- Xây tầng 1 cho các cột mốc chia hết cho 2.
- Xây tầng 2 cho các cột mốc chia hết cho 4.
- Xây tầng 3 cho các cột mốc chia hết cho 8.
- Và tiếp tục quy luật tương tự cho các tầng tiếp theo.
- Nhìn theo hướng này, ta thấy rằng ta sẽ xây thêm tầng cho các cột mốc nếu nó liên tiếp chia hết cho các số trong dãy (2, 4, 8, ...)
- Gọi f(x) là tổng độ cao từ cột mốc 1 đến cột mốc x.
- Để tính tổng độ cao từ cột mốc l đến cột mốc r, ta sử dụng tính chất của kĩ thuật prefix sum: f(r) - f(l-1).

### Thuật toán
- Để tính tổng độ cao từ cột mốc 1 đến cột mốc x, chúng ta xây dựng một hàm f(x).
- Cụ thể, ta thực hiện các bước sau:
1. Khởi tạo biến i = 2 (đại diện cho dãy 2, 4, 8, 16, ...).
2. Khởi tạo biến s = 0 (tổng độ cao từ cột mốc 1 đến cột mốc x).
3. Sử dụng vòng lặp while để thực hiện các bước sau cho đến khi i > x:
- Tại mỗi vòng lặp:
- Tính số lượng cột mốc chia hết cho i từ 1 đến x bằng cách lấy phần nguyên của phép chia x cho i.
- Cộng kết quả vào biến s.
- Tăng giá trị của i lên gấp đôi.
4. Trả về giá trị của biến s là kết quả của hàm f(x).

## [Tập xe](https://lqdoj.edu.vn/problem/csp)

### Mô tả bài toán
- Nhập số lượng học sinh (n) và một chỉ số cân nặng (m).
- Nhập mảng arr chứa chỉ số cân nặng của các học sinh.
- Yêu cầu: In ra số lượng cặp học sinh có tổng trọng lượng không vượt quá m.

### Hướng làm bài:
1. **Sắp xếp mảng arr tăng dần:** Để thực hiện kỹ thuật chặt nhị phân, cần sắp xếp mảng arr theo thứ tự tăng dần.
2. **Duyệt từng học sinh i từ 0 đến n-2:**
- Sử dụng hàm chặt nhị phân để tìm học sinh j có chỉ số trọng lượng lớn nhất sao cho tổng trọng lượng của học sinh i và j không vượt quá m.
- Nếu tìm được j, thì số lượng học sinh có thể ngồi với học sinh i là j - i.
- Bởi vì mảng được sắp xếp tăng dần nên nếu i có thể ngồi với j thì i có thể ngồi với tất cả các học sinh từ i+1 -> j (những học sinh này có trong lượng <= học sinh j).
- Từ i+1 đến j có j-i học sinh nên số lượng học sinh có thể ngồi với học sinh i là j-i
- Cộng kết quả này vào biến đáp án (ans).
- Nếu không tìm được học sinh nào ngồi được với i, không cộng gì vào kết quả.

### Thuật toán:
- **Hàm chặt nhị phân:**
- Nhận vào chỉ số i và trả về chỉ số j (với j > i) sao cho arr[j] là số lớn nhất, mà tổng của arr[i] và arr[j] không vượt quá m.
- Khởi tạo l = i+1, r = n-1, j = -1.
- Đoạn ta sẽ tìm kiếm từ i+1 -> n-1 bởi vì ta phải trả về chỉ số j > i.
- Khởi tạo j = -1, tức nếu không tìm thấy bất kì phần tử nào cộng với arr[i] <= m, ta trả về -1.
- Vòng lặp while l <= r:
- Tính mid bằng trung bình cộng của l và r.
- Nếu arr[i] + arr[mid] <= m:
- Lưu lại chỉ số mid vào j và dời đoạn đang xét sang những phần tử có giá trị lớn hơn (từ mid+1 -> r).
- Nếu arr[i] + arr[mid] > m:
- Dời đoạn tìm kiếm sang l -> mid-1 để tìm trong các giá trị nhỏ hơn.
- Trả về kết quả trong biến j.

- **Duyệt từng học sinh i từ 0 đến n-2:**
- Nếu không có học sinh ngồi được với học sinh i ta tiếp tục duyệt tới học sinh i+1, Ngược lại:
--> Cộng số lượng học sinh có thể ngồi với i vào kết quả.

## [maxle](https://lqdoj.edu.vn/problem/tknp02)

### Mô tả bài toán:
#### Input:
- Hai số nguyên n, k.
- Mảng arr chứa n số nguyên.
- k số nguyên x.
#### Output:
- Với mỗi số x, tìm giá trị lớn nhất nhỏ hơn hoặc bằng x trong mảng arr.

### Hướng làm bài:
- Bước 1: Xây dựng hàm chặt nhị phân để tìm vị trí có giá trị lớn nhất nhỏ hơn hoặc bằng x trong mảng arr.
- Hàm này nhận vào một giá trị x và trả về vị trí của phần tử lớn nhất nhỏ hơn hoặc bằng x trong mảng arr.
- Khởi tạo biến ans = -1.
- Khởi tạo l = 0, r = n-1, thể hiện đoạn ta tìm kiếm trên mảng arr ban đầu từ đầu đến cuối.
- Sử dụng thuật toán chặt nhị phân để tìm giá trị phù hợp.
- Trong mỗi vòng lặp:
- Tính mid là giá trị trung bình cộng của l và r.
- Nếu arr[mid] <= x, lưu giá trị này vào biến ans, và tiếp tục tìm ở đoạn từ mid+1 đến r để tìm giá trị lớn hơn.
- Nếu arr[mid] > x, tìm ở đoạn từ l đến mid-1 để tìm giá trị nhỏ hơn.
- Trả về kết quả ans + 1.(Vì mảng trong bài có chỉ số bắt đầu từ 0)

### Thuật toán:
- Duyệt qua từng số x trong mảng đầu vào.
- Sử dụng hàm chặt nhị phân để tìm giá trị lớn nhất nhỏ hơn hoặc bằng x trong mảng arr.

## [Số giàu có (THTB - TP 2021)](https://lqdoj.edu.vn/problem/21thtbdna2)
### Mô tả bài toán
- **Input:** Số N.
- **Yêu cầu:** In ra số có tổng các ước lớn nhất từ 1 đến N.

### Hướng làm bài
- Ta cần xây dựng một mảng s[x] với ý nghĩa s[x] là tổng của tất cả các ước của x.
- Sau đó, tìm giá trị lớn nhất của s[x] để in ra giá trị x.

### Thuật toán xây dựng mảng s[x]
1. Khởi tạo mảng s với s[1] = 1, vì 1 chỉ có một ước là chính nó.
2. Khởi tạo mảng s[i] = i + 1 với i từ 2 đến N. Mọi số đều có hai ước là 1 và chính nó.
3. Sử dụng thuật toán sàng nguyên tố Eratosthenes để cộng thêm các ước khác.
4. Với mỗi số nguyên tố i, ta cộng thêm i và i//j vào s[j], với j là bội của i.
5. Lưu ý rằng nếu i và i//j bằng nhau, chỉ cộng vào một trong hai.

## [Cà phê muối (THTB Sơn Trà, Đà Nẵng 2024)](https://lqdoj.edu.vn/problem/24strb3)
### Mô tả bài toán
- Có n khách hàng, mỗi khách hàng thứ arr[i] sẽ từ chối mua nếu giá sản phẩm lớn hơn arr[i].
- Yêu cầu: Tìm mức giá nhỏ nhất để đạt được doanh thu lớn nhất.

### Hướng làm bài
- Với tinh thần "KHÁCH HÀNG LÀ THƯỢNG ĐẾ", chúng ta sẽ quyết định giá bán dựa trên các mức giá mà khách hàng đưa ra.
- Đầu tiên, sắp xếp tăng dần các mức giá.
- Giả sử ta đang xét mức giá của khách hàng thứ i (0 <= i < n) là arr[i], nếu ta lấy mức giá này để bán thì tất cả các khách hàng từ i đến n-1 đều sẽ mua sản phẩm (vì mảng đang sắp xếp tăng dần).
- Doanh thu tương ứng sẽ là mức giá arr[i] nhân với số lượng khách hàng từ i đến n-1.
- Nếu doanh thu này lớn hơn doanh thu trước đó mà ta đã tìm được, ta cập nhật biến doanh thu lớn nhất, đồng thời mức giá nhỏ nhất là arr[i], vì ta đang sắp xếp mảng tăng dần nên mức giá đầu tiên cho cùng một doanh thu sẽ luôn là nhỏ nhất.

## [Bảng nhân](https://lqdoj.edu.vn/problem/bnhan)
### Mô tả bài toán
- Bảng số có kích thước n hàng và m cột, trong đó giá trị của mỗi ô được tính bằng tích của chỉ số hàng và chỉ số cột.
- Yêu cầu: In ra giá trị nhỏ thứ k trong bảng.

### Hướng làm bài
- Tính toán tất cả các giá trị i*j và lưu vào một mảng arr.
- Xác định vị trí cao nhất mà một giá trị x có thể đứng trong mảng arr bằng hàm f(x).
- Quan hệ giữa giá trị x và vị trí f(x) là tỉ lệ thuận: khi x tăng, f(x) cũng tăng, và ngược lại.
- Nếu f(x) = l, tức là x sẽ đứng trong khoảng từ 1 đến l.
- Mục tiêu là tìm giá trị của vị trí thứ k. Nếu x là giá trị mà f(x) >= k, thì x có thể là giá trị cần tìm.
- Do tỉ lệ thuận giữa x và f(x), nên x >= giá trị của vị trí thứ k (vì f(x) >= k) . Để x gần với giá trị của vị trí thứ k, ta sẽ giảm x.
- Nếu f(x) < k, tức là vị trí giá trị x không thể là k, và các giá trị nhỏ hơn x cũng vậy, vì thế ta tiến hành tăng x.

### Thuật toán
- Sử dụng thuật toán chặt nhị phân để tăng hoặc giảm giá trị của x.

## [Xếp diêm (THTA Sơn Trà, Đà Nẵng 2024)](https://lqdoj.edu.vn/problem/24stra3)
### Mô tả bài toán:
- Bài toán yêu cầu sử dụng một số lượng que diêm n cho trước để xếp thành một số nhỏ nhất và một số lớn nhất có thể.
- Số que diêm cần cho việc xây dựng các chữ số là:
- Số 1: 2 que
- Số 2: 5 que
- Số 3: 5 que
- Số 4: 4 que
- Số 5: 5 que
- Số 6: 6 que
- Số 7: 3 que
- Số 8: 7 que
- Số 9: 6 que
- Số 0: 6 que

### Hướng làm bài
- **Xây dựng số nhỏ nhất:**
- Để tạo số nhỏ nhất, ta sẽ cố gắng sử dụng ít chữ số nhất có thể. Do đó, ta sẽ ưu tiên sử dụng số 8 (số tốn nhiều que diêm nhất).
- Tuy nhiên, khi số que diêm còn ít hơn 14, cách tiếp cận này không còn phù hợp. Vì vậy, ta sẽ sử dụng số 8 cho đến khi số que diêm ít hơn 14, sau đó xử lí riêng.
- Gọi MIN[x] là số nhỏ nhất có thể xây dựng từ x que diêm (1 <= x < 14)
- Ta có:
MIN[0] = 0
MIN[1] = 1
MIN[2] = 1
MIN[3] = 7
MIN[4] = 4
MIN[5] = 2
MIN[6] = 6 // Lưu ý MIN[6] sẽ được giải thích ở dưới
MIN[7] = 8
MIN[8] = 10
MIN[9] = 18
MIN[10] = 22
MIN[11] = 20
MIN[12] = 28
MIN[13] = 68
MIN[14] = 88

- Số nhỏ nhất sẽ là số thu được từ MIN[n%7+7], sau đó ghép với các số 8. Có thể chỉ có một số 8 ở phía sau.
- MIN[6] phải bằng 6 chứ không được bằng 0, bởi vì MIN[n%7+7] được ưu tiên đứng trước các số 8 để tạo ra số nhỏ nhất. Điều này ngăn chặn số 0 đứng đầu.

- **Xây dựng số lớn nhất:**
- Để tạo số lớn nhất, ta muốn sử dụng nhiều chữ số nhất có thể, nên ta sẽ sử dụng số 1 (chỉ cần 2 que diêm) và thêm số 7 (chỉ cần 3 que diêm) nếu n là số lẻ.
- Nếu n chẵn, số lớn nhất sẽ có n//2 số 1.
- Nếu n lẻ, số lớn nhất sẽ có một số 7 và n//2-1 số 1.

## [Giao lưu THT 2024 lần 3 - Bài A bảng A](https://lqdoj.edu.vn/problem/24gl3a1)

### Mô tả bài toán

- Mỗi mảnh đất trong bài toán được xác định bằng hai tọa độ: góc trái trên và góc phải dưới.

- Bài toán đặt ra hai mảnh đất:
- Mảnh đất 1 có tọa độ (Ax1, Ay1) -> (Ax2, Ay2).
- Mảnh đất 2 có tọa độ (Bx1, By1) -> (Bx2, By2).

- Nhiệm vụ: Tìm và in ra tọa độ của mảnh đất Hình Vuông nhỏ nhất bao quát cả hai mảnh đất đã cho.

### Hướng làm bài

- Để tìm hình vuông nhỏ nhất bao quát cả hai mảnh đất, ta cần tìm hình chữ nhật nhỏ nhất trước.

- Để tìm diện tích hình chữ nhật, ta cần biết chiều dài và chiều rộng của nó:
- Để tìm chiều dài, ta cần hai điểm: điểm trái và điểm phải.
- Điểm trái sẽ có tọa độ x nhỏ nhất giữa (Ax1, Bx1).
- Điểm phải sẽ có tọa độ x lớn nhất giữa (Ax2, Bx2).
- Để tìm chiều rộng, ta cần hai điểm: điểm trên và điểm dưới.
- Điểm trên sẽ có tọa độ y lớn nhất giữa (Ay2, By2).
- Điểm dưới sẽ có tọa độ y nhỏ nhất giữa (Ay1, By1).

- Diện tích hình vuông nhỏ nhất bao quát cả hai mảnh đất sẽ bằng lớn nhất giữa chiều dài và chiều rộng của hình chữ nhật, bình phương kết quả này để có diện tích.

## [Đồng hồ (THTB Liên Chiểu 2024)](https://lqdoj.edu.vn/problem/24lchb2)

### Mô tả bài toán

- Trên một đồng hồ, có 60 vạch tượng trưng cho 60 phút.
- Kim phút đang đứng ở vị trí là **m** (phút).
- Hỏi sau **n** phút, vị trí đứng của kim đồng là bao nhiêu.

**Ví dụ:** Nếu kim đang đứng ở phút số 5, sau 10 phút, kim sẽ đứng ở phút số 15.

### Hướng làm bài

Đối với đồng hồ, vòng quay là một tính chất tự nhiên. Khi kim phút đi quay vòng, nếu vượt quá phút 59, nó sẽ quay trở lại 0, tạo ra một chu kỳ. Vì vậy, để xác định vị trí của kim phút sau **m** phút, ta thực hiện các bước sau:

1. Tính tổng của **n** phút và **m** phút.
2. Lấy phần dư của tổng trên khi chia cho 60.
3. Kết quả chính là vị trí mới của kim phút trên đồng hồ.

## [Giao lưu THT 2024 lần 3 - Bài B Bảng A](https://lqdoj.edu.vn/problem/24gl3a2
### Tính chất toán học
a % k == 0
b % k == 0
c % k == 0
--> (a+b+c) % k == 0

### Nhận xét
- Dựa vào tính chất trên, ta lấy một ví dụ.
- Nếu n được tách 3 số a, b và c (a, b, c đều chia k)
--> (a+b+c) % k == 0
Mà a, b, và c là các số hạng cấu thành số n
--> n % k == 0
Ví dụ: 12345 = {12, 3, 45}
12 * 1000 + 3 * 100 + 45*1
{12, 3, 45} % 3 == 0
--> 12345 % 3 == 0

### Thuật toán
- Ta kiểm tra nếu n không chia hết k
--> In ra 0 (vì sẽ không tách số n được)
- Ngược lại, thì ta bắt đầu tách.
- Ta lấy từng chữ số từ trái sang phải, nếu như các số ta vừa lấy chia hết cho k thì ta sẽ tách được một nhóm chia hết k.
Ví dụ: 12345
--> 1
--> 12 (có thêm nhóm {12}
--> 123 (có thêm nhóm {3}
--> 1234
--> 12345 (có thêm nhóm {45}
- Vậy ta có 3 nhóm {12} {3} {45}

## [Giao lưu THT 2024 lần 3 - Bài D bảng A, Bài B bảng B2](https://lqdoj.edu.vn/problem/24gl3b)
### Mô tả bài toán
- Cần mua a bóng xanh, b bóng đỏ.
- Bóng xanh giá x đồng
- Bóng đỏ giá y đồng
- Chi phí đổi giữa 2 màu là c

### Nhận xét
- Để mua a bóng xanh và b bóng đỏ, ta có các cách mua sau.
- Mua mà không đổi màu:
--> a*x + b*y
- Mua xanh hết rồi đổi qua đỏ:
--> a*x + b*(x+c)
- Mua đổ hết rồi đổi qua xanh:
--> a*(y+c) + b*y

## [Xếp sách (THTA Liên Chiểu 2024)](https://lqdoj.edu.vn/problem/24lcha3)
### Mô tả bài toán
- Cho một xâu gồm 3 chữ cái T, V, A được sắp xếp lộn xộn.
- In ra một xâu có các kí tự của xâu nhập vào nhưng, kí T được in trước, sau đó tới V, rồi tới A.

### Hướng dẫn làm bài
- Để in ra một kí tự, ta cần biết số lần xuất hiện của nó.
- Ví dụ muốn in ra kí tự 'T'.
- Ta tạo biến cT = 0 (để đếm số lần xuất hiện của kí tự T)
- Chạy từng phần tử trong xâu nhập để đếm số lần xuất hiện.
- In ra kí tự tự "T" với cT lần.
- Tương tự với 2 kí tự "V" và "A".

## [Số học (THTB Liên Chiểu 2024)](https://lqdoj.edu.vn/problem/24lchb4)
### Mô tả bài toán
- Cho một số n
- In ra số nhỏ nhất có 3 ước lớn hơn hoặc bằng n.

### Nhận xét
- Số có 3 ước, là một số chính phương mà có căn bậc 2 là số nguyên tố.
- Cho nên ta sẽ tìm số nguyên tố bằng từ căn n rồi bình phương lên.

### Hướng dẫn
- Xây dựng một hàm kiểm tra số nguyên tố
- Tạo i bằng căn của n ( lưu i cẩn thận đừng để i^2 nhỏ n)
- Kiểm tra xem i có phải là nguyên tố không, nếu có thì dừng lại -> In ra kết quả.
- Nếu không thì tăng i lên để tìm kiếm i lớn hơn.

## [Chữ số nguyên tố (THTB Liên Chiểu 2024) (Cách làm Python)](https://lqdoj.edu.vn/problem/24lchb3)
### Mô tả bài toán:

- **Input:** Nhận một số tự nhiên có rất nhiều chữ số.
- **Output:** Xuất ra các chữ số nguyên tố theo thứ tự từ trái sang phải. (Mỗi chữ số chỉ xuất hiện một lần duy nhất)

### Nhận xét, quan sát:

- Các chữ số nguyên tố là {2, 3, 5, 7}.
- Để kiểm tra một chữ số có phải là nguyên tố, ta chỉ cần xem xét xem nó có thuộc vào tập các chữ số nguyên tố hay không.

### Thuật toán:

- Khởi tạo một set **prime** chứa các chữ số nguyên tố: {2, 3, 5, 7}.
- Nhập số nguyên dưới dạng một chuỗi.
- Duyệt từng chữ số trong chuỗi số đó và chuyển nó thành số nguyên.
- Kiểm tra xem số đó có thuộc vào tập **prime** hay không:
- Nếu thuộc, in ra số đó cùng một dấu cách.
- Loại bỏ số đó khỏi tập **prime** để đảm bảo mỗi chữ số chỉ được in ra một lần duy nhất. (Code: `prime.remove(i)`)

## [Chữ số nguyên tố (THTB Liên Chiểu 2024) (Cách làm C++)](https://lqdoj.edu.vn/problem/24lchb3)
### Mô tả bài toán
- Input: Cho một số nguyên có rất nhiều chữ số
- Output: Một dãy số gồm các số nguyên tố có một chữ số. Được in ra theo thứ tự từ trái sang phải của số nhập vào. (Lưu ý, mỗi số chỉ in 1 lần)

### Nhận xét
- Ta chỉ ra tối 4 số

### Hướng dẫn làm bài
- Nhập n là một xâu.
- Tạo một set CSNT gồm 4 số {2, 3, 5, 7}
----> set<ll> CSNT = {2, 3, 5, 7};
- Chạy lần lượt từ trái sang phải các kí tự của n.
- Ví dụ kí tự hiện tại đang xét là c
- Chuyển kí tự c đang xét sang số nguyên.
- Kiểm tra xem c có thuộc set CSNT.
----> `if (CSNT.find(c) != CSNT.end())`
- Nếu thuộc thì nó là chữ số NT, ta in nó ra. Sau đó ta xóa nó ra khỏi set.
----> `CSNT.erase(c)`

## [Tính tổng dãy số (THTA Liên Chiểu 2024)](https://lqdoj.edu.vn/problem/24lcha4)
### Mô tả bài toán:
- Ta có tổng: S = -1 + 2 -3 + 4 ... + N*(-1)^n
- Tính S

### Nhận xét:

- Nếu N chẵn
- S = -1 + 2 - 3 + 4 - 5 + 6 + - 7 + 8 + ... -(N-1) + N
= 1 + 1 + 1 + 1 + ... + 1
= (N / 2) * 1

- Nếu N lẻ:
- S = -1 + 2 - 3 + 4 - 5 + 6 + - 7 + 8 + ... - (N-2) + (N-1) - N
= (-1+2) + (-3+4) + (-5+6) + (-7+8) + ... (-(N-2) + (N-1)) - N
= 1 + 1 + 1 + 1 + ... + 1 - N
= (N-1)/2 - N

## [Chữ số nguyên tố (THTB Liên Chiểu 2024)](https://lqdoj.edu.vn/problem/24lchb3)
### Mô tả bài toán:
- Nhập vào một số nguyên n.
- In ra các chữ số nguyên tố theo thứ tự từ trái sang phải.
- Lưu ý chỉ liệt kê mỗi số 1 lần

### Xây dựng hàm
- Kiểm tra xem 1 chữ số có phải là số nguyên tố không.
- Ta chỉ cần kiểm xem nó có bằng 2, 3, 5 hoặc 7 không.

### Hướng làm bài
- Tạo vector ans để liệt kê các chữ số nguyên tố.
- Ta sử dụng hàm hàm trên để kiểm tra xem 1 chữ số có phải là nguyên tố.
- Nếu nó là nguyên tố thì ta phải kiểm tra thêm là nó đã xuất hiên chưa bằng một cái map<ll, bool> đặt là had.
- Nếu had[a[i]] = true --> a[i] đã xuật hiện
- Mặc định, ban đầu had[a[i]] = false --> a[i] chưa xuất hiện.
- Nếu a[i] là số nguyên tố và a[i] chưa xuất hiện thì ta thêm a[i] vào vector ans và đặt had[a[i]] = true
- Sau đó in các chữ số đã liệt kê trong vector ans ra.

### Hướng dẫn thêm:
- Cách lấy chữ số cuối trong số N. Gọi số đó là D.
---> D = N % 10 Sau đó N /= 10
- Lưu ý là nhớ reverse ans vì ta đang lấy từ phải sang trái.

## [Đổi quà (THTA Thanh Khê 2024)](https://lqdoj.edu.vn/problem/24tkha4)

#### Mô tả bài toán
- Cho 4 số nguyên n, a, b, c.
- Có 2 loại chai, loại a có giá là a đồng một chai và loại b có giá là b đồng một chai.
- Nếu đưa cửa hàng một cái vỏ chai loại b, bạn sẽ nhận được c đồng giảm giá cho mỗi chai loại b bạn mua sau đó.
- Bạn có thể mua chai theo 2 cách:
1. Mua loại a trước, sau đó mua loại b.
2. Mua loại b trước, sau đó mua loại a.
- Bạn cần tính số chai nhiều nhất có thể mua được với số tiền n.

#### Giải thích thuật toán
- Nếu số tiền không đủ để mua cả 2 loại chai (n < a và n < b), số chai mua được là 0.
- Nếu chỉ đủ tiền mua loại a (n >= a and n < b), số chai mua được là n // a.
- Nếu chỉ đủ tiền mua loại b (n >= b and n < a), số chai mua được là (n - b) // (b - c) + 1.
- Lấy (n - b) là bởi bạn/ sẽ dùng n đồng mua trước 1 chai loại b, sau đó mỗi chai sau này chỉ cần tốn (b - c) đồng (vì được giảm giá c đồng nếu bạn đưa cho cửa hàng 1 vỏ chai cũ). Vì vậy ta lấy số tiền còn lại chia cho (b - c). Sau đó, cộng thêm 1 là bởi (n - b) // (b - c) là số chai mua khuyến mãi, cộng thêm 1 chai ban đầu không có khuyến mãi.
- Nếu có đủ tiền mua cả 2 loại chai (n >= a và n >= b), số chai mua được sẽ là tổng hợp của 2 trường hợp trên theo 2 cách:
1. Mua loại a trước rồi mua loại b (d1).
2. Mua loại b trước rồi mua loại a (d2).
Cách tính d1:

        d1 = n // a
        n1 = n % a # tiền dư sau khi mua loại a trước
        if (n1 >= b):
        d1 += (n1-b)//(b-c)+1

Cách tính d2:

        d2 = (n-b)//(b-c)+1
        n2 = n - d2*(b-c)  # tiền dư sau khi mua loại b trước
        d2 += n2 // a

- Ta so sánh d1 và d2, sau đó in ra số chai nhiều nhất.

#### Code giải quyết bài toán:

?? # Đọc hướng rồi tự code cho quen nhé, chứ chép nhiều không hay đâu 😅

## [Xếp chữ cái (THTA Thanh Khê 2024)](https://lqdoj.edu.vn/problem/24tkha3)

- Nhập độ dài của dãy 1 từ bàn phím và gán giá trị này cho biến n1.
n1 = int(input())

- Nhập chữ cái của Tom từ bàn phím và gán giá trị này cho biến c1, loại bỏ các khoảng trắng ở đầu và cuối chuỗi (nếu có).
c1 = input().strip()

- Nhập độ dài của dãy 2 từ bàn phím và gán giá trị này cho biến n2.
n2 = int(input())

- Nhập chữ cái của Jerrry từ bàn phím và gán giá trị này cho biến c2.
c2 = input().strip()

- Nhập chỉ số k từ bàn phím và gán giá trị này cho biến k.
k = int(input())

# Kiểm tra nếu k nhỏ hơn hoặc bằng độ dài của dãy 1.
if k <= n1: 
    # Nếu ký hiệu của dãy 1 là 'A'
    if c1 == 'A':
        # In ra k kí tự A trong xâu của Tom
        print(k)
    # Nếu ký hiệu của dãy 1 là 'B'.
    else:
        # In ra giá trị 0, vì không có chữ A nào trong xâu của Tom
        print(0)
# Nếu k lớn hơn độ dài của xâu Tom viết
else:
    # Nếu ký hiệu của dãy 1 là 'A'.
    if c1 == 'A':
        # Nếu ký hiệu của dãy 2 là 'A'.
        if c2 == 'A':
            # In ra kết quả là tổng của n1 và k-n1, lấy 2 phần gồm bên trái và bên phải (tức cả trong xâu của Tom và Jerry)
            print(n1 + (k-n1))
        # Nếu ký hiệu của dãy 2 là 'B'.
        else:
            # In ra giá trị của n1, chỉ lấy trong xâu của Tom
            print(n1)
    # Nếu ký hiệu của dãy 1 là 'B'.
    else:
        # Nếu ký hiệu của dãy 2 là 'A'.
        if c2 == 'A':
            # In ra kết quả là k-n1, chỉ lấy trong xâu của Jerry
            print(k-n1)
        # Nếu ký hiệu của dãy 2 là 'B', không có chữ A nào để lấy
        else:
            # In ra giá trị 0.
            print(0)

## [Hội khỏe phù đổng (THTA Thanh Khê 2024)](https://lqdoj.edu.vn/problem/24tkha2)

Ta có hình vẽ sau:
- Hình tròn màu đỏ tượng trưng cho những học sinh chơi cờ vua.
- Hình tròn màu xanh tương trưng cho những học sinh chơi bóng bàn.

- Theo đề:
- Y là số học sinh chơi cờ vua, nó bao gồm 2 phần: những học sinh chỉ chơi cờ vua (phần a) và những học sinh chơi cả cờ vua và bóng bàn (phần b).
--> Y = a + b
- Tương tự với Z là những học sinh chơi bóng bàn, ta có:
--> Z = b + c
- X là tất cả học sinh tham gia nên ta gộp cả 3 phần lại:
--> X = a + b + c

Tính số học sinh chơi cả 2 môn, tức là ta đang đi tìm b.
- Y + Z = a + b + b + c = (a+b+c) + b
- X = (a+b+c)
==> b = Y+Z - X

Xét trường hợp đặc biết, số học sinh chơi một môn nào đó không được lớn hơn tổng số học sinh tham gia nên nếu:
- Y > X hoặc Z > X ta in ra -1, ngược lại in ra kết quả ở trên.

## [Độ tương đồng của chuỗi](https://lqdoj.edu.vn/problem/equivalent)
### Mô tả bài toán
- Có 2 xâu, cho biết độ tương đồng của nó
- Độ tương sẽ dựa trên số lượng kí tự mà chúng đều có
- Ví dụ:
S1 = "abbccd"
S2 = "abbedfbcd"
-> Độ tương đồng: 5
Bởi vì:
- Có chung 1 chữ a
- Có chung 2 chữ b
- Có chung 1 chữ d
- Có chung 1 chữ c

# Nhận xét:
- Nếu xâu S1 có 'd1' kí tự 'c', S2 có 'd2' kí tự 'c' thì 2 xâu sẽ có chung min(d1, d2) kí tự 'c'.
- Vậy để làm bài ta chỉ cần đi đếm số lần xuất hiện của các kí tự trong 2 xâu. Rồi lấy min của số lượng kí tự ít hơn trong 2 xâu.

## [Excel](https://lqdoj.edu.vn/problem/olp5excel)

- Từ một kí tự số ta trừ cho 48 để về chỉ số
- Từ một kí tự chữ ta trừ cho 65 để về chỉ số

- Bước 1: Lấy thao tác (MAX hay SUM):

string opr = ""; // operation
opr += cal[i] (i: 0 -> 2)
// cal là phép tính ta đang xứ lí (Ví dụ MAX(A2, B3))

- Bước 2: Chuyển từ B6 -> 5,1

    '0' - '0' -> 0
    '9' - '0' -> 9
    'A' - 'A' -> 0
    'B' - 'A' -> 1
    ll col1 = cal[4] - 'A'
    ll row1 = cal[5] - '0' - 1;
    ll val1 = arr[row1][col1]
    // Ta đi tìm giá trị thứ 2 (val2) bằng phương pháp tương tự.

Bước 3: Thực hiện phép tính dựa vào những giá trị đã có

## [Số nhỏ thứ k](https://lqdoj.edu.vn/problem/sortcb02)

Vì ta sẽ nhập mảng bắt đầu từ 0 nên
- Khi K = 4. Sổ nhỏ thứ 4: arr[3]
- Khi K = 5. Số nhỏ thứ 5: arr[4]
- Khi K = 9. Số nhỏ thứ 9: arr[8]
--> Số nhỏ thứ k: arr[k-1]

Bước 1: Nhập n và k.
Bước 2: Nhập mảng arr.
Bước 3: Sắp xếp mảng arr tăng dần.
Bước 4: In ra số nhỏ thứ k.

## [Mua xăng](https://lqdoj.edu.vn/problem/swcbuygas)
### Hướng làm
- Ta cần mua N lít xăng, đi tới tiệm xăng, ta thấy có 2 loại:
- Nếu như anh mua 1 can loại 1 lít thì phải trả 'a' đồng
- Nếu như anh mua 1 can loại 2 lít thì phải trả 'b' đồng

- Giờ ta sẽ xem là mua can loại nào thì rẻ hơn.

- Nếu như mua can loại 1 lít
- Thì cần mua bao nhiêu can?
----> N Can
- Mà 1 can loại 1 lít là a đồng
Tổng tiền nếu mua can loại 1 lít: "a*n" đồng

- Nếu như mua can loại 2 lít:
- Nếu N chẵn thì số can cần mua là?
--> N/2 can loại 2 lít
- Mà 1 can loại 2 lít là b đồng
--> Tổng tiền khi mua ở trường hợp này: b*N/2

- Nếu N lẻ thì số can cần mua là?
--> N/2 + 1 (can loại 1 lít)
- Mà 1 can loại 1 lít là a đồng
--> Tổng tiền khi mua ở trường hợp này: N/2*b + a

## [Chất điểm](https://lqdoj.edu.vn/problem/olp5pmeet)

### Giải thích bài toán
Lưu ý: dùng double (C++) hoặc float (Python) thay cho long long

x1 là vị trí người 1
x2 là vị trí người 2

v1 là vận tốc người 1
v2 là vận tốc người 2

t là khoảng thời gian mà 2 người sẽ gặp nhau

x là chỗ 2 người gặp nhau

Sau t giây thì người 1 tới x, tức là:
x1 + v1*t = x (*)
Sau t giây thì người 2 cũng tới x, tức là:
x2 + v2*t = x (**)
---> Từ (*) và (**), suy ra:
x1 + v1*t = x2 + v2*t
==> x1 - x2 = v2*t - v1*t
==> x1 - x2 = (v2-v1)*t
==> t = (x1-x2)/(v2-v1)

Vậy thời gian để hai người gặp nhau được tính bằng công thức:
`t = (x1-x2)/(v2-v1)`

### Xét các trường hợp sau để giải bài
TH1: x1 == x2, cần 0 giây để gặp nhau

TH2: x1 != x2 and v1 == v2, không thể gặp nhau

Ngang đây mới tính t, nếu tình t ở trường hợp 2 sẽ bị lỗi Runtime Error vì:
t = (x1-x2)/(v2-v1)
Mà v1 == v2 --> v2-v1 = 0
--> Lỗi chia cho số 0

TH3: Nếu tính ra t, mà t âm, tức là không thể gặp nhau

TH4: Ngoài trường hợp trên, thì t là đáp án cần tìm

## [Tìm các số chia hết cho 3](https://https://lqdoj.edu.vn/problem/cb01)


Đáp án của bài là: P[b] - P[a-1]

## [Trị tuyệt đối](https://https://lqdoj.edu.vn/problem/div2aorangevol2)

/C-A/
-> khoảng cách từ điểm C đến điểm A
/B-C/
-> khoảng cách từ điểm C đến điểm B

Yêu cầu đề: |C-A| = |B-C|
-> khoảng cách từ điểm C đến điểm A bằng
khoảng cách từ điểm C đến điểm B

-> C là điểm nằm chính giữa của A và B
-> C = (A+B)/2
* Đề yêu cầu C là một số nguyên nên tổng (a+b) phải là 1 số chẵn
-> (A+B) % 2 == 0

## [Tìm các số chia hết cho 3 trong đoạn a, b](https://lqdoj.edu.vn/problem/scrcb02)

* Số lượng số chia hết cho 3, từ 1 -> x:
-> Công thức tính: x/3
* Gọi P[x] là số lượng số chia hết cho 3 từ 1->x.
-> P[x] = x/3

- Pb là số lượng số chia hết cho 3 từ 1->b
- Pa là số lượng số chia hết cho 3 từ 1->a
-> Vậy đáp án số lượng số chia hết cho 3 từ a->b: P[b]-P[a-1]

* Lưu ý: Nhiều bạn sẽ nhầm là P[b] - P[a] nhưng nếu tính như vậy ta sẽ mất đi số a. (Tính chất này tương đồng với kĩ thuật Prefix Sum)

## [Tổng bội số](https://lqdoj.edu.vn/problem/scrtongboi)

- Số lượng số chia hết cho k từ 1 đến x được tính bằng công thức: `x/k` (gọi là `p[x]`).
- Số lượng số chia hết cho k từ a đến b:
- `pab = p[b] - p[a-1] = b/k - (a-1)/k`
- Số cặp số chia hết cho k từ a đến b:
- `so_cap = pab/2`
- Để tìm số đầu tiên chia hết cho k: `a += (k-(a%k))%k`
- Để tìm số cuối cùng chia hết cho k: `b -= b%k`
- Tổng của một cặp là: `t = (a+b)`
- Đáp án: `t*so_cap` (lấy tổng 1 cặp nhân cho số lượng cặp)

## [tongboi2](https://lqdoj.edu.vn/problem/tongboi2)
- Tương tự như bài tổng bội ở trên, nhưng hãy xem xét lại từng công thức:

- Tìm số lượng số chia hết cho k từ l->r: r/k -(l-1)/k
- Số lượng cặp số chia hết cho k: (r/k -(l-1)/k)/2.0
- Công thức tính tổng 1 cặp: l+r (nhớ xử lí l, r trước để l, r luôn chia hết cho k như bài trên)

- Ta thấy răng cả 3 công thức trên chia có công thức tính số cặp là trả về kết quả số thực. Nhưng mà trong C++, có thể xảy ra lỗi làm tròn số thực dấu chấm động, do máy tính không thể biểu diễn chính xác số thập phân vô hạn. Vậy hãy thử suy nghĩ thử xem có cách nào để ta không phải dùng kiểu double khi tính toán, tức là chỉ tính toán với các số nguyên và chia lấy nguyên nhưng vẫn ra kết quả chính xác.

- Ta thử gộp để tính trong 1 công thức, vậy tổng tất cả các số chia hết cho k từ l->r được tính bằng:
- (l+r)*(r/k -(l-1)/k)/2.0
--> tổng 1 cặp nhân cho só lượng căp
* Ta thấy có số 2.0, tức là phép tính này sẽ sử dụng kiểu double, và sẽ xảy ra trường hợp làm tròn không chính xác.

* Để tránh việc đó, ta chuyển công thức lại thành:
- (l+r)*(r/k -(l-1)/k)/2
-> Ở đây, ta nhân trước rồi mới chia

* Bởi vì ta có thể chứng minh được (l+r)*(r/k -(l-1)/k) luôn ra kết quả là một số chẵn. Cứ xét hợp trường hợp của l, r là thấy rõ.

* Vì vậy ta có thể tiếp tục chia lấy nguyên cho 2 và nhận được kết quả chính xác.

## [Đánh giá số đẹp](https://lqdoj.edu.vn/problem/1920sodep)

* Gọi biến T là tổng các chữ số của N. (Ban đầu khởi tạo T = 0)
* Lấy chữ số cuối cùng của một số N (N % 10) cộng vào T.
* Loại bỏ chữ số cuối cùng của một số N => N // 10
* Lặp lại các thao tác trên cho đến khi N == 0.

## [Ước có ước là 2](https://lqdoj.edu.vn/problem/k16)

* Lưu ý: xử lí từng test case.

* Tìm tất cả ước của n:
* Chạy 1 vòng for i từ 1 -> round(sqrt(n))
* Nếu n chia hết cho i, thì ta có 2 ước d1 và d2
* Trong đó d1 = i, d2 = n/i
* Ta kiểm tra từng ước xem ước nào là chẵn thì tăng đếm lên
* Lưu ý, nếu 2 ước bằng nhau và đều là số chẵn thì giảm đếm lui 1.
* In ra đếm

## [KT Số nguyên tố](https://lqdoj.edu.vn/problem/ktprime)

* Code: https://pastie.io/hgxebw.xls

* Ta đã biết, số Nguyên tố là số chỉ có 2 ước là 1 và chính nó.
* Vậy nếu ta xét số n.
* Nếu n nhỏ hơn 2 thì n không phải số nguyên tố, ta return false.
* Nếu nó là số nguyên tố thì nó chỉ có 2 ước là 1 và n.
* Dựa vào điều này, ta kiểm tra xem đoạn từ 2 -> n-1.
* (Ta không chạy từ 1 vì n luôn chia hết cho 1)
* (Ta không chạy tới n bởi vì n luôn chia cho n)
* (Và 1 và n là 2 ước duy nhất của 1 số Nguyên tố)
* Nếu n chia hết cho bất kì số nào trong đoạn thì n không phải là số Nguyên tố.
* Ngược lại, nếu n không chia hết cho bất kì số nào khác thì n là số Nguyên tố.

* Nếu chạy i từ 2 -> n-1 thì sẽ gặp lỗi TLE.
-> Ta xử lí bằng cách chạy từ 2 -> round(sqrt(n))

## [Số hoàn hảo](https://lqdoj.edu.vn/problem/primes)

* Code: https://pastie.io/vimdqz.xls

* Tìm tất cả các i từ 1 -> round(sqrt(n))
* Nếu n chia hết cho i, ta có 2 ước là: d1 = i, d2 = n/i
* Nếu 2 ước đó khác nhau thì ta cộng cả 2 vào tổng
* Nếu 2 ước đó giống nhau thì ta chỉ cộng 1 trong 2 vào tổng.
* Cuồi cùng chỉ cần kiểm tra nếu tồng = 2*n, ta in YES, ngược lại NO

## [Số nguyên tố](https://lqdoj.edu.vn/problem/primes)

* Duyệt tất cả các số trong mảng
* Kiểm tra từng số xem nó có phải là số nguyên tố không.
* Nếu có so sánh với giá trị lớn nhất hiện tại để tìm ra kết quả.

## [Ước chung đặc biệt](https://lqdoj.edu.vn/problem/mcd)
* Code: https://pastie.io/vimdqz.xls
* Trước tiên ta phải ây dựng một hàm tính tổng các chữ số của một số n:
* Bước 1: chuyển đổi số n thành một xâu s
* Bước 2: cộng tất cả kí tự số trong s vào một tổng 't' ('t' là một biến tổng)
* Lưu ý: ta phải chuyển kí tự của s sang kiểu int rồi mới cộng được vào tổng 't'

* Sau đó ta đi tìm ước chung của a và b:
* Việc này khá dễ dàng, ta tìm tất cả các ước của a, gọi ước đó là 'i', nếu b cũng chia hết cho 'i', thì 'i' là ước chung của a và b

* Ta tìm tổng chữ số lớn nhất của số 'i' ở trên nữa là xong. (Tìm bằng một biến max)
* In ra max.

* Tìm tất cả ước chung của a và b:
* Tìm tất cả các ước của a.
(nếu a % i == 0, thì có 2 ước là i và a/i)
* Rồi nếu b cũng chia hết cho các ước đó thì đó là ước chung.
* So sánh tổng các chữ số của ước chung đó với biến kết quả. (sử dụng hàm tổng chữ số đã xây dựng ở trên)

## [Số nguyên tố](https://lqdoj.edu.vn/problem/primes)

* Xây dựng hàm kiểm tra số nguyên tố của một số n, trả về kết quả là true (Nếu n là NT), ngược lại trả về false:
* Nếu n nhỏ hơn 2 thì trả về false. (số nhỏ hơn 2 thì không phải là số NT)
* Duyệt i từ 2 đến căn của n, nếu n chia hết cho một số i bất kì thì return false.
* Nếu n **không chia hết cho số i nào cả** thì mình return true.

* Tìm số nguyên tố bằng hàm đã tạo
* Duyệt một vòng for nữa để in ra chỉ số của số nguyên tố lớn nhất đó

## [UCLN với N](https://lqdoj.edu.vn/problem/gcdx)

* Tạo biến đếm bằng 0.
* Chạy một vòng for x từ 1 đến n, kiểm tra nếu gcd(x, n) == p thì tăng đếm lên.
* In ra đếm.

## [ƯCLN với bước nhảy 2](https://lqdoj.edu.vn/problem/gcdinc2seq)

* Hint 1: Xét trường hợp x là số lẻ
* Hint 2: Xét trường hợp x là số chẵn
* Trường hợp đặc biệt: k = 0

## [gcd( a -> b)](https://lqdoj.edu.vn/problem/kh05)

* Hint 1 (Quan sát): Vì dữ liệu đầu vào rất rất lớn nên ta không thể dùng for hay dùng long long int.
* Hint 2: Thử tìm ước chung lớn nhất của 1 dãy liên tiếp nhau.
* Hine 3: Nếu a = b, thì dãy của ta chi gồm 1 số, và ước chung lớn nhất dãy là chính số đó.

* Giải:
* Nếu a != b, thì ước chung lớn nhất của dãy liên tiếp là 1.
* Ngược lại (a == b), thì dãy chỉ có duy nhất 1 phần tử, và UCLN là chính số đó. (a hoặc b)

## [number of steps](https://lqdoj.edu.vn/problem/kh03)
* Điều kiện vòng lặp: (a != 0 && b != 0)
* Thực hiện theo đề:
* Nếu a > b, thì gán a = ...
* Ngược lại (b >= a), thì gán b = ...
* Tăng đếm ở trong vòng lặp.

* Cách làm nhanh hơn tránh lỗi TLE:
* Điều kiện vòng lặp tương tự ở trên.
* Trường hợp a > b:
* Nhưng thay vì phải lấy a = a-b (khi a > b) thì ta rút ngắn thời gian chạy bằng cách a = a % b;
* Như vậy, số lượng thao tác tăng lên 1 đoạn là: a/b
* Trường hợp b > a ngược lại ở trên.

## [Cộng trừ trên Module](https://lqdoj.edu.vn/problem/addmodul)

- Đơn giản thực hiện truy vấn theo đề.
- Nhưng sau khi thực hiện 1 truy vấn:
- Nếu số đó quá nhỏ (< 0), ta cộng nó lên 'mod'. (Nghĩ nôm na là cho nó bớt nhỏ)
- Nếu số đó quá lớn (>= mod), ta trừ nó đi 'mod'. (Nôm na là cho nó bớt lớn đi)

- In ra kết quả cuối cùng.

## [Tích lấy dư (HSG9-2016, Hà Nội](https://lqdoj.edu.vn/problem/16hsg9hn1)

* Nhập ba dòng
* Dòng 1: nhập a, b, c
* Dòng 2: nhập d, e, f
* Dòng 3: nhập g, h, i
* Sau đó tính như công thức của đề, nhớ chia liên tục để tránh tràn số.

## [Doraemon và cuộc phiêu lưu ở hòn đảo kho báu (Bản dễ)](https://lqdoj.edu.vn/problem/adventure1)

* Sử dụng 2 vòng for i và for j lồng nhau. Biến i, j nằm trong khoảng [l, r] (l <= i, j <= r)
* Tìm số chuối dư:
* rem = i*j % m
* Tìm giá trị dư nhỏ nhất:
* ans = min(ans, rem)
* In ra ans

## Ước số chung nhỏ nhất (HSG12'19-20)
* Tìm ước chung lớn nhất của dãy:
* Lưu ý: gcd(0, x) = x
* Dựa vào lưu ý trên, ta tạo một biến g. (g này sẽ UCLN của dãy)
* Ta tìm giá trị của g bằng cách:
* Ban đầu đặt g = 0.
* Ta tìm giá trị ước chung lớn nhất g bằng cách, duyệt từng phần tử trong mảng, đặt:
* g = gcd(g, a[i]) // a[i] là phần tử trong mảng
* Sau khi tìm được g là UCLN của dãy, ta tìm ước nhỏ nhất của g, gọi ước nhỏ nhất đó là D, khi đó D đồng thời là ước nhỏ nhất của mảng.
* Tìm D bằng cách:
* Chạy vòng lặp i từ 2 đến g:
* Nếu g chia hết cho i, ta đặt D = i và ngay lập tức break.
* Vì i đi từ nhỏ đến lớn, ta ngắt vòng lặp để giữ i là ước nhỏ nhất khác 1 của g.

[
Chia táo 2](https://lqdoj.edu.vn/problem/math14)

* Số táo dư: n % m
* Cần đủ m quả táo cho m người
* Vậy số táo thiếu: m - n%m
* Đồng thời, số tào cần thêm cũng là: m - n%m

* Ta phải xét trường hợp nếu không có táo dư, thì ta không cần táo nữa => In ra 0
* Ngược lại in ra số táo dư ở công thức trên.

## [Doraemon và cuộc phiêu lưu ở hòn đảo kho báu (Bản khó)](https://lqdoj.edu.vn/problem/adventure2)

- Ta đã biết rằng, khi chia lấy dư cho M thì kết quả trả về
nằm trong đoạn [0, M-1].
- Buổi trước ta cũng đã chứng minh được rằng, trong một đoạn gồm M số liên tiếp (hoặc hơn M số liên tiếp) thì sẽ luôn
có một số chia hết cho M, tức là kết quả phép dư = 0.
-> Dựa vào điều này, ta kiểm tra nếu đoạn L->R chứa M số trở lên, ta in ra 0. (0 là giá trị nhỏ nhất của một phép chia lấy dư)
- Ngược lại, tức đoạn L->R chứa ít hơn M số thì sao, ta chú ý vào ràng buộc của bài. (1 <= M <= 2000)
=> Đoạn từ L tới R chứa ít hơn 2000 số; 1 <= L, R <= 2000
=> Với ít hơn 2000 số, ta dễ dàng tính được bằng cách dùng 2 vòng for lồng nhau tương tự phiên bản dễ của bài.

## [Mã số](https://lqdoj.edu.vn/problem/c11)
* Gọi a[i] là số tối đa cấp cho người i. (i = 0 -> n-1)
* Ta sắp xếp mảng a tăng dần để phát cho người a[i] nhỏ trước. Để tránh trường hợp người i bị hết số.
* Bắt đầu phát cho người i từ 0 -> n-1, số cách phát cho người i là: a[i]-i
* Giải thích: a[i] là số cách phát cho người đó, nhưng trước đó đã phải phát cho i người, nên là phải trừ ra.
* Nhân cho kết quả, sau đó lấy dư cho số 10 mủ 9 + 7.

## [Số thân thiện](https://lqdoj.edu.vn/problem/thanthienso)

- Trước tiên, xây dựng hàm đảo ngược số nguyên N, thuật toán như sau:
- Thực hiện vòng lặp cho đến khi N > 0:
- Lấy số cuối cùng của N (N % 10)
- Bỏ vào sau biến kết quả (res += N % 10)
- Sau đó, liền nhân 10 res để tạo một chỗ trống cho số sau.
- Loại bỏ số cuối cùng của N vừa được ta thêm vào kết quả.

- Sau khi thực hiện vòng lặp, ta sẽ bị dư 1 số 0 ở cuối, do ta đã chừa 1 chỗ cho số tiếp theo nào đó, vì vậy chỉ cần loại bỏ số 0 này, thì ta sẽ được đáp án chính xác.

- Sau khi xây dựng hàm ta chỉ cần tìm UCLN của N và số đảo ngược N, nếu kết quả ra 1 thì in ra YES, ngược lại in ra NO.

## [FNUM](https://lqdoj.edu.vn/problem/findnum)
- Giả sử trường hợp xấu nhất là N gồm 1 triệu số 9.
- Vậy tổng các chữ số của n tối đa là 9 triệu.
- Lưu ý: n đang là string
- Tình tổng các chữ số của N bằng hàm tính tổng các chữ số của 1 string. Tổng này tối đa 9 triệu, đã giải thích ở trên.

- Thì ta thấy, kết quả này có thể tính tiếp bằng hàm tính tổng các chữ số của một số nguyên int.

- Tìm tất cả các số mà Đăng thích, điều kiện của các số này là tận cùng khác 3 và không chia hết -cho 3.
- Khi nhìn vào ràng buộc của đề là ta chỉ cần tìm 1000 số.
- Sau khi tìm 1000 số, ta chỉ việc đọc dữ liệu và in ra số thứ k.

Pseudo code -> Mã giả

// Tìm 1000 số mà Đăng thích
Cnt = 0 // đếm số lượng số Đăng thích đã tìm được
Vector<int> arr // vector để lưu những số Đăng thích
i = 1 // biến i để tìm những số mà Đăng thích
While (cnt < 1000) {
	If (i là số đăng thích) {
	    Đẩy i vào vector arr để lưu lại số i
		Tăng cnt lên
	}
	Tăng i lên
}

* Hàm tính tổng các chữ số của 1 xâu:

int tong_chu_so(string n) {
    int tong = 0;
    while (n.empty() == false) { // thực hiện khi xâu chưa rỗng
        tong += n.back() - '0'; // chuyển về số rồi cộng vào tổng
        n.pop_back(); // vứt kí tự cuối cùng
    }
    return tong;
}

## [Số may mắn](https://lqdoj.edu.vn/problem/thtkvmn22a3)

#include <iostream>

using namespace std;
/*
Số không may mắn là số chia hết cho 5 hoặc
chia 5 dư 3

Số may mắn là số chia không hết cho 5 và chia 5
dư khác 3
*/

int main() {
  // nhập n
  // tạo tổng bằng 0
  // duyệt tất cả các số từ 1 tới n-1
  // kiểm tra nếu nó là số may mắn, điều kiện
  // ở trên -> thì cộng nó vào tổng.
  // In ra tổng
  return 0;
}

## [GCD & LCM](https://lqdoj.edu.vn/problem/gcdlcm)

Tìm: a, b, c, d

Điều kiện:
* a + b + c + d = n
* gcd(a, b) = lcm(c, d)

Nếu a = 1, b = n-3
gcd(1, n-3) = 1
=> gcd(a, b) = 1

Nếu c = 1, d = 1
lcm(1, 1) = 1
=> lcm(c, d) = 1

=> gcd(a, b) = lcm(c, d)
Và a + b + c + d = 1 + n-3 + 1 + 1 = n
=> Bộ a, b, c, d thõa mãn điều kiện, vậy ta in ra bộ: 1, n-3, 1, 1

## [Số thân thiện](https://lqdoj.edu.vn/problem/thanthienso)

- Hàm reverse một số nguyên long long:

long long reverse(long long n) {
    long long res = 0;
    while (n > 0) {
        res *= 10; // 
        res += n % 10;
        n /= 10;
    }
    // res là số đảo ngược của n
    return res;
}

## [Số Đặc Biệt](https://lqdoj.edu.vn/problem/kh07)
### Hướng dẫn sơ bộ
A[1]%K = A[2]%K = A[3]%K = ... = A[N]%K = D

A[1] % K = D
A[2] % K = D
A[3] % K = D
...
A[i] % K = D
...
A[n] % K = D

A[1] % k - A[2] % k = D - D
(A[1] - A[2]) % k = 0
=> A[1] - A[2] chia hết cho k
=> k là ước của (A[1] - A[2])

Chứng minh tương tự
=> k cũng là ước của (A[2] - A[3])
=> k cũng là ước của (A[3] - A[4])
=> k cũng là ước của (A[4] - A[5])
...
=> k cũng là ước của (A[n-1] - A[n])

Gọi B là dãy (A[i] - A[i+1]) với i chạy từ 1 đến n-1

=> k là ước chung của B

Vậy ta phải tìm tất cả các ước chung của B

Trước tiên, ta phải tìm ước chung lớn nhất của B

Sau đó tìm tất cả các ước của UCLN đó, các ước đó là ước chung của B. (Khi nó là ước của UCLN thì nó là UC)

### Hướng làm bài
A[1]%K = A[2]%K
A[1]%k - A[2]%k == 0
A[1] * 1%k - A[2] * 1%k == 0
(A[1]-A[2]) % k == 0

=> k là ước của abs(A[1]-A[2])

CMTT: k là ước của abs(A[2] - A[3]

CMTT: k là ước chung của abs(A[i] - A[i+1]) (i: 1-> n)

Nếu nó là ước của UCLN thì nó là UC

### Thuật toán
- Bước 1: Nhập

- Bước 2: Xây dựng mảng brr bằng abs(arr[i]- arr[i+1])

- Bước 3: Tìm UCLN của mảng brr
brr[i] = abs(arr[i] - arr[i+1]
(i = 0 -> n-2)

- Bước 4: Tìm ước của UCLN đó
vector<ll> ans;
for (ll i = 1; i*i <= n; ++i)
if (n % i == 0) {
ll d1 = i, d2 = n/i;
if (d1 != d2)
push_back cả 2 cái
else
push_back 1 cái
}
Vì cần in ra theo tăng dần, nên ta sort lại

- Bước 5: In kết quả

## [CATBIA](https://lqdoj.edu.vn/problem/catbia)
Giải thích:
- X, Y lần lượt là chiều dài và chiều rộng hình chữ nhật.(2 giá trị này ta nhập từ input)
- Gọi A là cạnh hình vuông được cắt ra từ hình nhữ nhật.
- Để khi cắt ra chiều dài không bị dư thì X phải chia hết cho A
- Để khi cắt ra chiều rộng không bị dư thì Y phải chia hết cho A
-> Vậy A là ƯỚC CHUNG của X và Y
- Để cắt ra ít hình vuông nhất thì hình vuông phải có diện tích lớn nhất, suy ra cạnh hình vuông phải lớn nhất, tức là A phải lớn nhất
-> Vậy A là ƯỚC CHUNG LỚN NHẤT của X và Y.
-> Số lượng hình vuông cắt ra bằng diện tích HCN chia cho diện tích HV

Hướng dẫn:
- Nhập X, Y
- A = GCD(X, Y)
- S1 = X*Y (S1 là diện tích HCN)
- S2 = A*A (S2 là diện tích HV)
- In ra S1//S2

## [Mua chocolate](https://lqdoj.edu.vn/problem/cbuying)

# Nhập n, m (n là số loại kẹo, m là số tiền
# mình có)

# Khởi tạo mảng candy = []
for _ in range(n):
    price, cow = ...
    candy.append([price, cow])
    
# Sắp candy tăng dần theo price

# Bắt đầu đi mua kẹo
# khởi tạo c = 0 (số kẹo mình mua)
for i in range(n):
    price, cow = candy[i][0], candy[i][1]
    # Loại kẹo i có cow con bò thích ăn
    # ta sẽ kiểm tra xem có mua luôn cow
    # cái kẹo được không.
    # Nếu m >= price*cow thì ta mua hết cow
    # cái, vậy m -= price*cow, c += cow
    # Ngược m < price*cow
    # so_keo_mua_duoc = m // price
    # m -= so_keo_mua_duoc*price
    # c += so_keo_mua_duoc
print(...)

## [OBNOXIOUS](https://lqdoj.edu.vn/problem/hatenumber)
- Đăng ghét: số chia hết cho 3 hoặc số tận cùng là 3
- Đăng thích: số không chia hết cho 3 và số tận cùng khác 3
- Tìm 1000 số đăng thích
- B1: Khởi tạo biến dem = 0, dùng đếm xem đã tìm được bao nhiêu số Đăng thích.
- B2: Khởi tạo biến i = 1, dùng để tìm số Đăng thích.
- B3: Khởi tạo một mảng kq = [] để lưu các số Đăng thích.
- B4: Sử dụng vòng lặp while, điều kiện là dem <= 1000
Bên trong vòng lặp while ta thực hiện như sau:
Nếu i là số Đăng thích thì dùng lệnh append để đẩy vào mảng kq, đồng thời tăng biên dem lên 1.
Tăng i lên
- B5: Nhập q truy vấn
- B6: Sử dụng vòng lặp for chạy q lần
Trong vòng lặp for:
Nhập k
In ra kq chỉ số k-1

## [Ước số chung nhỏ nhất (HSG12'19-20)](https://lqdoj.edu.vn/problem/1920ucnn)

Giải thích:
- Vì ước chung của mảng array đồng thời là ước của ước chung lớn nhất của mảng array. Nên, thay vì ta tìm ước chung nhỏ nhất của mảng array, ta sẽ đi tìm ước nhỏ nhất của ước chung lớn nhất của mảng arr.

- Giải thích rõ hơn:
- Gọi g là ước chung lớn nhất của mảng array, thay vì tìm ước chung nhỏ nhất của mảng array theo đề bài, ta sẽ tiến hành tìm ước nhỏ nhất của g.

Hướng dẫn làm bài

- Nhập n (số lượng phần tử trong mảng arr)
- Nhập mảng arr: arr = list(map(int, input().split()))
- Tìm ước chung lớn nhất của mảng arr
- Gọi g là ước chung lớn nhất của mảng arr:
Khởi tạo g = 0
from math import *
for v in arr:
g = gcd(g, v)
- Vậy g bây giờ là UCLN của arr
- Giờ ta tìm UCNN của arr bằng cách tìm ước nhỏ nhất của g.
- Gọi d là ước nhỏ nhất của g
for i in range(2, g+1)
Nếu g chia hết cho i
Thì ta đặt d = i để lưu lại ước nhỏ nhất sau đó ngay lập tức break
- In ra d

## [Mua sách](https://lqdoj.edu.vn/problem/book)

Giải thích:
- Ta sẽ cố gắng mua những quyên sách dư sao cho chúng có giá rẻ nhất.
- Đồng thời ta lấy khuyến mãi của những quyển sách mắc tiền nhất.
- Như vậy ta thấy rằng, sắp xếp giảm dần rồi mua sách từ đầu tới cuối là chiến dịch mua hàng hợp lí.

Thuật toán:
- Nhập mảng bằng append
- Sắp xếp giảm dần
- for i từ 0 đến n-1:
nếu i % 3 == 2
thì mình sẽ không cần trả tiền cho quyển này
(vì nó quyển rẻ nhất trong 3 quyển)
sử dụng lệnh continue
ngược lại, cộng giá của quyển sách i vào tổng tiền
- In ra tổng tiền

## [Tìm số anh cả](https://lqdoj.edu.vn/problem/soanhca)
for _ in range(int(input()):
n = input() # n là 1 string
n = list(n) # chuyển n từ string sang list
sắp xếp n giảm dần với tham số reverse = True
n.sort(reverse = True)
In ra n bằng lệnh: print(''.join(n))

## [Nguyên tố Again](https://lqdoj.edu.vn/problem/triplenguyeto)

Đề bài:
- Cho N
- Tìm 2 số nguyên tố A, B (A <= B) sao cho A+B cũng là một nguyên tố và (A+B <= N)

Giải thích:
- Nếu A+B là một số nguyên tố thì (A+B) phải là một số lẻ.
+ Ta có trường hợp đặt biệt số 2 là một số chẵn mà vẫn là số nguyên tố.
+ Giả sử nếu A+B == 2 => A, B < 2 => A, B lúc này không phải số nguyên tố

=> A+B chỉ có thể là số lẻ.

- Vì (A+B) là một số lẽ nên cặp số A, B phải là một số lẻ và một số chẵn.
- Ta có số chẵn duy nhất là số nguyên tố là 2. Suy ra A == 2 (vì A <= B).
- Giờ ta chỉ cần tìm số B, vậy số B là một số nguyên tố lẻ nào đó từ 3 -> N-2. Sao cho A+B một số nguyên tố.
- Ta sàng nguyên tố trước và dùng vòng lặp for B từ 3 -> N-2 để tìm số B còn lại.

## [Giả thuyết của Henry](https://lqdoj.edu.vn/problem/primehenry)

- Giả thuyết nói rằng với một số n, mọi số m từ (1 -> 1000), thì n*m+1 đều là số nguyên tố.
- Nhiệm vụ của chúng ta là chứng minh giả thuyết sai nên ta chỉ cần tìm một số m và in ra sao cho (n*m+1 không phải là số nguyên tố)
- Cách tìm m:
- m trong khoảng [1, 1000], ta kiểm tra nếu n*m+1 không phải số nguyên tố thì ta lưu m lại.
- Ta kiểm tra bằng cách dùng mảng is_prime sau khi đã sàng nguyên tố.
- Cách lưu lại: ta sử dụng biến ans, nếu thõa mãn điều kiện thì ta đặt ans = m để lưu lại m.
- In ra ans

## [Đếm ước](https://lqdoj.edu.vn/problem/cses1713)

- Tạo mảng cnt gồm 10^7 phần tử, với ý nghĩa cnt[i] là số lượng ước của i
- Ví dụ: cnt[9] = 3 (vì 9 có 3 ước: 1, 3, 9)
- Nhưng ban đầu tất cả chỉ được khởi tạo bằng 2 vì mọi số đều có 2 ước là 1 và chính nó.
- Tiến hành đếm ước trên ý tưởng:
- Giải sử ta đang xét đến số i, thì ta tăng cnt của các số là bội của i (Như là 1*i, 2*i, 3*i, ...) vì những số đó chia hết cho i. Nhưng để tránh bị trùng, ta sẽ tăng từ i*i, (i+1)*i, (i+2)*i, ...

## [Cánh diều - FLOWER - Tính tiền bán hoa](https://lqdoj.edu.vn/problem/cdl1p4)Đề cho n, m, a

- Ta có mảnh vườn chiều rộng 'm' mét, chiều dài 'n' mét.
-> Vậy diện hình chữ nhật là "m*n" mét vuông

- 1 mét vuông trồng được 1 khóm hoa
-> Vậy "n*m" mét vuông trồng được "n*m" khóm hoa.

- 1 khóm hoa bán được a tiền
-> vậy có "n*m" khóm hoa bán được a * n * m

## [Tìm cặp số](https://lqdoj.edu.vn/problem/findpair)

Bước 1: Sắp xếp tăng dần mảng "arr"
Bước 2: Tạo 2 con trỏ left và right, với left = 0, right = n-1.
Bước 3: Thực hiện chạy 2 con trỏ với điều kiện left luôn nhỏ hơn right:
- Con trỏ bên trái chạy qua bên phải
- Con trỏ bên phải chạy qua bên trái

Khi chạy sẽ xảy 3 trường hợp:
1) arr[left] + arr[right] == X
2) arr[left] + arr[right] < X
3) arr[left] + arr[right] > X

Bước 4: Kiểm tra xem có tìm được đáp án không bằng cách dựa vào con trỏ left và right.

## [Đếm cặp đôi (HSG'20)](https://lqdoj.edu.vn/problem/capdoi)

Để làm bài này ta sử dụng 2 con trỏ left và right chạy ngược hướng nhau trên mảng arr đã sắp xếp, left là chạy qua phải và right sẽ chạy qua trái.

Bước 1: Nhập n, x tương ứng số phần tử và tổng x.
Bước 2: Sắp xếp mảng arr.
Bước 3: Đếm số lần xuất hiện của từng phần tử, gọi cnt[v] là số lần xuất hiện của phần tử có giá trị v.
Bước 4: Sử dụng vòng lặp while left < right, ta tìm các cặp có tổng bằng x thông qua việc thu hẹp dần đoạn từ left -> right. Ban đầu left = 0, right = n-1. Ta có 3 trường hợp sau:
TH1) arr[left] + arr[right] > x: ta giảm right để giảm tổng xuống
TH2) arr[left] + arr[right] < x: ta tăng left để tăng tổng lên
TH3) arr[left] + arr[right] == x:
- Trường hợp này, điều kiện đề đã thõa mãn.
Ở đây lại xảy ra 2 trường hợp con:
TH 3.1: arr[left] != arr[right], ta xử lí như sau:
- Ta cố định một đầu, rồi cộng số lượng phần tử có thể ghép cặp ở đầu còn lại vào ans. Sau đó thay đổi đầu mà ta cố định lên để tìm các cặp khác.
- Ví dụ ta cố định đầu left, thực hiện:
`
ans += cnt[arr[right]]
left += 1
`


Ở ví dụ trong hình vẽ, ta đang tìm cặp tổng bằng 5, con trỏ left đang ở giá trị 1, con trỏ right đang ở giá trị 4. Ta cố định left ở giá trị left sau đó cộng số lần xuất hiện của giá trị 4 là 3 thì ta có được 3 cặp tổng bằng 5. Sau đó ta dịch left lên để tìm các cặp khác.

(Lưu ý là ta vẫn có thể cố định đầu right và theo login tương tự)

TH 3.2: arr[left] == arr[right], ta xử lí như sau:
Ta sử dụng công thức bắt tay:
ans += arr[left]*(arr[left]-1)/2
(arr[left] == arr[right] nên có thể sử dụng 1 trong 2)
Giải thích công thức bắt tay:

giả sử ta đang ở trong trường hợp cụ thể này:

ta đem 3 số 3 ra ghép cặp (bắt tay với nhau) thì ta sẽ có 3 cặp (3 lần bắt tay) thể hiện qua 3 đoạn thẳng

***Sau khi sử dụng công thức bắt tay, ta đã ghép cặp cho tất cả các phần tử giống nhau và tổng bằng x rồi nên nhớ thực hiện break vòng lặp while***

Bước 5: In ra ans.

## [Tập xe](https://lqdoj.edu.vn/problem/csp)

Chúng ta sử dụng 2 con trỏ left và right, trong đó left di chuyển sang phải và right di chuyển sang trái. Cả 2 con trỏ này chạy trên mảng arr đã được sắp xếp theo thứ tự tăng dần.

**Bước 0:** Nhập số lượng phần tử n và tổng k.

**Bước 1:** Sắp xếp mảng arr theo thứ tự tăng dần.

**Bước 2:** Khởi tạo left = 0 và right = n-1. Đoạn mà chúng ta đang xem xét là từ vị trí left đến vị trí right trên mảng arr. Vì vậy, chúng ta sử dụng điều kiện while left < right và xử lí 2 trường hợp sau:
- **TH1:** Nếu arr[left] + arr[right] > k:
- Đơn giản chỉ cần giảm giá trị của right.
- **TH2:** Nếu arr[left] + arr[right] <= k:
- Giữ giá trị left cố định.
- Khi giá trị left được cố định, chúng ta ghép left với tất cả các phần tử từ left+1 đến right để tạo thành các cặp có tổng <= k.
Minh họa qua hình dưới đây:

- Khi giá trị left cố định là 1, ta có thể ghép 1 với các giá trị từ 2 đến 6 (right) để tạo thành các cặp có tổng <= 7. - Vì vậy, chúng ta thực hiện: ``` ans += right - left ```
- Sau khi left được cố định để tính toán, ta tăng giá trị của left lên: ``` left += 1 ```
-
**Bước 3:** In ra kết quả.
## [sunw](https://lqdoj.edu.vn/problem/sunw)

Đây là một bài toán sử dụng kỹ thuật 2 con trỏ. Chúng ta sẽ sử dụng hai con trỏ left và right, trong đó left di chuyển sang phải và right di chuyển sang trái. Hai con trỏ này đại diện cho đoạn mảng mà chúng ta đang xem xét từ left đến right. Điều kiện để áp dụng kỹ thuật này là mảng đã được sắp xếp theo thứ tự tăng dần.

**Bước 1:** Nhập số lượng phần tử n và tổng x của một cặp.

**Bước 2:** Sắp xếp mảng theo thứ tự tăng dần.

**Bước 3:** Bắt đầu thực hiện kỹ thuật 2 con trỏ.

- Khởi tạo left = 0 và right = n-1 để đảm bảo ban đầu chúng ta xét toàn bộ mảng. Điều kiện dừng vòng lặp while là left < right, vì đoạn mà chúng ta đang xét phải có ít nhất 2 phần tử.
- Có hai trường hợp cần xét:
- **TH1:** Nếu arr[left] + arr[right] > x:
+ Nếu ta tăng giá trị của left, tổng cân nặng của hai người sẽ càng tăng. Vì vậy, chúng ta giảm giá trị của right.
+ Tức là người bên phải đang quá nặng, chúng ta sẽ cho người này ngồi trên một ghế riêng.
+ Do đó, chúng ta giảm giá trị của right và tăng số lượng ghế cần dùng lên 1.
- **TH2:** Nếu arr[left] + arr[right] <= x:
+ Hai người này có thể ngồi chung trên một ghế, vì tổng cân nặng của họ không vượt quá giá trị x. Sau đó, chúng ta tiếp tục xét hai người khác.
+ Do đó, chúng ta tăng giá trị của left, giảm giá trị của right và tăng số lượng ghế lên 1.

**Bước 4:** Xử lí trường hợp đặc biệt.

- Nếu left == right, đồng nghĩa với việc đoạn đang xét (từ left đến right) chỉ còn 1 phần tử. Tức là chỉ còn một người chưa có chỗ ngồi. Vì vậy, chúng ta cần thêm 1 ghế cho người này.

**Bước 5:** In ra số lượng ghế cần dùng.

## [Fibo đầu tiên](https://lqdoj.edu.vn/problem/fibo00)

Thuật toán tìm n số fibo đầu tiên

1) Nhập n
2) Vì cần lưu n số fibo nên ta phải tạo mảng có n phần tử
3) Ta biết rằng 2 số fibo đầu tiên là 1 và 1 nên ta gán:
arr[0] = 1
arr[1] = 1
4) Ta tìm các số fibo còn lại bằng cách chạy 1 vòng for từ 2 đến n, sau đó áp dụng công thức:
arr[i] = arr[i-1] + arr[i-2]

5) In ra mảng arr

## [Kiểm tra dãy đối xứng](https://lqdoj.edu.vn/problem/ktdxcqt)

Nếu nhập mảng bình thường list(map(...)) thì ta sẽ dính lỗi MLE, vì vậy ta sẽ nhập mảng bằng xâu:
arr = input().split()

B1: Nhập như ở trên
B2:

Cách 1: Thực hiện với những ngôn ngữ như C++, Java

Tạo 2 con trỏ left và right:
- Với left chạy từ bên trái cùng, chạy sang phải
- Với right chạy từ bên phải cùng, chạy sang

- 2 con trỏ này sẽ dừng lại khi chúng gặp nhau.

- Ta sẽ chạy 2 con trỏ này cùng lúc, vì vậy nó sẽ luôn đối xứng nhau, ta chỉ cần kiểm tra xem nó có bằng nhau không.
-> Nếu có thì dịch trỏ left lên, dịch trỏ right xuống để kiểm tra tập tiếp theo.
-> Nếu không thì xâu này không phải xâu đối xứng, ta có thể dừng chạy luôn.

Cách 2: Thực hiện với những ngôn ngữ ngữ như Python

- Kiểm tra xem mảng arr có giống với mảng đảo ngược của nó không.
- Tức là nếu arr = arr[::-1]
- >> Là xâu đối xứng, in ra True
- >> Ko là xâu đối xứng, in ra False

## [Số chính phương](https://lqdoj.edu.vn/problem/if06)

Tốt, dưới đây là cách giải thích bài toán kiểm tra số chính phương một cách đơn giản và chi tiết hơn cho học sinh tiểu học:

Bài toán: Kiểm tra số chính phương

1. Giới thiệu khái niệm:
- Số chính phương là một số mà căn bậc hai của nó cũng là một số nguyên.
- Ví dụ: Số 4 là số chính phương vì căn bậc hai của 4 là 2, và 2 cũng là một số nguyên.

2. Hướng dẫn về cách kiểm tra số chính phương:
- Để kiểm tra xem một số có phải là số chính phương hay không, ta sẽ thực hiện hai bước đơn giản:
- Bước 1: Tính căn bậc hai của số đó.
- Bước 2: Kiểm tra xem kết quả căn bậc hai có phải là một số nguyên hay không.
- Nếu kết quả căn bậc hai là một số nguyên, thì số ban đầu là số chính phương.
- Nếu kết quả căn bậc hai không phải là một số nguyên, thì số ban đầu không phải là số chính phương.

2. Nhập số nguyên từ người dùng:

     n = int(input())

5. Kiểm tra xem số có phải là số chính phương hay không:

from math import*
def kt_so(n):
    if int(n) == n:
        return True
    else:
        return False
def kt_chinh(n):
    if kt_so (sqrt(n)) == True:
        return True
    else:
        return False
n = int(input())
if kt_chinh(n) == True:
    print('YES')
    
else:
    print('NO')

6. Giải thích kết quả:
- Giải thích rằng chương trình sẽ in ra kết quả xác định xem số đã nhập có phải là số chính phương hay không.
- Nếu số đó là số chính phương, chương trình sẽ in ra thông báo "YES".
- Nếu số đó không phải là số chính phương, chương trình sẽ in ra thông báo "NO".

## [Đếm chữ số lẻ (THT TP 2019)](https://lqdoj.edu.vn/problem/19thtbdna1)

Bước 1: Nhập xâu s.
Bước 2: Chạy từng kí tự trong xâu s, chuyển kí tự đó về kiểu số nguyên, rồi kiểm tra xem số đó có chia 2 dưa 1 hay không.
-> Nếu có thì tăng đếm lên
-> Nếu không thì thôi =))
Bước 3: In ra số biến đếm.

## [Dịch cúm (THTB - TP 2021)](https://lqdoj.edu.vn/problem/21thtbdna1)

Ví dụ:
- Xâu có 3 chữ C thì ta chỉ có thể có 3 chữ CORONA.
- Xâu có 4 chữ O thì ta chỉ có thể có 2 chữ CORONA.

Vậy đáp án chính là giá trị min của số lượng các chữ: C, R, N, A, O div 2

Lưu ý là ta cần 2 chữ O cho mỗi chữ CORONA nên số lượng chữ O phải chia nguyên 2.

## [high](https://lqdoj.edu.vn/problem/high)

- Để xử lí bài toán này, ta áp dụng kĩ thuật 2 con trỏ sau khi đã sắp xếp tăng dần 2 dãy Nam và Nữ.
- Một con trỏ ở mảng Nam chạy từ trái cùng sang phải, và một con trỏ ở mảng Nữ hoạt động tương tự như vậy.
- Ta thử ghép 1 bạn nam và 1 bạn nữ tương ứng với 2 con trỏ này, rồi xem xét các trường hợp xảy ra.
- Đồng thời dựa vào tính chất tăng dần của 2 mảng đã sắp xếp để xét các trường hợp tiếp theo. (Loại bỏ các trường hợp thừa)

- Sau đây là phần thuật toán chi tiết.
- B1: Nhập n, m, k tương ứng số lượng nam, số lượng nữ, và độ chênh lệch cho phép.
- B2: Sắp xếp tăng dần cả 2 mảng.
- B3: Khởi tạo 2 con trỏ cho 2 mảng như đã nói ở trên, ban đầu giá trị của chúng đề bằng 0. (Xét 2 phần tử đầu tiên của 2 mảng)
- B4: Bắt đầu chạy 2 con trỏ, vì nó đều chạy từ trái sang phải nên điều kiện là chúng đều phải nhỏ hơn số lượng phần tử trong mảng mình đang đi.
- Phân trường hợp:
- TH1: Thõa mãn điều kiện:
Tăng số lượng cặp ghép được lên 1.
Vì mỗi nam chỉ ghép được với nữa, và ngược lại, cấm các thể loại badboy trapgirl nên ta đồng thời tăng 2 con trỏ lên để tiến hành ghép người khác.
- TH2: Không thõa màn điều kiện, tức abs(boys[iboy] - girls[igirl]) > k:
Như vậy, theo toán học, ta lại phải xét tiếp 2 trường hợp là:
- TH 2.1: boys[iboy] - girls[igirl] > k:
Ở trường hợp này, rõ ràng ta thấy rằng nếu tăng iboy lên trong một mảng boys đang tăng dần, phép tính boys[iboy] - girls[igirl] sẽ càng lớn và không bao giờ có thể bằng k. Vì vậy ta tăng igirl (con trỏ mảng Nữ) để hiệu này giảm xuống.
- TH 2.2: - girls[igirl] - boys[iboy] > k
Đây là trường hợp còn lại nên là hãy dùng lệnh else, suy nghĩ tương tự và theo hướng ngược lại ở trường hợp 2.1 trên, ta tăng iboy (con trỏ mảng Nam).

Bước 5: Chỉ việc in ra kết quả số lượng cặp ghép được.

## [minict12](https://lqdoj.edu.vn/problem/minict12)

- Bài này ta sử dụng kĩ thuật 2 con trỏ left và right.
- nhưng không chạy ngược hướng nhau như những bài trên mà chạy cùng 1 hướng từ trái sang phải.
- Con trỏ right chạy trước đi kéo dài đoạn từ left -> right ra (Vì đề yêu cầu ta phải tìm đoạn dài nhất thõa màn)
- Con trỏ left chạy theo sau để rút ngắn đoạn từ left -> right cho đến khi thõa mãn với yêu cầu của đề.
- Ta sẽ in ra vị trị con trỏ left và right sao cho đoạn left->right là dài nhất

Thuật toán chi tiết như sau:

B1: Nhập n, k. Tương ứng là số lượng phần tử của mảng và số lượng số khác nhau có thể chấp nhận được trong 1 mảng. Sau đó nhập mảng arr.

B2: Khởi tạo một cặp con trỏ để duyệt tìm đoạn dài nhất thõa mãn, và một cặp con trỏ đáp án để lưu lại câu trả lời. Vì ta chạy từ trái sang phải nên ban đầu, tất cả con trỏ đều bằng 0.

B3: Ta bắt đầu thực hiện kĩ thuật 2 con trỏ, vì 2 con trỏ đều chạy sang phải, con trỏ left thì chạy theo sau con trỏ right, nên điều kiện để làm ở đây là right < n:
TH1: Trường hợp mà ta có thể thêm phần tử hiện tại mà con trỏ right đang đứng (là arr[right]) vào đoạn hiện tại đang xét (tức đoạn từ left -> right).
- Điều kiện của trường hợp này, là arr[right] đã xuất hiện trong đoạn hiện tại, hoặc là nếu thêm arr[right] vô thì số lượng số khác nhau trong đoạn vẫn chưa vượt quá k.
- Ta thực hiện các thao tác sau:
- So sánh với biến kết quả xem có dài hơn đoạn đã lưu được không.
- Tăng số lần xuất hiện trong đoạn của arr[right] lên 1.
- Nếu arr[right] chưa xuất hiện thì thêm arr[right] vào tập các số đã xuất hiện (kiểu dữ liệu set).
- Tăng biến right lên để xét các số tiếp theo.
TH2: Trường hợp ta không thể thêm right vào đoạn đang xét, chung quy là ngược lại với trường hợp trên.
- Điều kiện của trường hợp này ngược lại với TH trên nên ta có thể dùng lệnh else.
- Để có thể thêm right vào đoạn đang xét, ta phải vứt bớt các phần tử trong đoạn ở phía con trỏ left cho tới khi thõa mãn điều kiện có thể thêm right vào.
- Ta làm điều đó bằng cách thực hiện các thao tác sau:
- Giảm số lần xuất hiện của arr[left] vì ta sắp loại nó ra khỏi đoạn.
- Nếu như số lần xuất hiện của arr[left] về 0 ta loại phần tử này ra khỏi tập các phần tử khác nhau.
- Cuối cùng tăng left lên để loại bỏ phần tử này ra khỏi đoạn.

B4: In ra 2 con trỏ kết quả đã lưu.

Code gợi ý: https://pastie.io/bbtaww.cpp

## [Tổng liên tiếp không quá t](https://lqdoj.edu.vn/problem/sumconset)

Bài này tương tự bài ở trên nên ta sẽ đi thẳng vào thuật toán:

Bước 1: Nhập n là số lượng phần tử, t là tổng tối đa cho phép của các phần tử liên tiếp trong mảng.
Bước 2:
- Khởi tạo biến kết quả = 0. Biến kết quả ở đây lưu độ dài của đoạn liên tiếp dài nhất có tổng khôgn quá t.
- Khởi tạo biến tổng ban đầu = 0. Vì ban đầu ta chưa xét phần tử nào.
Bước 3: Khởi tạo 2 con trỏ left = 0 và right = 0. Sau đó bắt đầu thực hiện kĩ thuật 2 con trỏ.
- Điều kiện còn thực hiện right < n. (vì ta đang muốn nó chạy sang phải)
- Xét 2 trường sau:
- TH1: có thể thêm phần tử ở con trỏ right vào đoạn vì tổng vẫn chưa vượt quá t.
- Điều kiện là tổng hiện tại cộng với giá trị phần tử con trỏ right đang đứng vẫn chưa vượt quá t.
- Ta thực hiện các thao tác sau:
- Thêm giá trị phần tử right vào tổng.
- Cập nhật giá trị của kết quả (hay độ dài đoạn dài nhất tìm được).
- Dịch con trỏ right lên để xét phần tử tiếp theo.
- TH2: Ngược lại ở trường hợp trên.
- Vì nếu thêm right vào tổng bây giờ thì sẽ vượt quá t, nên ta phải vứt bớt các phần tử bên left trước. Đến khi tổng các phần tử còn lại đủ nhỏ ta mới bắt đầu nhảy lên trường hợp trên để thêm right.
- Ta thực hiện các thao tác sau:
- Trừ khỏi tổng giá trị của phần tử left.
- Tăng left lên để loại bỏ phần tử này ra khỏi đoạn từ left -> right.
Bước 4: In ra kết quả

***Code gợi ý: https://pastie.io/jtnxkd.cs***

## [Kaninho tập đếm với xâu](https://lqdoj.edu.vn/problem/strcnt)
- Bài này là bài cuối cùng trong contest Hai Con Trỏ rồi nên là sẽ được ghi theo phong hướng Simple make perfect 1 chút.
- Áp dụng kĩ thuật 2 con trỏ left và right, cả 2 đều từ trái -> phải.
- Right có nhiệm vụ thêm phần tử vào đầu đoạn (left -> right) để đoạn trở nên dài nhất có thể.
- Left có nhiệm vụ xóa phần tử ở cuối đoạn khi right không thể thêm được nữa.

- Yêu cầu bài này: Nhập xâu (tạm gọi là mạng cho dễ nói) và 1 số k. In ra số lượng đoạn con trong mảng có số lần xuất hiện của các phần tử trong nó không quá k.

- Thuật toán:
- B1: Nhập dữ liệu
- B2: Khởi tạo các biến cần dùng:
- Biến kết quả: ans = 0; // Ban đầu chưa tìm kết quả nào
- Biến left, right đều bằng 0 vì chạy từ trái -> phải.
- Cấu trúc dữ liệu map để lưu lại số lần xuất hiện của 1 phần tử trong đoạn left -> right.
- B3: Tiến hành kĩ thuật 2 con trỏ
- Điều kiện thực hiện: right < n
- Phân ra 2 trường hợp:
- TH 1: Thêm được right
- Điều kiện: Vì ta sắp sửa thêm phần tử này vào đoạn nên nếu số lần đã xuất hiện của nó cộng 1 vẫn chưa quá k thì ok, ta thêm được.
- Cộng số lượng xâu con thõa mãn vào biến kết quả.
- Tăng số lần xuất hiện của nó lên.
- Tăng right lên để xét phần tử tiếp theo.
- TH 2: Không thêm được right
- Như đã nói ở trên, đây là lúc left thực hiện nhiệm vụ của mình.
- Giảm số lần xuất hiện của phần tử left. (Vì ta đang loại nó ra).
- Tăng left lên để chính thức loại phần tử này ra khỏi đoạn.
- B4: In ra biến kết quả

- Code gợi ý: https://pastie.io/mmyofk.cpp

## [4 VALUES](https://lqdoj.edu.vn/problem/largeval)
- Sau khi sắp xếp tăng dần mảng
`a[0], a[1], a[2], ..., a[n-3], a[n-2], a[n-1]`

- Phần tử nhỏ: `a[0]`
- Phần tử lớn nhất: `a[n-1]`
- Phần tử nhỏ nhì: `a[1]`
- Phần tử lớn nhì: `a[n-2]`

Lấy ra 4 giá trị sao cho `(a-b)*(c-d)` lớn nhất:

` (a[n-1] - a[1]) * (a[n-2] - a[0]) `

- (số lớn nhất - số bé nhì)*(số lớn nhì - số bé nhất)

## [Xâu con (HSG12'18-19)](https://lqdoj.edu.vn/problem/1819substr)

***Code gợi ý: https://pastie.io/wafnam.cpp***

## [Cánh diều - CAMERA - Camera giao thông
](https://lqdoj.edu.vn/problem/cdl6p8)
https://pastie.io/qbheld.cpp

## [minict08](https://lqdoj.edu.vn/problem/minict08)

Cho 1 xâu s, thay đổi 1 số kí tự để có ít nhất k kí tự khác nhau:

Ví dụ:
xâu: `justys`
cần ít nhất: `6` kí tự khác nhau

Ta thay đổi kí tự s sang 1 kí khác (z)
được xâu: `justyz` có `6` kí tự khác nhau
-> thõa mãn đề bài

Nếu số lượng kí tự của xâu nhỏ hơn k thì ta không thể biến đổi.
-> Ví dụ một xâu có `5` kí tự thì ta không thể biển thành một xâu có `7` kí tự khác nhau được.

Nếu biến đổi được:

- TH1: Số lượng kí tự khác nhau của xâu đang lớn hơn hoặc bằng k. Thì ta không cần biến đổi -> Số lần biến đổi là `0`.
- TH2: Số lượng kí tự khác nhau của xâu bé hơn k. Thì số lần biến đổi là: `k - số lượng kí tự khác nhau`

## [K-Amazing Numbers](https://lqdoj.edu.vn/problem/kbeautiful)

Trước hết ta phải công nhận 1 điều rằng: nếu 1 số xuất hiện ở tất cả các đoạn có kích thước là
k thì chúng sẽ xuất hiện ở các đoạn dài hơn như k + 1, k + 2, k + 3, ...

Ví dụ có mảng:

1 3 3 1 3 5 3

Ta thấy số 3 đang ở trong tất cả các đoạn có 2 phần tử liên tiếp, như vậy nó cũng sẽ ở trong các đoạn có
3, 4, 5 phần tử liên tiếp

- Tiếp theo, ta bắt đầu đi tìm khoảng cách dài nhất của các giá tr

arr.insert(0, 0)

pos = [0]*(n+1)
dis = [0]*(n+1)

for i in range(1, n+1):
dis[arr[i]] = max(dis[arr[i]], i - pos[arr[i]])
pos[arr[i]] = i

# Vòng for này để xét đoạn cuối cùng (đoạn có bên phải đến phần tử cuối cùng)
for i in range(1, n+1):
dis[i] = max(dis[i], n - pos[i] + 1)

- Tiếp tục là tìm giá trị nhỏ nhất của các khoảng cách

 for i in range(1, n+1):
        res[dis[i]] = min(res[dis[i]], i)    

- Cuối cùng là dựa vào phần đầu mà mình đã nói ở bài này, các bạn tự làm tiếp ngang đây nhé.

## [minict26](https://lqdoj.edu.vn/problem/minict26)

- Các hộp lớn hơn có thể chồng trên hộp nhỏ hơn, các hộp nhỏ hơn có thể nằm dưới các hộp lớn hơn. Tuy chỉ có các hộp bằng nhau là không thể chồng lên nhau.
- Vậy bài này ta đi tìm số lượng hộp có kích thước bằng nhau nhiều nhất.

Hướng dẫn:
- Đầu tiên, ta đếm phân phối số lượng hộp mỗi loại, để xem với kích cỡ nào đó thì có bao nhiêu hộp.
- Từ đó ta tìm số lượng hộp có kích cỡ bằng nhau lớn nhất.
- Cuối cùng in ra kết quả

## [Xâu chẵn](https://lqdoj.edu.vn/problem/scrxauchan)

Yêu cầu đề:
'''
Kiểm tra một xâu có phải là xâu chẵn hay không, định nghĩa xâu chẵn
là xâu có tất cả các kí tự xuất hiện chẵn lần
'''

Hướng dẫn:
'''
Trước khi đếm số lần xuất hiện, ta thực hiện xóa bỏ các phần tử trùng nhau
bằng cách sử dụng hàm set

Sau đó, ta sẽ sử dụng hàm count để đếm số lần xuất hiện của các phần tử,
nếu có bất kì phần tử nào có số lần xuất hiện lẻ, thì đó không phải là xâu
chẵn. Ta đặt biến kiểm tra thành false.

Cuồi cùng, ta chỉ cần dựa vào biến kiểm tra là biết được nên in ra Yes
hay No
'''

Lời giải:

s = input()
# Ở đây, ta sử dùng set để loại bỏ các kí tự trùng nhau
kt = True
for i in a:
    # sử dụng hàm count để đếm số lượng xuất hiện của nó, nếu lẽ thì kt = False
        kt = False
        break
if (kt):
    print('Yes')
else:
    print('No')
 

## Dãy số

[Dãy số](https://lqdoj.edu.vn/problem/d13seq3)

### Hướng làm bài

Để giải bài toán này, ta sẽ xây dựng hai mảng `pfs_left[]` và `pfs_right[]`, với ý nghĩa là tổng đoạn con có độ dài chia hết cho 3 lớn nhất ở bên trái và phải của mỗi vị trí trong dãy số. Sau đó, ta sẽ duyệt qua mỗi vị trí trong dãy số ban đầu để tìm ra tổng lớn nhất của đoạn con có độ dài chia hết cho 3 mà kết thúc tại mỗi vị trí.

### Thuật toán

1. Bắt đầu bằng việc thao tác trên dãy số, ta sẽ thêm một phần tử giá trị bất kỳ vào đầu dãy số để làm cho dãy số bắt đầu từ chỉ số 1.

arr.insert(0, 0)

2. Xây dựng mảng `pfs_left[]` với ý nghĩa là tổng độ dài đoạn con có độ dài chia hết cho 3 lớn nhất kết thúc tại vị trí i (đi từ trái qua).

INF = int(1e9)
pfs_left = (n+1)*[-INF]
for i in range(3, n+1):
    pfs_left[i] = arr[i] + arr[i-1] + arr[i-2] + max(0, pfs_left[i-3])

3. Tiếp tục xây dựng để đạt được kết quả cuối cùng là `pfs_left[i]` là tổng đoạn con lớn nhất có độ dài chia hết cho 3 ở bên trái của i (bất kể nó có kết thúc ở i không).

for i in range(1, n+1):
	pfs_left[i] = max(pfs_left[i], pfs_left[i-1])

4. Thực hiện tương tự cho mảng `pfs_right[]`.

5. Chạy tất cả các vị trí i trong dãy số để tìm giá trị lớn nhất của `pfs_left[i] + pfs_right[i]`.

6. In ra kết quả.
---

## [Bạt che nắng](https://lqdoj.edu.vn/problem/18thtbdna2)

### Hướng làm bài

Khi giải bài toán này, chúng ta cần tìm ra đoạn đường được phủ bởi tấm bạt che nắng sao cho đoạn đường này là dài nhất có thể. Để làm điều này, ta có thể duyệt từ đầu đến cuối đoạn đường, xem mỗi phần tử của đoạn đường có được phủ hay không. Khi gặp phần đầu của một tấm bạt nào đó, ta tăng số lượng tấm bạt đang được sử dụng ở đoạn đường hiện tại. Ngược lại, khi gặp phần cuối của một tấm bạt, ta giảm số lượng tấm bạt đang được sử dụng ở đoạn đường hiện tại. Khi số lượng tấm bạt đang được sử dụng ở một vị trí nào đó lớn hơn 0, có nghĩa là đoạn đường đó đã được phủ bởi tấm bạt. Ngược lại, nếu số lượng tấm bạt đang được sử dụng bằng 0, đoạn đường đó vẫn còn trống chưa được phủ. Sau khi ta đã xác định được trạng thái phủ của mỗi phần tử trong đoạn đường, ta có thể dễ dàng tìm ra đoạn đường được phủ dài nhất bằng cách đếm số lượng phần tử `True` liên tiếp dài nhất trong mảng đánh dấu.

### Thuật toán

1. Khởi tạo một mảng có độ dài tương ứng với chiều dài của đoạn đường.
- python

length = int(6e4) + 1
road = [0]*(length)

- c++

const ll len = int(1e6) + 1;
ll road[len];
memset(road, 0, sizeof road);

2. Đọc dữ liệu đầu vào và tăng/giảm giá trị trong mảng `road` tương ứng với các cặp l, r trong input.

- python

for _ in range(n):
    l, r = map(int, input().split())
    road[l] += 1
    road[r] -= 1

- c++

while (n--) {
    ll l, r;    cin >> l >> r;
    road[l]++, road[r]--;
}

3. Duyệt qua từng phần tử trong mảng `road` để xác định trạng thái phủ của mỗi phần tử trong đoạn đường.
- python

cnt = 0
cover = [False]*(length)
for i in range(0, length):
    cnt += road[i] # cập nhật trạng thái của vị trí hiện tại
    cover[i] = cnt > 0 # nếu cnt > 0 thì chỗ này đã được phủ bạt

- c++

ll cnt = 0;
bool cover[len];
for (int i = 0; i < len; ++i) {
    cnt += road[i]; // cập nhật trạng thái của vị trí hiện tại
    if (cnt > 0) // nếu cnt > 0 thì chỗ này đã được phủ bạt
        cover[i] = true;
    else
        cover[i] = false;
}

4. Tìm đoạn được phủ dài nhất bằng cách đếm số lượng phần tử `True` liên tiếp dài nhất trong mảng `cover`.

max_cover = 0; cur_cover = 0
for i in range(0, length):
    if cover[i] == True:
        cur_cover += 1
        max_cover = max(max_cover, cur_cover)
    else:
        cur_cover = 0

- c++

ll max_len = 0, cur = 0;
for (int i = 0; i < len; ++i) {
    if (cover[i] == true) {
        cur++;
        max_len = max(max_len, cur);
    } else {
        cur = 0;
    }
}

5. In ra độ dài của đoạn được phủ dài nhất.

---

## [Bảng ký tự (Vòng Sơ loại 2022: Bài 2 của bảng B)](https://lqdoj.edu.vn/problem/thttq2022b2)

### Yêu cầu đề:
Cho mảng 2 chiều kích thước mxn mà mỗi phần tử là A hoặc B.
In ra diện tích hình chữ nhật lớn nhất mà số lượng chữ A và B chênh lệch là không quá k.
### Hướng làm bài
Bài này ta có thể duyệt trâu bằng một chút khéo léo khi chạy vòng lặp for. (Sử dụng kĩ thuật Prefix Sum 2 chiều)
### Thuật toán
- Step 0: Bài này ta sẽ sử dụng mảng bắt đầu từ chỉ số 1 để tiện sử dụng Prefix Sum.
- ***Lưu ý là bài này phải xử lý nhiều test case 1 lúc nhé.***
- Step 1: Nhập dữ liệu, ta sẽ lấy dữ liệu cho các phần tử là A hay B mà ta thay thể tương ứng 1 và -1. Như vậy nếu số lượng chữ A và chữ B bằng nhau thì tổng sẽ bằng 0, đồng nghĩa với độ chênh lệch là 0.
- Python

- C++.

- Step 2: Xây dựng mảng Prefix Sum 2D.
- Giờ ta sẽ nói về Prefix Sum 2 chiều.
- Dùng mảng 2 chiều P sẽ để lưu tổng cộng dồn.
- P[i, j] là tổng của tất cả các phần tử trong hình chữ nhật có đường chéo từ ô [0, 0] xuống ô [i, j].
- 

- 

- Giờ hãy để ý một chút, nó sẽ rất đơn giản thôi.

- 

- 

- 

- Giờ hãy tưởng tượng nếu ta lấy HCN màu xanh dương gộp với HCN màu vàng thì sao?
- Có phải ta sẽ có được HCN màu cam nhưng thiếu ô A[i, j] và thừa 1 HCN màu xanh lá không?
- Vậy công thức để tính P[i,j] là:
- P[i,j] = P[i-1][j] + P[i][j-1] - P[i-1, j-1] + A[i, j]
- (Cam = Vàng + Xanh Dương - Xanh lá + A[i, j])

- Ok tiến hành code để xây dựng mảng Prefix Sum 2D.
- Python
*'mtx' là mảng 'A' đang nói ở trên*
- C++

- Tiếp tục là cách tính tổng một hình chữ nhật bất kì có góc trái trên mang chỉ số là [i, j], góc phải dưới là [u, n].

- 

- Hãy kiểm tra xem, có phải công thức là:
- Tổng các phần tử HCN Xanh Dương = P[u, v] - P[i-1, v] - P[u, j-1] + P[i-1, j-1]
- Giải thích
- P[u, v] là cả 4 HCN trên
- P[i-1, v] = Xanh Lục + Vàng
- P[u, j-1] = Cam + Vàng
- P[i-1, j-1] = Vàng
- Vậy lấy cả 4 màu - (Xanh Lục + Vàng) - (Cam + Vàng) + Vàng
= 4 màu - Xanh Lục - Vàng - Cam - Vàng + Vàng
= 4 màu - Xanh Lục - Vàng - Cam
= Xanh Dương

Vậy là ta đã xây dựng xây dựng thành công mảng prefix sum 2D.

- Step 3: Để tìm đáp án, ta duyệt trâu tất cả các hình chữ nhất trong mảng. Hình như nhật này sẽ có góc trái trên là [i, j] và góc phải dưới là [u, v]. Vậy ta sử dụng 4 vòng for như sau.
- Python
- C++

- Giờ ta sẽ về nói 2 câu if ở trên, nhờ khéo léo đặt vào 2 câu if này ta mới chạy kịp.

if (n-i+1)*(m-j+1) <= res:
    break

-> Ta đang lấy tất cả hình chữ nhật có góc trái trên là [i, j], và hình chữ nhật lớn nhất ta tìm được sẽ có góc phải dưới là [n, m]. Nhưng nếu HCN lớn nhất đó cũng không lớn hơn HCN mà ta đã tìm được và lưu trong biến "res" thì ta không cần tìm nữa => break.

if (u-i+1)*(v-j+1) <= res:
    break

*Lưu ý ta đang chạy u, v giảm dần*

-> Vì u, v giảm dần nên kích thước hình chữ nhật ta đang xét sẽ giảm dần. Nếu hình chữ nhật ta đanh xét có diện tích không lớn hơn kết quả ta đã có được trước đó trong res, thì khi giảm kích thước xuống vẫn sẽ không có kết quả tốt hơn. => Vì vậy ta break.

Step 3: In ra kết quả.

---

## [K-Amazing Numbers](https://lqdoj.edu.vn/problem/kbeautiful)

### Hướng làm bài
Ta sử dụng 1 mảng để lưu khoảng cách tối đa mà một giá trị nào đó xuất hiện liên tục.
Một mảng khác để lưu giá trị nhỏ nhất luôn xuất hiện trong một khoảng cách nào đó.
Từ hai mảng này, ta sẽ sử dụng hướng prefix sum để làm bài.

### Thuật toán

***Step 0: Khiến mảng bắt đầu từ 1 (1 index based) để dễ dàng xử lý trên mảng hơn.***

arr.insert(0, -1)

***Step 1: Xây dựng mảng dis[i] là khoảng cách dài nhất mà giá trị là i xuất hiện liên tục.***

Vì nếu giả sử có 3 số 1 trên một mảng.
2 số một đằng trước cách nhau 3 số, 2 số 1 đằng sau cách nhau 5 số. Thì ta phải nói rằng khoảng cách để luôn luôn có có 2 số 1 trong đoạn là 5 số. (Nghĩa là lấy max của những khoảng cách này)

1. Gọi pos[arr[i]] là vị trí mà giá trị của
phần tử thứ i xuất hiện trước đó.

dis = [-INF]*(n+1)pos = [0]*(n+1)

- Khởi tạo giá trị mặc định cho dis[i] là những giá trị rất nhỏ(Vì ta đang lấy max).

- Còn pos thì là '0' vì chưa xuất hiện lần nào, kiểu như là ta đang để nó ở vạch xuất phát.

2. Nếu lầy vị trí hiện tại của một phần tử trừ cho vị trị xuất hiện trước đó, ta được khoảng cách mà phần tử đó xuất hiện.
- Tức:

    dis[arr[i]] = i - pos[arr[i]]

- Nhưng ta phải lấy khoảng cách dài nhất nên:

    dis[arr[i]] = max(dis[arr[i]], i - pos[arr[i]])

- Nhớ đặt lại vị trí xuất hiện trước đó là vị trí ta vừa đứng để thực hiện với giá trị tiếp theo:

    pos[i] = i

3. Cuối cùng, ta thấy rằng khoảng cách từ một giá trị 'i' nào đó đến hết mảng chưa được xét đến, nên ta cần thêm

    for i in range(1, n+1):
        dis[i] = max(dis[i], n-pos[i]+1)

Giải thích:
- Khoảng cách của giá trị i đến hết sẽ bằng vị trí cuối cùng (n) trừ cho vị trí xuất hiện cuối cùng của nó (n - pos[i]).
- Ta cộng thêm 1 bởi vì sau vị trí pos[i], nó không xuất hiện lần nào nữa. Khoảng cách từ pos[i] đến n là n - pos[i] + 1.

Ví dụ: 3 1 2 3 4 5
- Ta sẽ xét giá trị 3.
- Vị trí số ba thứ nhất là 1.
- Vị trí số ba thứ hai là 4.
- Vậy khoảng cách 2 số 3 đầu từ là 4 - 1 = 3.
- Vì từ số 3 thứ nhất đi qua 3 số là sẽ gặp số 3 tiếp theo.

- Giờ ta tiếp tục xét đoạn từ phía sau số 3 thứ 2 (cuối cùng) đến hết.
- Vị trí của phần tử cuối cùng 6.
- Ta thấy phải tiếp đi qua 3 số mới hết đoạn này. Nhưng nếu lấy 6 - 4 thì mới được 2. Vậy ta phải cộng thêm 1 mới có kết quả chính xác.

***Step 2: Xậy dựng mảng mang val[i] là giá trị của phần tử nhỏ nhất luôn xuất hiện mỗi 'i' đoạn bất kì. (đây chính là đáp án của cả bài)***

1. Khởi tạo giá trị cho mảng là những giá trị rất rất lớn.

val = [INF]*(n+1)

2. Xây dựng val[i].

for i in range(1, n+1):
    val[dis[arr[i]]] = min(val[dis[arr[i]]], arr[i]);

- Khoảng cách dài nhất của phần tử arr[i]: ```val[dis[arr[i]]]```
- Giá trị của phần tử arr[i]: ```arr[i]```
- Vậy đoạn code trên mang ý nghĩa, với khoảng cách như vậy, thì arr[i] đã là phần tử nhỏ nhất chưa. Nếu có, ta lưu lại ```arr[i]``` vào ```val[dis[arr[i]]]```.

3. Tiếp tục nhỏ hóa val[i] để có đáp án chính xác.
- Ta biết rằng, một phần tử luôn xuất hiện trong đoạn 3 số bất kì thì cũng sẽ luôn xuất hiện trong đoạn 4 số bất kì.
- Phải vậy không, xem xét phần tử có giá trị là 3 trong đoạn sau:

    - Rõ ràng ta thấy cứ 3 số thì có 1 số 3. Và 4 số thì cũng sẽ có 1 số ba.
    - Mà ```val[3] = 3``` ```val[4] = 7```
    - Vậy nếu giá trị luôn xuất hiện đoạn 3 số ```val[3]``` mà nhỏ hơn giá trị luôn xuất hiện hiện trong đoạn 4 số ```val[4]``` thì thay vì lấy ```val[4]``` ta lấy ```val[3]``` sẽ tốt hơn.
    - Suy ra:

- Ta có đoạn code sau:

for i in range(1, n+1):
	val[i] = min(val[i], val[i-1])

***Step 4: In ra kết quả***
Mọi thứ đều đã được chuẩn bị xong, giờ ta chỉ cần in ra mảng val[i].

Lưu ý là nếu val[i] = INF tức là chẳng có phần tử nào liên tục xuất hiện trong các đoạn có i số cả. Vì vậy ta sẽ in ra -1 với các giá trị này. (Theo đề)