Chọn ĐTQG Cà Mau 2025

Chọn ĐTQG Cà Mau 2025

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Phản đối xứng

Một xâu được gọi là chuẩn đối xứng nếu độ dài xâu lớn hơn 1 và khi đọc xâu từ trái sang phải cũng giống như đọc xâu từ phải sang trái. Ví dụ, xâu ABBA và xâu AABAA là chuẩn đối xứng; còn xâu ABAB và xâu A không phải là chuẩn đối xứng.

Một xâu được gọi là phản đối xứng nếu không tồn tại xâu chuẩn đối xứng xuất hiện trong xâu đó như là một xâu con liên tiếp. Ví dụ, xâu ABCAB là xâu phản đối xứng; còn xâu ABBA và xâu AABAA không là xâu phản đối xứng.

Alice có một xâu kí tự S độ dài n (đánh chỉ số bắt đầu từ 1) và cần thực hiện q thao tác, mỗi thao tác thuộc một trong hai loại sau: 1) Thao tác loại 1 có dạng: 1 i j, trong đó 1 ≤ i, j ≤ n, sẽ thực hiện tráo hai kí tự ở vị trí thứ i và thứ j cho nhau. 2) Thao tác loại 2 có dạng: 2 l r, trong đó 1 ≤ l < r ≤ n, yêu cầu kiểm tra xâu con của xâu S gồm các kí tự liên tiếp từ l đến r có phải là một xâu phản đối xứng hay không.

Yêu cầu: Cho xâu S và q thao tác, hãy giúp Alice thực hiện các thao tác trên xâu S.

Input

• Dòng đầu tiên chứa hai số nguyên dương n, q (n, q ≤ 3 × 10⁵).

• Dòng thứ hai chứa một xâu độ dài n, mỗi kí tự là một chữ cái hoa (‘A’..’Z’).

• Dòng thứ t (1 ≤ t ≤ q) trong q dòng tiếp theo chứa ba số nguyên mô tả thao tác.

Output

• Ghi ra một số dòng ứng với thao tác loại 2, ghi số 1 nếu xâu con tương ứng là xâu phản đối xứng, ngược lại ghi số 0.

Subtasks

• Có 40% số test thỏa mãn: n, q ≤ 100;

• 30% số test khác thỏa mãn: Cả q thao tác đều là thao tác loại 2;

• 30% số test còn lại không có ràng buộc nào thêm.

Sample Input 1

5 4
ABCAB
2 1 5
1 3 4
2 1 5
2 3 5

Sample Output 1

1
0
1

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Mật mã di truyền

Alice đang nghiên cứu một loại vi khuẩn với bộ gen dạng vòng tròn. Để đơn giản mô hình và thuận lợi trong xử lí, Alice biểu diễn chuỗi gen bằng một chuỗi nhị phân độ dài 2 × n. Vị trí của các kí tự được đánh số bắt đầu từ 1 đến 2 × n và ở mỗi vị trí là một trong hai loại protein cơ bản, được mã hóa là 0 hoặc 1. Kí tự ở vị trí thứ i (1 ≤ i ≤ n) bằng với kí tự ở vị trí thứ i + n.

Alice phát hiện ra rằng vi khuẩn sẽ có đặc tính đột biến nguy hiểm nếu đoạn "gen kích hoạt" xuất hiện trong vòng gen của vi khuẩn. Gen kích hoạt là một chuỗi nhị phân s có độ dài m (m ≤ n). Chuỗi s được gọi là xuất hiện nếu có thể tìm thấy s bằng cách đọc liên tiếp m kí tự trên chuỗi nhị phân biểu diễn độ dài 2 × n. Để đánh giá xác suất xảy ra đột biến, Alice cần biết có bao nhiêu cấu trúc gen khác nhau của vi khuẩn chứa "gen kích hoạt". Hai cấu trúc gen được coi là khác nhau nếu hai chuỗi nhị phân độ dài 2 × n có ít nhất một vị trí mà kí tự tại vị trí đó khác nhau.

Yêu cầu: Cho n và chuỗi s, hãy đếm số lượng cấu trúc gen khác nhau của vi khuẩn chứa "gen kích hoạt".

Input

• Dòng đầu chứa số nguyên n (n ≤ 60);

• Dòng thứ hai chứa một xâu kí tự s chỉ gồm kí tự 0 hoặc 1 (độ dài xâu s không vượt quá n).

Output

• Ghi ra một dòng chứa một số là lượng cấu trúc gen khác nhau của vi khuẩn chứa "gen kích hoạt".

Subtasks

• Có 30% số test thỏa mãn: n ≤ 20.

• 30% số test khác thỏa mãn: Độ dài xâu s không vượt quá 10.

• 40% số test còn lại không có ràng buộc nào thêm.

Sample Input 1

3
11

Sample Output 1

4

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 3. Trò chơi kinh doanh

Alice tham gia một trò chơi kinh doanh như sau: Alice được cung cấp một số T tiền ban đầu trong tài khoản và được phép kinh doanh trên n mặt hàng. Trò chơi diễn ra trong R lượt, trong mỗi lượt Alice được phép mua bán các mặt hàng nhằm thu về nhiều lợi nhuận nhất. Cụ thể, mỗi lượt, giá của từng mặt hàng được công bố và Alice được phép mua bán theo hai bước như sau:

• Bước 1 - Bán hàng: Nếu Alice đang có m_i đơn vị mặt hàng thứ i (1 ≤ i ≤ n) thì Alice có thể tiến hành bán s_i đơn vị mặt hàng (0 ≤ s_i ≤ m_i). Số tiền bán hàng sẽ được chuyển vào tài khoản ngay lập tức, trong đó P_i là giá mặt hàng thứ i, e là phí phụ thêm khi bán một đơn vị hàng. Số tiền thu được là s_i × (P_i - e). Số lượng hàng thứ i còn lại trong kho của Alice là (m_i - s_i).

• Bước 2 - Mua hàng (thực hiện sau khi tiến hành xong Bước 1): Nếu muốn mua s_i đơn vị mặt hàng thứ i (1 ≤ i ≤ n), Alice phải đủ tiền và trả ngay lập tức số tiền mua hàng. Số tiền trong tài khoản sẽ bị trừ đi một lượng là s_i × (P_i + d), trong đó P_i là giá mặt hàng thứ i, d là phí phụ thêm khi mua một đơn vị hàng. Số lượng hàng mua sẽ được chuyển vào kho. Số lượng mặt hàng i trong kho không được phép vượt quá C_i.

Yêu cầu: Hãy giúp Alice tìm cách mua bán hàng để tổng lượng tiền thu được là lớn nhất.

Input

• Dòng đầu chứa năm số nguyên không âm n, T, R, d, e (n ≤ 10⁹; T, R ≤ 10⁶).

• Dòng thứ hai chứa n số nguyên dương C₁, C₂, ⋯, C_n cho biết số lượng tối đa của từng mặt hàng được phép chứa trong kho (C_i ≤ 20, i = 1, 2, ⋯, n).

• Dòng thứ k (1 ≤ k ≤ R) trong R dòng tiếp theo chứa n số nguyên dương cho biết giá của n mặt hàng tại lượt thứ k, các số có giá trị không vượt quá 10⁶.

Output

• Ghi ra một số nguyên dương duy nhất là tổng lượng tiền Alice có được sau R lượt theo cách mua bán hàng tìm được.

Subtasks

• Có 50% số test của bài có tính chất: n = 3; R ≤ 5.

• Có 25% số test khác của bài có tính chất: n ≤ 5; R ≤ 5.

• Có 25% số test còn lại của bài có tính chất: n ≤ 5; R ≤ 500; d = e = 0.

Sample Input 1

3 2 2 1 0
1 1 1
1 1 1
2 3 4

Sample Output 1

4

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 4. Du lịch

Đất nước Alpha có n thành phố, đánh số từ 1 đến n. Các thành phố được nối với nhau bởi n - 1 đường hai chiều, mỗi đường nối một cặp thành phố và bảo đảm có đường đi lại giữa hai thành phố bất kì (trực tiếp hoặc đi qua một số thành phố khác). Thành phố thứ i (1 ≤ i ≤ n) có sân bay nếu số i là một số nguyên tố. Alice đang lên kế hoạch thăm một số thành phố của đất nước Alpha. Alice đánh giá s_i là mức độ yêu thích thăm thành phố i. Hành trình thăm đất nước Alpha của Alice bắt đầu thăm tại một thành phố có sân bay, đi thăm một số thành phố, hai thành phố liên tiếp trên hành trình có đường đi trực tiếp, không đi lại thành phố đã thăm, cuối cùng kết thúc tại một thành phố cũng có sân bay.

Yêu cầu: Tìm hành trình mà tổng mức độ yêu thích của các thành phố trên hành trình (bao gồm cả thành phố bắt đầu và kết thúc) là lớn nhất (hành trình có thể chỉ thăm một thành phố).

Input

• Dòng đầu tiên chứa một số nguyên n (2 ≤ n ≤ 2 × 10⁵);

• Dòng thứ hai gồm n số nguyên s₁, s₂, ⋯, s_n (|s_i| ≤ 10⁶; 1 ≤ i ≤ n);

• Dòng thứ i (1 ≤ i ≤ n - 1) trong n - 1 dòng tiếp theo chứa hai số nguyên u, v mô tả đường đi thứ i.

Output

• Ghi ra một dòng chứa một số là tổng mức độ yêu thích của hành trình tìm được.

Subtasks

• Có 30% số test thỏa mãn: n ≤ 100 và các giá trị s_i đều bằng 1.

• 20% số test khác thỏa mãn: Các giá trị s_i đều bằng 1.

• 50% số test còn lại không có ràng buộc nào thêm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 5. Trò chơi

Alice và Bob chơi một trò chơi trí tuệ trên lưới ô vuông kích thước m × n. Các hàng của lưới được đánh số từ 1 đến m từ trên xuống, các cột được đánh số từ 1 đến n từ trái sang phải, ô nằm ở hàng i (1 ≤ i ≤ m), cột j (1 ≤ j ≤ n) được gọi là ô (i, j).

Alice chọn một số nguyên dương D, sau đó cô chọn k (k ≤ m × n) ô phân biệt trên lưới (i₁, j₁), (i₂, j₂), ⋯, (i_k, j_k) và giữa ô thứ t (1 ≤ t ≤ k) điền một số nguyên s_t (0 ≤ s_t < D).

Bob cần điền số không âm nhỏ hơn D lên trên mỗi cạnh thuộc ít nhất một trong các ô Alice chọn để với mỗi ô trong k ô đều thỏa mãn: Tổng các số điền trên bốn cạnh chia cho D có phần dư bằng đúng số mà Alice điền ở giữa ô đó. Alice cho Bob biết tồn tại cách điền thỏa mãn.

Yêu cầu: Cho m, n, D và k ô với số điền ở giữa, hãy giúp Bob đưa ra một phương án điền các số trên các cạnh thỏa mãn yêu cầu.

Input

• Dòng đầu tiên chứa bốn số nguyên dương m, n, D, k (m × n ≤ 10⁵; D ≤ 10⁹);

• Dòng thứ t (1 ≤ t ≤ k) trong k dòng tiếp theo chứa các số nguyên i_t, j_t, s_t (1 ≤ i_t ≤ m; 1 ≤ j_t ≤ n; 0 ≤ s_t < D).

Output

• Ghi ra k dòng, dòng thứ t (1 ≤ t ≤ k) chứa bốn số nguyên không âm nhỏ hơn D lần lượt là các số điền trên các cạnh bên trái, bên trên, bên phải, bên dưới của ô (i_t, j_t).

Subtasks

• Có 30% số test thỏa mãn: m ≤ 4; m × n ≤ 100; D = 3; k ≤ 4.

• 30% số test khác thỏa mãn: m ≤ 4; m × n ≤ 100; D = 3.

• 20% số test khác thỏa mãn: m × n ≤ 100; D = 3.

• 20% số test còn lại không có ràng buộc nào thêm.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 6. Bảng điện tử

Bảng điện tử thường cung cấp ngắn gọn các thông tin quan trọng, các sự kiện, khẩu hiệu trong các dịp lễ hội. Công ty của Alice vừa xuất xưởng một bảng thông tin điện tử có dạng một hàng gồm n vị trí, mỗi vị trí hiển thị một kí tự. Các vị trí được đánh số từ 1 đến n từ trái qua phải. Các kí tự chạy từ phải qua trái. Cứ mỗi giây kí tự ở vị trí i chuyển sang vị trí i - 1 (i = 2, 3, ⋯, n) và kí tự mới từ xâu dữ liệu vào được đưa lên bảng ở vị trí n. Ban đầu, tất cả các vị trí đều chứa dấu cách.

Trong thời gian thử nghiệm, Alice chọn một số nguyên k (1 ≤ k ≤ 10) và cho phát lên bảng điện tử xâu S được tạo bằng cách viết liên tiếp các số tự nhiên chia hết cho k nằm trong đoạn [1, 10¹⁵].

Yêu cầu: Cho xâu T độ dài n, chỉ chứa các kí tự số trong phạm vi từ 0 đến 9. Hãy xác định thời điểm lần đầu tiên xuất hiện xâu T, giả thiết là thời điểm bắt đầu phát thử nghiệm là 0.

Input

• Dòng đầu tiên chứa hai số nguyên n, k;

• Dòng thứ hai chứa xâu T độ dài n.

Output

• Ghi ra một số nguyên là thời điểm lần đầu tiên xuất hiện xâu T. Nếu xâu T không xuất hiện ghi -1.

Subtasks

• Có 20% số test của bài có tính chất: Thời điểm lần đầu tiên xuất hiện xâu T nhỏ hơn 10⁶.

• Có 40% số test khác của bài có tính chất: 6 < n ≤ 30.

• Có 40% số test còn lại của bài có tính chất: 30 < n ≤ 150.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: Lời giải phụ thuộc cách hiểu đề; cần đối chiếu nguồn.