Olympic 30/4 2026 - Khối 11

Olympic 30/4 2026 - Khối 11

Nguồn: ClueOJ statement pages printed to PDF and merged in exam order; not an original scan

Chuyển nhập/xuất tệp sang stdin/stdout khi chạy trên website.

Câu 1. Giao lưu

Kỳ thi Olympic truyền thống 30 tháng 4 quy tụ N đoàn thí sinh đến từ các trường khác nhau trên khắp cả nước. Mỗi đoàn bao gồm C thí sinh, trong đó thí sinh thứ j ở đoàn thứ i có chỉ số kỹ năng là A_ij.

Ban tổ chức muốn chọn ra một đội gồm N thí sinh, mỗi đoàn một thí sinh để chơi một trò chơi giao lưu. Để mỗi thí sinh thể hiện hết khả năng của mình, ban tổ chức muốn nhóm được chọn gồm các thí sinh có chỉ số kỹ năng càng tương đồng càng tốt. Cụ thể, ban tổ chức muốn sự chênh lệch chỉ số kỹ năng của thí sinh có chỉ số kỹ năng cao nhất và thấp nhất trong đội được chọn là nhỏ nhất có thể. Lê được ban tổ chức giao nhiệm vụ lựa chọn thí sinh cho trò chơi, nhưng vì số lượng thí sinh quá lớn nên cậu cũng không biết phải làm thế nào.

Yêu cầu : Bạn hãy giúp Lê chọn ra đội chơi một cách tối ưu nhất.

Input

• Dòng đầu gồm hai số nguyên dương N và C (1 ≤ N,C ≤ 1500).

• Dòng thứ i trong số N dòng tiếp theo gồm C số nguyên dương A_i1, A_i2, ⋯, A_iC (1 ≤ A_ij ≤ 10⁹).

Output

Gồm duy nhất một số là chênh lệch chỉ số kỹ năng nhỏ nhất tìm được.

Scoring

Sample Input 1

2 3
3 1 8
5 6 7

Sample Output 1

1

Sample Input 2

3 3
3 1 4
2 7 16
9 8 10

Sample Output 2

4

Notes

Trong ví dụ thứ nhất, Lê có thể chọn thí sinh thứ ba của mỗi đoàn để tạo thành một đội gồm các thí sinh có chỉ số kỹ năng lần lượt là 7 và 8. Chênh lệch chỉ số kỹ năng trong trường hợp này là 1.

Trong ví dụ thứ hai, Lê có thể chọn thí sinh thứ ba của đoàn thứ nhất và thí sinh thứ hai của đoàn thứ hai và thứ ba để tạo thành một đội gồm các thí sinh có chỉ số kỹ năng lần lượt là 4,7,8. Chênh lệch chỉ số kỹ năng trong trường hợp này là 4.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.

Câu 2. Đếm đồ

Trong khi ôn luyện các dạng bài toán quy hoạch động để chuẩn bị cho kỳ thi Olympic truyền thống 30 tháng 4, Hồng gặp một bài dạng quy hoạch động cái túi. Bài toán yêu cầu đếm số cách chọn ra một số đồ vật trong một tập hợp các đồ vật cho trước sao cho tổng khối lượng của chúng không vượt quá K. Đây là dạng bài toán cơ bản nên Hồng đã nhanh chóng giải quyết được bài toán này. Tuy nhiên, Hồng đã nghĩ ra một ý tưởng mới bằng việc thay phép cộng các khối lượng thành phép nhân. Bài toán mới được Hồng phát biểu như sau:

Cho một đa tập S (một tập hợp mà mỗi số có thể xuất hiện nhiều lần) chỉ gồm các số nguyên dương. Có hai dạng thao tác thay đổi tập S như sau:

• +x: thêm một phần tử có giá trị x vào tập S.

• -x: xóa một phần tử có giá trị x khỏi tập S. Nếu tập S có nhiều phần tử cùng giá trị x, thao tác này chỉ xóa đi một trong số chúng.

Sau mỗi thao tác, Hồng muốn đếm số lượng tập con của S sao cho tích các phần tử của chúng không nhỏ hơn L và không lớn hơn R. Lưu ý là tính cả tập rỗng với quy ước tập rỗng có tích các phần tử bằng 1.

Yêu cầu : Hãy giúp Hồng giải quyết bài toán này.

Input

• Dòng đầu gồm ba số nguyên dương Q,L,R (1 ≤ Q ≤ 300; 1 ≤ L ≤ R ≤ 10⁹).

• Mỗi dòng trong số Q dòng tiếp theo thuộc một trong hai dạng sau:+x: mô tả thao tác thêm một phần tử có giá trị x vào tập S (1 ≤ x ≤ 10⁹).-x: mô tả thao tác xóa một phần tử có giá trị x khỏi tập S (1 ≤ x ≤ 10⁹). Dữ liệu đảm bảo tại thời điểm xóa trong tập S có ít nhất một phần tử có giá trị x.

Output

Gồm Q dòng, mỗi dòng chứa số lượng tập con thỏa mãn sau thao tác tương ứng. Vì kết quả có thể rất lớn nên chỉ cần in ra phần dư của đáp án khi chia cho 10⁹+7.

Scoring

Sample Input 1

5 2 10
+ 2
+ 3
+ 4
- 2
+ 3

Sample Output 1

1
3
5
2
4

Notes

• Sau thao tác đầu tiên, S={2}. Có một tập duy nhất thỏa mãn là {2}.

• Sau thao tác thứ hai, S={2,3}. Các tập thỏa mãn là {2},{3},{2,3}.

• Sau thao tác thứ ba, S={2,3,4}. Các tập thỏa mãn là {2},{3},{4},{2,3},{2,4}.

• Sau thao tác thứ tư, S={3,4}. Các tập thỏa mãn là {3},{4}.

• Sau thao tác cuối cùng, S={3,3,4}. Các tập thỏa mãn là {3},{3},{4},{3,3}.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: Chưa xác minh thời gian chạy trên toàn miền.

Câu 3. Trang trí

Để trang trí cho buổi lễ bế mạc của kỳ thi Olympic truyền thống 30 tháng 4, Phong dự định thiết kế một mạng lưới gồm các bóng đèn và dây đèn treo trên trần nhà. Mỗi dây đèn kết nối chính xác hai bóng đèn, và giữa mỗi cặp bóng đèn bất kỳ có không quá một dây đèn. Phong định nghĩa khoảng cách giữa hai bóng đèn là số lượng dây đèn ít nhất kết nối thông qua các bóng đèn trung gian. Trong ngôn ngữ đồ thị, mạng lưới Phong muốn xây dựng là một đồ thị vô hướng không trọng số, với mỗi đỉnh tương ứng với một bóng đèn, mỗi cạnh tương ứng với một dây đèn nối hai bóng đèn và khoảng cách giữa hai bóng đèn là đường đi qua ít cạnh nhất giữa hai đỉnh tương ứng.

Hiện tại, Phong đã có sẵn N bóng đèn màu với các màu sắc khác nhau, các bóng đèn này được đánh số từ 1 đến N, và chưa có dây đèn nào. Phong muốn có một buổi lễ đáng nhớ với sự phân bố hợp lý giữa N bóng đèn màu. Phong chuẩn bị một ma trận A kích thước N × N, trong đó A_ij là độ hợp lý giữa bóng đèn màu thứ i và bóng đèn màu thứ j với mong muốn xây dựng mạng lưới sao cho A_ij bằng khoảng cách giữa chúng. Do đó, Phong có thể phải mua thêm một số bóng đèn trắng và dây đèn để hoàn thiện mạng lưới theo ý của mình. Do ngân sách cho buổi lễ hạn chế nên Phong muốn tìm cách mua thêm ít bóng đèn trắng nhất có thể (không có giới hạn về số lượng dây đèn phải mua thêm). Số lượng dây đèn Phong phải mua thêm là số lượng dây đèn trong phương án dựng mạng lưới sử dụng ít bóng đèn trắng nhất mà Phong tìm được.

Yêu cầu : Hãy giúp Phong tìm ra một phương án hợp lệ xây dựng mạng lưới sử dụng ít bóng đèn trắng nhất.

Input

• Dòng đầu chứa một số nguyên dương N là số bóng đèn màu (2 ≤ N ≤ 10).

• Dòng thứ i trong số N dòng tiếp theo chứa N số nguyên không âm A_i1, A_i2, ⋯, A_iN là độ hợp lý giữa các cặp bóng đèn màu (A_ii=0; 1 ≤ A_ij=A_ji ≤ 10, ∀ i ≠ j).

Output

• Nếu không tồn tại phương án thỏa mãn, in ra-1 -1(hai số-1) trên một dòng.

• Ngược lại, in ra kết quả theo định dạng sau:Dòng đầu gồm hai số nguyên K và M lần lượt là số lượng bóng đèn trắng và số lượng dây đèn mà Phong phải mua thêm.Mỗi dòng trong số M dòng tiếp theo gồm hai số nguyên dương i và j mô tả một dây đèn kết nối bóng đèn thứ i và bóng đèn thứ j (1 ≤ i < j ≤ N+K). Các bóng đèn trắng mà Phong mua thêm được đánh số từ N+1 đến N+K.

Lưu ý : có thể chứng minh được rằng nếu tồn tại phương án thỏa mãn thì cũng tồn tại một phương án thỏa mãn mà không phải mua thêm quá 500 bóng đèn trắng.

Scoring

Đối với mỗi test, gọi K_P là số lượng bóng đèn trắng phải mua thêm trong phương án của bạn và K_J là số lượng bóng đèn trắng phải mua thêm trong phương án của Ban giám khảo:

• Nếu K_P ≤ K_J, bạn được 100% số điểm của test đó.

• Nếu K_P > K_J+400, bạn được 0 điểm cho test đó.

• Nếu K_J < K_P ≤ K_J+400, phần trăm số điểm của bạn cho test đó được tính theo công thức:S=(1-√([)4]{K_P-K_J-0.75400})× 100%.

Subtask 1 gồm chín test cố định sau:

• Test 1 — 0,36 điểm, K_J=0: 4 0 1 2 1 1 0 1 2 2 1 0 1 1 2 1 0

• Test 2 — 0,36 điểm, K_J=0: 5 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0

• Test 3 — 0,36 điểm, K_J=29: 7 0 10 10 10 10 10 10 10 0 10 10 10 10 10 10 10 0 10 10 10 10 10 10 10 0 10 10 10 10 10 10 10 0 10 10 10 10 10 10 10 0 10 10 10 10 10 10 10 0

• Test 4 — 0,36 điểm, K_J=40: 10 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0 9 9 9 9 9 9 9 9 9 9 0

• Test 5 — 0,36 điểm, K_J=1: 8 0 2 2 2 1 2 2 1 2 0 2 4 3 1 2 3 2 2 0 2 3 2 2 1 2 4 2 0 3 4 4 1 1 3 3 3 0 3 3 2 2 1 2 4 3 0 2 3 2 2 2 4 3 2 0 3 1 3 1 1 2 3 3 0

• Test 6 — 0,60 điểm, K_J=13: 4 0 9 7 8 9 0 10 7 7 10 0 9 8 7 9 0

• Test 7 — 0,60 điểm, K_J=3: 5 0 1 2 3 4 1 0 1 3 4 2 1 0 2 3 3 3 2 0 2 4 4 3 2 0

• Test 8 — 0,60 điểm, K_J=1: 10 0 2 2 3 2 3 3 3 1 2 2 0 1 2 1 1 2 1 2 2 2 1 0 3 2 1 1 2 3 2 3 2 3 0 1 3 2 3 2 3 2 1 2 1 0 2 1 2 1 2 3 1 1 3 2 0 2 2 3 3 3 2 1 2 1 2 0 1 2 3 3 1 2 3 2 2 1 0 3 3 1 2 3 2 1 3 2 3 0 1 2 2 2 3 2 3 3 3 1 0

• Test 9 — 0,60 điểm, K_J=38: 10 0 7 9 6 6 6 8 5 5 6 7 0 8 7 8 7 9 6 4 6 9 8 0 8 9 9 7 10 9 8 6 7 8 0 8 4 7 7 6 4 6 8 9 8 0 7 8 4 6 7 6 7 9 4 7 0 5 7 5 2 8 9 7 7 8 5 0 6 5 6 5 6 10 7 4 7 6 0 5 5 5 4 9 6 6 5 5 5 0 6 6 6 8 4 7 2 6 5 6 0

Sample Input 1

4
0 1 1 1
1 0 2 2
1 2 0 2
1 2 2 0

Sample Output 1

0 3
1 2
1 3
1 4

Sample Input 2

4
0 1 1 2
1 0 2 1
1 2 0 2
2 1 2 0

Sample Output 2

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

Notes

Phong không cần phải mua thêm bóng đèn trắng nào trong ví dụ thứ nhất mà chỉ cần nối các bóng đèn màu như kết quả đã cho.

Trong ví dụ thứ hai, một phương án tối ưu là Phong mua thêm một bóng đèn trắng và nối các bóng đèn như kết quả đã cho.

---

Ghi chú về bản chuyển thể

Nhập từ stdin và in ra stdout, không cần tạo tệp .INP/.OUT.

Trạng thái lời giải: C++ đã qua bộ kiểm thử cục bộ; chưa xác nhận AC trên OJ.