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

🎓 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

Thầy Sơn vừa mua về ~S~ cây giống và muốn trồng toàn bộ số cây này trong khu vườn sau nhà. Để dễ chăm sóc, thầy xếp cây thành một lưới hình chữ nhật gồm ~a~ hàng, mỗi hàng ~b~ cây (~a, b~ là các số nguyên dương, ~a \le b~ và ~a \times b = S~). Hai cách xếp được coi là khác nhau nếu cặp ~(a, b)~ khác nhau.

Sau khi trồng, thầy cần rào quanh khu vườn. Với cách xếp ~a~ hàng, ~b~ cột, chiều dài hàng rào cần dùng là ~2 \times (a + b)~ mét.

Thầy Sơn có ~T~ phương án mua cây khác nhau. Với mỗi phương án (mỗi giá trị ~S~), hãy giúp thầy tính:

• Có bao nhiêu cách xếp ~S~ cây thành lưới hình chữ nhật như trên.
• Chiều dài hàng rào ngắn nhất có thể (trong tất cả các cách xếp).

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~T~ ~(1 \le T \le 10)~ — số phương án.
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~S~ ~(1 \le S \le 10^{12})~.

Kết quả

Gồm ~T~ dòng, dòng thứ ~i~ ghi hai số nguyên cách nhau một dấu cách: số cách xếp và chiều dài hàng rào ngắn nhất ứng với phương án thứ ~i~.

Giới hạn (Subtask)

• Subtask 1 (~40\%~ số điểm): ~S \le 10^6~.
• Subtask 2 (~60\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

3
12
7
36

Sample Output 1

3 14
1 16
5 24

Giải thích

• ~S = 12~: có ~3~ cách xếp là ~(1, 12), (2, 6), (3, 4)~; hàng rào ngắn nhất là ~2 \times (3 + 4) = 14~.
• ~S = 7~: chỉ có cách ~(1, 7)~, hàng rào dài ~16~.
• ~S = 36~: có ~5~ cách ~(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)~; hàng rào ngắn nhất là ~2 \times (6 + 6) = 24~.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).

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

🎓 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

Sáng nay, tiệm sửa đồng hồ của thầy Sơn nhận cùng lúc ~N~ chiếc đồng hồ của ~N~ khách hàng (tất cả được giao ở thời điểm ~0~). Chiếc đồng hồ thứ ~i~ cần đúng ~t_i~ phút để sửa xong.

Thầy Sơn làm một mình nên chỉ sửa được một chiếc tại một thời điểm; khi đã bắt đầu sửa chiếc nào thì phải sửa xong chiếc đó rồi mới chuyển sang chiếc khác, giữa hai chiếc không có thời gian nghỉ.

Theo cam kết của tiệm, khách hàng thứ ~i~ được đền bù ~w_i~ nghìn đồng cho mỗi phút chờ, tính từ thời điểm ~0~ đến lúc đồng hồ của họ sửa xong. Nghĩa là nếu đồng hồ thứ ~i~ sửa xong tại thời điểm ~C_i~ thì tiệm phải đền ~w_i \times C_i~ nghìn đồng cho khách đó.

Hãy giúp thầy Sơn chọn thứ tự sửa đồng hồ sao cho tổng tiền đền bù ~\sum_{i=1}^{N} w_i \times C_i~ là nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 2 \times 10^5)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~t_i~ và ~w_i~ ~(1 \le t_i, w_i \le 10^4)~.

Kết quả

Một số nguyên duy nhất là tổng tiền đền bù nhỏ nhất (đơn vị: nghìn đồng).

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 8~.
• Subtask 2 (~30\%~ số điểm): ~w_i = 1~ với mọi ~i~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 2 giây.

Sample Input 1

3
3 1
1 2
4 6

Sample Output 1

40

Giải thích

Sửa theo thứ tự đồng hồ ~2 \to 3 \to 1~:

• Đồng hồ ~2~ xong tại phút ~1~, đền ~2 \times 1 = 2~.
• Đồng hồ ~3~ xong tại phút ~1 + 4 = 5~, đền ~6 \times 5 = 30~.
• Đồng hồ ~1~ xong tại phút ~5 + 3 = 8~, đền ~1 \times 8 = 8~.

Tổng cộng ~2 + 30 + 8 = 40~, không có thứ tự nào cho tổng nhỏ hơn.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).

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

🎓 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

Trong đêm hội trăng rằm, trên con phố đi bộ người ta treo ~N~ chiếc đèn lồng thành một hàng, đánh số từ ~1~ đến ~N~ theo thứ tự từ trái sang phải. Chiếc đèn thứ ~i~ có độ sáng ~a_i~.

Thầy Sơn rất thích chụp ảnh. Thầy chọn hai chiếc đèn ~l < r~ làm hai mép của bức ảnh. Bức ảnh được gọi là hài hòa nếu mọi chiếc đèn nằm giữa hai mép (tức các đèn ~l+1, l+2, \dots, r-1~) đều không sáng hơn bất kỳ đèn mép nào, nói cách khác:

~\max(a_{l+1}, a_{l+2}, \dots, a_{r-1}) \le \min(a_l, a_r)~.

Nếu ~r = l + 1~ (không có đèn nào ở giữa) thì bức ảnh luôn hài hòa.

Hãy đếm số cặp ~(l, r)~ với ~1 \le l < r \le N~ tạo thành bức ảnh hài hòa.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^9)~.

Kết quả

Một số nguyên duy nhất là số cặp ~(l, r)~ thỏa mãn.

Giới hạn (Subtask)

• Subtask 1 (~30\%~ số điểm): ~N \le 3000~.
• Subtask 2 (~30\%~ số điểm): các giá trị ~a_i~ đôi một khác nhau.
• Subtask 3 (~40\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 2 giây.

Sample Input 1

5
4 2 3 2 5

Sample Output 1

7

Giải thích

Các cặp hài hòa là: ~(1,2), (2,3), (3,4), (4,5)~ (kề nhau), ~(1,3)~ (giữa là ~2 \le \min(4,3)~), ~(3,5)~ (giữa là ~2 \le \min(3,5)~) và ~(1,5)~ (giữa lớn nhất là ~3 \le \min(4,5)~). Cặp ~(2,4)~ không hài hòa vì đèn giữa có độ sáng ~3 > 2~.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).

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

🎓 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

Một trận lũ bất ngờ ập đến vùng đồng bằng. Bản đồ khu vực là một lưới gồm ~N~ hàng và ~M~ cột, mỗi ô là một trong các kí tự:

• . — ô đất trống;
• # — ô đá cao, cả người lẫn nước đều không đi vào được;
• * — ô đang có nước (nguồn lũ), có thể có nhiều ô như vậy;
• S — vị trí hiện tại của thầy Sơn (là ô đất trống);
• E — trạm cứu hộ (là ô đất trống). Thầy Sơn cần đến được ô này.

Thời gian tính theo phút, bắt đầu từ phút ~0~. Trong mỗi phút, lần lượt xảy ra hai việc:

1. Thầy Sơn phải di chuyển sang một trong bốn ô kề cạnh (trên, dưới, trái, phải). Thầy Sơn không được đi ra ngoài bản đồ, không được vào ô đá và không được vào ô đang có nước. Nếu ô thầy Sơn vừa bước vào là E thì thầy Sơn được cứu ngay lập tức.
2. Sau đó, nước tràn từ mỗi ô có nước sang tất cả các ô kề cạnh không phải ô đá. Nếu ô thầy Sơn đang đứng bị nước tràn tới thì thầy Sơn gặp nguy hiểm — thầy Sơn không được phép để chuyện này xảy ra.

Lưu ý:

• Bản đồ có thể không có ô * nào.
• Nước tràn vào cả ô S và ô E như các ô đất trống khác — trạm cứu hộ không chặn được nước.
• Nếu trong cùng một phút thầy Sơn bước vào ô E (việc 1) và nước cũng tràn tới ô E (việc 2), thầy Sơn vẫn được tính là thoát hiểm thành công, vì thầy đã được cứu trước khi nước tới.
• Thầy Sơn được phép đi lại vào ô mình đã đi qua, nhưng không được đứng yên tại chỗ.
• Số phút cần tìm chính là số bước di chuyển của thầy Sơn.

Hãy tính số phút ít nhất để thầy Sơn đến được trạm cứu hộ một cách an toàn, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N, M~ ~(1 \le N, M \le 1000;\ N \times M \ge 2)~.
• ~N~ dòng tiếp theo, mỗi dòng là một xâu gồm đúng ~M~ kí tự mô tả một hàng của bản đồ. Bản đồ có đúng một kí tự S và đúng một kí tự E.

Kết quả

Một số nguyên duy nhất là số phút ít nhất để thầy Sơn đến được ô E. Nếu không thể, in ra -1.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): bản đồ không có ô nước *.
• Subtask 2 (~30\%~ số điểm): ~N, M \le 50~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 3 giây.

Sample Input 1

4 5
S....
.###.
...#.
.#..E

Sample Output 1

7

Sample Input 2

4 5
S...#
..*.#
.#...
...#E

Sample Output 2

-1

Sample Input 3

3 5
S...E
####.
..*..

Sample Output 3

4

Giải thích

• Ví dụ 1: không có nước, thầy Sơn đi theo đường ngắn nhất gồm ~7~ bước, chẳng hạn đi hết hàng ~1~ sang phải rồi đi xuống theo cột ~5~.
• Ví dụ 2: nước lan rất nhanh từ ô ở hàng ~2~, cột ~3~ và chặn mọi con đường đến E trước khi thầy Sơn tới nơi.
• Ví dụ 3: Thầy Sơn đi thẳng sang phải ~4~ phút. Nước tới ô E cũng ở phút thứ ~4~, nhưng trong phút đó thầy Sơn di chuyển trước và được cứu ngay khi bước vào E, nên vẫn an toàn.

Nguồn: Đề tự luyện HSG Tin học lớp 9 (đề tự soạn).