Câu hỏi của Nguyễn Quang Hiếu

Question

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

Cho số nguyên dương

trịnh kim bảo · Accepted Answer

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.

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).
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:

Khởi tạo low = 1, high = 2000000000 (hoặc một giá trị đủ lớn như 1000000000 + 7).
Khởi tạo ans_m = high (để lưu trữ kết quả m nhỏ nhất).
Trong khi low <= high:
- 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.
Sau khi vòng lặp kết thúc, ans_m sẽ chứa giá trị mmin cần tìm.
Kết quả cuối cùng là n=2×ans_m.

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

Tìm m nhỏ nhất sao cho m(m+1)>11.
Thử các giá trị m:
- m=1:1(1+1)=2≤11
- m=2:2(2+1)=6≤11
- m=3:3(3+1)=12>11
Vậy mmin=3.
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

Câu trả lời:

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.

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).
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:

Khởi tạo low = 1, high = 2000000000 (hoặc một giá trị đủ lớn như 1000000000 + 7).
Khởi tạo ans_m = high (để lưu trữ kết quả m nhỏ nhất).
Trong khi low <= high:
- 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.
Sau khi vòng lặp kết thúc, ans_m sẽ chứa giá trị mmin cần tìm.
Kết quả cuối cùng là n=2×ans_m.

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

Tìm m nhỏ nhất sao cho m(m+1)>11.
Thử các giá trị m:
- m=1:1(1+1)=2≤11
- m=2:2(2+1)=6≤11
- m=3:3(3+1)=12>11
Vậy mmin=3.
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

Trong Microsoft Excel...	Trong Google Trang tính...
Cộng tác trong Excel dành cho web	Cộng tác trong Trang tính theo thời gian thực
Chia sẻ bằng Excel dành cho web hoặc bảng tính được chia sẻ	Chia sẻ trực tiếp từ Trang tính
Lưu tự động bằng SharePoint hoặc OneDrive	Lưu tự động vào Drive
Quản lý các phiên bản bằng Lịch sử hoặc Lịch sử phiên bản trong OneDrive	Quản lý phiên bản bằng lịch sử phiên bản
Thêm công thức và sử dụng tính năng tự động hoàn thành công thức để nhận nội dung đề xuất	Thêm công thức và sử dụng nội dung đề xuất công thức xuất hiện khi bạn nhập văn bản
Ghi macro hoặc sử dụng VBE	Ghi macro hoặc sử dụng Google Apps Script
Tạo bộ lọc	Tạo bộ lọc và chế độ xem bộ lọc
Chèn các bảng tổng hợp đề xuất hoặc tạo một bảng theo cách thủ công	Tạo các bảng tổng hợp theo cách thủ công hoặc tự động nhờ tính năng Khám phá
Tạo biểu đồ theo cách thủ công	Tạo biểu đồ theo cách thủ công hoặc tự động nhờ tính năng Khám phá
Đặt thông báo trong OneDrive	Đặt thông báo trong Trang tín

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

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

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

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

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

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

Chúng tôi đề xuất

Tài nguyên

Ứng dụng mobile

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

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

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

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

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

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

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

Bảng xếp hạng

Phần quà đặc biệt từ OLM

Hè này, gói VIP OLM có gì cho bạn?

Các khóa học có thể bạn quan tâm

Yêu cầu VIP

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