Dãy Sau Những Tổng Đôi · canuc80k2801

Description

Khôi phục chính xác dãy số nguyên dương ẩn bằng các truy vấn trả về tổng của hai vị trí khác nhau.

Trạng thái cần tìm được bộ tương tác chọn trước khi phiên bắt đầu và không thay đổi trong suốt phiên. Lời giải không được đọc trực tiếp trạng thái này; mọi thông tin chỉ đến từ các phản hồi hợp lệ của giao thức bên dưới.

Interaction

Đọc $n$ trước khi hỏi. Truy vấn có dạng ? $i$ $j$ với $1 \leq i, j \leq n$ và $i$ khác $j$ ; đáp án cuối có dạng ! $a_{1}, \dots, a_{n}$ . Flush sau mỗi dòng.

Bộ tương tác trả đúng $a_{i} + a_{j}$ cho mỗi truy vấn hợp lệ. Dòng bắt đầu bằng ! phải chứa đúng $n$ số của dãy.

Dãy đúng nhận AC; chỉ cần một phần tử sai nhận WA. Sai cú pháp, sai chỉ số hoặc vượt $n$ truy vấn nhận lỗi giao thức. Khi nhận $- 1$ hoặc khi luồng vào kết thúc bất thường, chương trình phải dừng ngay. Mọi dòng truy vấn và đáp án đều phải được đẩy khỏi bộ đệm, chẳng hạn bằng endl hoặc cout.flush() trong C++.

Constraints

$3 \leq n \leq 5000$ và $1 \leq a_{i} \leq 1 0^{5}$ . Có không quá $n$ truy vấn; mọi tổng vừa trong kiểu số nguyên $64$ bit.

Scoring

Subtask small - $50$ điểm: mười hidden session đầu dùng kích thước nhỏ để kiểm tra mô hình giao thức và các trường hợp biên cơ bản.
Subtask full - $50$ điểm: mười hidden session còn lại dùng toàn bộ giới hạn, gồm ít nhất hai session $upper - t ai l$ bổ sung cho nhau khi contract có nhiều đại lượng kích thước.
Mỗi hidden session có giá trị $5$ điểm. Một session chỉ được tính điểm khi toàn bộ cuộc hội thoại kết thúc với verdict AC.

Example interaction

Mẫu E01

Bộ tương tác -> Lời giải: 3
Lời giải -> Bộ tương tác: ? 1 2
Bộ tương tác -> Lời giải: 137708
Lời giải -> Bộ tương tác: ? 2 3
Bộ tương tác -> Lời giải: 163658
Lời giải -> Bộ tương tác: ? 1 3
Bộ tương tác -> Lời giải: 159696
Lời giải -> Bộ tương tác: ! 66873 70835 92823
Kết quả: AC

Giải thích: Ba tổng được trả về là $a_{1} + a_{2}, a_{2} + a_{3}$ và $a_{1} + a_{3}$ . Từ ba phương trình đó lời giải suy ra đúng ba giá trị của dãy mẫu rồi gửi toàn bộ dãy, nên nhận AC.

Ý tưởng: Dùng ba tổng a1+a2, a2+a3, a1+a3 để suy ra ba phần tử đầu; sau đó hỏi a(i-1)+ai và khôi phục lần lượt.
Tính đúng đắn: Ta duy trì đúng bất biến mô tả trong thuật toán sau mỗi phản hồi. Mỗi bước chỉ loại một khả năng khi phản hồi của bộ tương tác chứng minh khả năng đó không thể là đáp án; vì trạng thái ẩn không đổi trong phiên, bất biến được bảo toàn cho đến dòng kết luận. Khi thuật toán dừng, đối tượng còn lại hoặc các giá trị đã khôi phục là duy nhất phù hợp toàn bộ phản hồi, nên đáp án gửi đi là đúng.
Giới hạn truy vấn và độ phức tạp: 3 ≤ n ≤ 5000 và 1 ≤ a_i ≤ 100000. Có không quá n truy vấn; mọi tổng vừa trong kiểu số nguyên 64 bit. Cài đặt dùng bộ nhớ tuyến tính theo kích thước trạng thái công khai, hoặc hằng số khi bài không có dãy công khai.