PVHOI 2.2 bài 6: Biến đổi bảng chữ số (60 điểm)

Xem dạng PDF

Gửi bài giải

Điểm: 1,70 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal

Cho một bảng gồm ~m~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~m~ theo thứ tự từ trên xuống dưới và các cột được đánh số từ ~1~ đến ~n~ theo thứ tự từ trái qua phải. Ô ở hàng ~i~ và cột ~j~ được kí hiệu là ~(i, j)~. Trên mỗi ô của bảng có ghi một chữ số từ ~0~ đến ~9~.

Một đường đi hợp lệ trên bảng này là một đường đi xuất phát từ ô góc trái trên và kết thúc ở ô góc phải dưới, đồng thời mỗi bước đi chỉ đi xuống ô ngay phía dưới hoặc ngay bên phải. Nói cách khác, một đường đi hợp lệ là một dãy các ô thỏa mãn:

  • Ô đầu tiên là ~(1, 1)~.
  • Ô cuối cùng là ~(m, n)~.
  • Kế tiếp sau ô ~(i, j)~ là ô ~(i, j + 1)~ hoặc ô ~(i + 1, j)~.

Xét bảng số dưới đây với ~m = 3~ hàng và ~n = 4~ cột:

~1~ ~2~ ~3~ ~4~

~5~ ~6~ ~7~ ~8~

~9~ ~0~ ~3~ ~6~

Ta tiến hành liệt kê mọi đường đi hợp lệ trên bảng này. Với mỗi đường đi, ta lần lượt viết các chữ số ở các ô đi qua để tạo thành một con số. Khi đó, ta sẽ được các số sau: ~123486~, ~123786~, ~123736~, ~126786~, ~126736~, ~126036~, ~156786~, ~156736~, ~156036~ và ~159036~.

Một bảng chữ số được gọi là hoàn toàn chia hết cho ~p~ khi và chỉ khi tất cả các con số tạo được từ mọi đường đi hợp lệ đều chia hết cho ~p~. Ví dụ, bảng số dưới đây

~3~ ~4~ ~5~

~7~ ~2~ ~6~

hoàn toàn chia hết cho ~3~ vì mọi số tạo thành từ mọi đường đi hợp lệ đều chia hết cho ~3~.

Cho một bảng chữ số, bạn được biến đổi bảng chữ số thông qua thao tác sau: Ở mỗi lần biến đổi, bạn chọn ra một ô ~(i, j)~ trên bảng và thay đổi chữ số tại ô này theo một trong những cách sau:

  • Nếu hiện tại ô đang chứa chữ số ~d > 0~, bạn được đổi sang chữ số ~d - 1~.
  • Nếu hiện tại ô đang chứa chữ số ~d < 9~, bạn được đổi sang chữ số ~d + 1~.
  • Nếu hiện tại ô đang chứa chữ số ~0~, bạn được đổi sang chữ số ~9~.
  • Nếu hiện tại ô đang chứa chữ số ~9~, bạn được đổi sang chữ số ~0~.

Hãy tìm cách biến đổi bảng với số lần ít nhất có thể để được một bảng hoàn toàn chia hết cho ~p~.

Input

Dòng đầu tiên chứa ba số nguyên ~m~, ~n~ và ~p~ ~(1 \leq m, n \leq 2000, 1 \leq p \leq 50)~.

Trong ~m~ dòng còn lại, mỗi dòng chứa ~n~ chữ số (từ ~0~ đến ~9~) mô tả bảng số.

Output

Dòng đầu tiên in ra số lần biến đổi bảng nhỏ nhất cần thực hiện để có được một bảng hoàn toàn chia hết cho ~p~.

Trong ~m~ dòng còn lại, mỗi dòng in ra ~n~ chữ số thể hiện bảng số sau khi biến đổi.

Nếu có nhiều cách biến đổi tối ưu, bạn được phép in ra một cách bất kì.

Sắp tát

Bộ test của bài được chia làm các sắp tát như sau:

  • Sắp tát ~1~ (~6~ điểm): ~m = 1~
  • Sắp tát ~2~ (~12~ điểm): ~m = 2~ và ~p \leq 9~
  • Sắp tát ~3~ (~9~ điểm): ~p = 3~
  • Sắp tát ~4~ (~12~ điểm): ~p~ là một lũy thừa của ~2~.
  • Sắp tát ~5~ (~21~ điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~60~ điểm.

Với mỗi test, bạn được ~50\%~ số điểm nếu tìm ra được số lần biến đổi nhỏ nhất nhưng không tìm ra được bảng số sau khi biến đổi.

Ví dụ

Input 1

4 4 3
2207
1997
0101
2003

Output 1

6
2106 
1996 
0000 
3003

Input 2

3 3 2
846
202
648

Output 2

0
846 
202 
648

Bình luận

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


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