BOI 2026 - Ngày 1

Bạn có \(n\) khối gỗ thuộc \(k\) màu khác nhau, được xếp thành một hàng. Màu của các khối là \(c_1,c_2,\ldots,c_n\), mỗi giá trị nằm trong đoạn từ \(1\) đến \(k\).

Một màu được gọi là cân bằng nếu vị trí trung bình của các khối mang màu đó bằng \((n+1)/2\). Giá trị này không nhất thiết là số nguyên.

Ví dụ, xét cách xếp \(7\) khối có màu lần lượt là \(1,2,2,1,3,1,2\). Vị trí trung bình của màu \(1\) là \((1+4+6)/3=11/3\), của màu \(2\) là \((2+3+7)/3=4\), và của màu \(3\) là \(5\). Vì \((7+1)/2=4\), màu \(2\) cân bằng còn màu \(1\) và \(3\) không cân bằng.

Hình 1: Cách xếp bảy khối trong ví dụ; màu \(2\) là màu cân bằng.

Hãy xác định có thể sắp xếp lại các khối sao cho mọi màu đều cân bằng hay không.

Dữ liệu vào

Dòng đầu chứa số nguyên \(t\), là số lượng bộ test.

Mỗi bộ test gồm hai dòng:

• Dòng đầu chứa hai số nguyên \(n,k\), lần lượt là số khối và số màu khác nhau.
• Dòng thứ hai chứa \(n\) số nguyên \(c_1,c_2,\ldots,c_n\). Mỗi màu đều xuất hiện ít nhất một lần.

Dữ liệu ra

Với mỗi bộ test, in YES nếu tồn tại cách sắp xếp và in NO nếu không tồn tại. Nếu tồn tại, ở dòng tiếp theo in \(n\) số nguyên mô tả màu của các khối theo một thứ tự hợp lệ.

Ràng buộc

• \(1\le t\le100\).
• \(1\le k\le n\le2\cdot10^5\).
• \(1\le c_i\le k\).
• Tổng \(n\) qua mọi bộ test không vượt quá \(2\cdot10^5\).

Phân nhóm

1. \(4\) điểm: \(n\le3\).
2. \(13\) điểm: \(n\le15\).
3. \(18\) điểm: có nhiều nhất một màu xuất hiện số lần lẻ.
4. \(23\) điểm: mọi màu xuất hiện số lần bằng nhau.
5. \(15\) điểm: \(k\le15\).
6. \(27\) điểm: không có ràng buộc thêm.

3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1

YES
1 2 2 1 1 1 2
NO
YES
1 1

Nguồn

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

Cho một lưới \(n\times n\), mỗi ô là đất hoặc nước. Các hàng và cột được đánh số từ \(1\) đến \(n\). Mỗi bước, bạn có thể đi sang trái, sang phải, lên hoặc xuống. Hai ô được gọi là liên thông nếu có thể đi giữa chúng qua một hoặc nhiều bước mà luôn ở trên các ô cùng loại.

Các ô đất tạo thành một hòn đảo liên thông và các ô nước tạo thành một đại dương liên thông. Hàng đầu, hàng cuối, cột đầu và cột cuối chỉ gồm các ô nước.

Bạn cần trả lời \(q\) truy vấn. Với hai ô đất \((r_1,c_1)\) và \((r_2,c_2)\), hãy tìm số bước ít nhất để đi từ ô thứ nhất tới ô thứ hai mà luôn ở trên đất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(n,q\), lần lượt là kích thước lưới và số truy vấn.

\(n\) dòng tiếp theo, mỗi dòng gồm \(n\) ký tự mô tả lưới. Ký tự . biểu diễn nước và # biểu diễn đất.

\(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(r_1,c_1,r_2,c_2\), mô tả hàng và cột của hai ô đất.

Dữ liệu ra

Với mỗi truy vấn, in đáp án trên một dòng riêng.

Ràng buộc

• \(3\le n\le1000\).
• \(1\le q\le10^5\).
• Trong mọi truy vấn, \(1<r_1,c_1,r_2,c_2<n\).

Phân nhóm

1. \(10\) điểm: \(n\le200\), \(q\le200\).
2. \(6\) điểm: trên mỗi hàng và mỗi cột, không có ô nước nào nằm giữa hai ô đất.
3. \(16\) điểm: không có hình vuông \(2\times2\) nào gồm toàn ô đất.
4. \(28\) điểm: trên mỗi hàng, không có ô nước nào nằm giữa hai ô đất.
5. \(40\) điểm: không có ràng buộc thêm.

8 4
........
..####..
.##.###.
.##.###.
.#......
.#####..
..#####.
........
2 3 3 7
4 5 4 5
4 7 7 7
6 2 3 2

5
0
17
3

Nguồn

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

Một đất nước có \(n\) thành phố, đánh số \(1,2,\ldots,n\), được nối bởi \(m\) con đường hai chiều. Số đường nhiều hơn số thành phố không quá \(10\), và luôn có thể đi giữa hai thành phố bất kỳ qua một hoặc nhiều con đường.

Một du khách lập kế hoạch chuyến đi với các điều kiện sau:

• Chuyến đi bắt đầu tại thành phố \(1\) và kết thúc tại thành phố \(n\).
• Chuyến đi gồm đúng \(k\) bước, mỗi bước đi qua một con đường.
• Không được đi tới rồi quay lại ngay trên cùng một con đường trong hai bước liên tiếp. Vẫn được dùng cùng một con đường nhiều lần nếu giữa hai lần dùng có bước khác.

Có bao nhiêu kế hoạch đi từ thành phố \(1\) tới thành phố \(n\) trong đúng \(k\) bước? Hai kế hoạch khác nhau nếu tại một bước nào đó chúng đi tới hai thành phố khác nhau.

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(n,m,k\), lần lượt là số thành phố, số con đường và số bước của chuyến đi.

\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên phân biệt \(u,v\), biểu thị một con đường nối hai thành phố đó. Giữa hai thành phố có nhiều nhất một con đường.

Dữ liệu ra

In số kế hoạch khác nhau theo modulo \(10^9+7\).

Ràng buộc

• \(2\le n\le2\cdot10^5\).
• \(n-1\le m\le n+10\).
• \(1\le k\le10^4\).

Phân nhóm

1. \(7\) điểm: \(n,k\le10\).
2. \(8\) điểm: \(n,k\le100\).
3. \(11\) điểm: \(m=n-1\).
4. \(29\) điểm: \(m=n-1\) hoặc \(m=n\).
5. \(15\) điểm: \(n\le1000\).
6. \(30\) điểm: không có ràng buộc thêm.

4 5 5
1 2
1 3
2 3
2 4
3 4

4

4 3 4
1 2
2 3
2 4

0

Nguồn

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