Tìm kiếm tam phân

Mức độ: Nâng cao

Tìm kiếm nhị phân theo đáp án cần một câu hỏi có/không đơn điệu. Có những bài không như vậy: đề hỏi giá trị lớn nhất của một hàm mà hàm đó tăng dần rồi giảm dần, ví dụ doanh thu theo giá bán (giá thấp quá thì lãi ít, giá cao quá thì không ai mua). Tìm kiếm tam phân tìm đỉnh của hàm như vậy mà không cần thử mọi giá trị.

Ý tưởng

Hàm f trên đoạn [thap, cao] tăng rồi giảm (gọi là hàm một đỉnh). Chọn hai điểm m₁ nhỏ hơn m₂ bên trong đoạn rồi so f(m₁) với f(m₂):

• f(m₁) nhỏ hơn f(m₂): đỉnh không thể nằm bên trái m₁. Nếu đỉnh ở bên trái m₁ thì từ m₁ sang m₂ hàm đang giảm, f(m₂) phải nhỏ hơn f(m₁), mâu thuẫn. Bỏ phần [thap, m₁).
• Ngược lại: đỉnh không nằm bên phải m₂, lý luận tương tự. Bỏ phần (m₂, cao].

Chọn m₁, m₂ chia đoạn thành ba phần bằng nhau thì mỗi lần bỏ được một phần ba. Đoạn dài N chỉ cần khoảng log_1,5N lần so sánh, với N = 10⁹ là khoảng 52 lần.

Ví dụ doanh thu: giá vé p nghìn đồng thì có 100 - p khách mua, doanh thu f(p) = p × (100 - p).

Trên số nguyên, đặt d = (cao - thap) / 3 (lấy phần nguyên), m₁ = thap + d, m₂ = thap + 2d. Bỏ phần trái thì thap = m₁ + 1, bỏ phần phải thì cao = m₂ - 1.

thap	cao	m1	m2	f(m1)	f(m2)	Bỏ
0	100	33	66	2211	2244	phần trái, thap = 34
34	100	56	78	2464	1716	phần phải, cao = 77
34	77	48	62	2496	2356	phần phải, cao = 61
…

Cứ thế đến khi đoạn còn vài số thì thử hết, được đỉnh p = 50, doanh thu 2500.

Tìm kiếm tam phân trên số nguyên

Trên số nguyên có cách gọn hơn: f tăng rồi giảm nghĩa là f(x + 1) - f(x) dương rồi âm. Câu hỏi “f(x) có nhỏ hơn f(x + 1) không?” là đơn điệu (đúng, đúng, …, sai, sai), nên tìm điểm chuyển bằng tìm kiếm nhị phân quen thuộc: x đầu tiên mà f(x) ≥ f(x + 1) chính là đỉnh.

Python

def f(p):
    return p * (100 - p)

thap, cao = 0, 100
while thap < cao:
    giua = (thap + cao) // 2
    if f(giua) < f(giua + 1):      # còn đang tăng: đỉnh ở bên phải giua
        thap = giua + 1
    else:                          # đã bắt đầu giảm (hoặc đứng yên): đỉnh là giua hoặc bên trái
        cao = giua
print(thap, f(thap))

C++

#include <iostream>
using namespace std;

long long f(long long p) {
    return p * (100 - p);
}

int main() {
    long long thap = 0, cao = 100;
    while (thap < cao) {
        long long giua = (thap + cao) / 2;
        if (f(giua) < f(giua + 1)) thap = giua + 1;   // còn đang tăng
        else cao = giua;                              // đã bắt đầu giảm
    }
    cout << thap << " " << f(thap) << "\n";
    return 0;
}

Lưu ý: cách này đúng khi hàm không có đoạn bằng nhau trước khi tới đỉnh (tăng ngặt rồi giảm). Với hàm lồi (giảm rồi tăng, và mức giảm chậm dần), ví dụ tổng khoảng cách |x - a₁| + … + |x - a_n|, các đoạn bằng nhau chỉ có thể xuất hiện tại đáy, nên tìm đáy vẫn đúng. Hàm có đoạn bằng ở lưng chừng thì không dùng được tìm kiếm tam phân.

Tìm kiếm tam phân trên số thực

Với số thực, lặp một số lần cố định (ví dụ 100 lần), mỗi lần bỏ một phần ba. Sau 100 lần đoạn chỉ còn (2/3)¹⁰⁰ độ dài ban đầu, khoảng 2,5 × 10^-18 lần.

Ví dụ: từ tấm bìa vuông cạnh a, cắt bốn góc bốn hình vuông cạnh x rồi gấp thành hộp không nắp. Thể tích V(x) = x × (a - 2x)² với x từ 0 đến a/2: x nhỏ thì hộp quá thấp, x lớn thì đáy quá nhỏ, nên V tăng rồi giảm.

Python

a = float(input())

def the_tich(x):
    return x * (a - 2 * x) * (a - 2 * x)

thap, cao = 0.0, a / 2
for _ in range(100):
    m1 = thap + (cao - thap) / 3
    m2 = cao - (cao - thap) / 3
    if the_tich(m1) < the_tich(m2):
        thap = m1
    else:
        cao = m2
print(f"{the_tich(thap):.6f}")

C++

#include <cstdio>

double a;

double theTich(double x) {
    return x * (a - 2 * x) * (a - 2 * x);
}

int main() {
    scanf("%lf", &a);
    double thap = 0, cao = a / 2;
    for (int lan = 0; lan < 100; lan++) {
        double m1 = thap + (cao - thap) / 3, m2 = cao - (cao - thap) / 3;
        if (theTich(m1) < theTich(m2)) thap = m1;
        else cao = m2;
    }
    printf("%.6f\n", theTich(thap));
    return 0;
}

Với a = 6: hộp lớn nhất khi x = 1, thể tích 1 × 4 × 4 = 16.

Làm sao biết hàm có một đỉnh?

Đây là phần khó nhất của bài, cần lý luận, không thể chỉ đoán. Vài dấu hiệu hay dùng:

Dấu hiệu	Ví dụ
tổng các hàm lồi là hàm lồi	tổng khoảng cách tới n điểm, tổng bình phương khoảng cách
giá trị lớn nhất của các hàm lồi là hàm lồi	khoảng cách xa nhất tới n điểm
hàm bậc hai	p × (100 - p), (x - a)2 + (x - b)2
một đại lượng tăng, một đại lượng giảm, lấy lớn hơn	max(k × a, (n - k) × b)

Hàm lồi có đáy (giảm rồi tăng) thì tìm đáy; đổi dấu hàm (tìm đỉnh của -f) là quay về trường hợp tăng rồi giảm.

Luyện tập

Gồm 16 bài, chia thành 2 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Hàm trên số nguyên

Bài 1. Giá trị lớn nhất của hàm bậc hai

Nhập a, b, c, L, R (1 ≤ a ≤ 1000, |b| ≤ 10⁶, |c| ≤ 10¹², -10⁶ ≤ L ≤ R ≤ 10⁶). In ra giá trị lớn nhất của f(x) = -a × x² + b × x + c với x nguyên từ L đến R.

Ví dụ: nhập 1 10 3 -5 20 thì in ra 28.

Kiểm tra: nhập 7 -1234 999 -300000 -50.

Xem đáp số

55383

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Định giá vé

Nếu giá vé là p nghìn đồng (p nguyên, 0 ≤ p ≤ N) thì có max(0, N - k × p) khách mua. Mỗi khách nhà xe tốn c nghìn đồng chi phí. Lợi nhuận là (p - c) × (số khách). Nhập N, k, c (1 ≤ N ≤ 10⁹, 1 ≤ k ≤ 1000, 0 ≤ c ≤ 10⁹). In ra lợi nhuận lớn nhất (có thể là 0 khi không bán được vé nào có lãi).

Ví dụ: nhập 100 2 10 thì in ra 800.

Kiểm tra: nhập 1000000000 7 35000000.

Xem đáp số

20358035714285713

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Điểm hẹn

n bạn sống trên một con đường thẳng, bạn thứ i ở km x_i. Chọn một km nguyên p làm điểm hẹn để tổng quãng đường mọi bạn phải đi (|x₁ - p| + … + |x_n - p|) nhỏ nhất. Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số x_i (0 ≤ x_i ≤ 10⁹). In ra tổng quãng đường nhỏ nhất.

Ví dụ:

Nhập	In ra
5 2 9 4 15 7	18

Kiểm tra: nhập

10
100 3 58 1000000000 17 64 64 250 9 41

Xem đáp số

1000000350

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Tổng bình phương nhỏ nhất

Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số nguyên (|a_i| ≤ 10⁶). Chọn số nguyên p để tổng (a₁ - p)² + … + (a_n - p)² nhỏ nhất. In ra tổng đó.

Ví dụ:

Nhập	In ra
4 1 2 6 8	33

Kiểm tra: nhập

9
-1000000 5 17 999999 -3 44 44 1000000 -250000

Xem đáp số

2999980336281

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Điểm hẹn trong thành phố

Thành phố có đường kẻ ô vuông, đi từ (x, y) đến (X, Y) mất |x - X| + |y - Y| bước. n bạn ở các điểm (x_i, y_i). Chọn điểm hẹn (X, Y) có tọa độ nguyên để tổng số bước nhỏ nhất. Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có x, y (|x|, |y| ≤ 10⁹). In ra tổng số bước nhỏ nhất.

Ví dụ:

Nhập	In ra
3 1 5 4 1 6 7	11

Kiểm tra: nhập

6
0 0
10 -3
-7 8
1000000000 2
5 5
-1000000000 -1000000000

Xem đáp số

3000000040

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 6. Hai quầy thu ngân

Có N khách xếp hàng thanh toán ở hai quầy. Quầy một phục vụ mỗi khách mất a phút, quầy hai mất b phút. Chia k khách cho quầy một và N - k khách cho quầy hai (0 ≤ k ≤ N), hai quầy làm cùng lúc. Nhập N, a, b (1 ≤ N, a, b ≤ 10⁹). In ra số phút ít nhất để phục vụ xong mọi khách.

Ví dụ: nhập 10 3 2 thì in ra 12.

Kiểm tra: nhập 1000000000 7 13.

Xem đáp số

4550000000

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Xếp hộp liền nhau

Có n cái hộp trên một kệ dài, hộp thứ i ở ô số a_i (các ô khác nhau). Cần dời các hộp sao cho chúng nằm ở n ô liền nhau p, p + 1, …, p + n - 1 (p nguyên tùy chọn). Dời một hộp từ ô u sang ô v tốn |u - v| công. Dòng đầu có n (1 ≤ n ≤ 10⁵), dòng thứ hai có n số a_i (|a_i| ≤ 10⁹). In ra tổng công nhỏ nhất.

Ví dụ:

Nhập	In ra
4 1 10 3 7	9

Kiểm tra: nhập

8
-20 5 100 6 7 -1000000000 1000000000 50

Xem đáp số

2000000150

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Hàm trên số thực

Bài 8. Hộp không nắp

Từ tấm bìa hình vuông cạnh a, cắt ở bốn góc bốn hình vuông bằng nhau cạnh x rồi gấp thành hộp không nắp. Nhập a (1 ≤ a ≤ 100, số nguyên). In ra thể tích lớn nhất của hộp, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ: nhập 6 thì in ra 16.000000.

Kiểm tra: nhập 97.

Xem đáp số

67605.407407

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Hai chiếc thuyền

Hai chiếc thuyền chuyển động thẳng đều trên mặt hồ. Lúc t = 0, thuyền thứ nhất ở (x₁, y₁) với vận tốc (u₁, v₁) (sau t giây ở (x₁ + u₁ × t, y₁ + v₁ × t)), thuyền thứ hai tương tự. Dòng đầu có x₁, y₁, u₁, v₁, dòng thứ hai có x₂, y₂, u₂, v₂, dòng thứ ba có T (mọi số nguyên, giá trị tuyệt đối không quá 1000, T ≥ 0). In ra khoảng cách nhỏ nhất giữa hai thuyền trong khoảng thời gian từ 0 đến T, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
0 0 1 0 10 5 -1 0 20	5.000000

Kiểm tra: nhập

-300 120 7 -2
450 -80 -9 5
100

Xem đáp số

117.382659

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Trạm bơm bên bờ sông

Bờ sông là trục hoành. Có n ngôi nhà, nhà thứ i ở (x_i, y_i). Đặt một trạm bơm tại điểm (p, 0) và nối ống thẳng từ trạm tới từng nhà. Dòng đầu có n (1 ≤ n ≤ 10⁴), n dòng sau mỗi dòng có x, y (|x|, |y| ≤ 10⁴, số nguyên). In ra tổng chiều dài ống nhỏ nhất, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
2 0 3 8 3	10.000000

Kiểm tra: nhập

5
-100 40
250 -10
30 90
31 0
-7 -200

Xem đáp số

649.782542

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 11. Chạy rồi bơi

Bờ hồ là trục hoành, phía trên là đất, phía dưới là nước. Bạn An ở A = (0, a) trên bờ đất (a lớn hơn 0), cần đến B = (b, -c) dưới nước (c lớn hơn 0). An chạy với tốc độ v₁ trên đất, bơi với tốc độ v₂ dưới nước, đi thẳng từ A tới một điểm P trên bờ rồi bơi thẳng tới B. Nhập a, b, c, v₁, v₂ (số nguyên, 1 ≤ a, c, v₁, v₂ ≤ 1000, |b| ≤ 1000). In ra thời gian ngắn nhất, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ: nhập 3 8 3 1 1 thì in ra 10.000000.

Kiểm tra: nhập 120 -700 45 13 2.

Xem đáp số

76.871533

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Trạm phát sóng bên đường

Con đường là trục hoành. Có n ngôi nhà ở (x_i, y_i). Đặt một trạm phát sóng trên đường sao cho khoảng cách từ trạm tới nhà xa nhất là nhỏ nhất. Dòng đầu có n (1 ≤ n ≤ 10⁴), n dòng sau mỗi dòng có x, y (|x|, |y| ≤ 10⁴, số nguyên). In ra khoảng cách đó, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ:

Nhập	In ra
3 0 3 10 0 4 -4	5.450000

Kiểm tra: nhập

6
-500 100
900 -50
120 700
0 0
-300 -650
800 300

Xem đáp số

776.611228

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Khoảng cách từ điểm tới đoạn thẳng

Nhập 6 số nguyên px, py, ax, ay, bx, by (giá trị tuyệt đối không quá 10⁴, A khác B). In ra khoảng cách ngắn nhất từ điểm P = (px, py) tới một điểm thuộc đoạn thẳng AB (gồm cả hai đầu), làm tròn 6 chữ số sau dấu phẩy.

Ví dụ: nhập 0 5 -3 0 3 0 thì in ra 5.000000.

Kiểm tra: nhập 100 -40 -250 30 60 900.

Xem đáp số

353.190848

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Chỗ tối nhất giữa hai ngọn đèn

Hai ngọn đèn đặt ở hai đầu đoạn đường dài L: đèn một ở vị trí 0 có cường độ I₁, đèn hai ở vị trí L có cường độ I₂. Độ sáng tại vị trí x (0 nhỏ hơn x nhỏ hơn L) là I₁ / x² + I₂ / (L - x)². Nhập L, I₁, I₂ (số nguyên từ 1 đến 1000). In ra độ sáng nhỏ nhất trên đoạn đường, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ: nhập 10 1 1 thì in ra 0.080000.

Kiểm tra: nhập 37 125 8.

Xem đáp số

0.250548

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Ném bóng xa nhất

Ném quả bóng từ độ cao h mét với vận tốc v m/s, góc ném θ so với mặt đất (0 ≤ θ ≤ 90 độ), gia tốc g = 9,8 m/s², bỏ qua sức cản không khí. Bóng bay xa được v × cos θ × (v × sin θ + căn(v² × sin²θ + 2gh)) / g mét. Nhập h, v (số nguyên, 0 ≤ h ≤ 1000, 1 ≤ v ≤ 1000). In ra quãng đường xa nhất, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ: nhập 0 10 thì in ra 10.204082.

Kiểm tra: nhập 37 25.

Xem đáp số

93.737418

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 16. Đường ngắn nhất chạm bờ

Hai điểm A = (x₁, y₁) và B = (x₂, y₂) cùng ở phía trên trục hoành (y₁, y₂ lớn hơn 0). Đi từ A tới một điểm P trên trục hoành rồi tới B. Nhập x₁, y₁, x₂, y₂ (số nguyên, giá trị tuyệt đối không quá 10⁴). In ra quãng đường AP + PB ngắn nhất, làm tròn 6 chữ số sau dấu phẩy.

Ví dụ: nhập 0 3 8 3 thì in ra 10.000000.

Kiểm tra: nhập -150 40 900 275.

Xem đáp số

1096.232183

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.