BOI 2026 - Ngày 2

Cho hai số nguyên \(n,k\). Hãy chọn \(n\) điểm nguyên phân biệt trên mặt phẳng \(xy\) sao cho có đúng \(k\) cặp điểm có khoảng cách Euclid là số nguyên. Khoảng cách giữa \((x_1,y_1)\) và \((x_2,y_2)\) là

Có thể chứng minh rằng luôn tồn tại lời giải với các ràng buộc của đề.

Dữ liệu vào

Dòng duy nhất chứa hai số nguyên \(n,k\).

Dữ liệu ra

In \(n\) dòng. Dòng thứ \(i\) chứa hai số nguyên là tọa độ \(x,y\) của điểm thứ \(i\). Giá trị tuyệt đối của mọi tọa độ không được vượt quá \(10^9\).

Nếu có nhiều lời giải, có thể in bất kỳ lời giải hợp lệ nào.

Ràng buộc

• \(1\le n\le100\).
• \(0\le k\le n(n-1)/2\).

Phân nhóm

1. \(11\) điểm: \(n\le4\).
2. \(4\) điểm: \(k=n(n-1)/2\).
3. \(6\) điểm: \(k=0\).
4. \(19\) điểm: \(k\le n\).
5. \(22\) điểm: \(k\le n(n-1)/8\).
6. \(38\) điểm: không có ràng buộc thêm.

3 2

1 1
1 2
2 2

Khoảng cách từ \((1,1)\) tới \((1,2)\) và từ \((1,2)\) tới \((2,2)\) đều bằng \(1\). Khoảng cách từ \((1,1)\) tới \((2,2)\) bằng \(\sqrt2\), không phải số nguyên.

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.

Xét một đồ thị có hướng gồm \(n\) đỉnh, đánh số \(1,2,\ldots,n\). Đồ thị được gọi là một tournament nếu giữa mỗi cặp đỉnh có đúng một cạnh theo một trong hai hướng. Nói cách khác, với hai đỉnh phân biệt \(u,v\), có cạnh từ \(u\) tới \(v\) hoặc có cạnh từ \(v\) tới \(u\).

Một chu trình Hamilton là dãy \(c_1,c_2,\ldots,c_n\) đi qua mọi đỉnh rồi quay lại điểm xuất phát. Với mọi \(1\le i<n\), phải có cạnh từ \(c_i\) tới \(c_{i+1}\); ngoài ra phải có cạnh từ \(c_n\) tới \(c_1\).

Bạn được tự do xây dựng một tournament gồm \(n\) đỉnh. Sau đó, bộ chấm bí mật xáo trộn số hiệu các đỉnh. Hãy tìm một chu trình Hamilton trong đồ thị đã bị xáo trộn bằng cách truy vấn hướng cạnh.

Hình 1: Một tournament trước và sau khi số hiệu đỉnh bị xáo trộn; chu trình Hamilton được tô nổi bật.

Tương tác

Đây là bài tương tác. Ban đầu, đọc hai số nguyên \(n,t\), lần lượt là số đỉnh và số bộ test.

Tiếp theo, in \(n\) dòng mô tả tournament. Dòng thứ \(u\) phải gồm đúng \(n\) ký tự 0 hoặc 1; ký tự thứ \(v\) là 1 khi có cạnh từ \(u\) tới \(v\). Không được có cạnh từ một đỉnh tới chính nó, và giữa mỗi cặp đỉnh phân biệt phải có đúng một cạnh.

Sau đó có \(t\) bộ test. Mỗi bộ test dùng cùng tournament do bạn cung cấp, nhưng số hiệu đỉnh được xáo trộn độc lập và được giữ bí mật.

Để truy vấn, in:

? u v

trong đó \(1\le u,v\le n\) và \(u\ne v\) là số hiệu trong đồ thị đã xáo trộn. Bộ chấm trả về > nếu cạnh đi từ \(u\) tới \(v\), hoặc < nếu cạnh đi từ \(v\) tới \(u\).

Khi tìm được chu trình, in ! rồi in \(n\) số nguyên \(c_1,c_2,\ldots,c_n\). Các số này phải theo cách đánh số đã xáo trộn. Ngay sau đó, bộ test tiếp theo bắt đầu.

Phải flush standard output sau khi in đồ thị, truy vấn hoặc câu trả lời. Không được đọc hoặc ghi tệp. Khi tương tác kết thúc, chương trình phải thoát bình thường. Tệp đính kèm hamilton-test.py là công cụ thử tương tác chính thức; phần đầu tệp có hướng dẫn sử dụng.

Ràng buộc

• \(4\le n\le500\).
• \(1\le t\le200\).

Cách chấm

Mỗi phân nhóm chỉ có một test input với \(t=200\). Trong từng bộ test, số hiệu các đỉnh được xáo trộn đều ngẫu nhiên. Nếu dùng quá \(10^4\) truy vấn trong một bộ test, bạn nhận Wrong Answer.

Gọi \(Q\) là số truy vấn trung bình trên tất cả bộ test thuộc phân nhóm.

1. \(5\) điểm: \(n=4\), cần \(Q\le12\).
2. \(7\) điểm: \(n=50\), cần \(Q\le1225\).
3. \(12\) điểm: \(n=50\), cần \(Q\le300\).
4. Từ \(1\) đến \(76\) điểm: \(n=500\), cần \(Q\le1500\).

Trong phân nhóm \(4\), số điểm nhận được là

Ví dụ, \(Q=1500\) nhận \(1\) điểm, \(Q=1000\) nhận \(26\) điểm và \(Q=750\) nhận \(76\) điểm.

5 2

01110
00101
00010
01001
10100

? 1 2
>
? 2 3
>
? 3 4
>
? 4 5
>
? 5 1
>
! 1 2 3 4 5

? 1 2
<
? 1 5
>
? 4 3
>
? 4 5
<
? 3 2
>
! 1 5 4 3 2

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.

Cho mảng \(x_1,x_2,\ldots,x_n\) gồm \(n\) số nguyên. Bạn cần trả lời \(q\) truy vấn \((a,b)\). Trong một thao tác, được chọn một trong hai cách:

• sắp xếp \(a\) phần tử đầu tiên theo thứ tự không giảm; hoặc
• sắp xếp \(b\) phần tử cuối cùng theo thứ tự không giảm.

Với mỗi truy vấn, cần ít nhất bao nhiêu thao tác để sắp xếp toàn bộ mảng theo thứ tự không giảm? Mỗi truy vấn đều bắt đầu từ mảng ban đầu \(x_1,x_2,\ldots,x_n\).

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,q\), lần lượt là độ dài mảng và số truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(x_1,x_2,\ldots,x_n\).

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a,b\).

Dữ liệu ra

Với mỗi truy vấn, in số thao tác ít nhất trên một dòng. Nếu không thể sắp xếp mảng, in -1.

Ràng buộc

• \(1\le n,q\le2\cdot10^5\).
• \(1\le x_i\le10^9\).
• Trong mọi truy vấn, \(1\le a,b\le n\).

Phân nhóm

1. \(6\) điểm: \(n,q\le10\) và \(a+b\le n\) trong mọi truy vấn.
2. \(5\) điểm: \(n,q\le10\).
3. \(7\) điểm: \(a+b\le n\) trong mọi truy vấn.
4. \(14\) điểm: \(1\le x_i\le2\).
5. \(23\) điểm: \(n,q\le5000\) và mảng là một hoán vị của \(1,2,\ldots,n\).
6. \(12\) điểm: \(n,q\le5000\).
7. \(33\) điểm: không có ràng buộc thêm.

6 3
3 1 4 1 5 9
4 1
3 3
2 5

1
-1
2

Ở truy vấn thứ nhất, chỉ cần sắp xếp \(4\) phần tử đầu. Truy vấn thứ hai không thể thực hiện được. Ở truy vấn thứ ba, trước hết sắp xếp \(2\) phần tử đầu, sau đó sắp xếp \(5\) phần tử cuối.

Nguồn

Baltic Olympiad in Informatics 2026 - đề và dữ liệu chính thức.