THT C Vòng Sơ loại Toàn quốc 2025 - Lần 2

Chọn số

Cho \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\), hãy chọn ra một tập \(S\) nhiều số nhất mà không có hai số nào thuộc tập \(S\) chia hết cho nhau.

Input

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

Output

• Gồm một dòng chứa một số là số lượng số chọn thuộc tập \(S\).

Example

2
5 6

2

2
5 10

1

5
1 2 3 4 5

3

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n = 2\).
• Subtask \(2\) (\(30\%\) số điểm): \(n = 3\).
• Subtask \(3\) (\(20\%\) số điểm): Không có ràng buộc nào thêm.

Cho hai dãy số nguyên \(a_1, a_2, \dots, a_m\) và \(b_1, b_2, \dots, b_n\). Hãy tìm dãy chỉ số \(0 < i_1 < i_2 < \dots < i_k \leq m\) và dãy chỉ số \(0 < j_1 < j_2 < \dots < j_k \leq n\) thỏa mãn một trong hai điều kiện sau:

1. \(a_{i_1} \geq b_{j_1}; a_{i_2} \leq b_{j_2}; a_{i_3} \geq b_{j_3}; \dots\)
2. \(a_{i_1} \leq b_{j_1}; a_{i_2} \geq b_{j_2}; a_{i_3} \leq b_{j_3}; \dots\)

Input

• Dòng đầu chứa hai số nguyên \(m, n\);
• Dòng thứ hai chứa \(m\) số nguyên mô tả dãy \(a_1, a_2, \dots, a_m\) (\(|a_i| \leq 10^9\));
• Dòng thứ ba chứa \(n\) số nguyên mô tả dãy \(b_1, b_2, \dots, b_n\) (\(|b_j| \leq 10^9\)).

Output

• Gồm một dòng chứa số \(k\) lớn nhất tìm được.

Example

3 4
1 2 3
2 0 1 4

3

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(m \leq 20; n \leq 20\);
• Subtask \(2\) (\(40\%\) số điểm): \(m \leq 20; n \leq 5000\);
• Subtask \(3\) (\(20\%\) số điểm): \(m \leq 5000; n \leq 5000\).

Chia dãy

Alice có một dãy số gồm \(n\) phần tử, \(A = (a_1, a_2, \dots, a_n)\). Alice muốn chia dãy \(A\) thành một số đoạn con liên tiếp sao cho tổng giá trị mỗi đoạn con là lớn nhất. Giá trị của một đoạn con được định nghĩa là hiệu số giữa phần tử lớn nhất và phần tử nhỏ nhất trong đoạn con đó.

Alice cần xử lý \(Q\) thao tác thuộc một trong hai loại sau:

1. Loại 1 có dạng: 1 l r x, có nghĩa là gán \(a_i = a_i + x\) với mọi \(l \le i \le r\).
2. Loại 2 có dạng: 2 l r, có nghĩa là tìm cách chia dãy gồm các phần tử từ \(l\) đến \(r\) của dãy \(A\) sao cho tổng giá trị là lớn nhất có thể.

Yêu cầu: Với mỗi thao tác loại 2, hãy đưa ra tổng giá trị lớn nhất khi chia.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, Q\) (\(n, Q \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^6\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một trong hai loại thao tác như đã mô tả ở trên. Trong tất cả các thao tác \(1 \le l \le r \le n\) và \(|x| \le 10^6\).

Output

• Gồm nhiều dòng, mỗi dòng ghi một số là tổng giá trị lớn nhất tương ứng khi thực hiện thao tác loại 2.

Example

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

3
2

Ràng buộc

• Subtask 1 (25%): \(n \le 20; Q = 1\).
• Subtask 2 (25%): \(n, Q \le 200\).
• Subtask 3 (25%): \(n, Q \le 3000\).
• Subtask 4 (25%): Không có ràng buộc nào thêm.

Có \(n\) mảnh nhựa hình vuông đơn vị, các mảnh nhựa được đánh số từ \(1\) đến \(n\). Trên mỗi cạnh và ở tâm hình vuông của mảnh nhựa ghi một số nguyên không âm. Mảnh nhựa được phép xoay nhưng không được lật.

Nhiệm vụ của người chơi là lựa chọn các mảnh nhựa và xếp thành một dãy thỏa mãn điều kiện sau:

• Hai mảnh nhựa kề cạnh nhau thì số ghi trên hai cạnh tiếp xúc đó phải bằng nhau;
• Tổng các số ở tâm các mảnh nhựa xếp được là lớn nhất.

Input

• Dòng đầu chứa số nguyên \(n\);
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa năm số nguyên không âm \(a_i, b_i, c_i, d_i, w_i\) (\(0 \le a_i, b_i, c_i, d_i \le 3\)) mô tả các số trên bốn cạnh hình vuông theo chiều kim đồng hồ và số \(w_i\) là số ở tâm của mảnh nhựa thứ \(i\).

Output

• Ghi một số nguyên \(S\) là tổng các số ở tâm các mảnh nhựa xếp được lớn nhất.

Example

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

3

Ràng buộc

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(50\%\) số điểm): \(n \le 100\); \(a_i = b_i; c_i = d_i\).

Các nhà khảo cổ học đã tìm được \(n\) mảnh bản đồ cổ. Mỗi mảnh đều có dạng hình chữ nhật, cụ thể, mảnh bản đồ thứ \(k\) (\(1 \le k \le n\)) có kích thước \(a_k \times b_k\) ô vuông, mỗi ô được tô bằng một trong bốn màu \(0, 1, 2, 3\) thể hiện độ cao của ô đó. Các nhà khảo cổ cho rằng tất cả các mảnh bản đồ này thuộc trong một bản đồ lớn duy nhất. Tuy nhiên, họ không biết vị trí của các mảnh, chỉ biết rằng mỗi mảnh phải nằm trọn vẹn bên trong bản đồ lớn và chiếm nguyên các ô.

Hãy giúp các nhà khảo cổ xây dựng một bản đồ có diện tích nhỏ nhất sao cho mỗi mảnh xuất hiện nguyên vẹn ở một vị trí nào đó trong bản đồ lớn (giữ nguyên kích thước, không quay).

Input

• Dòng đầu chứa số nguyên \(n\) (\(n \le 100\)).
• Tiếp theo là \(n\) nhóm dòng, mỗi nhóm dòng mô tả một mảnh bản đồ với khuôn dạng:
  • Dòng đầu tiên chứa hai số nguyên dương \(a_k, b_k\) (\(a_k, b_k \le 10\)).
  • Tiếp theo là \(a_k\) dòng, mỗi dòng chứa \(b_k\) số mô tả mảnh bản đồ.

Output

• Dòng đầu chứa hai số nguyên \(r, c\) là kích thước bản đồ lớn xây dựng được.
• Tiếp theo là \(r\) dòng, mỗi dòng chứa \(c\) số mô tả bản đồ lớn.

Example

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

3 3
0 0 2
0 0 1
0 1 2

Scoring

Với mỗi test, gọi \(s\) là số lượng ô trong bản đồ thí sinh tạo ra (\(s = r \cdot c\)), \(d\) là kết quả của Ban giám khảo, khi đó thí sinh sẽ đạt:

• Nếu \(s - d \le 100\) thì đạt \(0.95^{\max(0, s-d)}\) điểm.
• Ngược lại, đạt \(0\) điểm.

Constraints

• Subtask \(1\) (\(20\%\) số điểm): Tất cả các mảnh có \(a_k = 1\).
• Subtask \(2\) (\(40\%\) số điểm): Tất cả các mảnh có \(a_k \le 2\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc nào thêm.