Tích mảng nhỏ nhất

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho mảng $a_{1}, a_{2}, \dots, a_{n}$ gồm $n$ số nguyên và một số nguyên dương $x$ . Một phép toán cho phép bạn chọn một chỉ số $i$ ( $1 \leq i \leq n$ ) và thay $a_{i}$ bằng $a_{i} + x$ hoặc $a_{i} - x$ . Một phép toán có thể được áp dụng nhiều lần lên cùng một vị trí.

Bạn được phép thực hiện không quá $k$ phép toán. Hãy in ra mảng kết quả $b_{1}, b_{2}, \dots, b_{n}$ sao cho tích $b_{1} \cdot b_{2} \cdot \dots \cdot b_{n}$ đạt giá trị nhỏ nhất có thể. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$ , $k$ , $x$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra $n$ số nguyên $b_{1}, b_{2}, \dots, b_{n}$ — mảng sau khi áp dụng không quá $k$ phép toán sao cho tích các phần tử là nhỏ nhất có thể. Với mọi $i$ , hiệu $b_{i} - a_{i}$ phải là một bội nguyên (có thể âm hoặc bằng $0$ ) của $x$ , và tổng số phép toán $\sum_{i = 1}^{n} \frac{| b_{i} - a_{i} |}{x}$ không vượt quá $k$ .

Ràng buộc

$1 \leq n, k \leq 2 \cdot 10^{5}$
$1 \leq x \leq 10^{9}$
$| a_{i} | \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 3 1 5 4 3 5 2	5 4 3 5 -1	Đẩy phần tử nhỏ nhất $a_{5} = 2$ qua $0$ bằng $3$ phép trừ: $2 \to 1 \to 0 \to - 1$ . Tích bằng $- 300$ .
5 3 1 5 4 3 5 5	5 4 0 5 5	Không đủ phép toán để đưa bất kỳ phần tử nào sang âm (cần ít nhất $4$ phép). Tốt nhất là đưa $a_{3} = 3$ về $0$ , làm tích bằng $0$ .
5 3 1 5 4 4 5 5	5 1 4 5 5	Cũng không thể tạo phần tử âm. Giảm $a_{2} = 4$ xuống $1$ để tích dương nhỏ nhất có thể.
3 2 7 5 4 2	5 11 -5	Trước hết đẩy $a_{3} = 2$ qua $0$ thành $- 5$ (mất $1$ phép). Dùng phép còn lại để tăng độ lớn phần tử nhỏ nhất theo dấu hiện tại: $a_{2} = 4$ thành $11$ . Tích bằng $- 275$ .

Bình luận

Không có bình luận tại thời điểm này.