Mỗi bước nhảy, con chó lại gần con thỏ một khoảng $X - Y$ mét. Ban đầu con chó cách con thỏ một khoảng $N$ mét, vậy số bước nhảy ít nhất để con chó vượt qua thỏ là $\lceil \frac{N}{X-Y} \rceil$. Trong đó $\lceil x \rceil$ là số nguyên nhỏ nhất lớn hơn hoặc bằng $x$.
Lưu ý, dãy số được cho là một dãy số tăng dần. Độ đẹp của dãy số là khoảng cách lớn nhất giữa hai phần tử liền kề nhau.
Gọi dãy $b$ là dãy khoảng cách, $b[i]=a[i]-a[i-1]$. Khi xóa một phần tử ở dãy $a$ thì dãy $b$ cũng thay đổi, cụ thể 2 phần tử liền kề của dãy $b$ sẽ gộp lại thành một. $a$ là dãy tăng dần vì thế các số trong dãy $b$ đều là số dương. Ta chọn tổng hai số liền kề trong dãy $b$ là lớn nhất là tối ưu nhất. Tuy nhiên để giải quyết bài này ta chỉ tìm khoảng cách lớn nhất giữa $a[i-2]$ và $a[i]$.
Đối với subtask 1 (20%), duyệt tất cả các trường hợp $X$ từ $1$ đến $N - 1$.
Đối với subtask 2, ta có nhận xét như sau:
Vì vậy, ta chọn $X=\frac{N}{2}+1$ thì sẽ có phần dư lớn nhất.
Đối với subtask 1 (20%), có thể sử dụng 2 vòng lặp lồng nhau để tìm kết quả.
Đối với subtask 2: Duyệt qua tất các ký tự từ trái sáng phải. Ta sử dụng một biến “đếm” lưu lại độ dài các nguyên âm liên tiếp kết thúc tại ký tự đang được xét. Nếu ký tự hiện tại không phải là nguyên âm, cập nhật biến đó về giá trị 0, ngược lại cộng thêm 1 vào biến đếm đó. Tại mỗi lần duyệt, ta lưu lại giá trị lớn nhất của biến đếm.
Một số bài tương tự: CSES - Repetitions CSES - Maximum Subarray Sum