Đề thi Sơ loại Tin học trẻ - 2022

Bài 1: Dãy cấp số nhân

Cho bảng chữ kích thước \(m \cdot n\), mỗi ô chứa một kí tự \(A\) hoặc \(B\). Một hình chữ nhật con của bảng được gọi là bảng đẹp bậc \(k\) nếu số lượng kí tự \(A\) và số lượng kí tự \(B\) trong bảng con chênh lệch không quá \(k\).

Yêu cầu

Cho bảng chữ kích thước \(m \cdot n\) và số nguyên \(k\), hãy tìm bảng con là bảng đẹp lớn nhất.

Input

• Dòng đầu chứa số nguyên \(T(T \leq 5)\) là số bộ dữ liệu.
• \(T\) nhóm dòng sau, mỗi dòng mô tả một bộ dữ liệu có dạng:
• Dòng đầu chứa ba số nguyên \(m, n, k\).
• \(m\) dòng tiếp theo, mỗi dòng chứa một xâu kí tự độ dài \(n\) chỉ gồm kí tự \(A\) hoặc \(B\).

Output

• Ghi ra thiết bị ra chuẩn \(T\) dòng, mỗi dòng chứa một số là số lượng ô trong bảng tìm được
  tương ứng với dữ liệu vào.

Scoring

• Có \(25\)% số điểm của bài có \(m \cdot n \leq 100\).
• Có \(25\)% số điểm của bài có \(m \cdot n \leq 2000\).
• Có \(25\)% số điểm của bài có \(m \cdot n \leq 40000, k = 0\).
• Có \(25\)% số điểm của bài có \(m \cdot n \leq 60000\).

Example

2
3 4 0
AAAA
BBBB
BAAA
3 4 1
AAAA
BBBB
BAAA

8
9

Phép nhân hai ma trận chỉ thực hiện được khi số cột của ma trận bên trái bằng số dòng của ma trận
bên phải. Nếu ma trận \(A\) có kích thước \(m\) x \(n\) và ma trận \(B\) có kích thước \(n\) x \(p\) , thì ma trận
tích C = \(A\) x \(B\) có kích thước \(m\) x \(p\) , phần tử đứng ở hàng thứ \(i\), cột thứ \(j\) xác định bởi:

\(c_{i,j} = a_{i,1}b_{1,j} + a_{i,2}b_{2,j} + \dots + a_{i,n}b_{n,j}\)

Phép nhân ma trận có các tính chất kết hợp: (\(A\) x \(B\)) x \(C\) = \(A\) x (\(B\) x \(C\))

Ví dụ:
\(A = \binom{0, 1}{1, 1}; A^2 = \binom{1, 1}{1, 2}; A^3 = \binom{1, 2}{2, 3}\)

Yêu cầu: Cho ma trận \(A\) kích thước \(n\) x \(n\) và ma trận B, hãy kiểm tra xem \(A^3\) có bằng hay \(B\) không?

Input

• Dòng thứ nhất chứa số nguyên dương \(T\) \((T \leq 20)\) là số lượng bộ dữ liệu;
• Tiếp theo là \(T\) nhóm dòng, mỗi nhóm dòng tương ứng với một bộ dữ liệu có dạng:
• Dòng đầu chứa số nguyên \(n\);
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả ma trận \(A\), các số có giá trị tuyệt đối không vượt quá 1000;
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên mô tả ma trận \(B\), các số có giá trị tuyệt đối không vượt quá 10^18.

Output

Ghi ra thiết bị ra chuẩn gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với một bộ dữ liệu theo thứ tự xuất hiện trong file dữ liệu vào: ghi thông báo ‘YES’ nếu \(A^3 = B\) và ghi ‘NO’ trong trường hợp ngược lại.

Scoring

• Có \(50\)% số test ứng với \(50\)% số điểm của bài thỏa mãn: \(n \leq 10\);
• \(50\)% số test còn lại ứng với \(50\)% số điểm của bài thỏa mãn: \(n \leq 500\).

Example

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

NO
YES

Cho chuỗi kí tự \(s\) có độ dài \(n\) chỉ bao gồm các kí tự in thường. Các kí tự được đánh số từ 0 đến \(n - 1\), \(s = s_0,s_1,\dots,s_{n-1}\)

Chuỗi này sẽ được áp dụng lần lượt các thao tác thay đổi \((i,j,c_1,c_2)\) là biến đổi các vị trí là kí tự \(c_1\) thành kí tự \(c_2\) trong đoạn từ \(i\) đến \(j\).

Yêu cầu: Cho biết chuỗi \(s\) ban đầu và \(m\) thao tác biến đổi, hãy đưa ra chuỗi cuối cùng sau biến đổi.

Input

• Dòng đầu chứa chuỗi \(s\) có độ dài \(n\) \((1 \leq n \leq 10^6)\), xâu \(s\) chỉ chứa kí tự thường;
• Dòng thứ hai chứa số \(m\) \((1 \leq m \leq 1.5 \times 10^5)\)
• \(m\) dòng tiếp theo mỗi dòng chứa \(i, j, c_1, c_2\) \((0 \leq i \leq j < n; c_1 \neq c_2)\)

Output

Ghi ra thiết bị ra chuẩn xâu \(s\) sau biến đổi.

Scoring

• Có \(20\)% số test ứng với \(20\)% số điểm của bài có \(n, m \le 2000\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có \(n, m \leq 5 \times 10^4\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có \(n \leq 3 \times 10^5\);
• Có \(20\)% số test khác ứng với \(20\)% số điểm của bài có các kí tự trong xâu và biến đổi chỉ là \('a'\) hoặc \('b'\);
• Có \(20\)% số test còn lại ứng với \(20\)% số điểm của bài không có ràng buộc gì thêm

Example

aaaabbbbcccc
3
0 2 a y
5 9 b c
1 3 a z

yyyzbccccccc

Tin sinh học (Bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệ của các ngành để giải quyết các vấn đề sinh học. Một bài toán được nghiên cứu để sử dụng phân tích dữ liệu sinh học như sau: Cho hai xâu \(S_1, S_2\), hãy tìm cách cắt xâu \(S_1\) thành ít đoạn nhất sau đó ghép tất cả các đoạn lại theo một thứ tự nào đó để nhận được xâu \(S_2\).

Ví dụ: \(S_1 = "abcabc", S_2 = "aabbcc"\), một phương án cắt \(S_1\) tại các vị trí sau kí tự thứ \(1\), thứ \(3\), thứ \(5\) nhận được bốn xâu \("a", "bc", "ab", "c"\) để ghép được xâu \(S_2 = "aabbcc"\).

Input

• Dòng đầu chứa xâu \(S_1\) chỉ gồm các kí tự \('a'\) đến \('z'\);
• Dòng thứ hai chứa xâu \(S_2\) chỉ gồm các kí tự \('a'\) đến \('z'\).

Output

Ghi \(-1\) nếu không tồn tại cách cắt thỏa mãn; ngược lại, gọi \(c\) là số điểm cắt và các vị trí cắt là \(1 \le p_1 < p_2 < \dots < n\), đánh số các đoạn được cắt ra theo thứ tự từ đầu đến cuối bắt đầu từ \(1\) đến \(c+1\) , trường hợp này cần ghi ra ba dòng theo khuôn dạng:

• Dòng đầu chứa số nguyên dương \(c\);
• Dòng thứ hai gồm \(c\) số nguyên là các vị trí cắt \(p_1,p_2,\dots,p_c\);
• Dòng thứ ba gồm \(c+1\) là một hoán vị của \(1,2,\dots,c+1\) mô tả cách ghép các đoạn, các số cách nhau bởi dấu cách.

Scoring

• Có \(30\)% số test ứng với \(30\)% số điểm có độ dài xâu \(S_1,S_2\) đều không vượt quá \(20\);
• Có \(30\)% số test khác ứng với \(30\)% số điểm có độ dài xâu \(S_1,S_2\) đều không vượt quá \(60\);
• Có \(40\)% số test còn lại ứng với \(40\)% số điểm có độ dài xâu \(S_1,S_2\) đều không vượt quá \(10^4\).

Cách tính điểm:

Có 20 test, mỗi test \(5.0\) điểm. Gọi số điểm cắt do thí sinh tìm được là \(c\), số điểm cắt của Ban giám khảo là \(q\), khi đó số điểm bạn đạt được cho mỗi test là \(5.0 \times min(1, \frac{q^5}{c^5})\)

Example

abcabc
aabbcc

3
1 3 5
1 3 2 4