Chương trình kiểm tra người chơi đầu tiên thắng trò chơi tạo xâu trong C++

Mô tả bài toán

Cho danh sách từ. Hai người chơi lần lượt thêm ký tự vào xâu sao cho xâu luôn là tiền tố của ít nhất một từ. Người viết thành một từ trong danh sách sẽ thua. Kiểm tra người chơi đầu có thắng không nếu cả hai chơi tối ưu.

Ví dụ: words = ["manage","manager","min"] → True (người 1 thắng).

Giải thuật

Nhóm các từ theo ký tự đầu. Nếu tồn tại nhóm mà từ ngắn nhất trong nhóm có độ dài chẵn → người chơi 1 thắng (vì người 2 sẽ bị ép viết hết từ đó). Cụ thể: với mỗi ký tự đầu, lấy từ ngắn nhất. Nếu độ dài chẵn → trả về true.

Ví dụ minh họa (C++)

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

bool solve(vector<string>& words) {
    map<char, set<string>> mp;
    for (auto& w : words) mp[w[0]].insert(w);
    for (auto& p : mp) {
        string shortest = *p.second.begin();
        if (shortest.size() % 2 == 0) return true;
    }
    return false;
}

int main() {
    vector<string> v = {"manage","manager","min"};
    cout << solve(v);
    return 0;
}

Đầu vào

{"manage","manager","min"}

Đầu ra

1