Tuyển sinh lớp 10 Chuyên PTNK 2026

Cho xâu \(S\) gồm các chữ cái Latin thường từ a tới z.

Ta được phép xáo trộn tùy ý vị trí các ký tự trong xâu \(S\), sau đó cắt xâu \(S\) thành các đoạn con sao cho tất cả các đoạn con thu được đều là xâu đối xứng.

Mục tiêu là thực hiện việc cắt sao cho số lượng đoạn con tạo thành là ít nhất có thể.

Input

• Một dòng duy nhất chứa xâu ký tự \(S\) (\(1 \le |S| \le 10^6\)) chỉ gồm các chữ cái Latin in thường.

Output

• Ghi ra một số nguyên duy nhất là số lượng đoạn con đối xứng ít nhất có thể chia được sau khi đã xáo trộn các ký tự.

Example

abcadd

2

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(|S| \le 9\), \(S\) chỉ gồm các ký tự a và b.
• Subtask \(2\) (\(30\%\) số điểm): \(|S| \le 9\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Dọc theo một ống dẫn nước nóng, người ta lắp \(n\) cảm biến nhiệt độ cách đều nhau, được đánh số từ \(1\) tới \(n\). Cảm biến thứ \(i\) đang hiển thị nhiệt độ đo được là \(a_i\) (nhiệt độ). Nhiệt độ có xu hướng phụ thuộc vào vị trí trên đường ống, theo đó người ta tính toán được nhiệt độ trung bình về mặt lý thuyết của đoạn \([l; r]\) (\(1 \le l \le r \le n\)) là \(l + r\). Để kiểm chứng, họ cần đếm số lượng đoạn phù hợp với lý thuyết.

Yêu cầu: Hãy đếm số đoạn cảm biến liên tiếp mà nhiệt độ trung bình đo được bằng với nhiệt độ trung bình về mặt lý thuyết. Cụ thể cần đếm số đoạn \([l; r]\) (\(1 \le l \le r \le n\)) thỏa mãn:

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 \le n \le 3 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).

Output

• Một dòng chứa số nguyên duy nhất là số đoạn thỏa mãn.

Example

3
3 3 6

3

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 300\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 3000\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Số nguyên dương \(m > 1\) được gọi là "số rất lẻ" nếu các ước dương của \(m\) (kể cả chính nó) có thể được viết lên một vòng tròn theo một thứ tự nào đó sao cho tổng của hai số đứng cạnh nhau luôn là một số lẻ.

Ngoài ra, tổng của tất cả các ước dương của \(m\) cũng phải là số lẻ.

Ví dụ, \(18\) là một số rất lẻ vì các ước của nó là: \(1, 2, 3, 6, 9, 18\). Có thể viết chúng lên vòng tròn theo thứ tự trên, khi đó tổng của hai số đứng cạnh nhau luôn là số lẻ. Đồng thời, tổng các ước của chúng cũng là số lẻ:

mà \(39\) cũng là số lẻ.

Yêu cầu: cho \(q\) truy vấn. Mỗi truy vấn gồm một số nguyên dương \(n\). Hãy in ra số lượng số rất lẻ là ước của \(n\).

Input

• Dòng đầu tiên chứa số nguyên dương \(q\) (\(q \leq 10\)) - số lượng truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(n\) (\(1 \leq n \leq 10^{18}\)).

Output

• Ghi ra \(q\) dòng, mỗi dòng một số nguyên duy nhất là câu trả lời cho truy vấn tương ứng.

Example

3
18
30
7

2
1
0

Subtasks

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 10^3\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \leq 10^6\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \leq 10^{12}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Cho ma trận kích thước \(n \times m\). Nhân vật phải di chuyển từ vị trí bắt đầu đến vị trí kết thúc theo chỉ định, bằng cách thực hiện các bước dịch chuyển tức thời từ ô \((x, y)\) đến ô \((z, t)\) thuộc bảng nếu thỏa mãn điều kiện \((z - x)^2 + (t - y)^2 = d_i\) với \(d_i\) là một trong \(k\) loại dịch chuyển cho trước.

Có thử thách:

• Cùng lúc với mỗi lượt nhân vật di chuyển, con sói cũng có thể đứng yên hoặc đi sang các ô chung cạnh với ô hiện tại của nó (trong phạm vi bảng). Nếu sau một lượt đi nào đó, nhân vật và sói đứng chung một ô thì nhân vật sẽ chết (cho dù ô đó là ô đích).
• Một số ô bị cấm, không ai được phép đi vào (cả sói và nhân vật).
• Sói ngụy trang rất tốt nên nhân vật chỉ biết được vị trí ban đầu của nó.

Lưu ý rằng cũng có thể có nhiều con sói trong ma trận.

Yêu cầu: tìm ít lượt di chuyển nhất để về đích, nếu không có cách nào thì in \(-1\).

Input

• Dòng đầu tiên gồm ba số nguyên \(n, m\) và \(k\) (\(1 \le n, m \le 500, 1 \le k \le 26\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(m\) ký tự mô tả ma trận bảng:
  • . : Ô trống mà nhân vật và sói có thể đi vào.
  • # : Ô tường cấm, không ai được phép đi vào.
  • s : Vị trí xuất phát của nhân vật.
  • t : Vị trí đích đến của nhân vật.
  • w : Vị trí ban đầu của sói.
• Dòng cuối cùng chứa \(k\) số nguyên \(d_1, d_2, \dots, d_k\) (\(1 \le d_1 < d_2 < \dots < d_k \le 26\)) là khoảng cách bình phương của các loại dịch chuyển.

Output

• Một số nguyên duy nhất là số lượt di chuyển ít nhất để nhân vật về đích an toàn, hoặc in ra \(-1\) nếu không có kế hoạch di chuyển nào khả thi.

Example

2 5 2
s..#.
w..#t
1 5

3

Scoring

• \(8\%\) số điểm: \(k = 1, d = 1\), không có ô w và không có ô #.
• \(20\%\) số điểm: \(k = 1, d = 5\), không có ô w và không có ô #.
• \(20\%\) số điểm: không có ô w.
• \(24\%\) số điểm: có đúng \(1\) ô w.
• \(28\%\) số điểm: Không có ràng buộc thêm.