USACO 2022 - Cow Camp

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2400 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Để đủ điều kiện tham dự trại hè dành cho bò, Bessie cần đạt điểm tốt ở bài cuối cùng của kỳ thi USACOW Open. Bài này có \(T\) bộ test phân biệt (\(2\le T\le 10^3\)) với trọng số bằng nhau, trong đó bộ test đầu tiên là ví dụ. Điểm cuối cùng của cô bằng số bộ test mà lần nộp cuối cùng vượt qua.

Đáng tiếc, Bessie quá mệt để suy nghĩ về bài toán, nhưng vì đáp án của mỗi bộ test chỉ là "yes" hoặc "no", cô có một kế hoạch! Cụ thể, cô quyết định liên tục nộp lời giải bất định sau:

if input == sample_input:
  print sample_output
else:
  print "yes" or "no" each with probability 1/2, independently for each test case

Lưu ý rằng với mọi bộ test ngoài ví dụ, chương trình này có thể sinh kết quả khác khi được nộp lại, vì vậy số bộ test mà nó vượt qua sẽ thay đổi.

Bessie biết rằng tổng cộng cô không thể nộp quá \(K\) (\(1\le K\le 10^9\)) lần, vì nếu không cô chắc chắn sẽ bị loại. Giá trị kỳ vọng lớn nhất có thể của điểm số cuối cùng của Bessie là bao nhiêu, giả sử cô tuân theo chiến lược tối ưu?

Dữ liệu vào

Dòng duy nhất chứa hai số nguyên \(T\) và \(K\) cách nhau bởi dấu cách.

Dữ liệu ra

In đáp án dưới dạng số thập phân có sai số tuyệt đối hoặc tương đối so với đáp án thực tế không quá \(10^{-6}\).

Phân nhóm

  • Các test 3–6 thỏa mãn \(T\le 25\) và \(K\le 100\).
  • Các test 7–9 thỏa mãn \(K\le 10^6\).
  • Các test 10–17 không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
2 3
Output 
1.875
Giải thích

Trong ví dụ này, Bessie nên tiếp tục nộp lại cho đến khi đã nộp \(3\) lần hoặc đạt trọn điểm. Bessie sẽ đạt trọn điểm với xác suất \(\frac{7}{8}\) và đạt nửa số điểm với xác suất \(\frac{1}{8}\), nên giá trị kỳ vọng của điểm số cuối cùng theo chiến lược này là \(\frac{7}{8}\cdot2+\frac{1}{8}\cdot1=\frac{15}{8}=1.875\). Như công thức cho thấy, giá trị kỳ vọng của điểm số Bessie có thể được tính bằng cách lấy tổng theo \(x\) của \(p(x)\cdot x\), trong đó \(p(x)\) là xác suất nhận được số điểm \(x\).

Ví dụ 2

Input 
4 2
Output 
2.8750000000000000000
Giải thích

Ở đây, Bessie chỉ nên nộp lần thứ hai nếu lần thử đầu tiên của cô vượt qua ít hơn \(3\) bộ test.

Nguồn

USACO 2022 February Contest, Gold — Cow Camp: https://usaco.org/index.php?page=viewproblem2&cpid=1210

Tác giả: Benjamin Qi.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: