Question

[Nguyễn Quang Hiếu]

Nguồn: Bài 1 đề thi Young ICT 2024 - Bảng B

Cho số nguyên dương \(k\).

Yêu cầu: Tìm số nguyên dương \(n\) nhỏ nhất thỏa mãn: Tổng các số chẵn không vượt quá \(n\) lớn hơn \(k\).

Dữ liệu: Gồm một dòng duy nhất chứa số nguyên \(k\).

Kết quả: Số \(n\) nhỏ nhất thỏa mãn.

Giới hạn:

- Subtask 1 (50% số điểm): \(1\le k\le10^9\).

- Subtask 2 (50% số điểm): \(10^9\le k\le10^{18}\).

Ví dụ:

Dữ liệu	Kết quả
11	6

Answer 1

[trịnh kim bảo]

Lời giải bài toán

Bài toán yêu cầu chúng ta tìm số nguyên dương n nhỏ nhất sao cho tổng các số chẵn không vượt quá n lớn hơn số k cho trước.

Phân tích bài toán

Gọi Sn​ là tổng các số chẵn không vượt quá n.

1. Nếu n là số chẵn: Đặt n=2m (với m là số nguyên dương). Các số chẵn không vượt quá n là 2,4,…,2m. Tổng của chúng là:Sn​=2+4+⋯+2m=2(1+2+⋯+m)=2⋅2m(m+1)​=m(m+1). Vì m=n/2, nên Sn​=2n​(2n​+1).
2. Nếu n là số lẻ: Đặt n=2m+1 (với m là số nguyên không âm). Các số chẵn không vượt quá n là 2,4,…,2m. Tổng của chúng là:Sn​=2+4+⋯+2m=m(m+1). Vì m=(n−1)/2, nên Sn​=2n−1​(2n−1​+1).

Chúng ta cần tìm số n nhỏ nhất thỏa mãn Sn​>k.

Xác định giá trị của n

Để Sn​>k, chúng ta có thể thấy rằng Sn​ phụ thuộc vào m, trong đó m là số lượng các số chẵn liên tiếp bắt đầu từ 2 (nếu n=2m) hoặc là số lượng các số chẵn liên tiếp trước n (nếu n=2m+1). Hàm f(m)=m(m+1) là một hàm tăng với m dương. Do đó, nếu m tăng, Sn​ sẽ tăng.

Chúng ta cần tìm số nguyên dương m nhỏ nhất sao cho m(m+1)>k. Gọi giá trị m này là mmin​.

• Nếu chúng ta chọn n=2mmin​: Tổng các số chẵn không vượt quá n là S2mmin​​=mmin​(mmin​+1). Theo định nghĩa của mmin​, giá trị này lớn hơn k.
• Nếu chúng ta chọn n=2mmin​−1: Tổng các số chẵn không vượt quá n là S2mmin​−1​=(mmin​−1)mmin​. Theo định nghĩa của mmin​ (là số nguyên nhỏ nhất sao cho m(m+1)>k), thì (mmin​−1)mmin​ phải nhỏ hơn hoặc bằng k. Do đó, n=2mmin​−1 không thỏa mãn điều kiện.

Vì n=2mmin​ thỏa mãn điều kiện và n=2mmin​−1 không thỏa mãn, và 2mmin​−1 là giá trị lớn nhất nhỏ hơn 2mmin​, nên 2mmin​ chính là số n nhỏ nhất thỏa mãn yêu cầu bài toán.

Tìm mmin​ bằng tìm kiếm nhị phân

Chúng ta cần tìm số nguyên dương m nhỏ nhất sao cho m(m+1)>k. Vì k có thể lên đến 1018, m sẽ vào khoảng k​, tức là khoảng 109. Chúng ta có thể sử dụng tìm kiếm nhị phân (binary search) để tìm mmin​.

Khoảng tìm kiếm:

• Giá trị nhỏ nhất của m có thể là 1.
• Giá trị lớn nhất của m: Nếu m(m+1)>1018, thì m xấp xỉ 109. Một cận trên an toàn cho m là 2×109.

Thuật toán tìm kiếm nhị phân:

1. Khởi tạo low = 1, high = 2000000000 (hoặc một giá trị đủ lớn như 1000000000 + 7).
2. Khởi tạo ans_m = high (để lưu trữ kết quả m nhỏ nhất).
3. Trong khi low <= high:
4. • Tính mid = low + (high - low) / 2.
   • Tính val = mid * (mid + 1). Lưu ý: Vì mid có thể lên đến 2×109, val có thể lên đến 4×1018. Kiểu dữ liệu long long trong C++ có thể chứa giá trị này (tối đa khoảng 9×1018), nên không xảy ra tràn số.
   • Nếu val > k:
   • • Điều này có nghĩa là mid có thể là mmin​ hoặc lớn hơn mmin​. Ta lưu mid vào ans_m và tìm kiếm ở nửa dưới: high = mid - 1.
   • Ngược lại (val <= k):
   • • Điều này có nghĩa là mid quá nhỏ. Ta cần tìm kiếm ở nửa trên: low = mid + 1.
5. Sau khi vòng lặp kết thúc, ans_m sẽ chứa giá trị mmin​ cần tìm.
6. Kết quả cuối cùng là n=2×ans_m.

Ví dụ minh họa (k=11)

1. Tìm m nhỏ nhất sao cho m(m+1)>11.
2. Thử các giá trị m:
3. • m=1:1(1+1)=2≤11
   • m=2:2(2+1)=6≤11
   • m=3:3(3+1)=12>11
4. Vậy mmin​=3.
5. Số n nhỏ nhất là 2×mmin​=2×3=6.

Kiểm tra lại:

• Tổng các số chẵn không vượt quá n=6 là 2+4+6=12. 12>11, thỏa mãn.
• Tổng các số chẵn không vượt quá n=5 là 2+4=6. 6≤11, không thỏa mãn.
• Vậy n=6 là giá trị nhỏ nhất.

Giới hạn và kiểu dữ liệu

• 1≤k≤1018.
• Vì k và các giá trị trung gian có thể lớn, cần sử dụng kiểu dữ liệu long long trong C++ cho k, m, n và các biến phụ trợ trong tính toán.
• tick cho mình