BOI 2019 - Ngày 2

Nhà hàng của Tom rất nổi tiếng. Một trong những lý do là mỗi món ăn đều được ít nhất \(K\) đầu bếp khác nhau cùng chế biến. Hôm nay cần chuẩn bị \(N\) món ăn, trong đó món thứ \(i\) cần \(A_i\) giờ làm việc.

Tom có thể thuê trong số \(M\) đầu bếp để chuẩn bị tất cả các món ăn, nhưng đầu bếp thứ \(j\) chỉ làm việc tối đa \(B_j\) giờ. Hơn nữa, ngay cả khi làm ít hơn, người đó vẫn muốn được trả công cho đủ \(B_j\) giờ.

Một đầu bếp có thể tham gia chế biến nhiều món với thời gian khác nhau. Tuy nhiên, một món ăn chỉ được chuẩn bị đúng yêu cầu nếu có ít nhất \(K\) đầu bếp tham gia và tổng thời gian họ làm việc cho món đó bằng đúng \(A_i\). Mỗi khi tham gia chế biến một món, một đầu bếp luôn làm việc cho món đó một số nguyên dương giờ.

Hãy giúp Tom chọn một tập đầu bếp tối ưu để tổng số giờ được trả công nhưng không làm việc là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\), \(M\), \(K\).

Dòng thứ hai chứa \(N\) số nguyên \(A_i\). Dòng thứ ba chứa \(M\) số nguyên \(B_j\).

Dữ liệu ra

In trên một dòng số giờ các đầu bếp không làm việc nhưng vẫn được trả công khi Tom chọn tập đầu bếp cần thuê một cách tối ưu. Nếu không thể chuẩn bị tất cả \(N\) món ăn theo các quy tắc đã mô tả, in Impossible.

Ràng buộc

\(1\le N,M,K,A_i,B_j\le 300\).

Phân nhóm

1. Nhóm 1 (9 điểm): \(1\le N,K\le 300\), \(1\le M\le 2\), \(1\le A_i,B_j\le 300\).
2. Nhóm 2 (22 điểm): \(1\le N,K\le 300\), \(1\le M\le 15\), \(1\le A_i,B_j\le 300\).
3. Nhóm 3 (20 điểm): \(1\le N,M,A_i,B_j\le 300\), \(K=1\).
4. Nhóm 4 (21 điểm): \(1\le N,M,K,A_i,B_j\le 40\).
5. Nhóm 5 (28 điểm): \(1\le N,M,K,A_i,B_j\le 300\).

Ví dụ

1 2 2
5
3 4

2

1 1 2
5
5

Impossible

3 3 3
3 3 2
3 3 3

Impossible

Nguồn

Baltic Olympiad in Informatics 2019, ngày 2, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.

Jill và Jane là hai chị em. Giáng sinh năm ngoái, mỗi người được tặng một sợi dây gồm những hạt nhiều màu. Ta có thể biểu diễn mỗi màu bằng một chữ cái trong bảng chữ cái tiếng Anh, từ a đến z, và mỗi sợi dây hạt bằng một xâu.

Hai chị em muốn làm vòng cổ từ những sợi dây của mình. Để làm một chiếc vòng cổ, mỗi người có thể bỏ đi một số hạt ở hai đầu dây (có thể không bỏ hạt nào), rồi nối hai đầu của phần dây còn lại. Chiếc vòng cổ thu được có thể được xoay và lật lại.

Hai chị em muốn những chiếc vòng cổ trông giống hệt nhau và dài nhất có thể. Độ dài lớn nhất mà họ có thể đạt được là bao nhiêu?

Dữ liệu vào

Dòng thứ nhất và dòng thứ hai, mỗi dòng chứa một xâu không rỗng gồm không quá \(N\) chữ cái thường, lần lượt mô tả sợi dây hạt của Jill và Jane.

Dữ liệu ra

Dòng đầu tiên chứa một số nguyên dương duy nhất: số hạt lớn nhất mà mỗi chiếc vòng cổ có thể có. Dữ liệu bảo đảm có thể tạo được hai chiếc vòng cổ có độ dài dương.

Dòng thứ hai chứa hai số nguyên: vị trí bắt đầu của phần dây được chọn làm vòng cổ trong xâu của Jill và trong xâu của Jane, theo thứ tự đó. Nếu có nhiều cách chọn, in bất kỳ cách nào. Các vị trí được đánh số từ trái sang phải, bắt đầu từ \(0\).

Ràng buộc

Mỗi xâu có độ dài từ \(1\) đến \(N\), với \(N\le 3000\), và chỉ gồm các chữ cái thường từ a đến z.

Bài này chỉ hỗ trợ C++17; giới hạn \(3\) MB của nhóm \(4\) được trình chấm áp dụng trực tiếp.

Phân nhóm

Chương trình nhận toàn bộ số điểm của một nhóm nếu tìm đúng những chiếc vòng cổ dài nhất có thể trong mọi test của nhóm. Nếu trong mỗi test của nhóm, chương trình tìm được những chiếc vòng cổ có độ dài ít nhất bằng một nửa độ dài tối ưu, chương trình nhận được \(20\%\) số điểm của nhóm.

1. Nhóm 1 (25 điểm): mỗi xâu không rỗng có độ dài không quá \(N=100\).
2. Nhóm 2 (20 điểm): mỗi xâu không rỗng có độ dài không quá \(N=400\).
3. Nhóm 3 (40 điểm): mỗi xâu không rỗng có độ dài không quá \(N=3000\).
4. Nhóm 4 (15 điểm): mỗi xâu không rỗng có độ dài không quá \(N=3000\); giới hạn thời gian không đổi, nhưng chương trình chỉ được sử dụng \(3\) MB bộ nhớ.

Ví dụ

zxyabcd
yxbadctz

4
3 2

Nguồn

Baltic Olympiad in Informatics 2019, ngày 2, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.

Mỗi năm, hai thành phố láng giềng đều cử một đội gồm \(K\) thí sinh tham gia \(K\) nội dung thi khác nhau. Mỗi thí sinh tham gia tất cả các nội dung. Điểm của một đội ở một nội dung là điểm cao nhất mà một thí sinh trong đội đạt được ở nội dung đó. Tổng điểm của đội là tổng điểm của đội ở tất cả các nội dung. Chẳng hạn, nếu \(K=3\) và điểm của các thí sinh là \((4,5,3)\), \((7,3,6)\) và \((3,4,5)\), thì điểm của đội ở các nội dung là \((7,5,6)\) và tổng điểm bằng \(18\).

Mỗi thành phố có một tập thí sinh đủ điều kiện để cử đi thi. Hai thành phố bắt đầu tranh luận không chỉ về việc thành phố nào có đội mạnh nhất, mà còn về việc thành phố nào có đội mạnh thứ \(C\) tốt hơn, với một số nguyên \(C\). Ở đây, \(C=1\) tương ứng với đội mạnh nhất, \(C=2\) tương ứng với đội mạnh thứ hai, và cứ như vậy.

Bạn cần giúp một thành phố xác định tổng điểm dự kiến của đội mạnh thứ \(C\), xét tất cả các đội khác nhau gồm \(K\) người có thể lập từ những thí sinh đủ điều kiện của thành phố đó. Hai đội được xem là khác nhau nếu có ít nhất một thí sinh khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\), \(K\), \(C\), trong đó \(N\) là tổng số thí sinh đủ điều kiện của thành phố, \(K\) là số thành viên trong đội (\(K\le N\)), và \(C\) là thứ hạng của đội cần tìm. Giá trị \(C\) không vượt quá số đội gồm \(K\) thành viên có thể lập được.

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(K\) số nguyên không âm, là điểm dự kiến của một thí sinh ở \(K\) nội dung thi. Không điểm nào lớn hơn \(10^6\).

Dữ liệu ra

In trên một dòng tổng điểm của đội mạnh thứ \(C\).

Ràng buộc

\(1\le N\le 500\), \(1\le K\le 6\), \(1\le C\le 2000\), \(K\le N\). Giá trị \(C\) không vượt quá số đội có thể lập được. Mỗi điểm số nằm trong khoảng từ \(0\) đến \(10^6\).

Phân nhóm

1. Nhóm 1 (13 điểm): \(1\le N\le 500\), \(1\le K\le 2\), \(1\le C\le 2000\).
2. Nhóm 2 (31 điểm): \(1\le N\le 100\), \(1\le K\le 6\), \(1\le C\le 2000\).
3. Nhóm 3 (24 điểm): \(1\le N\le 500\), \(1\le K\le 6\), \(1\le C\le 2000\); không điểm nào lớn hơn \(10\).
4. Nhóm 4 (32 điểm): \(1\le N\le 500\), \(1\le K\le 6\), \(1\le C\le 2000\).

Ví dụ

5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9

24

Nguồn

Baltic Olympiad in Informatics 2019, ngày 2, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.