Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

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 \times 2~; ~9 = 3 \times 3~; ~36 = 6 \times 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?

Dữ liệu vào (CP.INP)

Gồm hai số nguyên dương ~a, b~ ~(2 \le a \le b \le 10^{12})~.

Kết quả (CP.OUT)

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

Ràng buộc

• Có ~80\%~ số test ứng với ~80\%~ số điểm của bài thoả mãn ~2 \le a \le b \le 10^6~;
• ~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.

Ví dụ

Input

2 10

Output

2

Độ khó: Dễ (1/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

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 \times j~ ~(1 \le i \le n, 1 \le j \le 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~.

Dữ liệu vào (BS.INP)

Gồm hai số nguyên ~n~ và ~x~ ~(1 \le n \le 10^6, 1 \le x \le 10^{12})~ là kích thước của bảng và số nguyên ta cần tìm trong bảng.

Kết quả (BS.OUT)

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

Ràng buộc

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài thoả mãn ~0 < n \le 10^3, 1 \le x \le 10^6~;
• ~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.

Ví dụ

Input 1

6 5

Output 1

2

Input 2

6 12

Output 2

4

Input 3

5 13

Output 3

0

Giải thích:

Độ khó: Khá (3/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

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

Dữ liệu vào (CT.INP)

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(N \le 500)~;
• Dòng thứ hai bao gồm ~N~ số nguyên dương ~a_1, a_2, \ldots, 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^5~.

Kết quả (CT.OUT)

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.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn ~N \le 3~;
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 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.

Ví dụ

Input 1

5
1 2 4 5 2

Output 1

7

Giải thích: An có thể chọn những tờ tiền có mệnh giá ~1, 2, 4~. Bình chọn những tờ tiền còn lại có mệnh giá ~5, 2~. Mỗi người sẽ nhận được tổng số tiền là ~7~. Vì số tiền mỗi người nhận đã bằng nhau và đã chia hết số tiền nên họ sẽ không đầu tư.

Input 2

5
9 8 4 5 13

Output 2

17

Giải thích: An sẽ chọn những tờ tiền có mệnh giá ~9, 8~. Bình sẽ chọn những tờ tiền mệnh giá ~4, 13~. Mỗi người sẽ nhận được tổng số tiền là ~17~. Tờ tiền còn lại có mệnh giá ~5~ sẽ đem đi đầu tư.

Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

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.

Dữ liệu vào (TG.INP)

• 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 \le 500;\ N - 1 \le M < N^2/2;\ 1 < K \le 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 \le 10^9)~.

Kết quả (TG.OUT)

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.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn: ~K = N, N \le 500~;
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn: ~K \le 10, N \le 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.

Ví dụ

Input

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

Output

15

Giải thích: Cần làm các con đường:

1 2
2 4
3 4
4 5

Tổng độ dài nhỏ nhất là: ~15~

Độ khó: Khó (4/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Lưu ý: Tuy đề bài yêu cầu dữ liệu với file nhưng trên web thì cứ mặc định là đọc từ bàn phím và in ra màn hình nha các bạn.

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à ~\lfloor \sqrt{j - i + 1} \rfloor~ (lấy phần nguyên, ví dụ ~\lfloor 10{,}3333 \rfloor = 10~).

Dữ liệu vào (SX.INP)

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^6)~;
• Dòng thứ hai chứa ~N~ số nguyên dương là hoán vị từ ~1~ đến ~N~.

Kết quả (SX.OUT)

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

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 9~;
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 2000~;
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 10^5~;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài thoả mãn ~N \le 10^6~.

Ví dụ

Input

5
3 1 4 2 5

Output

2

Giải thích: Chọn dãy con ~[3, 1]~ mất chi phí ~1~ và chuyển thành dãy ~[1, 3, 4, 2, 5]~, sau đó chọn dãy con ~[3, 4, 2]~ với chi phí ~1~ để sắp xếp thành dãy ~[1, 2, 3, 4, 5]~ với tổng chi phí là ~2~.