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

Bài tập huấn luyện: Bốc sỏi

 

Từ ngàn xưa, khi thế gian chỉ là sỏi đá, các vị thần phải đào sông lấp biển để có một trái đất chỗ cao chỗ thấp, chỗ lồi chỗ lõm muôn màu muôn vẻ như ngày hôm nay. Do hồi đó chẳng có cái gì cả, xung quanh chỉ là sỏi đá, các vị thần đã phải nghĩ ra một trò chơi để giải trí. Trò chơi đó được miêu tả như sau.

Có N đống sỏi, mỗi đống có Ni viên. Ban đầu người ta cho một số K, và hai người lần lượt chơi. Khi đến lượt chơi, người đó chọn một đống sỏi (có số viên sỏi lớn hơn hoặc bằng K) và chia đống sỏi đó ra làm K phần (mỗi phần phải có ít nhất một viên), sau đó đóng sỏi lớn nhất và N – 1 đống sỏi khổng được chọn sẽ được giữ lại. Còn K – 1 đống sỏi khác sẽ bị bỏ đi. Trò chơi kết thúc khi có một người không thể chơi được nữa và đó chính là người thua cuộc. Một câu hỏi đặt ra, nếu bạn biết được trạng thái ban đầu của trò chơi liệu bạn có thể xác định được ai sẽ thắng không? Biết rằng các vị thần đó rất thông minh và các bước đi đều tối ưu, tức là nếu có thể thắng thì các vị thân luôn biết cách đi sao cho chắc chắn thắng.

InputSTONES.INP

  • Dòng đầu tiên ghi hai số nguyên dương K và T. Trong đó T là số bộ test còn K là số được lựa chọn chung cho cả T bộ test.
  • Tiếp theo là T bộ test, mỗi bộ test được miêu tả như sau:
    • Dòng đầu tiên là số N là số đống sỏi ban đầu.
    • N dòng tiếp theo, dòng thứ i ghi số Ni là số viên sỏi ở đống thứ i.

Output:            STONES.OUT

  • Ghi một xâu gồm T kí tự, kí tự thứ i bằng 1/0 tương ứng với vị thần thứ i có hoặc không có cách thắng.

Giới hạn:

  • 1 ≤ T ≤ 10.
  • 2 ≤ K ≤ 109.
  • 1 ≤ N ≤ 104.
  • K ≤ Ni ≤ 2 × 109. Trong 40% số test, Ni ≤ 1000
  • Thời gian: 1 s/test
  • Bộ nhớ: 8MB

Ví dụ:

STONES.INP STONES.OUT
3 2

3

807

343

897

5

946

115

693

310

172

01
Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lờ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ả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Geese Resort

Toulouse Sunset

Monolith

More Photos

Thống kê

  • 115,743 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: