HSG THPT - Thành phố Huế 2026
Điểm: 19
Toán học là một môn học rất quan trọng và có nhiều ứng dụng trong cuộc sống. Tuy nhiên, một số bạn cho rằng môn học này khó khăn và khó tiếp thu. Biết được điều đó, sau tiết học về luỹ thừa, thầy giáo đã thiết kế một trò chơi để học sinh hiểu thêm về bài học. Trò chơi được mô tả như sau:
Cho một dãy ~A~ gồm ~N~ số nguyên dương đôi một khác nhau và một số nguyên dương ~k~. Mỗi bạn sẽ chọn một số ~x~ bất kỳ trong dãy ~A~, mỗi số chỉ được chọn một lần. Nếu trong dãy đã cho tồn tại các số có giá trị ~x^2, x^3, \ldots, x^k~ (không quan tâm đến vị trí xuất hiện của các số trong dãy) thì bạn đó sẽ nhận được một phần thưởng.
Đếm xem có tối đa bao nhiêu bạn nhận được phần thưởng.
Dữ liệu vào
Gồm hai dòng:
- Dòng 1: Chứa hai số nguyên ~N, k (1 \le N \le 10^5, 1 \le k \le 10^5)~.
- Dòng 2: Chứa ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ tương ứng ~N~ phần tử của dãy số ~A (1 \le a_i \le 10^5)~.
Kết quả
Một dòng duy nhất là kết quả của bài toán.
Ví dụ
Input 1
9 3
1 2 3 4 8 9 16 32 64
Output 1
3
Học sinh chọn một trong ba số 1, 2, 4 sẽ nhận được phần thưởng: với ~x = 1~ thì ~1^2 = 1^3 = 1~ đều có trong dãy; với ~x = 2~ thì 4 và 8 có trong dãy; với ~x = 4~ thì 16 và 64 có trong dãy. Số 3 không được vì 27 không có trong dãy.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).
Điểm: 36
Trong giờ giải lao, giáo viên đưa ra một trò chơi với bảng hình chữ nhật. Bảng này được chia thành ~N \times M~ ô, trên mỗi ô ghi một số nguyên dương hoặc đặt một chiếc đinh nhọn. Một bạn học sinh thả một viên bi từ phía trên bảng, khi rơi xuống viên bi lăn theo quy tắc: từ ô ~(i, j)~ lăn xuống một trong số các ô ~(i+1, j-1), (i+1, j), (i+1, j+1)~. Ban đầu, học sinh đó được tặng một số điểm. Mỗi lần viên bi đi qua một ô:
• Nếu ô đó có giá trị số, học sinh sẽ được cộng thêm điểm ghi trên ô.
• Nếu ô đó có đinh, số điểm hiện tại của học sinh sẽ giảm đi một nửa hoặc gần một nửa (phần nguyên của số điểm khi chia cho 2).
Khi viên bi chạm đáy bảng, tổng điểm sẽ được ghi nhận. Tính số điểm ít nhất và nhiều nhất mà học sinh có thể nhận được khi viên bi chạm đáy.
Dữ liệu vào
Gồm các dòng:
- Dòng 1: Chứa hai số nguyên ~N, M (1 \le N, M \le 1000)~.
- Dòng 2: Chứa số nguyên ~b~ là số điểm ban đầu của học sinh ~(0 \le b < 30000)~.
- ~N~ dòng tiếp theo mô tả bảng hình chữ nhật kích thước ~N \times M~, trong đó nếu ô có giá trị 0 có nghĩa là ô có đinh, ngược lại là các số trên ô (các số này nguyên dương và bé hơn hoặc bằng 30000).
Kết quả
Dòng 1: Ghi số điểm ít nhất có thể nhận được khi viên bi chạm đáy. Dòng 2: Ghi số điểm nhiều nhất có thể nhận được khi viên bi chạm đáy.
Ví dụ
Input 1
5 5
100
1 7 5 10 2
6 8 4 1 9
9 6 0 7 14
10 18 3 2 0
5 0 6 11 10
Output 1
28
148
Đường đi cho điểm nhỏ nhất là (1,5) → (2,4) → (3,3) → (4,3) → ~(5,2): 100 + 2 = 102, + 1 = 103~, gặp đinh còn ~52, + 3 = 55~, gặp đinh còn 28.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).
Điểm: 38
An là một cậu bé rất thông minh, luôn tự đặt ra cho mình những câu hỏi thú vị về vấn đề trong cuộc sống. Vào một ngày mưa lớn, khi nhìn qua khung cửa sổ, An thấy hàng rào nhà mình đang bị ngập một phần trong nước. Hàng rào nhà An được ghép liên tiếp bởi ~N~ thanh gỗ có độ cao khác nhau. Khi nước dâng lên từ từ, những thanh gỗ thấp hơn hoặc bằng mực nước sẽ bị ngập. Lúc này hàng rào bị chia cắt thành nhiều nhóm thanh gỗ riêng biệt. An muốn biết xem số nhóm nhiều nhất có thể xuất hiện tại cùng một thời điểm là bao nhiêu?
Trong suốt quá trình nước dâng, hãy xác định số nhóm thanh gỗ riêng biệt nhiều nhất có thể xuất hiện tại cùng một thời điểm.
Dữ liệu vào
Gồm các dòng:
- Dòng 1: Chứa một số nguyên dương ~N (1 \le N \le 10^5)~.
- ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~H_i~ tương ứng với độ cao của thanh gỗ thứ ~i (1 \le H_i \le 10^9)~.
Kết quả
Một dòng duy nhất là kết quả của bài toán.
Ví dụ
Input 1
6
2
1
1
5
1
2
Output 1
3
Giải thích:
Khi mực nước bằng 1, các thanh có độ cao 1 (vị trí 2, 3, 5) bị ngập, hàng rào còn ba nhóm rời nhau: {1}, {4}, {6}.
Ràng buộc
- Có 40% số điểm tương ứng với ~N \le 1000~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).
Điểm: 38
Để tạo bóng mát, thành phố ~X~ muốn trồng cây xanh dọc các tuyến đường. Trước khi tiến hành trồng đại trà, đội nghiên cứu đã xây dựng một mô hình thử nghiệm. Ban đầu có ~N~ cây, các cây được đánh số từ 1 đến ~N~, cây thứ ~i~ có chiều cao ~H_i~. Có tất cả ~Q~ phương án chăm sóc được đề xuất, phương án thứ ~i~ có dạng ~(L_i, R_i, D_i)~ có nghĩa là thực hiện chăm sóc các cây từ ~L_i~ đến ~R_i~ cao thêm ~D_i~. Sau đó, đội nghiên cứu đã lập một bản kế hoạch ~M~ ngày, kế hoạch cho ngày thứ ~j~ có dạng ~(U_j, V_j, C_j)~ có nghĩa là thực hiện các phương án từ ~U_j~ đến ~V_j~, mỗi phương án ~C_j~ lần.
Tính chiều cao cuối cùng của ~N~ cây sau khi thực hiện xong toàn bộ kế hoạch. Vì kết quả có thể rất lớn nên hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.
Dữ liệu vào
Gồm các dòng:
- Dòng 1: Chứa ba số nguyên dương ~N, Q, M (1 \le N, Q, M \le 2 \times 10^6)~.
- Dòng 2: Chứa ~N~ số nguyên không âm ~H_1, H_2, \ldots, H_N (0 \le H_i \le 10^9)~.
- ~Q~ dòng tiếp theo chứa các phương án chăm sóc có dạng ~L_i, R_i, D_i (1 \le i \le Q, 1 \le L_i \le R_i \le N, 0 \le D_i \le 10^9)~.
- ~M~ dòng tiếp theo thể hiện bản kế hoạch của đội, mỗi dòng có dạng ~U_j, V_j, C_j (0 \le C_j \le 10^9)~.
Kết quả
~N~ số nguyên trên một dòng, tương ứng chiều cao của hàng cây sau khi thực hiện xong toàn bộ kế hoạch. Kết quả in ra phần dư khi chia cho ~10^9 + 7~.
Ví dụ
Input 1
5 3 2
10 0 5 0 7
2 4 3
1 3 2
3 5 1
1 2 2
2 3 1
Output 1
16 12 18 7 8
Ngày thứ nhất thực hiện phương án 1 và 2, mỗi phương án hai lần: chiều cao lần lượt thành 10 6 11 6 7 rồi 14 10 15 6 7. Ngày thứ hai thực hiện phương án 2 và 3, mỗi phương án một lần: 16 12 17 6 7 rồi 16 12 18 7 8. Lưu ý: bảng dữ liệu ra hiển thị trên trang đề bị mất một chữ số ở giá trị thứ hai; chuỗi kết quả đúng theo chính phần giải thích của đề (và theo cả bản vét cạn lẫn bản tối ưu trong tài liệu này) là 16 12 18 7 8.
Ràng buộc
- Có 40% số điểm tương ứng với ~1 \le N, Q, M \le 500~.
Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).