SQRT Contest #04 - Điền dấu
Xem dạng PDF
Gửi bài giải
Điểm:
29,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Xét biểu thức sau:
$$\pm 1^K \pm 2^K \pm 3^K \pm ... \pm M^K = C$$
Bạn được cho hai số nguyên ~N, K~. Nhiệm vụ của bạn là tìm một số nguyên dương ~M~ và thay thế các dấu ~\pm~ trong biểu thức trên thành dấu cộng hoặc trừ để giá trị ~|N - C|~ là nhỏ nhất có thể.
Dữ liệu
- Một dòng duy nhất gồm hai số nguyên không âm ~N, K~ ~(0 \le N \le 10^{12}, 1 \le K \le 9)~.
Kết quả
- Một dòng duy nhất gồm một xâu chỉ gồm các ký tự
+hoặc-mô tả kết quả bài toán. Ký tự thứ ~i~ trong xâu là+nếu dấu ~\pm~ thứ ~i~ trong biểu thức có thể được thay thành dấu cộng; ký tự thứ ~i~ trong xâu là-trong trường hợp ngược lại. Giới hạn độ dài xâu được cho trong bảng dưới đây:
| ~K~ | Độ dài kết quả tối đa |
|---|---|
| ~K \le 5~ | ~1\ 500\ 000~ |
| ~K = 6~ | ~200\ 000~ |
| ~K = 7~ | ~65\ 000~ |
| ~K = 8~ | ~18\ 000~ |
| ~K = 9~ | ~7\ 000~ |
Chấm điểm
- Giả sử điểm tối đa của một test là ~100~. Gọi ~X = |N - C|~ và ~P = 5 - \frac{K}{2}~. Điểm của bạn sẽ được tính như sau:
| Chênh lệch | Công thức tính điểm |
|---|---|
| ~X = 0~ | ~100~ |
| ~0 < X \le 4~ | ~85 + 15 \times (\frac{4 - X}{4})^P~ |
| ~4 < X \le 20~ | ~70 + 15 \times (\frac{20 - X}{16})^P~ |
| ~20 < X \le 100~ | ~45 + 25 \times (\frac{100 - X}{80})^P~ |
| ~100 < X \le 10^4~ | ~25 + 20 \times (\frac{4 - log_{10}(X)}{2})^P~ |
| ~10^4 < X \le 10^7~ | ~10 + 15 \times (\frac{7 - log_{10}(X)}{3})^P~ |
| ~10^7 < X \le 10^{10}~ | ~10 \times (\frac{10 - log_{10}(X)}{3})^P~ |
| ~X > 10^{10}~ | ~0~ |
Subtask
| Tỉ lệ điểm | Ràng buộc bổ sung |
|---|---|
| ~6\%~ | ~K = 1~ |
| ~6\%~ | ~N \le 1000, K = 2~ |
| ~8\%~ | ~N \le 10^5, K = 2~ |
| ~8\%~ | ~N \le 10^6, K = 3~ |
| ~8\%~ | ~N \le 10^8, K = 4~ |
| ~8\%~ | ~N \le 10^{10}, K = 5~ |
| ~10\%~ | ~K = 6~ |
| ~10\%~ | ~K = 7~ |
| ~10\%~ | ~K = 8~ |
| ~10\%~ | ~K = 9~ |
| ~16\%~ | Không có giới hạn gì thêm |
Ví dụ
Ví dụ 1
Dữ liệu
0 2
Kết quả
++-+--+
Giải thích:
Ta có: $$1^2 + 2^2 - 3^3 + 4^2 - 5^2 - 6^2 + 7^2 = 1 + 4 - 9 + 16 - 25 - 36 + 49 = 0$$
Do đó output được ~100\%~ số điểm.
Ví dụ 2
Dữ liệu
0 2
Kết quả
+
Giải thích:
Ta có ~1^2 = 1~, ~P = 5 - \frac{2}{2} = 4~. Do ~0 < |0 - 1| \le 4~ nên điểm của output được tính theo công thức: $$85 + 15 \times (\frac{4 - |2 - 1|}{4})^4 \approx 89.746$$
Do đó output được ~89.746\%~ số điểm.
Bình luận