VOI 21 Bài 5 - Rút gọn ma trận

Xem dạng PDF

Gửi bài giải


Điểm: 1,00 (OI)
Giới hạn thời gian: 1.5s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout

Người đăng:
Nguồn bài:
Kỳ thi Học sinh giỏi Quốc gia 2021 - Ngày 2
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Xét ma trận ~A~ gồm ~m~ hàng và ~n~ cột, các hàng được đánh chỉ số từ ~1~ đến ~m~ theo thứ tự từ trên xuống dưới, các cột được đánh chỉ số từ ~1~ đến ~n~ theo thứ tự từ trái sang phải. Kí hiệu ~A(i, j)~ là giá trị của phần tử nằm giao giữa hàng ~i~ và cột ~j~ ~(1 \le i \le m; 1 \le j \le n)~.

Có hai thao tác rút gọn ma trận theo hàng và cột.

  1. Thao tác rút gọn theo hàng: chọn hai hàng ~i~ và ~i + 1~ ~(1 \le i < m)~ mà tổng các phần tử trên hàng ~i~ bằng tổng các phần tử trên hàng ~i + 1~, việc rút gọn hàng ~i~ và ~i + 1~ theo các bước sau:

    • Bước 1: Thay đổi giá trị các phần tử trên hàng ~i~: ~A(i, j) = A(i ,j) + A(i + 1, j)~ với ~1 \le j \le n~;
    • Bước 2: Xóa hàng ~i + 1~ khỏi ma trận, khi đó số hàng của ma trận giảm đi một và các hàng được đánh chỉ số lại bắt đầu từ 1 từ trên xuống dưới.
  2. Thao tác rút gọn theo cột: chọn hai cột ~j~ và ~j + 1~ ~(1 \le j < n)~ mà tổng các phần tử trên cột ~j~ bằng tổng các phần tử trên cột ~j + 1~, việc rút gọn cột ~j~ vả ~j + 1~ theo các bước sau:

    • Bước 1: Thay đổi giá trị các phần tử trên cột ~j~: ~A(i, j) = A(i, j) + A(i, j + 1)~ với ~1 \le i \le m~;
    • Bước 2: Xóa cột ~j + 1~ khỏi ma trận, khi đó số cột của ma trận giảm đi một và các cột được đánh chỉ số lại bắt đầu từ 1 từ trái sang phải;

Yêu cầu: Cho ma trận ~A~, hãy tìm một dãy các thao tác rút gọn để nhận được ma trận có số lượng phần tử là ít nhất.

Dữ liệu

Vào từ đầu vào chuẩn (không phải từ file RMAT.INP):

  • Dòng đầu tiên chứa 2 số nguyên dương ~m~ và ~n~ là số hàng và số cột của ma trận;
  • Dòng thứ ~i~ ~(1 \le i \le m)~ trong số ~m~ dòng tiếp theo chứa ~n~ số nguyên, mỗi số có giá trị tuyệt đối không vượt quá ~10^6~, số thứ ~j (1 \le j \le n)~ là giá trị ~A(i, j)~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Kết quả

Ghi ra đầu ra chuẩn (không phải file RMAT.OUT) một số nguyên duy nhất là số lượng phần tử còn lại trong phương án thực hiện dãy các thao tác rút gọn tìm được.

Ràng buộc

  • Có ~30\%~ số test ứng với ~30\%~ số điểm của bài thỏa mãn: ~m = 1~ và ~n \le 10~;
  • ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thỏa mãn: ~m = 1~ và ~n \le 100~;
  • ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thỏa mãn: ~m \times n \le 500~;
  • ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thỏa mãn: ~m \times n \le 5000~;
  • ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thỏa mãn: ~m \times n \le 10^6~.

Ví dụ

Input
3 5
1 2 3 4 5
5 4 3 2 1
4 -1 -1 -1 2
Output
6
Giải thích

Dãy các thao tác rút gọn như sau:

  • Rút gọn hàng 1 và hàng 2 để nhận được ma trận:
6  6  6  6 6
4 -1 -1 -1 2
  • Rút gọn cột 2 và cột 3 để nhận được ma trận:
6 12  6 6
4 -2 -1 2
  • Rút gọn cột 1 và cột 2 để nhận được ma trận:
18  6 6 
 2 -1 2

Không thực hiện dược thêm thao tác rút gọn. Số lượng phần tử của ma trận thu được là ~6~.


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 4
    darkkcyan  đã bình luận lúc 28, Tháng 7, 2021, 9:00 chỉnh sửa

    Hiện tại bài này đã được điều chỉnh time limit lên 1.5s do 1 test mới được thêm vào làm các solution đúng cũ chạy quá 1s. Số người làm được bài này đã trở lại thành 13 người sumissions. Số lượng người AC là 9.


  • 6
    darkkcyan  đã bình luận lúc 28, Tháng 7, 2021, 8:31 chỉnh sửa

    Do bộ test vẫn yếu sau lần update đầu, một vài solution tham lam vẫn còn AC. Do chiến thuật sinh test chưa đủ khỏe, nên lượng số bằng nhau nằm cạnh nhau rất lớn, dẫn đến điều đáng tiếc này. Hiện tại mình vừa update bộ test và rejudge lại các solution. Điều đáng tiếc là giờ chỉ còn 1 nửa số solution AC (từ 14 xuống còn 7 submissions). Mình thành thật xin lỗi về sự cố này. :(

    Cảm ơn bạn Hau đã góp ý cho bộ test và đóng góp thêm 1 test vào bộ test cho bài này.

    Edit: số lượng submission giảm không phải là do cách làm tham lam, mà là do 1 test mới thêm vào làm các submissions TLE. Đây cũng là điều mình không ngờ tới, và cũng xin lỗi các bạn lần nữa về việc update lại bộ test.