Fun Game Problem

Blue_Manh · July 13, 2020, 2:31pm

Mọi người có thể hướng dẫn em bài này được không ạ, em cảm ơn ạ !

Vũ “Maripium” Hoàng Kiên là một bác sĩ phẫu thuật nổi tiếng và giàu có, thế nhưng đường tình duyên của anh lại rất trắc trở. Sau khi lập đàn cầu may, anh đã được crush chủ động tiếp chuyện! Crush thách anh chơi một trò chơi, nếu như anh thắng thì hai người sẽ đi ăn với nhau. Trò chơi đó như sau:

Cho n chồng chocolate, mỗi chồng có a[i] viên chocolate. Hai người lần lượt ăn các viên chocolate. Mỗi lần ăn chỉ được ăn ở duy nhất 1 chồng chocolate, và phải ăn ít nhất 1 viên, nhiều nhất a[i] viên. Không được ăn ở chồng đã hết chocolate ( a[i] = 0 ). Trò chơi kết thúc khi tất cả các chồng đều hết chocolate, khi đó đến lượt ai thì người đó thua. Bác sĩ đi trước.

Cho dãy a[1], a[2], ..., a[n] , hãy cho bác sĩ biết mình có được đi ăn với crush hay không.

Link gốc đây ạ:

SITUVN.gcd · July 13, 2020, 4:08pm

Để Kiên thắng thì đến lượt Crush, các chồng còn lại là [1, 1]. Nghĩ được mỗi thế.

Sherly1001 · July 13, 2020, 6:34pm

Thực ra thì bác sĩ có được đi chơi hay không là tùy vào tâm trạng của crush nha.

Nhưng mình là người tốt bụng nên sẽ cố gắng đẩy thuyền cho cặp đôi này. :V
Và mình làm kiểu ngu người như này, lười tạo acc codelearn để test nên hông biết đúng hay sai.

Ý tưởng thì là tham lam th.

Nếu chỉ có toàn 1 => xét số chồng chocolate, lẻ chồng thì bác sĩ thắng.
Lấy tham lam theo kiểu nếu lẻ chồng thì lấy nguyên một chồng.
Nếu chẵn chồng thì lấy sao cho còn chừa lại một viên chocolate.
Lấy cho đến khi các chồng kẹo chỉ còn một viên.
Do lấy ở chồng nào không quan trọng nên mình sẽ sort để đưa hết những chồng một viên về đầu mảng luôn.

def sher(a):
    n = len(a)
    a.sort()

    def test():
        if 1 == n: return 'yes'
        if 1 == a[n - 1]:
            if n % 2 == 0: return 'no'
            else: return 'yes'
        return None
    def take():
        nonlocal n
        if n % 2 == 0 and a[n - 1] > 1:
            a.pop()
            a.insert(0, 1)
        else:
            a.pop()
            n -= 1

    while True:
        uh_huh = test()
        if uh_huh: return uh_huh
        take()
        take()

a = [5, 7]
print(sher(a)) # no

HR16 · July 13, 2020, 7:24pm

Chạy được cái đã, performance tính sau .

Blue_Manh · July 14, 2020, 3:34am

Cám ơn mọi người mình tìm được tài liệu rồi ạ
https://diendantoanhoc.net/topic/153451-cách-thắng-trò-chơi-nim/

nitro2 · July 14, 2020, 6:13am

Bài toán này giống như 1 trò chơi dân gian của Việt Nam, chia sỏi ra thành nhiều cụm có số lượng ngẫu nhiên. Cách chơi tương tự. Ai bốc cuối không còn thì thua.
Ngày tết mình thường dùng hạt dưa để chơi.
Do não bé, nên bình thường mình sẽ đưa trò chơi về 2 dạng để mình chắc chắn thắng:

Dạng 1: Còn lại 2 chồng bằng nhau. Ví dụ 5 - 5
Nếu đối thủ bốc 1 viên thì mình bốc tương ứng 1 viên ở chồng còn lại (4-4). Nếu đối thủ bốc hết thì mình bốc hết theo.
Dạng 2: Còn lại 3 chồng có số lượng lần lượt 1-2-3
Dù đối thủ bốc thể nào thì cũng đưa về bài toán 2 chồng bằng nhau ở dạng 1.