[TFL x Tân Khoa] Contest #1 "Ôn thi Tuyển sinh 10" (TS10 Chuyên Tin 2025)

Trong lúc dọn dẹp lại nhà kho, Miku đã tìm thấy một chiếc piano đồ chơi gắn liền với tuổi thơ của mình, có hình dạng như sau (ở trên: nốt nhạc, ở dưới: thứ tự phím đàn):

Là một người yêu âm nhạc, Miku muốn chơi thử một giai điệu yêu thích. Cụ thể hơn, giai điệu này có thể biểu diễn bằng một xâu \(s\) gồm \(n\) kí tự, với kí tự thứ \(i\) là nốt thứ \(i\). Tuy nhiên, Miku đã quên hoàn toàn cách chơi đàn này, không biết cần phải ấn phím thế nào để ra được đoạn giai điệu \(s\). Là một lập trình viên, bạn hãy giúp Miku nhé!

Yêu cầu

Xác định các phím cần bấm theo thứ tự, để tạo nên giai điệu cho trước.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) (\(1 \leq n \leq 100\)).
• Dòng thứ hai gồm một xâu \(s\) chứa \(n\) kí tự \(s_1s_2 \dots s_n\) (\(s_i \in \{C, D, E, F, G, A, B\}\)).

Output

• Dòng duy nhất chứa \(n\) số, số thứ \(i\) là thứ tự của phím ứng với nốt nhạc thứ \(i\).

Example

14
DEFDAAGDEFDGGF

2 3 4 2 6 6 5 2 3 4 2 5 5 4

11
DEFDFGECCGF

2 3 4 2 4 5 3 1 1 5 4

Trong thư viện STL của ngôn ngữ C++, Double-ended queue (hay còn gọi là Deque) là một cấu trúc dữ liệu rất phổ biến và được sử dụng rộng rãi. Cụ thể hơn, nó là một kiểu dữ liệu tổng quát hoá của một hàng đợi, cho phép ta thực hiện thao tác thêm vào hoặc loại bỏ một phần tử ở cả hai đầu danh sách (ở cả vị trí đầu tiên và cuối cùng, trong khi đó, với hàng đợi thông thường ta chỉ có thể thêm phần tử vào cuối, và lấy ra phần tử ở đầu).

Miku đang có một Deque \(a\) gồm \(n\) phần tử, trong đó phần tử thứ \(i\) có giá trị là \(a_i\). Cô quyết định sẽ thực hiện thao tác sau chính xác \(m\) lần:

• Chọn phần tử đầu tiên hoặc phần tử cuối cùng của \(a\). (chú thích: trong bài toán này, phần tử đầu là \(a[1]\), phần tử cuối là \(a[n]\))
• Loại bỏ phần tử đó ra khỏi Deque, đồng thời \(n\) sẽ giảm đi 1.

Sau khi thực hiện xong, Miku sẽ tính tổng giá trị của những phần tử còn lại trong \(a\). Phụ thuộc vào quá trình thực hiện thao tác, tổng sau cùng có thể khác nhau. Do đó, Miku thắc mắc rằng tổng này sẽ đạt giá trị lớn nhất là bao nhiêu.

Yêu cầu: Tìm tổng lớn nhất còn lại sau khi thực hiện \(m\) thao tác.

Input

• Dòng đầu tiên gồm số nguyên dương \(n, m\) (\(1 \leq m \leq n \leq 2 \times 10^5\)).
• Dòng tiếp theo gồm một dãy \(a\) chứa \(n\) phần tử \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)).

Output

• Dòng duy nhất chứa kết quả của bài toán – tổng lớn nhất còn lại.

Example

8 3
5 2 6 4 7 1 8 3

26

Scoring

• \(25\%\) số điểm tương ứng với \(m = 0\).
• \(25\%\) số điểm khác tương ứng với \(1 \leq m \leq 16\).
• \(25\%\) số điểm khác tương ứng với \(1 \leq m \leq n \leq 2 \times 10^3\).
• \(25\%\) số điểm còn lại không có ràng buộc gì thêm.

Cho \(n\) điểm trên mặt phẳng tọa độ \(Oxy\). Lấy hai điểm bất kỳ trong số \(n\) điểm này (tạm gọi là \(A\) và \(B\)), ta cần biết liệu trung điểm của đoạn thẳng \(AB\) có phải là một điểm nguyên hay không. Nếu xét tất cả cặp điểm, có bao nhiêu trung điểm như thế?

Nhắc lại, điểm \((x, y)\) là điểm nguyên nếu cả hoành độ \(x\) và tung độ \(y\) đều là số nguyên.

Yêu cầu: Đếm trong \(n\) điểm cho trước, có bao nhiêu cặp tạo ra một đoạn thẳng có trung điểm là điểm nguyên.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \leq 10^5\)).
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa hai số nguyên \(x_i, y_i\) (\(|x_i|, |y_i| \leq 10^8\)).
• Dữ liệu vào đảm bảo không có hai điểm nào có cùng tọa độ.

Output

• Dòng duy nhất chứa một số nguyên dương – kết quả bài toán – số lượng cặp đếm được.

Example

3
0 0
1 1
2 2

1

Scoring

• 25% số điểm tương ứng với \(n = 2\).
• 25% số điểm khác tương ứng với \(n \leq 10^3\).
• 25% số điểm khác tương ứng với \(n \leq 10^5\) và tất cả các điểm cùng nằm trên một đường thẳng; đường thẳng này song song với một trong hai trục tọa độ.
• 25% số điểm còn lại không có ràng buộc gì thêm.

Đề bài nằm ở trong bài 1 - notes.

Tham gia vào kỳ thi ôn tập TS10 2025 - Contest #1 để đọc đề.