23

//Algo: Create a Binary Tree using inOrder and postOrder

void PreOrder(node *tRoot) {
	if (tRoot == NULL) return;
	cout << tRoot->info << " ";
	PreOrder(tRoot->left);
	PreOrder(tRoot->right);
}
// Call :
	pIndex = n-1;
	node *root = makeTree(inOrder, postOrder, 0, n-1);

// Algo: Spargue Grundy Number - 1D

int grundy[mx];
int rev[] = {1, 4, 27, 256, 3125, 46656};
int Cal(int x) {
    if (x == 0)
        return 0;
    int &ret = grundy[x];
    if (ret != -1)
        return ret;
    set <int> s;
    for (int f=0; f<6; f++) {
        if (x-rev[f] >= 0)
            s.insert(Cal(x - rev[f]));
    }
    int cnt = 0;
    while (s.find(cnt) != s.end())
        cnt++;
    return ret = cnt;
}

// Algo: Spargue Grundy Number - 2D
int dr[] = {-1, -2, -2, +1};
int dc[] = {-2, -1, +1, -2};
int validMove(int r, int c) {
    return r>=1 && r<=8 && c>=1 && c<=8;
}
int grundyNumber[mx+5][mx+5];
int Call(int r, int c) {
    if (!validMove(r, c))     // যদি কোন ঘরে যাওয়া না যায়
        return 0;             // তাহলে লুজিং পসিশন, মানে ০
    int &ret = grundyNumber[r][c];
    if (ret != -1)
        return ret;
    set <int> s;
    for (int f=0; f<4; f++) {
        int x = r + dr[f];    // বর্তমান ঘর থেকে যেসব ঘরে যাওয়া যায়
        int y = c + dc[f];
        if (validMove(x, y))  // যদি অন্য কোন ঘরে যাওয়া যায়
            s.insert(Call(x, y));
    }
    int cnt = 0;
    while (s.find(cnt) != s.end())
        cnt++;                 // মিনিমাম নাম্বার যেটি সেটে নাই
    return ret = cnt;
}