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

Bài tập huấn luyện: Cái cân dẫn đường

Bài 5:

Cho một đồ thị gồm N đỉnh và M đường đi 2 chiều. Tại đỉnh X có một quân cờ đang đứng tại đó. Một người chơi muốn di chuyển quân cờ về đỉnh Y. Mỗi bước anh ta có thể di chuyển quân cờ sang một đỉnh kề cạnh với cạnh đang đứng. Anh ta có một cái cân thăng bằng gồm 2 đĩa cân và K quả cân có khối lượng khác nhau đôi một. Ban đầu, hai bên đĩa cân không có quả cân nào. Để thực hiện mỗi nước đi, anh ta giữ nguyên vị trí các quả cân đã được đặt ở trên cân trước đó và đặt thêm một quả cân lên một trong hai đĩa cân. Nếu cân nghiêng về bên trái thì anh ta chỉ được phép di chuyển quân đến đỉnh có số hiệu nhỏ hơn đỉnh đó, nếu cân nghiêng về bên phải thì anh ta chỉ được phép di chuyển quân đến đỉnh có số hiệu lớn hơn đỉnh đó. Anh ta không được phép để cho cân thăng bằng

Bạn hãy giúp anh ta trình tự đặt các quả cân sao cho có thể di chuyển quân cờ về vị trí Y sớm nhất.

InputSCALES.INP

  • Dòng thứ nhất ghi 5 số nguyên N, M, K, X, Y.
  • Dòng thứ hai chứa K số nguyên thể hiện khối lượng của K quả cân.
  • Tiếp theo là M dòng, mỗi dòng ghi hai số U V thể hiện giữa đỉnh U và đỉnh V có đường đi 2 chiều.

Output:            SCALES.OUT

  • Dòng đầu tiên ghi số S là số bước di chuyển. Nếu không có cách đi thỏa mãn, ghi ra -1.
  • S dòng tiếp theo, mỗi dòng ghi 3 số U V P trong đó:
    • U là số hiệu đỉnh đang đứng.
    • V là số hiệu quả cân tiếp theo được đặt lên bàn cân.
    • P = 0 / 1 tương ứng với việc đặt lên bàn cân trái / bàn cân bên phải.
  • Dòng cuối cùng ghi duy nhất số Y.

Giới hạn:

  • 1 ≤ N ≤ 10000
  • 1 ≤ M ≤ 100000
  • 1 ≤ K ≤ 10000
  • Trọng lượng các quả cân ≤ 109
  • Thời gian 1s/test
  • Bộ nhớ : 16MB

Ví dụ:

SCALES.INP SCALES.OUT
5 4 5 1 4

1 2 3 4 5

1 2

2 3

3 5

5 4

4

1 3 1

2 2 0

3 1 1

5 4 0

4

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: