//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Cánh cửa vào Moria

Trên hành trình vô cùng nguy hiểm để phá hủy chiếc nhẫn của chúa quỉ Sauron, nhóm “Những người bạn” – dẫn đầu bởi Gandalf cần phải đi qua vùng mỏ Moria của người lùn. Nhưng để đi vào mỏ, họ phải tìm ra cánh cửa được phù phép bởi bùa chú – chỉ những ai có mật mã mới có thể vượt qua được. Họ đã tìm ra cánh cửa, nhưng mật mã thật hóc hiểm, đến nỗi Gandalf – một trong những phù thủy thông thái nhất, cũng không thể nào đoán ra được, ông cứ thử mãi, thử mãi…. Trong lúc chờ đợi, nhóm bạn nướng mực nhậu chơi cho đỡ buồn, không may cho họ mùi mực thơm lừng đánh thức bạch tuộc khổng lồ và nó vô cùng tức giận vì bà con của mình bị tàn sát (Bạn có thấy bạch tuộc với mực giống nhau không?). Nó hung dữ tấn công nhóm bạn. Tình hình nguy cấp quá rồi, bạn hãy giúp nhóm bạn tìm ra mật mã đó nào.

Biết rằng mật mã hợp lệ là 1 bảng NxN số, mỗi dòng là 1 hoán vị của N số từ 1 đến N , mỗi cột cũng là 1 hoán vị của N số như vậy (có nghĩa là mỗi dòng, mỗi cột chứa đủ tất cả các số 1..N, không số nào lặp lại 2 lần).

Bảng đã cho bao gồm M dòng đầu tiên được điền sẵn N–2 số, những dòng còn lại hoàn toàn trống. Bạn cần điền vào những ô trống còn lại để nhận được một mật mã hợp lệ. Với một bảng cho trước có thể có nhiều mật mã hợp lệ, bạn có thể đưa ra bất kì mật mã nào trong số đó.

InputMORIA.INP

Gồm một số bộ mật mã cần tìm, mỗi bộ mật mã bao gồm:

  • Dòng thứ nhất ghi 2 số nguyên N và M là kích thước của bảng và số dòng đã điễn sẵn.
  • N dòng tiếp theo, mỗi dòng ghi N số nguyên mô tả bảng: Số 0 có nghĩa là ô trống, các số từ 1 đến N là các số đã được điền.

Input luôn đảm bảo đúng đắn và có lời giải.

Output:            MORIA.OUT

Với mỗi Input , in ra N dòng mô tả mật mã tìm được. Mỗi lời giải cách nhau bởi 1 dòng trống.

Giới hạn:

  • 2 ≤ N ≤ 30 ; 0 ≤ M ≤ 15
  • Thời gian: 2 s/test
  • Bộ nhớ: 4 MB

Ví dụ:

MORIA.INP MORIA.OUT
3 0

0 0 0

0 0 0

0 0 0

5 2

1 2 0 4 0

2 0 1 0 4

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

1 2 3

2 3 1

3 1 2

1 2 5 4 3

2 3 1 5 4

3 1 4 2 5

4 5 3 1 2

5 4 2 3 1

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 150,179 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: