Nhân ma trận
Đề bài
Mô tả
Ming từng là một người chơi game nhịp điệu. Sau khi nhận ra thứ hạng thế giới của mình chủ yếu là nhờ "cày" các bản nhạc bị chấm điểm quá cao, và thực ra anh chơi rất tệ (đồng thời cũng trượt IOI vì mải chơi), Ming quyết định quay lại với lập trình thi đấu, nơi anh đỡ tệ hơn. Tuy nhiên, vì xa rời quá lâu, giờ anh phải học lại hầu hết mọi thứ từ đầu!
Hôm nay, Ming luyện tập phép nhân ma trận. Để hỗ trợ việc học, anh tự vẽ ma trận, trong đó ma trận thứ có hàng và cột. Mỗi phút, Ming chọn hai ma trận và có kích thước lần lượt là và , rồi thay chúng bằng tích , là một ma trận kích thước . Lưu ý rằng số cột của ma trận phải bằng số hàng của ma trận , nếu không Ming không thể thực hiện phép nhân. Anh có thể dừng lại bất cứ lúc nào, hoặc khi không còn cặp ma trận nào thỏa mãn để chọn.
Chẳng có gì bất ngờ, buổi "học" nhanh chóng trở nên nhàm chán. Ngay khi định kết thúc, Ming nhận ra một tính chất hiếm gặp: sau một số phép nhân của anh, tổng kích thước của tất cả các ma trận tăng thực sự so với lúc ban đầu! Một cách hình thức, gọi là số phép nhân Ming đã thực hiện, và () là số hàng và số cột của ma trận thứ sau tất cả các phép nhân, khi đó:
Ming rất tự hào về phát hiện ngẫu nhiên của mình và thách bạn tìm một dãy phép nhân bất kỳ đạt được tính chất trên. Tất nhiên, vì Ming mới học lại phép nhân ma trận gần đây, có thể anh đã nhầm và thực ra không tồn tại dãy phép nhân nào như vậy, khi đó bạn cũng cần thông báo cho anh.
Dữ liệu vào
Mỗi file dữ liệu gồm nhiều bộ dữ liệu. Dòng đầu tiên chứa số bộ dữ liệu (). Tiếp theo là mô tả các bộ dữ liệu:
- Dòng đầu tiên chứa số nguyên (), số ma trận ban đầu Ming có.
- Trong dòng tiếp theo, dòng thứ chứa hai số nguyên và (), lần lượt là số hàng và số cột của ma trận thứ .
Dữ liệu ra
Với mỗi bộ dữ liệu:
- Nếu không tồn tại dãy phép nhân nào làm tăng tổng kích thước các ma trận, in ra .
- Ngược lại, in ra số nguyên (). Sau đó in ra dòng, dòng thứ chứa ba số nguyên , và (), cho biết ở phép nhân thứ , Ming nhân một ma trận kích thước với một ma trận kích thước để được một ma trận mới kích thước .
Nếu có nhiều đáp án, bạn có thể in ra đáp án bất kỳ.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 4 1 4 1 5 2 5 3 6 3 36 69 18 36 67 18 2 2 1000000 1000000 1 |
-1 2 18 36 69 67 18 69 -1 |
Bộ thứ nhất: không có phép nhân hợp lệ nào với các ma trận ban đầu. Bộ thứ hai: tổng kích thước trước mọi phép nhân là ; sau các phép nhân, ma trận duy nhất còn lại có kích thước . Bộ thứ ba: tổng kích thước ban đầu là ; phép nhân hợp lệ duy nhất là nhân ma trận thứ nhất với ma trận thứ hai, được ma trận kích thước . |
| 1 2 5 1 1 5 |
1 5 1 5 |
Ví dụ bổ sung (không có trong đề gốc). Tổng kích thước ban đầu là ; nhân ma trận với ma trận được ma trận có kích thước . |
Bình luận