🎓 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

Hội chợ xuân ở trường THCS ven sông Tiền năm nay có gian hàng trò chơi của thầy Sơn mang tên "Ghép thẻ may mắn". Trên bàn có ~N~ tấm thẻ, tấm thẻ thứ ~i~ ghi một số nguyên dương ~a_i~ (viết bình thường, không có chữ số ~0~ vô nghĩa ở đầu).

Mỗi lượt chơi, người chơi chọn hai tấm thẻ khác nhau ~i~ và ~j~ ~(i \ne j)~, đặt thẻ ~i~ ở bên trái, thẻ ~j~ ở bên phải rồi đọc liền các chữ số thành một số mới. Ví dụ thẻ trái ghi ~12~, thẻ phải ghi ~345~ thì số ghép được là ~12345~; nếu đổi chỗ hai thẻ thì được ~34512~.

Số ghép được gọi là số may mắn nếu nó chia hết cho ~11~. Hai cách chọn ~(i, j)~ và ~(j, i)~ được coi là khác nhau; hai tấm thẻ khác nhau vẫn được coi là khác nhau dù ghi cùng một số.

Để chuẩn bị đủ quà, thầy Sơn cần biết: có tất cả bao nhiêu cách chọn cặp ~(i, j)~ với ~i \ne j~ cho ra số may mắn?

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 2 \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^{18})~.

Kết quả

Một số nguyên duy nhất là số cách chọn cặp ~(i, j)~ ~(i \ne j)~ mà số ghép được chia hết cho ~11~.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 1000~ và ~a_i \le 10^8~.
• Subtask 2 (~30\%~ số điểm): ~N \le 5000~.
• 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

6
39 67 1946 39 9159 82

Sample Output 1

6

Giải thích

Có ~6~ cách chọn cho ra số may mắn:

• thẻ ~1~ (~39~) bên trái, thẻ ~6~ (~82~) bên phải: ~3982 = 11 \times 362~;
• thẻ ~4~ (~39~) bên trái, thẻ ~6~ (~82~) bên phải: ~3982~;
• thẻ ~6~ bên trái, thẻ ~1~ bên phải: ~8239 = 11 \times 749~;
• thẻ ~6~ bên trái, thẻ ~4~ bên phải: ~8239~;
• thẻ ~2~ (~67~) bên trái, thẻ ~3~ (~1946~) bên phải: ~671946 = 11 \times 61086~;
• thẻ ~3~ bên trái, thẻ ~2~ bên phải: ~194667 = 11 \times 17697~.

Mọi cách chọn khác đều cho số không chia hết cho ~11~, chẳng hạn ~3967~ hay ~915939~.

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

🎓 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

Dọc một bờ sông Hậu có ~N~ xóm nhỏ. Coi bờ sông là một trục số, xóm thứ ~i~ nằm ở vị trí ~x_i~ (mét, tính từ cột mốc đầu xã) và có ~w_i~ người ngày nào cũng phải qua sông đi làm, đi học. Có thể có nhiều xóm nằm cùng một vị trí.

Thầy Sơn vận động bà con góp tiền xây đúng hai bến đò ở hai vị trí nguyên ~P~ và ~Q~ trên bờ (hai bến có thể đặt cùng một chỗ). Mỗi người sẽ đi bộ dọc bờ tới bến gần nhà mình hơn, nên quãng đường đi bộ của một người ở xóm ~i~ là ~\min(|x_i - P|, |x_i - Q|)~.

Hãy giúp thầy Sơn chọn vị trí hai bến sao cho tổng quãng đường đi bộ của tất cả mọi người

~\displaystyle S = \sum_{i=1}^{N} w_i \cdot \min(|x_i - P|,\ |x_i - Q|)~

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 ~x_i~ và ~w_i~ ~(0 \le x_i \le 10^9;~ ~1 \le w_i \le 10^4)~. Các xóm không nhất thiết được liệt kê theo thứ tự vị trí.

Kết quả

Một số nguyên duy nhất là tổng quãng đường đi bộ nhỏ nhất.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 100~.
• Subtask 2 (~30\%~ số điểm): ~N \le 5000~.
• 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

7
3 1
8 9
12 3
13 7
27 4
30 7
34 4

Sample Output 1

80

Giải thích

Thầy Sơn xây một bến ở vị trí ~8~ và một bến ở vị trí ~30~. Người ở các xóm tại vị trí ~3, 8, 12, 13~ đi tới bến ~8~; người ở các xóm tại vị trí ~27, 30, 34~ đi tới bến ~30~. Tổng quãng đường là

~1 \cdot 5~ ~+ 9 \cdot 0~ ~+ 3 \cdot 4~ ~+ 7 \cdot 5~ ~+ 4 \cdot 3~ ~+ 7 \cdot 0~ ~+ 4 \cdot 4~ ~= 80~.

Không có cách đặt hai bến nào cho tổng nhỏ hơn ~80~ (đặt bến thứ nhất ở bất kỳ vị trí nào từ ~8~ đến ~12~ cũng được ~80~).

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

🎓 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ùa lúa chín, thầy Sơn mượn xe tải nhỏ để giúp bà con chở lúa từ xã ~1~ về nhà máy xay ở xã ~N~. Vùng quê của thầy có ~N~ xã, đánh số từ ~1~ đến ~N~, và ~M~ con đường hai chiều; con đường thứ ~i~ nối xã ~u_i~ với xã ~v_i~ và đi qua một cây cầu có tải trọng ~c_i~ tấn. Giữa hai xã có thể có nhiều con đường khác nhau.

Xe chở ~W~ tấn lúa chỉ được đi qua cây cầu có tải trọng ít nhất ~W~ tấn (khối lượng của xe coi như không đáng kể). Thầy Sơn muốn:

1. Chở được nhiều lúa nhất trong một chuyến, tức là chọn số nguyên ~W~ lớn nhất sao cho có cách đi từ xã ~1~ tới xã ~N~ mà mọi cây cầu trên đường đều có tải trọng ít nhất ~W~;
2. Với khối lượng ~W~ đó, chọn cách đi qua ít cây cầu nhất.

Dữ liệu đảm bảo luôn có ít nhất một cách đi từ xã ~1~ tới xã ~N~. Hãy giúp thầy Sơn.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ ~(2 \le N \le 10^5;~ ~1 \le M \le 2 \times 10^5)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i, v_i, c_i~ ~(1 \le u_i, v_i \le N;~ ~u_i \ne v_i;~ ~1 \le c_i \le 10^9)~.

Kết quả

Hai số nguyên ~W~ và ~S~ trên một dòng, cách nhau một dấu cách: ~W~ là khối lượng lúa lớn nhất (tấn) chở được trong một chuyến, ~S~ là số cây cầu ít nhất phải đi qua khi chở ~W~ tấn.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): mọi cây cầu có cùng tải trọng.
• Subtask 2 (~30\%~ số điểm): ~N \le 2000~ và ~M \le 4000~.
• 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à 4 giây.

Sample Input 1

6 9
3 5 16
6 5 11
3 2 17
3 1 10
4 3 6
5 4 10
1 4 13
2 1 8
5 2 1

Sample Output 1

10 3

Giải thích

Thầy Sơn chở được ~10~ tấn, chẳng hạn đi theo đường ~1 \to 3 \to 5 \to 6~ qua ~3~ cây cầu có tải trọng ~10, 16, 11~ tấn. Không có cách đi nào chở được ~11~ tấn, và khi chở ~10~ tấn thì không có cách đi nào qua ít hơn ~3~ cây cầu.

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

🎓 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

Cuối tuần, thầy Sơn chèo xuồng ra chợ nổi Cái Răng mua quà cho học trò. Một ghe hàng bày bán ~N~ món quà, món thứ ~i~ có giá ~c_i~ nghìn đồng và mang lại cho học trò độ vui ~v_i~. Mỗi món chỉ có một cái, nên mua tối đa một lần.

Chủ ghe đang có chương trình khuyến mãi: nếu một lần mua từ ~3~ món trở lên thì món có giá rẻ nhất trong số các món đã mua được tặng (không phải trả tiền). Dù mua bao nhiêu món (từ ~3~ món trở lên) thì cũng chỉ có đúng một món được tặng. Nếu có nhiều món cùng rẻ nhất thì chỉ một trong số đó được tặng. Mua ~1~ hoặc ~2~ món thì phải trả đủ tiền.

Thầy Sơn mang theo ~B~ nghìn đồng và mua tất cả trong một lần. Hãy giúp thầy chọn các món quà sao cho số tiền phải trả không vượt quá ~B~ và tổng độ vui là lớn nhất. Thầy có thể không mua món nào (khi đó tổng độ vui bằng ~0~).

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~B~ ~(1 \le N \le 2000;~ ~0 \le B \le 10^4)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~c_i~ và ~v_i~ ~(1 \le c_i \le 2 \times 10^4;~ ~1 \le v_i \le 10^9)~.

Kết quả

Một số nguyên duy nhất là tổng độ vui lớn nhất.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): ~N \le 15~.
• Subtask 2 (~30\%~ số điểm): ~N \le 100~.
• 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à 4 giây.

Sample Input 1

6 29
16 19
7 6
18 9
12 19
9 5
11 19

Sample Output 1

57

Giải thích

Thầy Sơn mua ba món ~1~, ~4~ và ~6~ (giá ~16~, ~12~, ~11~ nghìn đồng). Vì mua ~3~ món nên món ~6~ (rẻ nhất, ~11~ nghìn đồng) được tặng; thầy chỉ trả ~16 + 12 = 28 \le 29~ nghìn đồng và tổng độ vui là ~19 + 19 + 19 = 57~. Không có cách mua nào được tổng độ vui lớn hơn.

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