Trại Bò

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie cần đạt điểm cao trong một bài thi có $T$ test case (trọng số bằng nhau) để được vào trại bò. Test case đầu tiên là test mẫu.

Bessie nộp một lời giải không xác định (nondeterministic): lời giải luôn trả lời đúng test mẫu, nhưng với mỗi test còn lại, nó trả lời đúng hoặc sai với xác suất $50 %$ mỗi loại.

Bessie có thể nộp tối đa $K$ lần. Sau mỗi lần nộp, cô biết điểm số và có thể quyết định giữ kết quả này hoặc nộp lại (kết quả cũ bị thay thế). Nếu nộp quá $K$ lần, Bessie bị loại (điểm 0).

Hãy tính điểm kỳ vọng tối đa mà Bessie có thể đạt được với chiến lược tối ưu. Điểm bằng số test case đúng.

Dữ liệu vào

Một dòng chứa hai số nguyên $T$ và $K$ .

Dữ liệu ra

Một số thực — điểm kỳ vọng tối đa, với sai số tuyệt đối hoặc tương đối $\leq 10^{- 6}$ .

Ràng buộc

$2 \leq T \leq 10^{3}$
$1 \leq K \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
2 3	1.875	Với $T = 2$ : ngoài test mẫu, chỉ có 1 test còn lại. Chiến lược tối ưu: nộp lại nếu sai test đó. Sau 3 lần nộp, xác suất đúng = $1 - (1 / 2)^{3} = 7 / 8$ . Kỳ vọng = $1 + 7 / 8 = 1.875$ .
4 2	2.875	Với $T = 4$ , $K = 2$ : điểm kỳ vọng tối đa là $2.875$ .

Bình luận

Không có bình luận tại thời điểm này.