// 演算法 / Algorithm:
// dp[i] = 面對 i 顆石頭且輪到你時是否必勝 / whether the player to move with i stones wins.
// dp[0]=false（不能動就輸）。對每個 i，試每個平方數 k*k；若某個 dp[i-k*k] 為 false，
// 代表能把必敗態丟給對手，故 dp[i]=true。/ If any move hands the opponent a losing state, you win.

#include <stdbool.h>   // 讓 C 能使用 bool / true / false / enables bool, true, false
#include <stdlib.h>    // 提供 calloc / free / for calloc and free

bool winnerSquareGame(int n) {
    // 配置 n+1 個 bool，索引 0..n；calloc 會把每格初始化為 0（即 false）
    // Allocate n+1 bools, indices 0..n; calloc zero-initializes every cell to false.
    bool *dp = (bool *)calloc(n + 1, sizeof(bool));

    // dp[0] 已是 false，代表 0 顆石頭時輪到你就輸 / dp[0] stays false: 0 stones = you lose.
    for (int i = 1; i <= n; i++) {          // 由小到大填表 / fill states from small to large
        // 試每個非零平方數 k*k，只要不超過 i / try each square k*k that fits in i
        for (int k = 1; k * k <= i; k++) {  // k*k 是這一步要拿走的石頭數 / stones removed this move
            // 拿走 k*k 後，對手面對 dp[i - k*k]；若它是必敗態(false)，我方就贏
            // After removing k*k, opponent faces dp[i - k*k]; if that is losing, we win.
            if (!dp[i - k * k]) {           // '!' 是邏輯反：!false == true / '!' negates the bool
                dp[i] = true;               // 找到必勝走法，記為必勝態 / found a winning move
                break;                       // 一個就夠，跳出內層迴圈 / one is enough, stop looking
            }
        }
        // 若迴圈走完都沒 break，dp[i] 仍是 calloc 給的 false（必敗態）
        // If no break happened, dp[i] remains false: a losing state.
    }

    bool ans = dp[n];   // 答案就是 n 顆石頭時先手(Alice)是否必勝 / answer for the starting state
    free(dp);           // 釋放先前 calloc 的記憶體，避免記憶體洩漏 / release the allocated memory
    return ans;         // 回傳結果 / return the result
}