TLEoj Contest #06 - Hiệu hai số - TLEOJ: TLE Online Judge

TLEoj Contest #06 - Hiệu hai số

Điểm: 1100 (thành phần)

Thời gian: 5.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

Noobcoder

Dạng bài

Bạn được cho một dãy số $A$ gồm $n$ phần tử bất kỳ $(1\le A_i\le 10^8)$ . Bạn được cho thêm 2 giá trị là $l$ và $r$ , với $l=min(A), r=max(A)$ .

Nhiệm vụ của bạn là in ra toàn bộ dãy số $A$ bằng cách hỏi câu lệnh sau: $?\ i\ j$ $(1\le i,j\le n)$ . Sau khi bạn hỏi lệnh thì máy sẽ trả về một giá trị là $A_i-A_j$ .

Bạn được hỏi lệnh này tối đa $n-1$ lần. Sau đó, bạn bắt buộc phải in ra toàn bộ dãy số $A$ với lệnh $!\ A_1\ A_2\ \dots\ A_{n-1}\ A_n$ .

Hướng dẫn cách giao tiếp với máy chấm

Để câu trả lời của bạn có thể đến được với máy chấm, bạn cần phải flush output của mình ra. Sau đây là cách flush output ở một vài ngôn ngữ phổ biến

C++: cout << endl;.
Pascal: flush(output).
Python: stdout.flush().
Java: System.out.flush().

Để hiểu rõ hơn, bạn có thể đọc blog của codeforces tại đây: https://codeforces.com/blog/entry/45307

Lưu ý: Một số test/submit có thể có verdict Time limit exceed khi cả chương trình của bạn và máy chấm đều cùng muốn nhập input. Lúc này máy chấm và chương trình của bạn đều chờ output của nhau và sẽ hết thời gian.

Lưu ý: Bạn có thể chạy thử chương trình interactive trên máy của chính mình.

Input, Output và Subtasks

Input

Dòng đầu tiên gồm một số nguyên dương $t$ là số testcase $(1\le t\le 100)$
Sau đó là $t$ testcase, mỗi testcase bao gồm 3 giá trị $n,l,r$ $(1\le n\le 10^5,1\le l\le r\le 10^8)$
Dữ liệu đảm bảo tổng $n$ trong tất cả testcase không quá $10^5$

Interaction: (stdin / stdout)

Sau khi đọc input, bạn không được hỏi quá $n-1$ câu hỏi, với mỗi câu hỏi được định dạng như sau:
- $?\ i\ j$ : Bạn chọn 2 chỉ số $i,j$ , và máy chấm sẽ xuất ra giá trị của $A_i-A_j$
Sau một vài lần hỏi, trường hợp bạn đã tìm ra hoán vị, bạn xuất ra đáp án với định dạng như sau:
- $!\ A_1\ A_2\ \dots\ A_n$ : Bạn trả lời dãy số $A$ mà bạn đã tìm thấy. Thao tác này sẽ không tính vào số lần hỏi. Sau hành động này, ta sẽ chuyển qua testcase tiếp theo.
Trường hợp bạn xuất ra hành động không hợp lệ, số lần hỏi của bạn vượt quá số lần cho phép hay bạn tìm ra kết quả sai, chương trình của bạn sẽ nhận kết quả Wrong answer. Bạn chỉ được nhận kết quả Accepted nếu bạn xuất ra đúng hoán vị trong tất cả testcase

Sample

Interaction: (stdin / stdout)

Máy chấm	Chương trình nộp	Giải thích
`1`		Có $t=1$ testcase
`2 1 2`		Trong testcase này, $n=2$
	`? 1 2`	Bạn chọn 2 chỉ số là $i=1, j=2$ để hỏi
`-1`		$A_1-A_2=-1$
	`! 1 2`	Bạn đã tìm thấy kết quả, dãy số $A=$ { $1,2$ } và may mắn đúng!

Bình luận

Không có bình luận nào.