(sanbang.*)

Nguồn: https://www.hackerrank.com

Đề bài:

Cho số nguyên dương \(n,\ k\) và dãy số nguyên dương \(a_{1},a_{2},\ldots,a_{n}\). Jerry muốn san bằng dãy số \(a_{1} + k,a_{2} + k,\ldots,a_{i - 1} + k,a_{n} + k\) bằng cách thực hiện nhiều lần các bước sau:

1. Chọn 2 số khác nhau trong dãy, gọi hai số đó là \(a,b\)

2. Thay giá trị số lớn bằng \(|a - b|\)

Các bước trên được thực hiện cho đến khi tất cả các số trong dãy có giá trị như nhau.

Ví dụ với dãy số 3 12 6 và \(k = 3\) thì Jerry sẽ thực hiện trên dãy số \(3 + 3,\ 12 + 3,\ 6 + 3\) như sau:

\(6,\ 15,\ 9\) \(\rightarrow\) chọn số 6 và 15 \(\rightarrow\) 6, 9, 9 \(\rightarrow\) chọn số 6 và 9 \(\rightarrow\) 6, 3, 9 \(\rightarrow\) chọn số 3 và 9 \(\rightarrow\) 6, 3, 6 \(\rightarrow\) chọn số 6 và 3 \(\rightarrow\) 3, 3, 6 \(\rightarrow\) chọn số 6 và 3 \(\rightarrow\) 3, 3, 3.

Vậy kết quả là 3

Dữ liệu vào:

+ Dòng đầu tiên ghi hai số nguyên dương \(n,\ q\ (1 \leq n,q \leq 10^{5})\) lần lượt cho biết số lượng phần tử dãy số và số lượng truy vấn.

+ Dòng thứ 2 ghi lần lượt các số \(a_{1},a_{2},\ldots,a_{n}\ (1 \leq a_{i} \leq 10^{14})\)

+ \(q\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(k\ (0 \leq k \leq 10^{9})\)

Kết quả:

+ Với mỗi truy vấn, in ra giá trị một phần tử của dãy \(a_{1} + k,a_{2} + k,\ldots,a_{i - 1} + k,a_{n} + k\) sau khi thực hiện san bằng. Mỗi truy vấn in kết quả trên một dòng.

Ví dụ: