Ban đầu một thiết bị có hệ số hiệu năng bằng 1. Mỗi lần điều chỉnh thiết bị:
mất đúng B giây;
làm hệ số hiệu năng tăng thêm 1.
Bạn được thực hiện một số nguyên k≥0 lần điều chỉnh, rồi chạy một tác vụ. Sau k lần điều chỉnh, thời gian chạy tác vụ là A/k+1 giây.
Tổng thời gian cần dùng là
kB+A/k+1.
Hãy tìm tổng thời gian nhỏ nhất.
Input
Input gồm hai số nguyên A và B.
Output
In tổng thời gian nhỏ nhất. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−6.
Constraints
1≤A,B≤1018.
Số lần điều chỉnh k là số nguyên không âm.
Scoring
Subtask 1 (50 điểm): A,B≤106.
Subtask 2 (50 điểm): không có giới hạn bổ sung.
Example
Test 1
Input
20 1
Output
12.9442719100
Giải thích: Thực hiện k=4 lần điều chỉnh mất 4 giây, sau đó tác vụ chạy trong 20/5 giây. Tổng hai phần bằng khoảng 12.94427191 giây và là nhỏ nhất.
Lời giải tóm tắt
Phân tích: Với số lần điều chỉnh nguyên k, tổng thời gian là
Phân tích:F(k)=Bk+A/sqrt(k+1).
Phân tích: Mở rộng biến thành số thực x≥0, ta có
Phân tích:F''(x)=3A/(4(x+1)^(5/2))>0.
Phân tích: Vì vậy hàm mở rộng lồi; dãy giá trị tại các số nguyên giảm rồi tăng. Nếu k>A/B thì riêng Bk>A=F(0), nên giá trị đó không thể tối ưu. Miền cần xét là [0, floor(A/B)+1].
Thuật toán: Tìm kiếm tam phân trên miền số nguyên. Khi đoạn còn không quá chín giá trị, duyệt tất cả số nguyên còn lại và lấy giá trị nhỏ nhất. Bước vét cuối xử lý chính xác trường hợp đáy liên tục nằm giữa hai số nguyên.
Chứng minh đúng đắn: Tính lồi của hàm mở rộng suy ra dãy F(k) là một đáy. Trong mỗi bước tam phân, so sánh hai điểm trong đoạn cho phép loại bỏ một phía không chứa cực tiểu. Đoạn còn lại luôn chứa ít nhất một số nguyên tối ưu. Cuối cùng thuật toán kiểm tra mọi số nguyên trong đoạn còn lại, nên trả đúng giá trị nhỏ nhất trên toàn miền hợp lệ.
Độ phức tạp:O(log(A/B+1)) lần đánh giá và O(1) bộ nhớ.