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

Bài tập huấn luyện: Sơn cửa

Phú ông beo_chay_so vừa mới xây dựng xong toà biệt thự của mình. Việc trước tiên phú ông muốn làm là đi sơn các cánh cửa trong ngôi nhà của mình. Toà biệt thự được mô tả là một kiểu kiến trúc kỳ quái không tuân theo bất kỳ quy luật tự nhiên nào. Nó bao gồm N phòng và 1 hệ thống hành lang nối các phòng với nhau. Mỗi một căn phòng thay vì chỉ có 1 cửa thì lại có tới Ai cánh cửa. Mỗi cánh cửa dẫn ra một hành lang nối tới một phòng khác. Hiện thời thị trường đang khuyến loại sơn mua 1 tặng 1. Cụ thể là nếu bạn mua 1 hộp sơn màu trắng bạn sẽ được tặng 1 hộp sơn màu đen và ngược lại nếu bạn mua 1 hộp sơn màu đen, bạn sẽ được tặng 1 hộp sơn màu trắng. Phú ông vừa xây xong biệt thự nên cũng khá là túng tiền. Mà cơ bản tính khí cũng khá là keo kiệt, ông ta quyết định sơn các cánh cửa theo cách sau đây:

  • Nếu cánh cửa X của phòng Y dẫn ra hành lang thông với cánh cửa U của phòng V thì 2 cánh cửa này phải sơn 2 màu khác nhau.
  • Ngoài ra bên cạnh đó là yêu cầu về thẩm mỹ, trong mỗi phòng thì số lượng cánh cửa sơn màu trắng và số lượng cánh cửa sơn màu đen không được chênh lệch quá 1.
  • Bên cạnh đó ông ta muốn tổng chênh lệch giữa số lượng cánh cửa sơn màu trắng và số lượng cánh cửa sơn màu đen là nhỏ nhất có thể được vì như vậy đỡ tốn tiền mua sơn.

Bạn hãy giúp phú ông beo_chay_so giải quyết bài toán kinh tế này .

InputRPAINT.INP

  • Dòng thứ nhất ghi số N là số phòng trong tòa biệt thự.
  • Dòng thứ i trong N dòng tiếp theo ghi thông tin về các cánh cửa của phòng thứ i. Đầu tiên là số cửa Ai. Tiếp theo là Ai số nguyên cho biết phòng i có các cánh cửa dẫn đến phòng nào.

Output:            RPAINT.OUT

  • Dòng thứ nhất, nếu có phương án thỏa mãn ghi ra “YES”, nếu không có ghi ra “NO SOLUTION”.
  • Nếu dòng thứ nhất ghi “YES” thì tiếp theo là N dòng. Dòng i mô tả về cách sơn cửa của phòng thứ i gồm Ai kí tự ‘W’ / ’B’ tương ứng với việc cánh cửa được sơn trắng hoặc đen. Thứ tự ghi trong output tương ứng với thứ tự ghi trong input. Mỗi kí tự ‘W’ / ‘B’ trong output được ghi cách nhau đúng một dấu cách.

Giới hạn:

  • 1 ≤ N ≤ 10000
  • Tổng số hành lang ≤ 100000
  • Thời gian: 1 s/test
  • Bộ nhớ: 8MB

Ví dụ:

RPAINT.INP RPAINT.OUT
53 2 3 43 1 3 54 1 2 4 53 1 3 53 2 3 4 YESB W BW B WB W W BW B B

B W W

(Với cách sơn như thế này thì chênh lệch giữa 2 màu bằng 0)

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ả

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

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: