TỔNG QUAN ĐỀ THI
| Bài | Tên bài | Tệp chương trình | Tệp dữ liệu | Tệp kết quả | Bộ nhớ (MB) | Thời gian (giây) | Điểm |
|---|---|---|---|---|---|---|---|
| 1 | Căn bậc hai | rgc.* | rgc.inp | rgc.out | 1024 | 1 | 6 |
| 2 | Bóng đá | bal.* | bal.inp | bal.out | 1024 | 1 | 6 |
| 3 | Số lớn nhất | max.* | max.inp | max.out | 1024 | 1 | 5 |
| 4 | Dãy hài hòa | seq.* | seq.inp | seq.out | 1024 | 1 | 3 |
Ghi chú: Dấu * được thay thế bởi cpp hoặc py tương ứng với ngôn ngữ lập trình C++ hoặc Python.
Bài 1. Căn bậc hai (6 điểm)
Hôm nay, lớp của An làm bài tập môn Toán về nội dung đưa thừa số ra ngoài dấu căn. Cô giáo giao bài tập về nhà là cho trước số nguyên dương \(n\), hãy tìm hai số nguyên dương \(x, y\) sao cho \(\sqrt{n} = x \times \sqrt{y}\) với \(x\) lớn nhất.
Ví dụ:
- Với \(n = 18\): do \(\sqrt{18} = 3 \times \sqrt{2}\) nên \(x = 3, y = 2\);
- Với \(n = 7\): do \(\sqrt{7} = 1 \times \sqrt{7}\) nên \(x = 1, y = 7\);
- Với \(n = 4\): do \(\sqrt{4} = 2 \times \sqrt{1}\) nên \(x = 2, y = 1\).
Dữ liệu: Vào từ tệp văn bản rgc.inp gồm một dòng chứa số nguyên \(n\) (\(1 \le n \le 10^{14}\)).
Kết quả: Ghi ra tệp văn bản rgc.out gồm một dòng chứa hai số nguyên \(x\) và \(y\).
Ví dụ:
| rgc.inp | rgc.out |
|---|---|
| 18 7 4 | 3 2 1 7 2 1 |
Ràng buộc:
- Có 30% số test ứng với 30% số điểm thỏa mãn: \(1 \le n \le 10^5\);
- 30% số test khác ứng với 30% số điểm thỏa mãn: \(1 \le n \le 10^9\);
- 40% số test còn lại ứng với 40% số điểm: Không có thêm ràng buộc nào.
Bài 2. Bóng đá (6 điểm)
Trong một giải đấu bóng đá có \(n\) đội bóng tham gia. Mỗi đội bóng phải đá với mỗi đội bóng khác đúng 2 trận lượt đi và về, trong đó có 1 trận trên sân nhà và 1 trận trên sân khách.
Mỗi đội bóng \(i\) có 2 trang phục thi đấu, 1 trang phục dành cho sân nhà có màu được biểu diễn bởi số nguyên \(x_i\), còn trang phục dành cho sân khách có màu được biểu diễn bởi số nguyên \(y_i\) (\(x_i \neq y_i\)). Các trang phục cùng màu thì được biểu diễn bởi cùng một số và các trang phục khác màu thì được biểu diễn bởi các số khác nhau.
Trong mỗi trận đấu, một đội mặc trang phục sân nhà, một đội mặc trang phục sân khách. Tuy nhiên, nếu hai đội cùng màu trang phục thì đội khách được phép thay trang phục sân nhà của mình.
Hãy tính xem trong giải đấu, mỗi đội mặc bao nhiêu lần trang phục sân nhà và bao nhiêu lần trang phục sân khách.
Dữ liệu: Vào từ tệp văn bản bal.inp. Dòng đầu tiên chứa số nguyên \(n\) (\(2 \le n \le 10^5\)). Dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa hai số nguyên \(x_i, y_i\) (\(1 \le x_i, y_i \le 10^9; x_i \neq y_i\)).
Kết quả: Ghi ra tệp văn bản bal.out gồm \(n\) dòng, trong đó dòng thứ \(i\) chứa hai số nguyên tương ứng là số lần mặc trang phục sân nhà và sân khách của đội bóng \(i\).
Ví dụ:
| bal.inp | bal.out |
|---|---|
| 3 4 7 7 4 4 2 | 3 1 4 0 2 2 |
Ràng buộc:
- Có 40% số test ứng với 40% số điểm thỏa mãn: \(2 \le n \le 1000\);
- 30% số test khác ứng với 30% số điểm thỏa mãn: \(1 \le x_i, y_i \le 10^5\);
- 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Bài 3. Số lớn nhất (5 điểm)
Cho hai số nguyên dương \(a\) và \(b\). Hãy tìm số \(c\) lớn nhất chứa tất cả các chữ số của \(a\) và \(b\), trong đó thứ tự xuất hiện các chữ số của \(a\) và \(b\) được giữ nguyên.
Dữ liệu: Vào từ tệp văn bản max.inp. Dòng đầu tiên chứa số nguyên dương \(a\) và dòng thứ hai chứa số nguyên dương \(b\) (\(a, b\) có không quá 1000 chữ số).
Kết quả: Ghi ra tệp văn bản max.out gồm một dòng chứa số \(c\) tìm được.
Ví dụ:
| max.inp | max.out |
|---|---|
| 20 4181 | 421810 |
Ràng buộc:
- Có 40% số test ứng với 40% số điểm thỏa mãn: \(a\) có 1 chữ số;
- 30% số test khác ứng với 30% số điểm thỏa mãn: Không có chữ số nào của \(a\) xuất hiện trong \(b\);
- 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.
Bài 4. Dãy hài hòa (3 điểm)
Quà sinh nhật của An là một bộ khối lập phương xếp hình. An xếp thành một dãy gồm \(n\) tháp, tháp thứ \(i\) có độ cao là \(a_i\).
An rất có cảm tình với số nguyên \(k\), vì vậy dãy liên tục các tháp được coi là hài hòa nếu chúng có độ cao trung bình là \(k\).
Cho \(n, k\) và \(a_i\) với \(i = 1, 2, ..., n\). Hãy xác định dãy tháp hài hòa dài nhất: độ dài của dãy tìm được và số thứ tự của tháp đầu tiên. Nếu tồn tại nhiều dãy cùng độ dài thì chỉ ra dãy tháp có vị trí đầu nhỏ nhất. Nếu không tồn tại dãy tháp thì đưa ra một số 0.