JOI 2011 Representative Selection - Ngày 1

Vào năm 20XX, cuối cùng kỳ thi IOI cũng được tổ chức tại đất nước JOI. Để chào mừng sự kiện này, người dân quyết định treo các băng rôn chào đón khắp các con phố. Như hình dưới đây, đất nước JOI có \(H\) con đường chạy theo hướng đông–tây và \(W\) con đường chạy theo hướng bắc–nam, tạo thành một lưới ô vuông. Nơi một con đường đông–tây giao với một con đường bắc–nam được gọi là giao lộ. Giao lộ thứ \(a\) tính từ phía bắc và thứ \(b\) tính từ phía tây được ký hiệu là \((a,b)\).

Tại mỗi giao lộ có một cây cột. Đất nước JOI có ba màu biểu tượng là đen, xám và trắng; mỗi cây cột được sơn bằng một trong ba màu này.
Hình minh họa đất nước JOI khi \(H=3\), \(W=4\). Phía trên hình là hướng bắc, phía bên trái là hướng tây.

Có thể dùng các cây cột này để treo băng rôn. Tuy nhiên, băng rôn sẽ gây cản trở nếu đi qua những nơi không phải là đường. Vì vậy, người dân chọn bốn cây cột khác nhau tại bốn đỉnh của một hình chữ nhật có mỗi cạnh song song với một con đường, rồi treo băng rôn quanh hình chữ nhật đó. Ngoài ra, trong bốn cây cột được chọn phải có ít nhất một cột đen, một cột xám và một cột trắng.

Yêu cầu

Cho \(H\), \(W\) và màu của các cây cột, hãy tính số cách chọn bốn cây cột thỏa mãn các điều kiện trên.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(H,W\), cách nhau bởi dấu cách.
• \(H\) dòng tiếp theo mô tả màu của các cây cột. Dòng thứ \(i+1\) (\(1\le i\le H\)) chứa \(W\) số nguyên, mỗi số là \(0\), \(1\) hoặc \(2\), cách nhau bởi dấu cách. Số thứ \(j\) cho biết màu của cột tại giao lộ \((i,j)\): \(0\) là đen, \(1\) là xám, \(2\) là trắng.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số cách chọn bốn cây cột.

Ràng buộc

• \(2\le H\le400\): số con đường chạy theo hướng đông–tây.
• \(2\le W\le400\): số con đường chạy theo hướng bắc–nam.
• Giới hạn thời gian CPU: \(1{,}5\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

• Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
• Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
• Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
• Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm.

• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(H\le100\) và \(W\le100\).

Ví dụ

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

12

Những con rồng đã xông vào địa điểm thi IOI. Phòng thi có dạng hình chữ nhật, được chia thành \(H\) hàng và \(W\) cột ô vuông. Các hàng được đánh số từ \(1\) đến \(H\), các cột được đánh số từ \(1\) đến \(W\); ô ở hàng \(x\), cột \(y\) được ký hiệu là \((x,y)\). Có \(N\) con rồng; con rồng thứ \(i\) ở ô \((X_i,Y_i)\). Không có hai con rồng nào cùng ở một ô.

Một con rồng có thể phun lửa tấn công các ô cùng hàng hoặc cùng cột với nó. Thí sinh chỉ được đứng trong những ô không có rồng, mỗi ô nhiều nhất một người, và không được đứng trong ô có nguy cơ bị rồng tấn công.

Để tăng số thí sinh có thể tham dự nhiều nhất có thể, chủ tịch M của JOI quyết định mang theo một thiết bị chống lửa và đứng tại một ô không có rồng. Ngay cả khi một thí sinh và một con rồng ở cùng hàng hoặc cùng cột, nếu chủ tịch M đứng giữa họ thì lửa sẽ bị chặn lại, nên thí sinh đó không bị con rồng ấy tấn công. Tuy nhiên, chủ tịch M biết đáp án của tất cả các bài thi, nên không thí sinh nào được đứng cùng ô với ông.

Yêu cầu

Cho kích thước phòng thi và vị trí các con rồng, hãy tìm số thí sinh lớn nhất có thể có mặt trong phòng khi chủ tịch M chọn vị trí tối ưu.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa ba số nguyên \(H,W,N\), cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo mô tả vị trí các con rồng. Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa hai số nguyên \(X_i,Y_i\), cách nhau bởi dấu cách, là vị trí con rồng thứ \(i\).

Không có hai con rồng nào ở cùng một ô. Có ít nhất một ô không có rồng.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số thí sinh lớn nhất có thể có mặt trong phòng thi.

Ràng buộc

• \(1\le H\le1\,000\,000\,000\): số hàng của phòng thi.
• \(1\le W\le1\,000\,000\,000\): số cột của phòng thi.
• \(1\le N\le100\,000\): số con rồng.
• \(1\le X_i\le H\) và \(1\le Y_i\le W\) với mọi \(1\le i\le N\).
• Giới hạn thời gian CPU: \(10\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

• Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
• Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
• Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
• Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các tỉ lệ dưới đây mô tả những tập dữ liệu có thể giao nhau:

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(H\le1000\) và \(W\le1000\).
• Các bộ dữ liệu chiếm \(40\%\) tổng số điểm thỏa mãn \(N\le1000\).
• Các bộ dữ liệu chiếm \(20\%\) tổng số điểm thỏa mãn đồng thời \(H\le1000\), \(W\le1000\) và \(N\le1000\).
• Các bộ dữ liệu chiếm \(50\%\) tổng số điểm thỏa mãn ít nhất một trong hai điều kiện: (\(H\le1000\) và \(W\le1000\)), hoặc \(N\le1000\).

Ví dụ

4 6 3
2 4
3 5
2 3

9

Joitter là một mạng xã hội đang rất được quan tâm, giúp mọi người giao tiếp với người quen trên Internet thuận tiện hơn thông qua việc dễ dàng đăng những bài nhật ký ngắn và chia sẻ ảnh.

Trên Joitter, một người dùng có thể thêm những người dùng khác vào danh sách “bạn bè”. Khi người dùng \(A\) muốn thêm người dùng \(B\) làm bạn, \(B\) sẽ nhận được thông báo. Nếu \(B\) đồng ý, hai người được thêm vào danh sách bạn bè của nhau. Việc này được tính là một lần kết bạn. Vì một lý do nào đó, mỗi lần kết bạn có một chi phí phụ thuộc vào hai người dùng. Việc \(A\) và \(B\) là bạn, đồng thời \(B\) và \(C\) là bạn, không nhất thiết có nghĩa là \(A\) và \(C\) là bạn.

Mỗi người dùng có thể chọn một trong ba chế độ công khai nhật ký sau:

1. Chỉ cho phép bạn bè đọc.
2. Chỉ cho phép bạn bè hoặc bạn của bạn bè đọc.
3. Chỉ cho phép những người dùng có thể đi đến được bằng cách lần theo các quan hệ bạn bè đọc.

Có \(N\) người vừa đăng ký Joitter, mỗi người chọn một trong ba chế độ trên. Tình cờ, không có chế độ nào được đúng một người chọn: với mỗi người dùng, luôn có ít nhất một người khác chọn cùng chế độ với họ.

Yêu cầu

Ban đầu, chưa có quan hệ bạn bè nào giữa \(N\) người này. Hãy tìm số lần kết bạn ít nhất để mỗi người trong số họ đều đọc được nhật ký của tất cả những người còn lại. Trong các cách thực hiện dùng đúng số lần kết bạn ít nhất đó, hãy tìm tổng chi phí nhỏ nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), là số người dùng. Các người dùng được đánh số từ \(1\) đến \(N\).
• \(N\) dòng tiếp theo mô tả chế độ công khai nhật ký của từng người. Dòng thứ \(1+i\) (\(1\le i\le N\)) chứa một số nguyên \(1\), \(2\) hoặc \(3\), tương ứng với chế độ (1), (2) hoặc (3) của người dùng \(i\). Bảo đảm mỗi người dùng có ít nhất một người khác chọn cùng chế độ.
• \(N\) dòng tiếp theo mô tả chi phí kết bạn. Dòng thứ \(1+N+i\) (\(1\le i\le N\)) chứa \(N\) số nguyên cách nhau bởi dấu cách. Số thứ \(j\) (\(1\le j\le N\)), ký hiệu \(C_{ij}\), là chi phí để người dùng \(i\) và \(j\) kết bạn. Với mọi \(i,j\), ta có \(C_{ii}=0\) và \(C_{ij}=C_{ji}\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa hai số nguyên cách nhau bởi dấu cách: số lần kết bạn nhỏ nhất để mọi người đều đọc được nhật ký của tất cả những người còn lại, và tổng chi phí nhỏ nhất để đạt được điều đó với đúng số lần kết bạn ấy.

Ràng buộc

• \(2\le N\le1000\).
• \(1\le C_{ij}\le1000\) với \(i\ne j\).
• \(C_{ii}=0\) và \(C_{ij}=C_{ji}\) với mọi \(1\le i,j\le N\).
• Giới hạn thời gian CPU: \(1\) giây. Giới hạn bộ nhớ: \(64\) MB.

Thông tin kỹ thuật

Theo tài liệu kỹ thuật của kỳ thi gốc:

• Chương trình phải kết thúc bình thường với mã trả về \(0\). Chỉ được tính điểm khi chương trình cho kết quả đúng, kết thúc bình thường và tuân thủ giới hạn thời gian, bộ nhớ.
• Nếu không có quy định khác, giới hạn ngăn xếp là \(8\) MB. Cần chú ý tránh tràn ngăn xếp khi dùng đệ quy.
• Một số bài có thể cần xử lý số nguyên vượt quá phạm vi \(32\) bit; khi đó, trong C/C++ cần dùng kiểu số nguyên \(64\) bit như long long, với định dạng %lld khi dùng scanf hoặc printf.
• Với lượng dữ liệu vào/ra lớn, tài liệu khuyến nghị dùng scanf/printf thay cho cin/cout do tốc độ vào/ra trên hệ thống thi gốc.

Phân nhóm

• Bài có tổng cộng \(100\) điểm, gồm \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm.

Ví dụ

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

15 62

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

4 20

3
3
3
3
0 8 7
8 0 9
7 9 0

2 15