BOI 2008 - Ngày 2

Sau cuộc bầu cử quốc hội, các đảng phải chọn một liên minh để thành lập chính phủ. Mỗi đảng giành được một số ghế. Liên minh là một tập con các đảng có tổng số ghế lớn hơn một nửa tổng số ghế quốc hội.

Một liên minh được gọi là dư thừa nếu có thể bỏ đi một đảng mà các đảng còn lại vẫn nắm hơn một nửa số ghế. Một đảng như vậy thực tế không có quyền lực, vì các thành viên khác vẫn có thể tự thông qua luật.

Hãy tìm một liên minh không dư thừa có tổng số ghế lớn nhất có thể.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) — số đảng (\(1\le n\le300\)). Các đảng được đánh số từ \(1\) đến \(n\).

Dòng thứ hai chứa \(n\) số nguyên không âm \(a_1,a_2,\ldots,a_n\), trong đó \(a_i\) là số ghế của đảng \(i\). Tổng số ghế dương và không vượt quá \(100\,000\).

Dữ liệu ra

Dòng đầu chứa số nguyên \(k\) — số đảng trong một liên minh không dư thừa có tổng số ghế lớn nhất.

Dòng thứ hai chứa \(k\) chỉ số đôi một khác nhau của các đảng thuộc liên minh. Nếu có nhiều đáp án, có thể in bất kỳ đáp án nào và theo bất kỳ thứ tự nào.

Phân nhóm

1. 40 điểm: \(n\le20\).
2. 60 điểm: không có ràng buộc bổ sung.

Ví dụ

4
1 3 2 4

2
2 4

Bản đồ Byteland được vẽ trên một lưới \(n\times m\), trong đó \(n\) là chiều dọc và \(m\) là chiều ngang. Các đường ngang được gọi là vĩ tuyến và đánh số từ \(0\) đến \(n\); các đường dọc được gọi là kinh tuyến và đánh số từ \(0\) đến \(m\).

Mỗi ô đơn vị cần một khoảng thời gian nhất định để tính dự báo thời tiết. Hệ thống cũ xử lý lần lượt tất cả các ô, nên tổng thời gian bằng tổng thời gian của từng ô.

Hệ thống mới dùng nhiều bộ xử lý. Ta chọn \(r\) vĩ tuyến và \(s\) kinh tuyến để chia bản đồ thành \((r+1)(s+1)\) hình chữ nhật. Mỗi bộ xử lý phụ trách một hình chữ nhật, với thời gian bằng tổng thời gian của các ô nằm trong đó. Thời gian hoàn tất toàn bộ dự báo là giá trị lớn nhất trong thời gian của các bộ xử lý.

Hãy chọn các đường chia sao cho thời gian hoàn tất là nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa bốn số nguyên \(n,m,r,s\) (\(1\le r<n\le18\), \(1\le s<m\le18\)).

\(n\) dòng tiếp theo chứa thời gian của các ô. Số thứ \(j\) trên dòng thứ \(i\) là \(c_{i,j}\) — thời gian của ô nằm giữa vĩ tuyến \(i-1\) và \(i\), đồng thời giữa kinh tuyến \(j-1\) và \(j\) (\(0\le c_{i,j}\le2\,000\,000\)).

Dữ liệu ra

In một số nguyên — thời gian hoàn tất nhỏ nhất có thể.

Phân nhóm

1. 40 điểm: \(n,m\le10\).
2. 60 điểm: không có ràng buộc bổ sung.

Ví dụ

7 8 2 1
0 0 2 6 1 1 0 0
1 4 4 4 4 4 3 0
2 4 4 4 4 4 3 0
1 4 4 4 8 4 4 0
0 3 4 4 4 4 4 3
0 1 1 3 4 4 3 0
0 0 0 1 2 1 2 0

31

Trong căn hầm tối của giáo sư Acidrain có hai ngăn kéo đựng găng tay: một ngăn đựng găng trái và một ngăn đựng găng phải. Mỗi ngăn có găng thuộc \(n\) màu. Giáo sư biết số găng của từng màu trong mỗi ngăn và biết chắc tồn tại ít nhất một cặp găng trái–phải cùng màu.

Trong hầm tối, ông không thể nhận ra màu của bất kỳ chiếc găng nào. Trước khi xuống hầm, ông phải quyết định chính xác sẽ lấy bao nhiêu găng từ mỗi ngăn sao cho, bất kể những chiếc cụ thể được lấy là gì, chắc chắn có ít nhất một cặp trái–phải cùng màu. Ông muốn tổng số găng phải mang lên là nhỏ nhất.

Hãy tìm một cặp số lượng tối ưu cần lấy từ hai ngăn.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) — số màu (\(1\le n\le20\)).

Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\ldots,a_n\) (\(0\le a_i\le10^8\)), trong đó \(a_i\) là số găng trái màu \(i\).

Dòng thứ ba chứa \(n\) số nguyên \(b_1,b_2,\ldots,b_n\) (\(0\le b_i\le10^8\)), trong đó \(b_i\) là số găng phải màu \(i\).

Dữ liệu ra

Dòng đầu chứa số găng cần lấy từ ngăn găng trái. Dòng thứ hai chứa số găng cần lấy từ ngăn găng phải.

Tổng hai số phải nhỏ nhất có thể. Nếu có nhiều đáp án đúng, có thể in bất kỳ đáp án nào.

Phân nhóm

1. 40 điểm: \(n\le4\) và \(a_i,b_i\le10\) với mọi \(i\).
2. 60 điểm: không có ràng buộc bổ sung.

Ví dụ

4
0 7 1 6
1 5 0 6

2
8