Kỳ thi HSG Duyên hải và Đồng bằng Bắc Bộ 2025 - Tin học - Khối 10

Khi giảng dạy về nội dung ước số chung lớn nhất, Alice đã cho học sinh bài toán sau:

Cho \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hãy chọn ra nhiều số nhất mà ước chung lớn nhất của chúng lớn hơn \(1\).

Ví dụ, với dãy số gồm bốn số \(4, 5, 8, 20\), có thể chọn được nhiều nhất ba số, chọn các số \(4, 8, 20\) có ước chung lớn nhất là \(4\).

Yêu cầu: Cho \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\). Hãy tính số lượng số nhiều nhất chọn được thỏa mãn điều kiện bài toán.

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(n \le 1000\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(a_i \le 10^{18}\)).

Output

• Ghi ra một số nguyên là số lượng số chọn được.

Example

4
4 5 8 20

3

4
2 4 6 8

4

Scoring

• Subtask 1 (\(20\%\) số điểm): \(n = 2\) và \(a_i \le 10^6\) (\(1 \le i \le n\)).
• Subtask 2 (\(30\%\) số điểm): \(n \le 18\).
• Subtask 3 (\(30\%\) số điểm): \(a_i \le 10^6\) (\(1 \le i \le n\)).
• Subtask 4 (\(20\%\) số điểm): Không có ràng buộc nào thêm.

Trong buổi họp lớp, Alice đã chụp được \(n\) bức ảnh, các bức ảnh được đánh số từ \(1\) đến \(n\). Bức ảnh thứ \(i\) (\(1 \le i \le n\)) có kích thước \(s_i\).

Có \(m\) bạn trong lớp muốn nhờ Alice sao chép các bức ảnh. Bạn thứ \(k\) (\(1 \le k \le m\)) sẽ đưa cho Alice hai ổ đĩa, ổ đĩa thứ nhất có sức chứa \(a_k\), ổ thứ hai có sức chứa \(b_k\) và một danh sách \(L_k\) là các bức ảnh không cần sao chép. Bạn thứ \(k\) mong muốn có thể sao chép được nhiều bức ảnh nhất vào hai ổ đĩa gồm các bức ảnh không thuộc danh sách \(L_k\).

Alice không chắc chắn có thể sao chép được tối đa các bức ảnh theo cách tối ưu. Tuy nhiên, bạn thứ \(k\) vẫn vui vẻ nếu số lượng bức ảnh sao chép được không ít hơn \((g_k - 1)\), trong đó \(g_k\) là số lượng tối đa các bức ảnh có thể sao chép được theo cách tối ưu.

Yêu cầu: Hãy giúp Alice đưa ra kế hoạch sao chép các bức ảnh cho các bạn. Giả sử \(t_k\) là số lượng bức ảnh mà Alice có thể sao chép cho bạn thứ \(k\) (\(1 \le k \le m\)), giá trị này được chấp nhận nếu \((g_k - 1) \le t_k \le g_k\).

Input

• Dòng đầu chứa hai số nguyên dương \(n, m\) (\(n, m \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(s_1, s_2, \ldots, s_n\) (\(s_i \le 10^9\)).
• Dòng thứ \(k\) (\(1 \le k \le m\)) trong \(m\) dòng sau có dạng:
  • Hai số đầu tiên là \(a_k, b_k\) (\(a_k, b_k \le 10^9\)).
  • Số thứ ba là số \(|L_k|\), là số bức ảnh mà bạn \(k\) không thích.
  • Tiếp theo là \(|L_k|\) số, là chỉ số các bức ảnh thuộc danh sách \(L_k\).

Tổng số lượng phần tử trong \(m\) danh sách không vượt quá \(10^5\) (\(\sum_{k=1}^{m}|L_k| \le 10^5\)).

Output

• Dòng đầu chứa số nguyên \(t_1\) là số bức ảnh có thể sao chép cho bạn thứ nhất.
• Dòng thứ hai là một xâu độ dài \(n\) chỉ gồm các kí tự 0, 1, 2 mô tả cách sao chép các bức ảnh cho bạn thứ nhất, trong đó kí tự thứ \(i\) (\(1 \le i \le n\)) bằng 0 cho biết bức ảnh thứ \(i\) không được sao chép, bằng 1 hoặc 2 cho biết bức ảnh \(i\) được sao chép vào đĩa 1 hoặc đĩa 2.
• Do dữ liệu ghi ra quá lớn nên với các bạn còn lại chỉ cần đưa ra số lượng bức ảnh có thể sao chép được. Cụ thể, dòng thứ ba chứa \(m - 1\) số \(t_2, t_3, \ldots, t_m\).

Example

6 3
2 1 1 3 4 1
5 5 0
5 5 2 2 6
5 7 0

5
111022
4 5

Scoring

• Subtask 1 (\(25\%\) số điểm): \(n \le 10\); \(m \le 3\); \(a_k, b_k \le 1000\); \(|L_k| = 0\).
• Subtask 2 (\(25\%\) số điểm): \(n \le 50\); \(m \le 3\); \(a_k, b_k \le 1000\).
• Subtask 3 (\(25\%\) số điểm): \(|L_k| = 0\).
• Subtask 4 (\(25\%\) số điểm): Không có ràng buộc nào thêm.

Alice thiết kế trò chơi điều khiển robot như sau: Một robot đặt trên một sân được biểu diễn như một lưới ô vuông kích thước \(n \times m\). Các dòng được đánh số từ \(0\) đến \(n - 1\), các cột được đánh số từ \(0\) đến \(m - 1\). Ô nằm giao giữa hàng \(i\) cột \(j\) được gọi là ô \((i, j)\). Một số ô của lưới là tường, các ô còn lại là ô tự do.

Người chơi điều khiển robot bằng bốn loại lệnh: U, D, L, R. Giả sử robot đang đứng tại ô \((x, y)\), robot sẽ di chuyển tương ứng như sau:

• Lệnh U: Nếu \(x = 0\) hoặc \((x - 1, y)\) là tường, robot sẽ không di chuyển. Ngược lại, robot sẽ di chuyển đến \((x - 1, y)\).
• Lệnh 😩 Nếu \(x = n - 1\) hoặc \((x + 1, y)\) là tường, robot sẽ không di chuyển. Ngược lại, robot sẽ di chuyển đến \((x + 1, y)\).
• Lệnh L: Nếu \(y = 0\) hoặc \((x, y - 1)\) là tường, robot sẽ không di chuyển. Ngược lại, robot sẽ di chuyển đến \((x, y - 1)\).
• Lệnh R: Nếu \(y = m - 1\) hoặc \((x, y + 1)\) là tường, robot sẽ không di chuyển. Ngược lại, robot sẽ di chuyển đến \((x, y + 1)\).

Người chơi không được biết chính xác vị trí ban đầu của robot, chỉ biết rằng robot có thể đang ở một trong \(k\) ô tự do \((u_1, v_1), (u_2, v_2), \ldots, (u_k, v_k)\).

Yêu cầu: Hãy tìm một dãy lệnh điều khiển robot để robot luôn kết thúc tại vị trí \((0, 0)\).

Input

• Dòng đầu chứa ba số nguyên dương \(n, m, k\) (\(n, m \le 200\); \(k \le 10\)).
• Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa \(m\) số mô tả lưới, số thứ \(j\) bằng 0 (hoặc 1) tương ứng ô \((i, j)\) là không có tường (hoặc có tường).
• Dòng thứ \(t\) trong \(k\) dòng tiếp theo, mỗi dòng chứa hai số \(u_t, v_t\).

Dữ liệu đảm bảo bài toán luôn có cách di chuyển thỏa mãn.

Output

• Ghi ra một dòng chứa một xâu chỉ gồm các kí tự L, R, U, D mô tả dãy lệnh.

Example

2 2 2
0 0
1 0
0 1
1 1

UL

Scoring

• Subtask 1 (\(15\%\) số điểm): \(k = 1\) và tất cả các ô đều là ô tự do.
• Subtask 2 (\(25\%\) số điểm): \(k = 1\).
• Subtask 3 (\(30\%\) số điểm): \(m, n \le 10\); \(k \le 3\).
• Subtask 4 (\(30\%\) số điểm): Không có ràng buộc nào thêm.