Chiến Lược Đoán Số Chi Phí Lệch

Binary-search Buổi 63 — Interactive & Constructive Mathematics
Points
35
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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.

Draft saved