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

Bài tập huấn luyện: Trò chơi nhặt đồng xu

 

Một bảng hình chữ nhật được chia thành 3 dòng và N cột. Trong một số ô của bảng có đặt một đồng xu có giá trị 1, còn các ô khác để trống. Người chơi được phép chọn 1 trong 3 ô bên trái nhất (1 trong 3 ô ở cột thứ nhất) để nhảy vào bảng theo ô đó. Sau đó, người chơi được phép di chuyển theo 4 hướng đến các ô chung cạnh với ô đang đứng. Người chơi không cho phép nhảy vào một ô 2 lần. Khi nhảy vào một ô nào đó, số tiền đã có của người chơi được nhân đôi. Nếu ô vừa nhảy vào có chứa xu, người chơi sẽ nhặt lấy đồng xu và số tiền sau khi nhân đôi sẽ được cộng thêm 1. Trò chơi kết thúc tại một ô nào đó trong 3 ô bên phải nhất (1 trong 3 ô ở cột N). Ban đầu số tiền của người chơi bằng 0.

Bạn hãy tìm một phương án di chuyển sao cho số tiền thu được là nhiều nhất và số các ô đi qua là ít nhất có thể. Nếu có nhiều phương án di chuyển thì chỉ cần đưa ra một trong các phương án đó.

InputCOIN.INP

  • Dòng đầu chứa số N là số cột của bảng.
  • 3 dòng tiếp theo, mỗi dòng chứa N số 0 hoặc 1 mô tả ô đó không có hoặc có đồng xu

Output:            COIN.OUT

  • Dòng đầu chứa chỉ số dòng mà người chơi nhảy vào bảng lúc bắt đầu.
  • Dòng tiếp theo chứa xâu mô tả đường đi người chơi. Xâu gồm các kí tự U, D, L, R thể hiện hướng đi của người chơi.

Giới hạn:

  • 1 ≤ N ≤ 80
  • Thời gian: 1 s/test
  • Bộ nhớ: 32MB

Ví dụ:

COIN.INP COIN.OUT
4

1 1 1 0

1 1 1 0

1 1 1 0

1

DDRUURDDRUU

(Với output trên số tiền thu được là 4088)

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: