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

Bài tập huấn luyện: Tham quan công viên

Công viên DISNEYLAND là một công viên hiện đại mới được xây dựng ở ngoại ô Hà Nội để dành riêng cho trẻ em. Công viên này có N điểm vui chơi được đánh số từ 1 đến N. Các điểm vui chơi được nối liền với nhau bằng các đoạn đường hai chiều theo hướng Bắc – Nam, hoặc Đông – Tây. Các điểm vui chơi nằm ở giao của hai con đường. Khoảng cách giữa hai điểm vui chơi liên tiếp cách đều nhau.

Bé Bi được bố mẹ cho phép đến công viên chơi trong một ngày. Vì công viên quá rộng lớn và hấp dẫn nên bé Bi muốn lựa chọn một con đường đi qua một số điểm vui chơi sao cho không có điểm vui chơi nào đi qua 2 lần. Vì bố mẹ sợ bé Bi bị lạc, nên bố mẹ chỉ cho phép bé đi trên đoạn đường gồm không quá K ngã rẽ (không được đổi hướng quá K lần). Biết rằng độ dài đoạn đường nối hai điểm kề nhau có giá trị là 1. Bạn hãy giúp bố mẹ bé tính xem, đoạn đường dài nhất thỏa mãn điều kiện đó có độ dài là bao nhiêu, và có bao nhiêu đoạn đường thỏa mãn điều kiện đó. Lưu ý rằng công viên rất hiện đại nên có cả hệ thống cầu vượt và hầm chui. Chính vì vậy sẽ có những trường hợp như test ví dụ thứ hai dưới đây (các đỉnh ở cùng tọa độ nhưng hoàn toàn phân biệt với nhau).

InputDISNEY.INP

  • Dòng thứ nhất ghi 2 số nguyên dương N và K là số điểm vui chơi và số ngã rẽ nhiều nhất.
  • Dòng thứ i trong N dòng tiếp theo ghi 4 số nguyên mô tả thông tin về điểm vui chơi thứ i. Bốn số nguyên là L, D, R, U là điểm vui chơi nằm bên trái, dưới, phải, trên điểm vui chơi thứ i. (Nếu có số bằng 0 tương ứng với phía đó không có điểm vui chơi nào).

Output:            DISNEY.OUT

  • Gồm 2 số nguyên S và P trong đó S là độ dài đường đi dài nhất và P là số đường đi có độ dài là S.

Giới hạn:

  • 0 ≤ K < N ≤ 10000
  • Thời gian: 0.5 s/test
  • Bộ nhớ: 1MB

Ví dụ:

DISNEY.INP DISNEY.OUT  
12 4

0 2 3 4

0 0 0 1

1 0 0 0

5 1 0 0

6 0 4 0

0 7 5 0

8 0 9 6

10 11 7 12

7 0 0 0

0 0 8 0

0 0 0 8

0 8 0 0

7 4 luyentap39
5 2

0 0 2 0

1 3 0 0

4 0 0 2

0 0 3 5

0 4 0 0

3 2

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: