Ở Code Jam có một trò chơi mang tên “Operation” (không liên quan gì đến phẫu thuật). Mỗi lá bài ghi một phép toán số học cơ bản \(O_i\) — cộng, trừ, nhân hoặc chia — cùng một toán hạng nguyên bên phải \(V_i\). Chẳng hạn, một lá có thể ghi + 0, - -2 hoặc / -4. Toán hạng có thể âm hoặc bằng 0, nhưng toán hạng của phép chia không bao giờ bằng 0.

Trong mỗi ván, ta chọn một giá trị nguyên ban đầu \(S\) và bày ra \(C\) lá bài. Người chơi phải sắp thứ tự các lá, dùng mỗi lá đúng một lần; sau đó áp dụng lần lượt các phép toán lên \(S\) để thu được kết quả cuối cùng.

Dù các toán hạng đều nguyên, mọi phép tính được thực hiện trên số hữu tỉ. Ví dụ, với \(S=5\) và các lá + 1, - 2, * 3, / -2, nếu dùng theo thứ tự vừa nêu thì kết quả là \((5+1-2)\times3/(-2)=-6\). Các phép toán luôn được thực hiện theo thứ tự lá bài, không xét độ ưu tiên toán tử. Nếu dùng thứ tự - 2, / -2, + 1, * 3, kết quả là \(((5-2)/(-2)+1)\times3=-3/2\); đây chính là giá trị lớn nhất có thể đạt với bộ bài ấy.

Hãy tìm giá trị cuối cùng lớn nhất có thể và biểu diễn nó dưới dạng phân số tối giản có mẫu số dương.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi test bắt đầu bằng hai số nguyên \(S\) và \(C\): giá trị ban đầu và số lá bài. Tiếp theo là \(C\) dòng; dòng thứ \(i\) chứa một ký tự \(O_i\) thuộc +, -, *, / và số nguyên \(V_i\), mô tả lá bài thứ \(i\).

Dữ liệu ra

Với mỗi test, in Case #x: y z, trong đó x là số thứ tự test bắt đầu từ 1, còn \(y,z\) là các số nguyên sao cho \(y/z\) là kết quả lớn nhất. Hai số \(y,z\) không có ước chung nào ngoài \(1\) và \(-1\), và \(z>0\).

Ràng buộc

• \(1\le T\le100\).
• \(-1000\le S\le1000\).
• \(O_i\) luôn thuộc +, -, *, /.
• \(-1000\le V_i\le1000\).
• Nếu \(O_i\) là / thì \(V_i\ne0\).

Phân nhóm

• Test Set 1 (Visible): \(1\le C\le15\).
• Test Set 2 (Hidden): \(1\le C\le1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
1 2

- 3
* 2
5 4
+ 1
- 2
* 3
/ -2
1000 7
* -1000
* -1000
* 1000
* 1000
* 1000
* 1000
* 1000
-1 3
- -1
* 0
/ -1
0 1
+ 0

Case #1: -1 1
Case #2: -3 2
Case #3: 1000000000000000000000000 1
Case #4: 1 1
Case #5: 0 1

Nguồn

Google Code Jam 2017, Chung kết thế giới, bài Operation.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.