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

Bài tập huấn luyện: Trò chơi với những con chuột

 

Ở một phiên chợ dành cho thiếu nhi có một trò chơi rất hấp dẫn với những con chuột trong một cái bàn. Nhiệm vụ của người chơi là phải làm bị thương những con chuột, càng nhiều càng tốt với một chiếc búa. Để làm cho trò chơi dễ dàng hơn, các bạn nhỏ đã hỏi bụt để biết được vị trí cũng như thời gian chính xác mà mỗi con chuột xuất hiện.

Coi mặt phẳng của mặt bàn là một hệ tọa độ Đề-các, mỗi con chuột sẽ xuất hiện từ một lỗ thủng trên mặt bàn với tọa độ nguyên (x,y) thỏa mãn 0 ≤ x, y ≤ N. Trong mỗi thời điểm, một vài con chuột sẽ xuất hiện ở những lỗ thủng khác nhau và sau đó lại chui xuống vào trước thời điểm tiếp theo. Ngay sau khi các con chuột xuất hiện và ngay trước lúc chúng biến mất, người chơi có thể di chuyển chiếc búa trên một đoạn thẳng có chiều dài tối đa là D. Để đơn giản, tọa độ của chiếc búa trước và sau khi di chuyển luôn là nguyên và coi kích thước của chiếc búa không đáng kể. Một con chuột sẽ bị thương nếu tâm của lỗ mà con chuột xuất hiện nằm trên đoạn thẳng chiếc búa di chuyển. Khi bắt đầu trò chơi, ngay trước thời điểm đầu tiên mà những con chuột xuất hiện, người chơi có thể đặt búa ở bất cứ vị trí nào.

Hãy giúp các em thiếu nhi làm bị thương nhiều chuột nhất có thể, để các em được những phần quà của ban tổ chức. Và tất nhiên ai giúp đỡ các em thiếu nhi nhiều nhất cũng sẽ có phần thưởng là điểm số trong tuần thi này.

InputGMOUSE.INP

  • Dòng đầu ghi 3 số N, D, M trong đó M là số con chuột.
  • M dòng tiếp theo mỗi dòng ghi 3 số lần lượt là tọa độ và thời điểm mà mỗi con chuột xuất hiện.

Output:            GMOUSE.OUT

  • Xuất ra một số duy nhất là số chuột lớn nhất có thể làm bị thương.

Giới hạn:

  • 1 ≤ N ≤ 20
  • 1 ≤ D ≤ 5
  • 1 ≤ M ≤ 1000
  • Thời điểm mà mỗi con chuột xuất hiện là số tự nhiên không lớn hơn 10.
  • Bộ nhớ: 2M
  • Thời gian giới hạn: 1s/test

Ví dụ:

GMOUSE.INP GMOUSE.OUT
5 4 3

0 0 1

1 2 1

2 4 1

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: