Thuật toán lập trình: tìm người chiến thắng trong cuộc thi

Question

Tôi sẽ cạnh tranh trong OBI (Olympic tin học Brazil, bằng tiếng Anh) và tôi đang thử một vài bài tập từ những năm qua. Nhưng tôi không thể tìm thấy một giải pháp cho bài tập này (tôi dịch nó, vì vậy có thể có một vài sai sót):

Sôcôla thi

Carlos và Paula chỉ có một túi bóng sô cô la. Vì họ sẽ ăn mọi thứ quá nhanh, họ đã thực hiện một cuộc thi:

• Họ sẽ ăn luân phiên, cái khác (Paula luôn bắt đầu).
• Mỗi lần, họ chỉ có thể ăn từ 1 đến M quả bóng, M do mẹ của Paula quyết định, vì vậy họ không bị nghẹt thở.
• Nếu một người ăn K lần lượt, người tiếp theo không thể ăn quả K.
• Bất kỳ ai không thể chơi theo các quy tắc trên đều bị mất.

Trong ví dụ dưới đây với M = 5 và 20 quả bóng, Carlos đã giành được:

Who plays  How many ate  Balls left 

            20 
Paula   5     15 
Carlos   4     11 
Paula   3     8 
Carlos   4     4 
Paula   2     2 
Carlos   1     1 

Lưu ý rằng cuối cùng, Carlos không thể ăn 2 quả bóng để giành chiến thắng, bởi vì Paula ăn 2 trong lượt cuối cùng của cô. Nhưng Paula không thể ăn quả bóng cuối cùng, bởi vì Carlos ăn 1 ở lượt cuối cùng của mình, vì vậy Paula không thể chơi và thua.

Cả hai đều rất thông minh và chơi tối ưu. Nếu có một chuỗi lượt để đảm bảo anh ta/cô ấy chiến thắng độc lập với lượt của người khác, anh ta/cô ấy sẽ chơi các trình tự này.

Nhiệm vụ:

Nhiệm vụ của bạn là tìm ra ai sẽ thắng cuộc thi nếu cả hai đều chơi tối ưu.

Nhập:

Đầu vào chỉ chứa một nhóm thử nghiệm, được đọc từ đầu vào chuẩn (thường là bàn phím).

Đầu vào có 2 số nguyên N (2 ≤ N ≤ 1000000) và M (2 ≤ M ≤ 1000), là N số quả bóng và M số được phép cho mỗi lượt.

Đầu ra:

Chương trình của bạn nên in, ở đầu ra tiêu chuẩn, một dòng chứa tên của người chiến thắng.

Ví dụ:

Input:   Output: 
5 3    Paula 
20 5   Carlos 
5 6    Paula 

Tôi đã cố gắng để giải quyết vấn đề, nhưng tôi không có ý tưởng như thế nào.

Có thể tìm thấy giải pháp trong C tại đây: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/solucoes/chocolate.c.txt Nhưng tôi không thể hiểu thuật toán. Ai đó đã đăng câu hỏi về vấn đề này ở một trang web khác, nhưng không ai trả lời.

Bạn có thể giải thích cho tôi thuật toán không?

Sau đây là các kết quả đầu ra dự kiến ​​của chương trình: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/gabaritos/chocolate.zip

Answer 1

Giả sử chúng ta có hàm boolean FirstPlayerWin (FPW) lấy hai đối số: số sôcôla còn lại (c) và di chuyển cuối cùng (l) tức là số lượng sô cô la được lấy ở vòng trước, là 0 ở bước đi đầu tiên. Thường lệ trả về đúng nếu và chỉ khi người chơi đầu tiên chơi ở tình huống này được đảm bảo thắng.

Trường hợp cơ sở là FPW (0, l) = false cho bất kỳ l! = 1

Nếu không, để tính toán FPW (c, l), FPW (c, l) là đúng nếu cho bất kỳ x < = M, x < = c, x! = L, FPW (c - x, x) là sai. Nếu không thì nó là sai. Đây là nơi lập trình động, bởi vì bây giờ tính toán của FPW được giảm xuống để tính toán FPW cho các giá trị nhỏ hơn của c.

Tuy nhiên, việc lưu trữ các mục nhập cho công thức này sẽ yêu cầu mục nhập bảng N * M, khi giải pháp bạn chỉ sử dụng chỉ sử dụng các mục nhập bảng 2N.

Lý do cho điều này là nếu FPW (c, 0) là đúng (người chơi đầu tiên thắng nếu có bất kỳ chuyển động nào tính sô cô la c) nhưng FPW (c, x) là sai cho x> 0, FPW (c , y) cho và y! = x phải đúng. Điều này là do nếu từ chối di chuyển x làm cho người chơi bị mất, tức là người chơi sẽ chỉ thắng bằng cách chơi x, thì di chuyển x có sẵn khi y bị cấm thay thế. Do đó, nó đủ để lưu trữ cho bất kỳ số đếm 'c' nào nhiều nhất là một hành động bị cấm làm cho người chơi bị mất ở đó. Vì vậy, bạn có thể cấu trúc lại vấn đề lập trình động để thay vì lưu trữ mảng 2 chiều FPW (c, x) bạn có hai mảng, một cửa hàng lưu trữ các giá trị FPW (c, 0) và cửa sổ kia cấm các hành động bị cấm người chơi đầu tiên thua thay vì thắng, nếu có.

Cách bạn truy cập văn bản chính xác của chương trình C được trích dẫn còn lại dưới dạng bài tập cho người đọc.

Answer 2

Tôi nghĩ rằng đây lại là một tập thể dục mỏng trá hình trong lập trình năng động. Trạng thái của trò chơi được mô tả bằng hai đại lượng: số lượng quả bóng còn lại và số quả bóng được ăn trong lần di chuyển trước đó. Khi số lượng quả bóng còn lại là < = M, trò chơi hoặc là thắng (nếu số còn lại không bằng số được ăn trong lần di chuyển trước) hoặc bị mất (nếu có - bạn không thể ăn tất cả các quả bóng, và đối thủ của bạn có thể ăn những quả bóng mà bạn để lại).

Nếu bạn đã tính toán tình huống thắng/thua cho tất cả các số bóng lên đến H và tất cả số bóng có thể được người chơi trước đó ăn và viết xuống bảng, thì bạn có thể tìm ra câu trả lời cho tất cả số lượng bóng lên đến H + 1. Một cầu thủ có bóng H + 1 và quả k được ăn trước đó sẽ xem xét tất cả các khả năng - ăn quả bóng cho i = 1 đến M ngoại trừ giá trị bất hợp pháp của k, để lại vị trí với bóng H + 1-i và trước đó di chuyển của i. Họ có thể sử dụng bảng cho tình huống thắng-thua cho đến H quả bóng còn lại để thử và tìm một k hợp pháp mang lại cho họ một chiến thắng. Nếu họ có thể tìm thấy một giá trị như vậy, vị trí H + 1/k là một chiến thắng. Nếu không, nó là một mất mát, vì vậy họ có thể mở rộng bảng để che đậy lên đến H + 1 quả bóng, và như vậy.

Tôi chưa từng làm việc với tất cả mã ví dụ chưa được hiển thị, nhưng có vẻ như nó có thể làm một cái gì đó như thế này - sử dụng một chương trình động như đệ quy để xây dựng một bảng.