canuc80k5702·3/26

Một Lần Điều Chỉnh

Nộp bài trên LQDOJ

Bài 57 · Ternary Search

Ban đầu một thiết bị có hệ số hiệu năng bằng . Mỗi lần điều chỉnh thiết bị:

  • mất đúng giây;
  • làm hệ số hiệu năng tăng thêm .

Bạn được thực hiện một số nguyên lần điều chỉnh, rồi chạy một tác vụ. Sau lần điều chỉnh, thời gian chạy tác vụ là giây.

Tổng thời gian cần dùng là

Hãy tìm tổng thời gian nhỏ nhất.

Input

  • Input gồm hai số nguyên và .

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á .

Constraints

  • .
  • Số lần điều chỉnh là số nguyên không âm.

Scoring

  • Subtask ( điểm): .
  • Subtask ( đ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 lần điều chỉnh mất giây, sau đó tác vụ chạy trong giây. Tổng hai phần bằng khoảng 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ớ.