USACO 2021 - US Open - Hạng Đồng

Bessie đã theo học chương trình tiến sĩ khoa học máy tính vì yêu thích ngành này, đồng thời bị cuốn hút bởi viễn cảnh một ngày nào đó trở thành “Tiến sĩ Bessie”. Sau một thời gian nghiên cứu, cô đã công bố \(N\) bài báo (\(1\le N\le10^5\)); bài báo thứ \(i\) nhận được \(c_i\) lượt trích dẫn (\(0\le c_i\le10^5\)) từ các bài báo khác trong giới nghiên cứu.

Bessie nghe nói thành công của một nhà khoa học có thể được đo bằng chỉ số \(h\). Chỉ số \(h\) là số nguyên lớn nhất \(h\) sao cho nhà khoa học có ít nhất \(h\) bài báo, mỗi bài có ít nhất \(h\) lượt trích dẫn. Ví dụ, một người có \(4\) bài báo với số lượt trích dẫn tương ứng là \((1,100,2,3)\) có chỉ số \(h\) bằng \(2\); nếu các số lượt trích dẫn là \((1,100,3,3)\) thì chỉ số \(h\) bằng \(3\).

Để tăng chỉ số \(h\), Bessie dự định viết một bài tổng quan có trích dẫn một số bài báo trước đây của mình. Do giới hạn số trang, cô chỉ có thể đưa vào tối đa \(L\) lượt trích dẫn (\(0\le L\le10^5\)), và tất nhiên mỗi bài báo của cô chỉ có thể được trích dẫn nhiều nhất một lần.

Hãy xác định chỉ số \(h\) lớn nhất mà Bessie có thể đạt được sau khi viết bài tổng quan này.

Lưu ý rằng cố vấn của Bessie có lẽ nên nói cho cô biết việc viết bài tổng quan chỉ nhằm tăng chỉ số \(h\) là không đúng đắn về mặt đạo đức; các nhà khoa học khác không nên noi theo Bessie.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(L\).

Dòng thứ hai chứa \(N\) số nguyên \(c_1,\ldots,c_N\) cách nhau bởi dấu cách.

Dữ liệu ra

In chỉ số \(h\) lớn nhất mà Bessie có thể đạt được sau khi viết bài tổng quan.

Phân nhóm

• Các test 1-7 thỏa mãn \(N\le100\).
• Các test 8-10 thỏa mãn \(N\le1000\).
• Các test 11-17 thỏa mãn \(N\le10^5\).

Ví dụ

4 0
1 100 2 3

2

4 1
1 100 2 3

3

Giải thích ví dụ 1. Bessie không thể trích dẫn bất kỳ bài báo nào trước đây. Như đã nêu, chỉ số \(h\) của \((1,100,2,3)\) là \(2\).

Giải thích ví dụ 2. Nếu Bessie trích dẫn bài báo thứ ba, các số lượt trích dẫn trở thành \((1,100,3,3)\). Như đã nêu, chỉ số \(h\) của dãy này là \(3\).

Nguồn

USACO 2021 US Open, Bronze - Acowdemia I: https://usaco.org/index.php?page=viewproblem2&cpid=1131

Tác giả: Dhruv Rohatgi.

Bessie đang nộp đơn vào chương trình sau đại học ngành khoa học máy tính và đã có một buổi phỏng vấn tại một phòng thí nghiệm danh tiếng. Tuy nhiên, để tránh làm phật lòng bất kỳ ai, Bessie muốn xác định thứ bậc thâm niên tương đối của \(N\) thành viên hiện tại trong phòng thí nghiệm (\(1\le N\le100\)). Không có hai thành viên nào có cùng thâm niên, nhưng việc xác định thứ bậc của họ có thể không dễ. Bessie sẽ xem các công trình công bố của phòng thí nghiệm.

Mỗi công trình có một danh sách tác giả, là một thứ tự của toàn bộ \(N\) thành viên. Danh sách được sắp theo lượng công sức mỗi thành viên đóng góp cho bài báo, từ nhiều đến ít. Nếu nhiều nhà nghiên cứu đóng góp công sức bằng nhau, họ được xếp theo thứ tự từ điển. Do các thành viên thâm niên hơn phải làm thêm các nhiệm vụ quản lý, một nhà nghiên cứu thâm niên hơn không bao giờ đóng góp nhiều công sức hơn một nhà nghiên cứu ít thâm niên hơn.

Ví dụ, xét một phòng thí nghiệm gồm sinh viên trẻ Elsie, Giáo sư Mildred thâm niên hơn và Trưởng khoa Dean rất thâm niên. Một bài báo có thể có thứ tự (Elsie-Mildred-Dean) nếu cả ba người đóng góp lượng công sức khác nhau: Elsie nhiều hơn Mildred và Mildred nhiều hơn Dean. Tuy nhiên, bài báo cũng có thể có thứ tự (Elsie-Dean-Mildred) nếu Mildred và Dean đóng góp bằng nhau, còn Elsie đóng góp nhiều hơn.

Cho \(K\) công trình của phòng thí nghiệm (\(1\le K\le100\)), hãy xác định đối với mọi cặp nhà nghiên cứu xem ai thâm niên hơn, nếu có thể suy ra được.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(K\) và \(N\).

Dòng thứ hai chứa \(N\) xâu cách nhau bởi dấu cách, là tên của các thành viên trong phòng thí nghiệm. Mỗi tên chỉ gồm các chữ cái thường và dài không quá \(10\) ký tự.

Mỗi dòng trong \(K\) dòng tiếp theo chứa \(N\) xâu cách nhau bởi dấu cách, biểu diễn danh sách tác giả của một công trình.

Dữ liệu ra

In \(N\) dòng, mỗi dòng gồm \(N\) ký tự. Trên dòng \(i\), với mọi \(j\ne i\), ký tự thứ \(j\) phải là:

• \(1\) nếu chắc chắn thành viên thứ \(i\) thâm niên hơn thành viên thứ \(j\);
• \(0\) nếu chắc chắn thành viên thứ \(i\) ít thâm niên hơn thành viên thứ \(j\);
• \(?\) nếu không thể suy ra từ các công trình đã cho.

Ký tự thứ \(i\) trên dòng \(i\) phải là \(B\), vì đó là chữ cái Bessie yêu thích.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

1 3
dean elsie mildred
elsie mildred dean

B11
0B?
0?B

2 3
elsie mildred dean
elsie mildred dean
elsie dean mildred

B00
1B0
11B

Giải thích ví dụ 1. Bài báo duy nhất (elsie-mildred-dean) không cung cấp đủ thông tin để xác định Elsie hay Mildred thâm niên hơn. Tuy nhiên, có thể suy ra Dean phải thâm niên hơn cả hai, nên hai thứ tự thâm niên Elsie<Mildred<Dean và Mildred<Elsie<Dean đều có thể xảy ra.

Giải thích ví dụ 2. Thứ tự thâm niên duy nhất phù hợp với cả hai bài báo là Elsie<Mildred<Dean. Bài báo thứ hai bổ sung thông tin từ ví dụ thứ nhất và giúp suy ra Mildred cũng thâm niên hơn Elsie.

Nguồn

USACO 2021 US Open, Bronze - Acowdemia II: https://usaco.org/index.php?page=viewproblem2&cpid=1132

Tác giả: Dhruv Rohatgi.

Bessie là một nghiên cứu sinh khoa học máy tính bận rộn. Tuy nhiên, ngay cả nghiên cứu sinh cũng cần bạn bè. Vì vậy, Farmer John đã mở một đồng cỏ với mục đích giúp Bessie và những con bò khác xây dựng tình bạn bền chặt.

Có thể coi đồng cỏ của Farmer John là một lưới hai chiều rộng gồm các ô vuông, giống như một bàn cờ khổng lồ. Mỗi ô được ký hiệu bởi:

• C nếu ô đó có một con bò;
• G nếu ô đó có cỏ;
• . nếu ô đó không có bò lẫn cỏ.

Để hai con bò phân biệt trở thành bạn, chúng phải chọn gặp nhau tại một ô có cỏ kề trực tiếp theo chiều ngang hoặc dọc với cả hai con. Trong quá trình đó, chúng ăn cỏ trong ô này, do đó các cặp bò sau này không thể dùng lại ô này làm điểm gặp. Một con bò có thể kết bạn với nhiều con bò khác, nhưng mỗi cặp bò chỉ có thể gặp nhau và trở thành bạn nhiều nhất một lần.

Farmer John hy vọng sẽ có nhiều cặp bò gặp nhau và trở thành bạn theo thời gian. Hãy xác định số tình bạn mới lớn nhất giữa các cặp bò phân biệt có thể được tạo ra khi hoạt động này kết thúc.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(M\) (\(N,M\le1000\)).

Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(M\) ký tự, mô tả đồng cỏ.

Dữ liệu ra

In số cặp bò lớn nhất có thể trở thành bạn khi hoạt động kết thúc.

Phân nhóm

• Các test 2-4 thỏa mãn \(N=2\).
• Các test 5-12 không có ràng buộc bổ sung.

Ví dụ

4 5
.CGGC
.CGCG
CGCG.
.CC.C

4

Nếu gán cho con bò ở hàng \(i\), cột \(j\) tọa độ \((i,j)\), thì trong ví dụ có các con bò tại \((1,2)\), \((1,5)\), \((2,2)\), \((2,4)\), \((3,1)\), \((3,3)\), \((4,2)\), \((4,3)\) và \((4,5)\). Một cách để bốn cặp bò trở thành bạn là:

• Hai con bò tại \((2,2)\) và \((3,3)\) ăn cỏ tại \((3,2)\).
• Hai con bò tại \((2,2)\) và \((2,4)\) ăn cỏ tại \((2,3)\).
• Hai con bò tại \((2,4)\) và \((3,3)\) ăn cỏ tại \((3,4)\).
• Hai con bò tại \((2,4)\) và \((1,5)\) ăn cỏ tại \((2,5)\).

Nguồn

USACO 2021 US Open, Bronze - Acowdemia III: https://usaco.org/index.php?page=viewproblem2&cpid=1133

Tác giả: Benjamin Qi.