Duyên hải Bắc Bộ 2025 - Khối 10 — đề thi, lời giải và phòng thi thử

Duyên hải Bắc Bộ 2025 - Khối 10

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. Ước chung

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, ..., 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, ..., 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 \leq 1000$ ).

Dòng thứ hai chứa $n$ số nguyên dương $a 1, a 2, ..., a n$ ( $a i \leq 1018$ ).

Output

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

Sample Input 1

4
5 8 4 20

Sample Output 1

Sample Input 2

4
2 4 6 8

Sample Output 2

Subtasks

Subtask 1 ( $20 %$ ): $n = 2$ và $a i \leq 106$ .

Subtask 2 ( $30 %$ ): $n \leq 18$ .

Subtask 3 ( $30 %$ ): $a i \leq 106$ .

Subtask 4 ( $20 %$ ): 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 2. Sao chép ảnh

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 \leq i \leq 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 \leq k \leq m$ ) sẽ đưa cho Alice hai ổ đĩa, ổ đĩa thứ nhất có sức chứa $a k$ , ổ đĩa 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 \leq k \leq m$ ), giá trị này được chấp nhận nếu $(g k - 1) \leq t k \leq g k$ .

Input

Dòng đầu chứa hai số nguyên dương $n, m$ ( $n, m \leq 105$ );

Dòng thứ hai chứa $n$ số nguyên dương $s 1, s 2, ..., s n$ ( $s i \leq 109$ );

Dòng thứ $k$ ( $1 \leq k \leq m$ ) trong $m$ dòng sau, mỗi dòng có dạng:Hai số đầu tiên là $a k, b k$ ( $a k, b k \leq 109$ );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á $105$ ( $\sum k=1 m |L k | \leq 105$ ).

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 \leq i \leq 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 thứ $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, ..., t m$ .

Sample Input

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

Sample Output

5
111022
4 5

Giải thích

Với bạn thứ 1, tối đa các bức ảnh có thể sao chép được là $5$ (ví dụ, đĩa 1 chứa bức ảnh 1, 2, 3; đĩa 2 chứa bức ảnh 5, 6). Kết quả đưa ra bằng $4$ hoặc $5$ đều được chấp nhận.

Với bạn thứ 2, tối đa các bức ảnh có thể sao chép được là $4$ (ví dụ, đĩa 1 chứa bức ảnh 1, 4; đĩa 2 chứa bức ảnh 3, 5). Kết quả đưa ra bằng $3$ hoặc $4$ đều được chấp nhận.

Với bạn thứ 3, tối đa các bức ảnh có thể sao chép được là $6$ (ví dụ, đĩa 1 chứa bức ảnh 1, 4; đĩa 2 chứa bức ảnh 2, 3, 5, 6). Kết quả đưa ra bằng $5$ hoặc $6$ đều được chấp nhận.

Subtasks

Subtask	Điểm	Ràng buộc
1	$25$	$n \leq 10; m \leq 3; a k, b k \leq 1000; L k = 0$ .
2	$25$	$n \leq 50; m \leq 3; a k, b k \leq 1000$ .
3	$25$	$L k = 0$ .
4	$25$	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 3. Di chuyển robot

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 D: 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), ..., (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 \leq 200; k \leq 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.

Sample Input

Sample Output

UL

Giải thích

Nếu ban đầu robot ở ô $(0, 1)$ thì vị trí robot sau mỗi lệnh tương ứng như sau: $(0, 1) \to (0, 1) \to (0, 0)$ .

Nếu ban đầu robot ở ô $(1, 1)$ thì vị trí robot sau mỗi lệnh tương ứng như sau: $(1, 1) \to (0, 1) \to (0, 0)$ .

Subtasks

Subtask	Điểm	Ràng buộc
1	$15$	$k = 1$ và tất cả các ô đều là ô tự do.
2	$25$	$k = 1$ .
3	$30$	$n, m \leq 10; k \leq 3$ .
4	$30$	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: Chưa xác minh thời gian chạy trên toàn miền.

Cấu trúc đề và tiến độ