Tăng đơn vị
Đề bài
Cho hai số nguyên dương $a$ và $b$. Ở mỗi bước bạn có thể tăng $a$ thêm $b$ đơn vị hoặc tăng $b$ thêm $a$ đơn vị.
Yêu cầu: cho số nguyên $n$, tìm số bước ít nhất để $a$ hoặc $b$ lớn hơn $n$.
Input:
- Dòng đầu chứa số nguyên $T$ là số lượng truy vấn.
- $T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên lần lượt là $a$, $b$ và $n$.
Output: ứng với mỗi truy vấn in ra kết quả trên một dòng chứa một số nguyên duy nhất là số bước ít nhất cần dùng.
Giới hạn: $1 \le T \le 100$; $1 \le a, b \le n \le 10^9$.
2
1 2 3
5 4 1002
7Giải thích ví dụ 1: $(1, 2) \to (3, 2) \to (3, 5)$: sau 2 bước $b = 5 > 3$. Chỉ 1 bước thì được $(3, 2)$ hoặc $(1, 3)$, chưa số nào lớn hơn 3.
Lời mở đầu
Bài này là bài "C+=" nổi tiếng trên Codeforces (Round 1368, bài A). Đây là một bài tham lam rất ngắn: chỉ có 2 lựa chọn mỗi bước, và ta sẽ chứng minh luôn chọn được một lựa chọn "tốt hơn hẳn". Mình sẽ đi từ cách thử hết mọi khả năng, rồi rút ra quy tắc tham lam và giải thích vì sao nó đúng.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, đề không ghi subtask. Thống kê theo nhóm:
| Test | T | a, b | n | Đáp án |
|---|---|---|---|---|
| 1 | 2 | 1 … 5 | 3 … 100 | 2 … 7 |
| 2 – 30 | 5 | 1 … 30 | 300 … 1 000 | 6 … 11 |
| 31 – 100 | 100 | 1 … 999 | 1 004 300 … 998 516 688 | 15 … 43 |
- Test 1 chính là ví dụ của đề.
- Test 2 – 30: mỗi test 5 truy vấn, $a, b \le 30$, $n \le 1000$ → đáp án chỉ từ 6 đến 11 bước.
- Test 31 – 100: mỗi test đủ 100 truy vấn, $a, b < 1000$ còn $n$ từ $10^6$ tới gần $10^9$ → đáp án tới 43 bước. Ở đây $a + b$ có thể vượt
intnếu không cẩn thận.
Mình chia 2 mức thành 2 "subtask" để so sánh:
| Subtask | Điều kiện | Test | Cách ăn được |
|---|---|---|---|
| 1 | n ≤ 1000, đáp án ≤ 11 | 1 – 30 | Cách 1, 2 |
| 2 | n ≤ 10⁹, đáp án tới 43 | 31 – 100 | Cách 2 |
Ý tưởngCộng vào số nhỏ hơn
Giả sử đang có $x \le y$. Hai lựa chọn cho ra:
- Cộng vào số nhỏ: $(x + y,\ y)$ → sắp lại là cặp $\{y,\ x + y\}$.
- Cộng vào số lớn: $(x,\ x + y)$ → cặp $\{x,\ x + y\}$.
Hai cặp có cùng số lớn $x + y$, nhưng số nhỏ của lựa chọn 1 là $y \ge x$. Nghĩa là cặp thứ nhất không kém hơn ở bất kỳ thành phần nào. Mà phép cộng thì "số lớn hơn vào, số lớn hơn ra": từ cặp to hơn, mọi dãy thao tác đều cho kết quả to hơn (hoặc bằng). Vậy cái gì cặp thứ hai làm được trong $k$ bước thì cặp thứ nhất cũng làm được trong $\le k$ bước.
if (a < b) a += b; else b += a;. Lặp tới khi $a > n$ hoặc $b > n$.Làm vậy thì cặp số biến đổi y hệt dãy Fibonacci: $(1, 1) \to (2, 1) \to (2, 3) \to (5, 3) \to (5, 8) \to \ldots$. Fibonacci tăng theo cấp số nhân (khoảng $1{,}618$ lần mỗi bước), nên dù $n = 10^9$ thì chỉ cần cỡ 45 bước – vòng lặp chạy tức thì, không cần công thức gì thêm.
Em nhập $a$, $b$, $n$ rồi bấm Tiếp để so sánh hai cách: cộng vào số nhỏ (tham lam) và cộng vào số lớn. Thanh màu là độ lớn của $a$, $b$ so với $n$:
Cách 1Thử hết, số bước tăng dần – O(2ᵈ)
Chưa nghĩ ra tham lam thì ta thử: có làm được trong $d = 0$ bước không? $d = 1$? $d = 2$?... Hàm đệ quy thu(a, b, d) thử cả 2 lựa chọn ở mỗi bước, trả về true nếu có cách nào làm vượt $n$ trong tối đa $d$ bước. $d$ đầu tiên thử được chính là đáp án.
- Kiểm tra
a > n || b > ntrước tiên: đã vượt rồi thì khỏi làm thêm. - Toán tử
||"ngắt mạch": nhánh đầu tiên đãtruethì không gọi nhánh thứ hai nữa. - Thử $d$ bước tốn $2^d$ lời gọi. Ở test nhỏ đáp án tối đa 11 thì nhẹ, còn test lớn đáp án tới 43: $2^{43}$ – không thể chạy kịp.
Kết quả chạy thật: C++ đúng 30/100 test (test 1–30, chậm nhất 0.006 giây); test 31–100 bị quá thời gian. Python đúng 30/100 test (test 1–30, chậm nhất 0.028 giây); test 31–100 bị quá thời gian.
Cách 2Tham lam – O(log n) mỗi truy vấn
- Mình dùng
long longcho an toàn: trước mỗi phép cộng thì $a, b \le n \le 10^9$ nên $a + b \le 2 \cdot 10^9$ – vẫn vừaint(tối đa khoảng $2{,}147 \cdot 10^9$) nhưng sát nút; chỉ cần đề nới $n$ lên một chút là tràn số ngay. - Khi $a = b$ thì cộng vào đâu cũng như nhau, code chọn
b += a. - Điều kiện dừng là "lớn hơn $n$" nên vòng lặp chạy khi
a <= n && b <= n.
Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.006 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.031 giây.
if (a > b) a += b; else b += a; thì số nhỏ không bao giờ tăng, số lớn chỉ tăng thêm đúng số nhỏ mỗi bước – tăng theo cấp số cộng. Ví dụ 2 cho ra 24 thay vì 7 (số 5 cứ cộng thêm 4 mỗi bước). Chạy thật: 0/100 test đúng – sai kết quả ở test 1–30, còn ở test 31–100 thì quá thời gian luôn vì số bước lên tới hàng triệu.
Nhận xét
Đăng nhận xét