trang chủ / đề bài / hongmatrix

Trò chơi của Hongcow

Đề bài

Mô tả

Đây là một bài toán tương tác (interactive).

Hệ thống giữ một ma trận bí mật M kích thước n×n, hàng và cột được đánh số từ 1 đến n. Mọi phần tử thoả 0≤Mi,j≤109, và Mi,i=0 với mọi i.

Với mỗi hàng i, hãy tìm giá trị nhỏ nhất trên hàng đó không kể phần tử nằm trên đường chéo chính, tức là minj≠iMi,j.

Để làm việc đó, bạn được đặt tối đa 20 truy vấn. Một truy vấn là một tập chỉ số phân biệt {w1,w2,…,wk} với 1≤k≤n và 1≤wt≤n. Hệ thống trả lời n số nguyên, số thứ i bằng min1≤t≤kMi,wt.

Câu trả lời của một truy vấn có tính cả phần tử đường chéo khi i thuộc tập chỉ số, nên với hàng i bạn chỉ dùng được những truy vấn mà tập chỉ số không chứa i.

Bạn sẽ nhận kết quả sai nếu đặt quá 20 truy vấn, nếu tập chỉ số có phần tử trùng nhau, nếu k nằm ngoài đoạn [1,n], hoặc nếu câu trả lời cuối cùng không đúng.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên n (2≤n≤1000).

Sau mỗi truy vấn, đọc một dòng chứa n số nguyên là câu trả lời của hệ thống.

Dữ liệu ra

Để đặt một truy vấn, in số nguyên k trên một dòng, rồi in k chỉ số phân biệt w1,w2,…,wk trên dòng tiếp theo.

Khi đã sẵn sàng trả lời, in −1 trên một dòng, rồi in n số nguyên trên dòng tiếp theo: số thứ i là giá trị nhỏ nhất của hàng i sau khi bỏ qua phần tử đường chéo. In câu trả lời cuối cùng không được tính là một truy vấn.

Sau mỗi lần in, bạn phải flush output (ví dụ cout << flush trong C++, flush=True trong Python).

Ràng buộc

  • 2≤n≤1000
  • 0≤Mi,j≤109
  • Mi,i=0 với mọi i
  • Tối đa 20 truy vấn

Ví dụ

Input Output Giải thích
2
0 9
7 0
1
1
1
2
-1
7 9
Ma trận bí mật là (0790). Truy vấn {1} trả về cột 1 là (0,9), truy vấn {2} trả về cột 2 là (7,0). Hàng 1 chỉ được phép dùng truy vấn {2} nên đáp án là 7; hàng 2 chỉ được phép dùng truy vấn {1} nên đáp án là 9.
3
0 5 0
3 0 8
0 0 4
2 7 0
2
1 3
1
2
2
1 2
1
3
-1
2 5 4
Ma trận bí mật là (032507480). Hàng 1 có các phần tử ngoài đường chéo là 3,2 nên nhỏ nhất bằng 2; hàng 2 được 5; hàng 3 được 4. Bốn truy vấn ở đây tương ứng với việc tách chỉ số theo hai bit thấp nhất.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0