Bài 1

1. Tóm tắt bài toán

• Cho n vị trí được đánh số từ 1 tới n. Khoảng cách giữa mỗi hai vị trí liên tiếp là 1 đơn vị độ dài.
• Con thỏ đang ở vị trí x₁, cà rốt ở vị trí x₂.
• Mỗi bước nhảy, con thỏ có thể di chuyển tối đa a đơn vị độ dài.

2. Yêu cầu

Tìm số bước nhảy ít nhất để con thỏ từ x₁ tới vị trí x₂.

[!Warning] Lưu ý chung

• Giá trị x₁ và x₂ có thể lên tới ~10^{12}~.
• Trong C++, cần dùng kiểu long long để tránh tràn số.

Subtask 1: x₂ ≤ 10⁶

1. Điều kiện ràng buộc

   • x₁ ≤ x₂ ≤ 10⁶
   • Ở subtask này, ta có thể brute-force (vét cạn).

2. Nhận xét

   • Để đạt số bước nhảy ít nhất, mỗi lần thỏ cố gắng nhảy đúng a đơn vị.
   • Gọi cnt là số bước nhảy tối thiểu.

3. Thuật toán (vét cạn)

   1. Khởi tạo cnt = 0 và cur = x₁.

   2. Trong khi cur < x₂:

      • Con thỏ nhảy thêm a đơn vị:

        cur += a
        

      • Tăng cnt lên 1:

        cnt += 1
        

   3. Dừng khi cur ≥ x₂.

   4. Kết quả trả về là cnt.

• Độ phức tạp thuật toán: ~O(x_2)~

1. Code mẫu
   https://www.ideone.com/ptCXT5

Subtask 2: Không có ràng buộc gì thêm

Nhận xét

1. Nhận xét
   • Như ở subtask 1, để tối thiểu hóa số bước, thỏ luôn cố gắng nhảy hết a đơn vị mỗi bước (trừ khi khoảng cách cuối cùng nhỏ hơn a).
   • Do vậy, số bước nhảy tối thiểu chính bằng: $$ \left\lceil \frac{x₂ - x₁}{a} \right\rceil $$ :::

1. Cách tính hiệu quả
   • Với hai số nguyên dương A và B, ta có: $$ \left\lceil \frac{A}{B} \right\rceil = \frac{A + B - 1}{B} \quad(\text{chia lấy phần nguyên}) $$
   • Áp dụng vào bài toán: $$ \text{Số bước tối thiểu} = \left\lceil \frac{x₂ - x₁}{a} \right\rceil = \frac{(x₂ - x₁) + a - 1}{a} $$

• Độ phức tạp thuật toán: ~O(1)~

1. Code mẫu
   https://www.ideone.com/N6bla8