HSG THPT - TP. Cần Thơ 2026
Điểm: 6
Một khu vườn ~A~ hình chữ nhật có kích thước chiều dài là ~m~, chiều rộng là ~n~. Hãy lập trình tìm diện tích hình vuông lớn nhất trong khu vườn ~A~.
Chẳng hạn, với ~m = 7~ và ~n = 3~, hình vuông lớn nhất có cạnh bằng 3, diện tích là 9.
Yêu cầu: Tìm diện tích hình vuông lớn nhất trong khu vườn ~A~.
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên dương ~m, n (m, n \le 10^9)~, mỗi số cách nhau một dấu cách.
Kết quả
Một số nguyên là diện tích hình vuông lớn nhất tìm được.
Ví dụ
Input 1
7 3
Output 1
9
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: 30
Cho một dãy gồm ~n~ bóng đèn, mỗi bóng đèn được điều khiển trạng thái bởi một công tắc riêng biệt là bật hoặc tắt. Nếu đèn đang ở trạng thái bật thì được ký hiệu là 1, ngược lại nếu tắt được ký hiệu là 0. Người điều khiển được phép thực hiện thao tác sau đúng một lần: chọn một đoạn các bóng đèn liên tiếp đang ở trạng thái tắt và chuyển tất cả chúng sang trạng thái bật.
Yêu cầu: Hãy đưa ra số lượng lớn nhất các bóng đèn liên tiếp nhau ở trạng thái bật, sau khi người điều khiển thực hiện thao tác trên một cách tối ưu.
Dữ liệu vào
Gồm hai dòng:
- Dòng đầu tiên ghi số ~n (n \le 2 \times 10^5)~.
- Dòng tiếp theo lần lượt ghi các trạng thái của bóng đèn là 0 hoặc 1, mỗi số cách nhau một dấu cách.
Kết quả
Một số nguyên là kết quả tìm được, nếu không thể thao tác thì in ra −1.
Ví dụ
Input 1
5
1 0 0 1 0
Output 1
4
Input 2
3
1 1 1
Output 2
-1
Ở ví dụ 1, bật hai đèn ở vị trí 2 và 3 tạo thành đoạn bật 1 1 1 1 gồm 4 đèn. Ở ví dụ 2, không có đèn nào đang tắt nên không thực hiện được thao tác.
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: 35
Cho một dãy số ~A~ gồm ~n~ phần tử số nguyên có dạng ~a_1, a_2, \ldots, a_n~. Gọi ~W~ là tổng giá trị của ~n - 1~ phần tử được chọn ra trong ~A~. Mỗi lần chọn một phần tử trong hai phần tử đầu tiên và thực hiện theo quy tắc sau:
• Nếu chọn ~a_1~ thì ~W = W + a_1~, sau đó lấy ~a_1~ ra khỏi dãy thì phần tử ~a_2~ lúc này là ~a_1~, phần tử ~a_3~ là ~a_2, \ldots~
• Ngược lại, nếu chọn ~a_2~ thì ~W = W - a_2~, sau đó lấy ~a_2~ ra khỏi dãy thì phần tử ~a_3~ lúc này là ~a_2, \ldots~
Yêu cầu: Hãy lặp lại quy tắc trên một cách tối ưu, xác định giá trị ~W~ lớn nhất khi chọn ra đúng ~n - 1~ phần tử.
Dữ liệu vào
Gồm hai dòng:
- Dòng đầu tiên ghi số ~n (2 \le n \le 10^5)~.
- Dòng tiếp theo ghi các số ~a_i (|a_i| \le 10^4)~, mỗi số cách nhau bởi một dấu cách.
Kết quả
Một số nguyên là kết quả tìm được.
Ví dụ
Input 1
4
1 2 -3 2
Output 1
6
Thứ tự chọn tối ưu như sau: ~W = 1 - (-3) + 2 = 6~.
Ràng buộc
- 30% số test tương ứng với số điểm có ~a_i > 0~.
- 20% số test tương ứng với số điểm có ~n \le 15~.
- 50% số test còn lại không ràng buộc gì thêm.
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: 41
Một nhóm khách mời gồm ~m~ nam, ~n~ nữ cùng đi dự tiệc. Nhóm khách mời này được xếp ngồi vào một bàn tròn sao cho giữa hai khách nam có ít nhất một khách nữ ngồi ở giữa.
Ví dụ: ~m = 2~ gồm ~m_1, m_2; n = 2~ gồm ~n_1, n_2~, ta có hai cách xếp.
Hai cách xếp ~A~ và ~B~ được xem là như nhau nếu xoay vòng cách xếp ~A~ trùng với cách xếp ~B~ và ngược lại.
Yêu cầu: Hãy tìm số cách xếp sao cho giữa hai nam có ít nhất một nữ ngồi giữa.
Dữ liệu vào
Một dòng duy nhất ghi hai số nguyên dương ~m, n (m, n \le 10^6)~, mỗi số cách nhau một dấu cách.
Kết quả
Một số là phần dư của kết quả tìm được khi chia cho ~10^9 + 7~.
Ví dụ
Input 1
2 2
Output 1
2
Input 2
3 3
Output 2
12
Input 3
3 2
Output 3
0
Ràng buộc
- 30% số test tương ứng với số điểm có ~m = n~ và ~m, n \le 20~.
- 70% số test còn lại không ràng buộc gì thêm.
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: 35
Một tập đoàn công nghệ đang xây dựng một mô hình máy tính phục vụ cho việc phát triển các mô hình trí tuệ nhân tạo. Mô hình này gồm nhiều máy tính kết nối với nhau thông qua tuyến đường là dây cáp. Một máy tính thứ ~u~ luôn được kết nối với máy tính thứ ~v~ thông qua một lộ trình duy nhất bằng hình thức trực tiếp hoặc gián tiếp (thông qua các máy tính trung gian). Độ dài đi từ ~u~ đến ~v~ được định nghĩa là số lượng tuyến đường đi từ ~u~ đến ~v~.
Yêu cầu: Hãy xác định độ dài lớn nhất kết nối hai máy tính trong mô hình.
Dữ liệu vào
Gồm các dòng:
- Dòng đầu tiên ghi số ~n (2 \le n \le 10^5)~ là số lượng các máy tính có trong mô hình.
- ~n - 1~ dòng tiếp theo ghi các giá trị ~u, v (1 \le u, v \le n)~ là thứ tự hai máy tính được kết nối, mỗi số cách nhau một dấu cách.
Kết quả
Một số nguyên là kết quả cần tìm.
Ví dụ
Input 1
3
1 2
2 3
Output 1
2
Input 2
6
1 2
3 2
2 4
4 5
4 6
Output 2
3
Ở ví dụ 2, lộ trình dài nhất là 1 → 2 → 4 → 5 gồm 3 tuyến cáp.
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).