2025 THT bảng B - Buổi 20

Cho 2 số nguyên \(a, b\). Trong 3 phép tính cộng, trừ, nhân \(a\) cho \(b\), tìm phép tính cho ra kết quả có giá trị lớn nhất.

Yêu cầu: In ra +, -, * tương ứng cho 1 trong 3 phép tính cho kết quả lớn nhất.

Input

• Một dòng duy nhất gồm hai số nguyên \(a, b\).

Output

• Một kí tự +, -, hoặc * tương ứng với phép tính cho kết quả lớn nhất.

Ràng buộc

• \(80\%\) số test có \(2 \le |a|, |b| \le 10^9\).
• \(20\%\) số test có \(2 \le |a|, |b| \le 10^{18}\).

Example

3 4

*

4 -3

-

Trong một hồ sen có \(n+1\) bông sen liên tiếp cách đều nhau (được đánh số từ \(0\) đến \(n\)). Một con ếch đang ở bông sen đầu tiên (bông thứ \(0\)) và nó muốn nhảy đến bông sen cuối cùng (bông thứ \(n\)). Trong một lần nhảy, nó chỉ có thể nhảy qua đúng \(a\) hoặc \(b\) bông sen.

Input

• Dữ liệu nhập vào từ bàn phím gồm một dòng duy nhất chứa ba số nguyên dương \(n, a, b\).

Output

• In ra màn hình số bước nhảy ít nhất để con ếch có thể đến đúng bông sen thứ \(n\). Nếu không thể, in ra -1.

Ràng buộc

• \(80\%\) số test có \(1 \leq n, a, b \leq 10^6\).
• \(20\%\) số test có \(1 \leq n \leq 10^{18}\) và \(1 \leq a, b \leq 10^6\).

Example

19 3 5

5

Một xâu kí tự \(S\) chỉ gồm các chữ cái (a...z, A...Z) và các chữ số (0...9).

Yêu cầu: Hãy tìm ra trong xâu \(S\) ba kí tự liên tiếp sao cho chúng có thể tạo thành một số nguyên dương có giá trị lớn nhất (phải giữ nguyên thứ tự), dữ liệu đảm bảo luôn tồn tại đáp án.

Input

• Dòng đầu tiên là một xâu kí tự \(S\) (\(1 \leq |S| \leq 10^6\)).

Output

• Một số nguyên dương có ba chữ số là kết quả bài toán.

Ràng buộc

• \(50\%\) số test có \(1 \leq |S| \leq 256\).
• \(50\%\) số test không giới hạn gì thêm.

Example

ABC1243DE15462FG

546

Một thương lái vận chuyển và buôn bán hàng dọc theo tuyến đường dài \(n\) km, dọc đường từ km đầu tiên (\(1\)) tới km thứ \(n\) là các điểm buôn bán. Ban đầu xem như thương lái đứng ở vị trí \(0\):

• Trong mỗi lần vận chuyển ông chỉ có thể đi đúng chính xác \(a\) hoặc \(b\) km hướng về phía \(n\) và dừng lại tại điểm buôn bán
• Nếu đi \(a\) km, thương lái sẽ mất chi phí là \(x\) đồng. Còn nếu đi \(b\) km, thương lái sẽ mất chi phí là \(y\) đồng
• Nếu buôn bán ở điểm dừng thứ \(i\), ông sẽ nhận được mức lợi nhuận là \(A_i\) đồng

Thương lái sẽ thực hiện việc vận chuyển và buôn bán như trên dọc theo tuyến đường và chỉ dừng lại ở điểm buôn bán thứ \(n\) (không được đi đến các điểm lớn hơn \(n\), đảm bảo luôn tồn tại cách đi hợp lệ)

Yêu cầu: Tìm số tiền lớn nhất thương lái có thể thu về. Lưu ý: chuyến buôn bán này có thể bị lỗ; nếu mọi cách đều lỗ thì phải chọn cách lỗ ít nhất.

Input

• Dòng đầu tiên gồm năm số nguyên dương \(n, a, x, b, y\) (đảm bảo có thể đi đến \(n\)).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(A_1, A_2, \dots, A_n\), mỗi số cách nhau một khoảng trống (\(1 \le A_i \le 10^9\)).

Output

• Một số nguyên duy nhất là số tiền lớn nhất thương lái có thể thu về.

Ràng buộc

• \(60\%\) số test có \(n \le 20\).
• \(40\%\) số test có \(n \le 10^6\).

Example

10 2 1 3 2
1 3 2 5 4 1 4 1 2 6

12

Cho ba số nguyên \(𝑎, 𝑏, 𝑐\), trong đó \(𝑎, 𝑏\) không đồng thời bằng 0, \(|𝑎|, |𝑏|, |𝑐| \le 10^9\). Xét phương trình:

\(𝑎.𝑥 + 𝑏.𝑦 = 𝑐\)

Yêu cầu: Tìm một nghiệm (\(𝑥, 𝑦\)) của phương trình trên, với \(𝑥, 𝑦\) là các số nguyên thỏa mãn \(|𝑥|, |𝑦| \le 10^{18}\)

Input

• Dòng 1 chứa số nguyên dương \(𝑇 \le 10^4\) là số bộ dữ liệu
• \(𝑇\) dòng tiếp theo, mỗi dòng chứa ba số nguyên dương \(𝑎, 𝑏, 𝑐 \le 10^9\) cách nhau bởi dấu cách ứng với một bộ dữ liệu

Output

• Ứng với mỗi bộ dữ liệu ghi ra hai nghiệm \(𝑥, 𝑦\) tìm được trên một dòng, nếu phương trình không có nghiệm thỏa mãn điều kiện đặt ra, ghi ra trên dòng đó duy nhất một số 0

Các số trên một dòng của input/output được/phải ghi cách nhau bởi dấu cách

Example

3
10 7 16
2 8 3
1 2 3

3 -2
0
1 1