Chọn ĐTQG Vĩnh Long 2025

Chọn ĐTQG Vĩnh Long 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. Nguyên tố

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có đúng hai ước số dương là 1 và chính nó.

Cho hai số nguyên dương X và Y.

Yêu cầu : Hãy đếm trong đoạn từ X đến Y có bao nhiêu số thỏa mãn: số lượng các ước của nó là số nguyên tố.

Input

• Dòng thứ nhất chứa số T (T ≤ 10⁵) là số lượng các đoạn cần đếm.

• T dòng tiếp theo, mỗi dòng chứa hai số nguyên dương X và Y (1 ≤ X ≤ Y ≤ 10⁶).

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Gồm T dòng, mỗi dòng gồm một số nguyên duy nhất là kết quả cần tìm.

Scoring

Sample Input 1

2
1 5
10 50

Sample Output 1

4
14

Notes

Xét trường hợp X = 1, Y = 5:

• Số 1 có 1 ước (số ước không phải nguyên tố).

• Số 2 có 2 ước (số ước là nguyên tố).

• Số 3 có 2 ước (số ước là nguyên tố).

• Số 4 có 3 ước (số ước là nguyên tố).

• Số 5 có 2 ước (số ước là nguyên tố).

Kết quả: 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 2. Nhận quà

Trong thời gian nghỉ hè, bạn B tham gia một trò chơi trực tuyến và được nhận quà.

Để thử thách khả năng của người chơi, hệ thống đưa ra cách nhận quà như sau:

Cho N món quà có giá trị lần lượt là a₁, a₂, ⋯, a_N và hai số X, M. Người chơi chỉ được nhận dãy các món quà liên tiếp nhau có tổng lũy thừa bậc X của giá trị các món quà chia hết cho M. Hai dãy quà liên tiếp là khác nhau nếu tồn tại ít nhất một món quà không thuộc cả hai dãy.

Ví dụ với 3 món quà: {1, 5, 5} thì có 6 dãy các món quà liên tiếp là {1}, {5}, {5}, {1, 5}, {5, 5}, {1, 5, 5}, với X = 1 và M = 5 thì chỉ có 3 phương án nhận quà là: {5}, {5} và {5, 5}.

Yêu cầu : Hãy cho biết bạn B có bao nhiêu phương án nhận quà.

Input

• Dòng thứ nhất chứa ba số nguyên dương N, X, M (1 ≤ N ≤ 10⁵; 1 ≤ X ≤ 10¹⁸; 1 ≤ M ≤ 10⁵) lần lượt là số món quà và giá trị X, M theo yêu cầu.

• Dòng thứ hai chứa N số tự nhiên a₁, a₂, ⋯, a_N (1 ≤ a_i ≤ 10²⁰) lần lượt là giá trị các món quà.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Một số nguyên duy nhất là kết quả cần tìm.

Scoring

Sample Input 1

3 1 5
1 5 5

Sample Output 1

3

Sample Input 2

5 2 3
3 3 3 3 3

Sample Output 2

15

---

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.

Câu 3. Ghép đôi

Đầu năm học mới, để tăng cường tính đoàn kết trong học sinh, nhà trường tổ chức trò chơi cho N học sinh tham gia. Mỗi học sinh được cấp một mã số là các số nguyên a₁, a₂, ⋯, a_N (0 ≤ a_i ≤ 10⁹). Người quản trò yêu cầu các học sinh cần ghép đôi lại thành từng cặp với nhau để tham gia trò chơi, điều kiện là tổng mã số của từng cặp đôi một với các cặp khác không chênh lệch quá giá trị K do người quản trò đặt ra. Để học sinh không mất quá nhiều thời gian tìm người ghép đôi, người quản trò quy ước K chỉ nhận giá trị 0 hoặc 1. Có thể có những học sinh sẽ không được ghép với bạn khác (những học sinh này sẽ hỗ trợ làm trọng tài) và mỗi học sinh nếu được ghép chỉ thuộc một cặp duy nhất.

Yêu cầu : Cho biết số lượng cặp học sinh nhiều nhất tìm được mà tổng mã số của từng cặp đôi một với các cặp khác chênh lệch nhau không vượt quá K.

Input

• Dòng thứ nhất chứa hai số nguyên N, K (0 < N ≤ 2 · 10³, 0 ≤ K ≤ 1) lần lượt là số lượng học sinh tham gia và giá trị do người quản trò đặt ra;

• Dòng thứ hai chứa N số nguyên a₁, a₂, ⋯, a_N (0 ≤ a_i ≤ 10⁹) lần lượt là mã số của các học sinh.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Gồm một số nguyên duy nhất là giá trị cần tìm.

Scoring

Sample Input 1

7 0
2 4 1 3 5 6 1

Sample Output 1

3

Sample Input 2

6 1
1 2 3 10 30 3

Sample Output 2

2

Notes

Trong ví dụ thứ nhất, một trong các phương án ghép đôi là 2-5, 4-3, 1-6 (tổng mã số của các cặp đôi một chênh lệch là 0).

Trong ví dụ thứ hai, phương án ghép đôi là 1-3, 2-3 (tổng mã số của các cặp đôi một chênh lệch không quá 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 4. In tài liệu

Công ty D là một trong những công ty in ấn đặt tại trung tâm thành phố. Hiện tại, công ty dùng N máy để in tài liệu cho khách. Do có nhiều loại máy in được sử dụng trong công ty, thời gian để in xong một tài liệu trên các máy in có thể khác nhau.

Yêu cầu : Cho biết T là số lượng khách hàng cần in tài liệu, hãy xác định thời gian tối thiểu cần thiết để công ty có thể in xong tài liệu cho tất cả khách.

Để in mỗi tài liệu chỉ được sử dụng một máy in.

Input

• Dòng thứ nhất chứa hai số nguyên dương T (0 < T ≤ 10¹²) và N (0 < N ≤ 20) lần lượt là số lượng khách in tài liệu và số lượng máy in;

• Dòng thứ hai chứa N số nguyên dương a₁, a₂, ⋯, a_N (0 < a_i < 500) lần lượt là thời gian in xong một tài liệu của mỗi máy.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Một số nguyên duy nhất là thời gian tối thiểu tìm được tính bằng phút (không kể thời gian chuyển sang in tài liệu khác).

Scoring

Sample Input 1

4 3
20 30 35

Sample Output 1

40

Notes

Có 4 khách in tài liệu và 3 máy in. Máy 1 in tài liệu cho khách 1 mất 20p, máy 2 in tài liệu cho khách 2 mất 30p, máy 3 in tài liệu cho khách 3 mất 35p. Sau 20p máy 1 in xong tài liệu cho khách 1 thì in cho khách 4. Sau 40p thì tất cả tài liệu đều được in xong.

---

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. Dãy con

Cho dãy số nguyên a₁, a₂, ⋯, a_N. Dãy số a_i1, a_i2, ⋯, a_ik được gọi là dãy con của dãy đã cho nếu 1 ≤ i₁ < i₂ < ⋯ < i_k ≤ N.

Một dãy số b₁, b₂, ⋯, b_m được gọi là dãy hình nón nếu tồn tại vị trí j sao cho:

b₁ < b₂ < ⋯ < b_j > b_j+1 > ⋯ > b_m (với 1 < j < m).

Yêu cầu : Tìm dãy con hình nón có tổng lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên N (3 ≤ N ≤ 1000);

• Dòng thứ hai chứa N số nguyên a₁, a₂, ⋯, a_N (1 ≤ a_i ≤ 10⁹).

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Một số nguyên duy nhất là kết quả tìm được. Trường hợp không tồn tại dãy con hình nón thì ghi 0.

Scoring

Sample Input 1

8
2 1 1 9 2 1 2 5

Sample Output 1

16

Sample Input 2

6
7 5 3 1 2 3

Sample Output 2

0

Notes

Trong ví dụ thứ nhất, dãy con hình nón có tổng lớn nhất là 2, 9, 5.

Trong ví dụ thứ hai, không tồn tại dãy con hình nón.

---

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. Vùng liên thông

Cho đồ thị G vô hướng, liên thông gồm N đỉnh (đánh số hiệu từ 1 đến N) và M cạnh (đánh số hiệu từ 1 đến M). Giữa hai đỉnh khác nhau của G có không quá một cạnh nối hai đỉnh đó.

Cho K là số hiệu của một đỉnh trong đồ thị (1 ≤ K ≤ N). Gọi H là đồ thị con của đồ thị G. Xét đồ thị con H(K): H(K) gồm các đỉnh có số hiệu từ 1 đến K và các cạnh (x, y) nối hai đỉnh nằm trọn trong khoảng từ 1 đến K (1 ≤ x, y ≤ K).

Yêu cầu : Với mỗi cặp giá trị K và V (1 ≤ V ≤ K ≤ N), liệt kê các đỉnh thuộc vùng liên thông chứa đỉnh V của đồ thị con H(K).

Input

• Dòng thứ nhất chứa hai số nguyên dương N, M (1 ≤ N ≤ 10⁵; 1 ≤ M ≤ 2 · 10⁵) lần lượt là số đỉnh và số cạnh của đồ thị G;

• Dòng thứ hai chứa M giá trị x_i;

• Dòng thứ ba chứa M giá trị y_i.

Trong đó: (x_i, y_i) là cạnh thứ i (1 ≤ i ≤ M) của đồ thị liên thông G;

• Dòng thứ tư chứa số nguyên dương Q (1 ≤ Q ≤ 10³) là số bộ dữ liệu;

• Q dòng tiếp theo, mỗi dòng chứa hai số K, V (1 ≤ V ≤ K ≤ N) lần lượt là số đỉnh của đồ thị con và đỉnh mà vùng liên thông sẽ chứa.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Gồm Q dòng, mỗi dòng liệt kê các đỉnh của vùng liên thông chứa đỉnh V (các đỉnh có thứ tự từ nhỏ đến lớn).

Scoring

Sample Input 1

8 7
1 1 4 4 3 7 5
6 5 1 8 5 3 2
2
4 1
8 3

Sample Output 1

1 4
1 2 3 4 5 6 7 8

Notes

Đồ thị liên thông có 8 đỉnh, 7 cạnh: (1, 6), (1, 5), (4, 1), (4, 8), (3, 5), (7, 3), (5, 2). Q = 2 bộ dữ liệu.

Với trường hợp bộ dữ liệu 1: K = 4, V = 1, vùng liên thông của đồ thị con chứa đỉnh V có các đỉnh: 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: Chưa xác minh thời gian chạy trên toàn miền.