Giải bài ntucoder ALBO - Alice và Bob

Link bài:

Thuật toán:

• Trường hợp k = 1, người chiến thắng sẽ được xác định đơn giản:
  
  • Nếu n lẻ, Alice sẽ là người thắng. Bằng không, Bob sẽ thắng.
• Trường hợp k > n, Alice sẽ thắng sau một lượt chơi.
  
• Trường hợp n = k, Alice sẽ thắng sau một lượt chơi. Tổng quát với trường hợp (2x+1) *k Alice sẽ thắng.
  
• Trường hợp n = 2k, Alice chỉ cần chọn k-1 và Bob có chọn thế nào thì Alice vẫn sẽ thắng.
  
• Trường hợp n = k+1, Alice có chọn thế nào thì Bob cũng sẽ là người thắng cuộc. Tổng quát với trường hợp (2x+1) *k +1, (x là số tự nhiên). Bob sẽ là người thắng cuộc.
  
  • Duy chỉ cần n = k+2 trở lên, nếu Alice chọn n-k-1, Alice sẽ có cửa thắng. Tổng quát với trường hợp (2x+1) *k+y (Với y < k) Alice sẽ là người thắng cuộc.
• Trường hợp n = 2*k+1, Alice sẽ lập tức chọn k ở lượt đầu tiên, và sau đó Bob có chọn thế nào thì Alice cũng sẽ thắng cuộc. Tổng quát với trường hợp 2x+2k+1. Alice sẽ là người thắng cuộc.
  
  • Tương tự như trên, với trường hợp 2x+2k+y (với y < k). Bob sẽ là người thắng cuộc.

Code:

Mã:

#include <bits/stdc++.h>
using namespace std;

int n, k;

int main(){
    //freopen("albo.inp", "r", stdin);
    //freopen("albo.out", "w", stdout);
    cin >> n >> k;
    if (k == 1){
        if ( n % 2 == 0) cout << "Bob will win"; else cout << "Alice will win";
    }else if (n%k == 0) cout << "Alice will win";
    else if (n <= k) cout << "Alice will win";
        else if (n%k == 1){
            if ((n-1)% (2*k) != 0) cout << "Bob will win";
            else cout << "Alice will win";
        }else if (n%k > 1){
            if ((n-(n%k))% (2*k) != 0) cout << "Alice will win";
            else cout << "Bob will win";
        }

    return 0;
}