CEOI 2026 - Ngày 2

Mỗi cặp hoa có thể được nối hoặc không nối. Hai hoa không nối \(a,b\) tự mọc thêm rễ nối nhau nếu tồn tại ít nhất hai hoa khác nhau \(c,d\) mà cả \(a\) và \(b\) đều nối với \(c,d\). Mọi rễ có thể mọc theo quy tắc này đã mọc xong.

Hãy cắt nhiều rễ hiện có nhất sao cho sau khi rễ mọc lại theo quy tắc trên, đồ thị thu được đúng như ban đầu.

Dữ liệu vào

Dòng đầu chứa \(n,m\). \(m\) dòng tiếp theo chứa \(a,b\), biểu thị hai hoa có rễ nối nhau. Các hoa được đánh số từ \(1\) đến \(n\). Đồ thị đầu vào được bảo đảm đã bão hòa theo quy tắc mọc rễ.

Dữ liệu ra

In số rễ lớn nhất có thể cắt.

Ràng buộc

• \(1\le n\le1000\), \(1\le m\le10^5\).

Phân nhóm

1. \(20\) điểm: \(n\le10\), \(m\le20\).
2. \(14\) điểm: \(m=n(n-1)/2\).
3. \(15\) điểm: mỗi hoa nối với nhiều nhất \(7\) hoa khác.
4. \(15\) điểm: \(n\le50\), \(m\le1000\).
5. \(36\) điểm: không có ràng buộc thêm.

Ví dụ

9 14
1 2
1 4
1 5
2 4
2 5
3 4
4 5
3 6
4 6
6 7
6 9
7 9
8 9
5 8

2

Nguồn

CEOI 2026 - Ngày 2, bài Flower Cutting.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.

Có \(n\) máy tính và \(m\) tháp ở các vị trí phân biệt trên một đường thẳng. Hãy ghép mọi máy tính thành các cặp khác nhau. Một dây nối hai máy có thể ghé bất kỳ dãy tháp nào theo thứ tự tùy ý, kể cả không ghé tháp nào; dây có thể đi ngang qua một tháp mà không ghé tháp đó.

Nếu dây đi từ vị trí \(a\) qua các tháp \(x_1,\ldots,x_k\) đến \(b\), độ dài là \(|a-x_1|+|x_1-x_2|+\cdots+|x_k-b|\). Điểm của dây là \(f\cdot u-l\), với \(u\) là số tháp khác nhau mà dây ghé. Các dây khác nhau có thể cùng ghé một tháp. Hãy tối đa tổng điểm.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi test gồm ba dòng: \(n,m,f\); \(n\) vị trí máy tính \(a_1,\ldots,a_n\); và \(m\) vị trí tháp \(b_1,\ldots,b_m\).

Dữ liệu ra

In \(T\) số nguyên, mỗi số là tổng điểm lớn nhất của một test.

Ràng buộc

• \(1\le T\le10^4\). Gọi \(N,M\) lần lượt là tổng các \(n,m\) qua mọi test: \(1\le N,M\le2\cdot10^5\).
• \(0\le f\le10^9\), \(n\) chẵn.
• \(1\le a_i,b_i\le10^9\); mọi vị trí trong một test là phân biệt.

Phân nhóm

1. \(5\) điểm: \(N\le5000\), \(m=1\).
2. \(10\) điểm: \(T\le20\), \(n\le10\), \(m\le100\).
3. \(27\) điểm: \(N,M\le5000\).
4. \(21\) điểm: \(N\le5000\).
5. \(37\) điểm: không có ràng buộc thêm.

Ví dụ

4
2 1 100
1 10
11
4 1 10
2 4 6 8
20
4 1 10
2 4 6 8
5
6 3 10
2 13 4 8 6 10
5 1 9

89
-4
12
51

Nguồn

CEOI 2026 - Ngày 2, bài Towers.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.

Ban đầu văn bản Vim chỉ chứa một ký tự -, con trỏ ở ký tự này và clipboard rỗng. Cần thu được đúng \(n\) dấu trừ liên tiếp. Các lệnh được phép là:

• h: sang trái, hoặc không làm gì nếu ở ký tự đầu.
• l: sang phải, hoặc không làm gì nếu ở ký tự cuối.
• Y: chép hậu tố từ con trỏ đến cuối văn bản vào clipboard.
• P: chèn một bản sao clipboard ngay trước con trỏ và đưa con trỏ tới ký tự vừa chèn cuối cùng; clipboard rỗng thì không làm gì.

Với mỗi \(n\), hãy in số lệnh ít nhất và một dãy lệnh đạt số đó.

Dữ liệu vào

Dòng đầu chứa \(t\). \(t\) dòng tiếp theo, mỗi dòng chứa một giá trị \(n\).

Dữ liệu ra

Với mỗi test, in một dòng gồm số lệnh ít nhất, một dấu cách, và một dãy lệnh đạt đúng số đó.

Ràng buộc

• \(1\le t\le100\), \(1\le n\le10^7\).

Phân nhóm

1. \(20\) điểm: \(n\le100\).
2. \(8\) điểm: \(n\le1000\).
3. \(18\) điểm: \(n\le10^4\).
4. \(18\) điểm: \(n\le10^5\).
5. \(18\) điểm: \(n\le10^6\).
6. \(18\) điểm: không có ràng buộc thêm.

Nếu mọi số lệnh tối ưu nhưng một dãy lệnh thiếu hoặc không hợp lệ, nhận một nửa điểm của phân nhóm đó.

Ví dụ

2
21
2

10 YPYPhPYPPP
2 YP

Nguồn

CEOI 2026 - Ngày 2, bài Vim.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn CEOI 2026 chính thức.