| Tên bài | Tên file | Tên file input | Tên file output | Điểm |
| Kỳ thi | CONTEST.* | CONTEST.OUT | CONTEST.OUT | 100 |
| Chia gạo | RICE.* | RICE.INP | RICE.OUT | 100 |
| Biến đổi xâu | STRING.* | STRING.INP | STRING.OUT | 100 |
| Xóa số | REMOVE.* | REMOVE.INP | REMOVE.OUT | 100 |
| Chia tay | CHIATAY.* | CHIATAY.INP | CHIATAY.OUT | 100 |
Lưu ý: Dấu * thay thế cho PY hoặc CPP tương ứng với ngôn ngữ lập trình Python hoặc C++ được sử dụng để làm bài.
Thí sinh chọn 4/5 bài để làm tùy vào năng lực của mình.
BÀI 1. Kỳ thi
Một kỳ thi Ban tổ chức sẽ ra đề gồm bài toán và độ khó của bài toán thứ dự định là không vượt quá . Có tác giả đề xuất bài toán cho Ban tổ chức, bài toán thứ có độ khó là . Ban đầu, cả hai dãy và đều được sắp xếp theo thứ tự không giảm.
Một số bài toán đề xuất có khó hơn dự định ban đầu, vì vậy người ra đề phải đề xuất thêm các bài toán khác. Khi một bài toán mới có độ khó được đề xuất, bài toán khó nhất sẽ bị xóa khỏi kỳ thi, và các bài toán sẽ được sắp xếp sao cho độ khó theo thứ tự không giảm.
Nói cách khác, trong mỗi thao tác, bạn chọn một số nguyên , chèn nó vào mảng , sắp xếp mảng theo thứ tự không giảm và xóa phần tử cuối cùng của nó.
Hãy tìm số lượng bài toán mới tối thiểu cần đề xuất để đảm bảo rằng cho tất cả .
INPUT: CONTEST.INP
- Dòng đầu tiên chứa 2 số nguyên ,
- Dòng thứ 2 chứa số nguyên ;
- Dòng thứ 3 chứa số nguyên .
OUTPUT: CONTEST.OUT: một số nguyên duy nhất là số lượng bài toán cần đề xuất.
Ví dụ:
| INPUT | OUTPUT | Giải thích |
| 6 10 14 20 20 22 27 8 12 15 18 22 30 | 2 | – Người ra đề sẽ thay bằng bài có độ khó và dãy = [8, 10, 14, 20, 20, 22] – Người ra đề sẽ thay bằng bài có độ khó và dãy = [8, 10, 14, 18, 20, 20] |
| 6 4 5 6 7 8 9 1 2 3 4 5 6 | 3 |
Giới hạn:
- Subtask 1: 50% số điểm
- Subtask 2: 50% số điểm còn lại không có ràng buộc gì
BÀI 2. Chia gạo
Sống tại nhà Phú Ông từ nhỏ, Bờm và Cuội là đôi bạn rất thân. Một hôm, do làm việc siêng năng, chăm chỉ nên hai bạn đã được Phú Ông thưởng cho túi gạo. Có gạo rồi, nhưng vấn đề nảy sinh hết sức phức tạp là hai bạn không làm sao chia nhau các túi gạo được. Bởi vì ai cũng muốn giành được nhiều túi gạo về mình. Băn khoăn suốt mấy ngày đêm, cuối cùng hai bạn đành dắt nhau đến nhờ Phú Ông chia giúp.
Nghĩ mãi nghĩ mãi rồi Phú Ông cũng tìm ra được một cách chia mà có lẽ theo ông hai bạn sẽ vui vẻ sau khi nhận được số túi gạo về mình. Dắt hai bạn ra sân đình, Phú Ông yêu cầu Bờm vẽ đường thẳng khác nhau song song với trục Oy có hoành độ , Cuội vẽ đường thẳng khác nhau song song với trục Ox có tung độ , rồi đặt vào các giao điểm của các đường thẳng, mỗi giao điểm 1 túi gao. Sau đó Phú Ông vẽ một đường tròn với toạ độ tâm bán kính , cho Bờm lấy số túi gạo ở phía ngoài đường tròn, Cuội lấy số túi gạo còn lại.
Yêu cầu: Tính số túi gạo chênh lệch của hai bạn.
INPUT: RICE.INP
- Dòng đầu tiên theo thứ tự là 5 số .
- Dòng thứ hai ghi số mô tả hoành độ các đường thẳng Bờm vẽ.
- Dòng thứ ba ghi số mô tả tung độ các đường thẳng Cuội vẽ.
OUTPUT: RICE.OUT
- Một số nguyên duy nhất là số túi gạo chênh lệch của Bờm và Cuội.
Giới hạn:
Ví dụ:
| INPUT | OUTPUT |
| 3 4 3 3 3 1 5 6 1 7 6 3 | 2 |
Ràng buộc:
- Subtask1: 60% test
- Subtask2: 40% test còn lại không có ràng buộc gì.
Bài 3. Biến đổi xâu
Cho xâu kí tự , bạn được thực hiện phép biến đổi sau: Chọn hai chỉ số và sao cho , thay kí tự ở vị trí thứ thành kí tự ở vị trí thứ .
Ví dụ, giả sử xâu = “hanh”; bằng cách chọn và , ta có thể biến đổi xâu thành “haah”. Tuy nhiên, bạn không thể biến đổi từ xâu hanh thành “hnnh”.
Cho hai xâu kí tự và có cùng độ dài, bạn được thực hiện phép biến đổi trên không giới hạn số lần. Bạn cần trả lời có thể biến đổi từ thành hay không?
INPUT: STRING.INP:
- Dòng đầu tiên ghi số nguyên là số bộ test
- nhóm dòng tiếp theo, mỗi nhóm chứa hai xâu và có độ dài không quá 5*104 ký tự các chữ cái in thường.
OUTPUT: STRING.OUT:
- Gồm t dòng, mỗi dòng thông báo “yes” nếu có thể biến đổi từ thành hoặc thông báo “no” nếu không thể biến đổi xâu thành .
Ví dụ:
| INPUT | OUTPUT |
| 2 hanh hnnh hanh haah | no yes |
Ràng buộc:
- Subtask1: 60% test
- Subtask2: 40% test còn lại không có ràng buộc gì.
Bài 4. Xóa số
Trong quyển vở ghi chép Toán của Bình có hai dãy số có cùng độ dài . Anh ta định nghĩa giá trị của hai dãy là tổng các tích ghép cặp dãy thứ nhất với dãy thứ hai đảo ngược. Ví dụ với hai dãy sau:
| 3 | -4 | -3 | -2 | 2 | 0 |
| -3 | 0 | 5 | -1 | 3 | 2 |
Thì giá trị của hai dãy này là:
3 × 2 + (−4) × 3 + (−3) × (−1) + (−2) × 5 + 2.0 + 0 × (−3) = −13
Bình rất thích cặp dãy có giá trị lớn. Anh ta quyết định xóa phần tử đầu tiên (có thể là 0) và xóa phần tử cuối cùng (có thể là 0) sao cho hai dãy còn lại có giá trị lớn nhất.
Yêu cầu: Viết chương trình xác định và cũng như giá trị lớn nhất tìm được.
INPUT: REMOVE.INP:
- Dòng đầu tiên ghi số nguyên là độ dài của hai dãy ban đầu
- Hai dòng tiếp theo, mỗi dòng có số nguyên mô tả hai dãy ban đầu. Tất cả các số trong hai dãy có giá trị nằm trong khoảng từ -1000 đến 1000
OUTPUT: REMOVE.OUT:
- Hai số và được ghi trên dòng đầu
- Dòng thứ hai ghi giá trị lớn nhất tìm được
- Nếu có nhiều cách chọn thì chỉ cần đưa ra một trong số chúng.
Ví dụ:
| INPUT | OUTPUT |
| 6 3 -4 -3 -2 2 0 -3 0 5 -1 3 2 | 0 3 24 |
Ràng buộc:
- Subtask1: 60% test
- Subtask2: 40% test còn lại không có ràng buộc gì.
Bài 5. Chia tay
Đất nước Alpha có thành phố và đoạn đường nối các thành phố, tất cả các thành phố luôn đảm bảo sự đi lại với nhau.
Alice và Jonh là một cặp vợ chồng, họ quyết định chia tay nhau (vì lý do gì thì chỉ có máy tính mới biết). Họ ghét nhau đến nỗi mỗi người sẽ tìm một thành phố để ở mà khoảng cách giữa hai thành phố của họ là xa nhất. Khoảng cách giữa hai đỉnh và là số cạnh đi qua khi di chuyển từ sang .
Yêu cầu: Hãy giúp cặp đôi không hạnh phúc này tìm hai thành phố thỏa mãn yêu cầu trên.
INPUT: CHIATAY
- Dòng đầu chứa số nguyên
- dòng tiếp theo chứa hai số và thể hiện có đường đi trực tiếp giữa thành phố và .
OUTPUT: CHIATAY
- Một dòng duy nhất ghi khoảng cách xa nhất giữa hai thành phố mà họ sẽ ở.
Ví dụ:
| INPUT | OUTPUT | Giải thích |
| 7 1 6 1 2 1 3 1 5 3 7 2 4 | 4 | Hai thành phố họ lựa chọn để ở là 4 và 7 |
