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

Bài tập huấn luyện: Đánh số đồ thị

Cho một đơn đồ thị vô hướng gồm K x N đỉnh, các đỉnh được chia thành K nhóm, mỗi nhóm có N đỉnh. Các nhóm đuợc đặt tên bằng các chữ cái in hoa ‘A’, ‘B’, ‘C’, … các đỉnh tương ứng thuộc các nhóm được đặt tên bằng các số từ 0 đến N – 1. Giả sử ChK là chữ cái ứng với nhóm thứ K, ta quy ước chữ cái tiếp sau ‘A’ là ‘B’, tiếp sau ‘B’ là ‘C’, … tiếp sau ChK là ‘A’ và ký hiệu chữ cái tiếp sau Ch là next(Ch). Đồ thị này có các tính chất sau:

  • Giữa các đỉnh thuộc cùng một nhóm không có cạnh nối.
  • Các đỉnh thuộc 2 nhóm bất kỳ có tên là Ch và next(Ch) có đúng N cạnh nối từ đỉnh thuộc nhóm Ch đến đỉnh thuộc nhóm next(Ch).

Bạn cần được yêu cầu đánh số các đỉnh của đồ thị sao cho:

  • Các đỉnh thuộc 1 nhóm được đánh các số là hoán vị của các số tự nhiên từ 0 đến N – 1.
  • Với 2 nhóm Ch và next(Ch) bất kỳ thì N số trên N cạnh nối các đỉnh thuộc chúng là khác nhau. Nếu đỉnh i thuộc nhóm Ch được đánh số là P kề với đỉnh j thuộc nhóm next(Ch) được đánh số là Q thì cạnh nối 2 đỉnh này được đánh số là (N + P – Q) mod N.

Biết rằng 2 cách đánh số các đỉnh của đồ thị được coi là khác nhau nếu trong 2 cách đánh số, tồn tại một đỉnh thuộc một nhóm nào đó được đánh số khác nhau. Bạn hãy tính số cách đánh số khác nhau.

InputGRNUM.INP

  • Dòng thứ nhất ghi 2 số nguyên dương K và N là số nhóm và số đỉnh thuộc 1 nhóm.
  • Mỗi dòng trong K x N dòng tiếp theo ghi 1 cạnh của đồ thị theo dạng Ch i j trong đó Ch là một ký tự, i và j là 2 số nguyên với ý nghĩ có cạnh nối từ đỉnh i của nhóm Ch đến đỉnh j của nhóm next(Ch).

Output:            GRNUM.OUT

  • Ghi ra duy nhất một số nguyên là số lượng cách đánh số khác nhau tìm được.

Giới hạn:

  • 1 ≤ K ≤ 5
  • 1 ≤ N ≤ 20
  • Số cách đánh số khác nhau luôn đảm bảo không quá 1000000
  • Thời gian: 1 s/test
  • Bộ nhớ: 1 MB

Ví dụ:

GRNUM.INP GRNUM.OUT
3 3A 0 0A 1 2A 2 1B 1 0B 1 2B 2 2C 0 2C 1 1C 1 2 54

About pascalteacher

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

Thảo luận

Chưa có phản hồi.

Gửi phản hồ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 Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Clouds and sky

Toss-up

Winter Sunrise

More Photos

Thống kê

  • 95,640 lượt xem

pascalteacher.nct@gmail.com


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

%d bloggers like this: