Chiến Lược Đoán Số Chi Phí Lệch
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Trong một trò chơi tương tác, hệ thống chọn bí mật một số nguyên $X \in {1, 2, \dots, N}$. Ở mỗi bước, bạn được quyền chọn một ngưỡng nguyên $m$ và đặt câu hỏi: "$X \le m$ có đúng không?"
- Nếu hệ thống trả lời ĐÚNG ($X \le m$), bạn phải trả chi phí $A$.
- Nếu hệ thống trả lời SAI ($X > m$), bạn phải trả chi phí $B$.
Giả sử bạn sử dụng chiến lược đặt câu hỏi thích nghi tối ưu để luôn chắc chắn xác định chính xác giá trị của $X$ trong mọi tình huống. Hãy tính tổng chi phí nhỏ nhất trong trường hợp xấu nhất để tìm ra $X$.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $T$ ($1 \le T \le 200$) là số bộ test.
- $T$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $N, A, B$ ($1 \le N \le 10^{12}$, $1 \le A, B \le 10^9$).
Dữ liệu ra
Với mỗi bộ test, in ra trên một dòng tổng chi phí nhỏ nhất trong trường hợp xấu nhất.
Ví dụ
| Input | Output |
|---|---|
| 3 5 1 2 1 5 7 10 3 3 |
4 0 12 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion