trang chủ / đề bài / icpc25_reg_m

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 384 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ẽ n ma trận, trong đó ma trận thứ i có ai hàng và bi cột. Mỗi phút, Ming chọn hai ma trận A và B có kích thước lần lượt là p×q và q×r, rồi thay chúng bằng tích A×B, là một ma trận kích thước p×r. Lưu ý rằng số cột của ma trận A phải bằng số hàng của ma trận B, 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 m là số phép nhân Ming đã thực hiện, và ci,di (1≤i≤n−m) là số hàng và số cột của ma trận thứ i sau tất cả các phép nhân, khi đó:

∑i=1naibi<∑i=1n−mcidi

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 τ (1≤τ≤10). Tiếp theo là mô tả các bộ dữ liệu:

  • Dòng đầu tiên chứa số nguyên n (2≤n≤1000), số ma trận ban đầu Ming có.
  • Trong n dòng tiếp theo, dòng thứ i chứa hai số nguyên ai và bi (1≤ai,bi≤106), lần lượt là số hàng và số cột của ma trận thứ i.

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 −1.
  • Ngược lại, in ra số nguyên m (1≤m<n). Sau đó in ra m dòng, dòng thứ j chứa ba số nguyên pj, qj và rj (1≤pj,qj,rj≤106), cho biết ở phép nhân thứ j, Ming nhân một ma trận kích thước pj×qj với một ma trận kích thước qj×rj để được một ma trận mới kích thước pj×rj.

Nếu có nhiều đáp án, bạn có thể in ra đáp án bất kỳ.

Ràng buộc

  • 1≤τ≤10.
  • 2≤n≤1000.
  • 1≤ai,bi≤106.

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à 36·69+18·36+67·18=4338; sau các phép nhân, ma trận duy nhất còn lại có kích thước 67·69=4623. Bộ thứ ba: tổng kích thước ban đầu là 2·106+106·1=3·106; 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 2·1=2.
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à 5+5=10; nhân ma trận 5×1 với ma trận 1×5 được ma trận 5×5 có kích thước 25.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0