HSG12 Hà Nội 2022

HSG12 Hà Nội 2022

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. Số chính phương đặc biệt

Số chính phương đặc biệt là số chính phương được tạo bởi một số nguyên tố. Ví dụ 4 = 2 × 2; 9 = 3 × 3; 36 = 6 × 6 nên 4 và 9 là số chính phương đặc biệt còn 36 thì không phải là số chính phương đặc biệt.

Yêu cầu: Cho 2 số nguyên dương a, b. Hãy đếm xem trong đoạn [a ⋯ b] có bao nhiêu số chính phương đặc biệt?

Input

• Gồm hai số nguyên dương a, b (2 ≤ a ≤ b ≤ 10¹²).

Output

• Gồm một dòng chứa một số duy nhất là kết quả của bài toán.

Sample Input 1

2 10

Sample Output 1

2

Subtasks

• Có 80% số test ứng với 80% số điểm của bài thoả mãn 2 ≤ a ≤ b ≤ 10⁶;

• 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.

---

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. Bảng số

Cho một bảng vuông gồm n hàng và n cột. Các hàng được đánh số từ 1 đến n, các cột được đánh số từ 1 đến n. Ô ở hàng thứ i và cột thứ j có giá trị là i × j (1 ≤ i ≤ n, 1 ≤ j ≤ n).

Yêu cầu: Cho một số nguyên dương x. Hãy đếm số lượng ô trong bảng có giá trị bằng x.

Input

• Gồm hai số nguyên n và x (1 ≤ n ≤ 10⁵, 1 ≤ x ≤ 10⁹).

Output

• Số nguyên duy nhất là số lượng ô trong bảng có giá trị bằng x.

Sample Input 1

6 5

Sample Output 1

2

Sample Input 2

6 12

Sample Output 2

4

Sample Input 3

5 13

Sample Output 3

0

Subtasks

• Có 70% số test ứng với 70% số điểm của bài thoả mãn 0 < n ≤ 10³, 1 ≤ x ≤ 10⁶;

• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì 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. Chia tiền thưởng

Nhờ hoàn thành tốt công việc, An và Bình được công ty thưởng N tờ tiền. Tờ tiền thứ i có mệnh giá a_i. Hai bạn muốn chia đôi số tiền thành hai phần bằng nhau bằng cách chia cho mỗi người một số tờ tiền. Vì thế hai bạn quyết định sẽ chọn ra những tờ tiền để tổng số tiền hai bạn nhận được bằng nhau và lớn nhất, phần còn lại (nếu có) sẽ đem đi đầu tư.

Yêu cầu: Hãy giúp hai bạn tính tổng số tiền lớn nhất mà mỗi người nhận được trước khi đầu tư.

Input

• Dòng đầu tiên chứa số nguyên dương N (N ≤ 500);

• Dòng thứ hai bao gồm N số nguyên dương a₁, a₂, ⋯, a_N là mệnh giá của những tờ tiền. Tổng giá trị những tờ tiền sẽ không vượt quá 10⁵.

Output

• Gồm một dòng duy nhất là số tiền lớn nhất mà mỗi người nhận được.

Sample Input 1

5
1 2 4 5 2

Sample Output 1

7

Sample Input 2

5
9 8 4 5 13

Sample Output 2

17

Subtasks

• Có 40% số test ứng với 40% số điểm của bài thoả mãn N ≤ 3;

• 30% số test tiếp theo ứng với 30% số điểm của bài thoả mãn N ≤ 12;

• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì 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 4. Trạm gác trung tâm

Ban quản lí rừng nguyên sinh đang quản lý một khu vực rộng lớn. Họ đã xây dựng N trạm canh gác rừng (được đánh số từ 1 đến N) và các trạm này được nối với nhau bởi M con đường. Trong N trạm canh gác người ta đã chọn ra K trạm làm trạm gác trung tâm - nơi điều hành các trạm gác nhỏ hơn và chứa các dụng cụ, phương tiện bảo vệ rừng. Để đi lại và vận chuyển thiết bị dễ dàng giữa các trạm gác trung tâm, Ban quản lí quyết định nâng cấp một số con đường sao cho K trạm gác trung tâm đều đi được đến nhau.

Yêu cầu: Hãy chọn các con đường nối K trạm gác trung tâm để nâng cấp sao cho tổng độ dài các con đường này là nhỏ nhất.

Input

• Dòng đầu tiên ghi ba số nguyên dương N, M, K lần lượt là số lượng các trạm gác, số các con đường nối giữa các trạm gác và số lượng các trạm gác trung tâm (1 < N ≤ 500; N - 1 ≤ M < N²/2; 1 < K ≤ N);

• Dòng thứ hai ghi K số nguyên là số hiệu của K trạm gác trung tâm;

• Trong M dòng tiếp theo, mỗi dòng ghi ba số nguyên u, v, c với ý nghĩa con đường hai chiều nối trực tiếp giữa hai trạm u và v có độ dài là c (1 < c ≤ 10⁹).

Output

• Một dòng duy nhất chứa tổng độ dài các con đường thỏa mãn yêu cầu trên.

Sample Input 1

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

Sample Output 1

15

Subtasks

• Có 40% số test ứng với 40% số điểm của bài thoả mãn: K = N, N ≤ 500;

• 30% số test tiếp theo ứng với 30% số điểm của bài thoả mãn: K ≤ 10, N ≤ 200;

• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì 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: Lời giải chưa bao phủ toàn bộ đề.

Câu 5. Sắp xếp hoán vị

Cho số nguyên dương N và dãy hoán vị từ 1 đến N. Hãy tính tổng chi phí nhỏ nhất để sắp xếp dãy hoán vị ban đầu thành dãy tăng dần. Biết rằng có thể chọn một dãy con liên tiếp từ i đến j và sắp xếp lại dãy con này thành dãy tăng dần với chi phí là [√(j - i + 1)] (lấy phần nguyên, ví dụ [√(10,3333)] = 10).

Yêu cầu: Tính chi phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần.

Input

• Dòng đầu tiên chứa số nguyên dương N (1 ≤ N ≤ 10⁶);

• Dòng thứ hai chứa N số nguyên dương là hoán vị từ 1 đến N.

Output

• Chi phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần.

Sample Input 1

5
3 1 4 2 5

Sample Output 1

2

Subtasks

• Có 30% số test ứng với 30% số điểm của bài thoả mãn N ≤ 9;

• 30% số test tiếp theo ứng với 30% số điểm của bài thoả mãn N ≤ 2000;

• 30% số test tiếp theo ứng với 30% số điểm của bài thoả mãn N ≤ 10⁵;

• 10% số test còn lại ứng với 10% số điểm của bài thoả mãn N ≤ 10⁶.

---

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.