Thử thách vi mạch
Đề bài
Mô tả
Một công ty vi xử lý nổi tiếng nhờ bạn bố trí một số linh kiện có thể thay thế cho nhau (gọi là widget) trên một vài con chip của họ. Thiết kế của mỗi con chip là một bảng vuông khe cắm. Mỗi khe chứa được đúng một linh kiện, và bạn cần đặt được càng nhiều widget càng tốt.
Tất nhiên, thiết kế vi xử lý hiện đại rất phức tạp. Không may là bạn có một số ràng buộc:
- Một số khe bị vô hiệu hóa.
- Một số khe đã có sẵn linh kiện khác, không thể dùng để đặt widget.
- Các bus bộ nhớ song sinh được nối vào cạnh ngang và cạnh dọc của chip, và tải băng thông của chúng phải cân bằng. Vì vậy hàng thứ nhất phải có số linh kiện đúng bằng cột thứ nhất, hàng thứ hai phải có số linh kiện đúng bằng cột thứ hai, và cứ thế. Số linh kiện được đếm gồm cả các linh kiện có sẵn trên chip lẫn các widget được thêm vào.
- Tương tự, nguồn điện được nối vào cuối mỗi hàng và mỗi cột. Để tránh các điểm quá nhiệt, mỗi hàng và mỗi cột chứa không quá tổng số linh kiện trên chip, với và cho trước.
Đặc tả của một con chip gồm dòng, mỗi dòng ký tự, trong đó . là một khe trống, / là một khe bị vô hiệu hóa và C là một khe đã có sẵn linh kiện. Ví dụ:
grid C C / . . . / . / / . . C . C / . C . . / . / C /
Nếu mỗi hàng hoặc cột chứa không quá số linh kiện, số widget lớn nhất có thể thêm vào con chip này là . Một cách đặt như sau, trong đó W là widget được thêm vào một khe trống:
grid C C / W . W / W / / W . C . C / . C W W / W / C / highlight green 1,4 2,1 2,3 3,1 4,4 4,5 5,2
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên: kích thước chip , và hai số , như mô tả ở trên. Mỗi dòng trong dòng tiếp theo chứa ký tự mô tả các khe, mỗi ký tự là một trong ., / hoặc C như mô tả ở trên.
Sau bộ test cuối cùng là một dòng gồm ba số .
Dữ liệu ra
Với mỗi bộ test, in một dòng bắt đầu bằng số thứ tự của bộ test theo đúng định dạng Case i: của ví dụ. Nếu có lời giải, in số widget lớn nhất có thể thêm vào con chip. In impossible nếu không có lời giải.
Ràng buộc
- .
- , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 1 1 /. // 2 50 100 /. C/ 2 100 100 ./ C. 5 3 10 CC/.. ./.// ..C.C /.C.. /./C/ 5 2 10 CC/.. ./.// ..C.C /.C.. /./C/ 0 0 0 |
Case 1: 0 Case 2: 1 Case 3: impossible Case 4: 7 Case 5: impossible |
Bộ 1: đặt widget vào ô làm hàng 1 có 1 linh kiện còn cột 1 có 0, nên không đặt gì. Bộ 2: đặt widget vào ô , mỗi hàng và mỗi cột có đúng 1 trong 2 linh kiện. Bộ 3: cột 1 luôn nhiều hơn hàng 1 đúng một linh kiện (ô có sẵn, ô bị vô hiệu hóa). Bộ 4: cách đặt như hình trên. Bộ 5: cùng con chip với tỉ lệ , không có cách đặt nào thỏa mãn. |
| 3 1 2 ... ... ... 3 1 4 ... ... ... 2 1 2 C. .. 3 1 3 C// .C. /.. 2 1 2 C/ /. 0 0 0 |
Case 1: 9 Case 2: 0 Case 3: 3 Case 4: 1 Case 5: 1 |
Bộ 1: lấp đầy bảng, mỗi hàng và cột có linh kiện. Bộ 2: với luôn có một hàng chứa ít nhất tổng số, vượt nếu tổng dương, nên chỉ để trống cả bảng. Bộ 3: lấp đầy bảng, mỗi hàng và cột có linh kiện. Bộ 4: đặt widget vào ô , mỗi hàng và cột có đúng 1 trong 3 linh kiện. Bộ 5: một mình linh kiện có sẵn chiếm cả hàng 1, phải đặt thêm widget vào ô . |
Bình luận