Krdytkyu

I am referring to this problem https://practice.geeksforgeeks.org/problems/cycle-race/0.

The Problem description:

Jack and Jelly are two friends. They want to go to a place by a cycle ( Assume that they live in same house). Distance between the place and their house is 'N' km. Rules of game are as follows:
- Initially Jelly will ride cycle.
- They will ride cycle one by one.
- When one is riding cycle other will sit on the carrier of cycle.

- In each ride they can ride cycle exactly 1, 2 or 4 km. One cannot ride more than remaining distance.

- One who reaches school riding cycle will win.
Both play optimally. You have to find who will win this game.

Input:
First line of input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of a single line containing an integer N.

Output:
Print the name of winner i.e 'JACK' or 'JELLY'.

I have written following code for this problem.
Bottom-up approach solution gives me time out.
The top-down approach gives me Segfault. Most probably due to recursion stack.
How can I improve my solution?
Please help me.
Thanks in advance.

Bottom Up (Timeout):

#include <iostream>

using namespace std;



bool arr[2][10000001];



int main() {

    int t, n;

    cin >> t;

    while(t--) {

        cin >> n;



        arr[0][1]=arr[0][2]=arr[0][4]=0;

        arr[1][1]=arr[1][2]=arr[1][4]=1;

        arr[0][3]=1;

        arr[1][3]=0;



        for(int i=5;i<=n;i++) {

            for(int player=0;player<2;player++) {

                if(arr[1-player][i-1]==player||

                   arr[1-player][i-2]==player||

                   arr[1-player][i-4]==player) {

                       arr[player][i] = player;

                   } else {

                       arr[player][i] = 1-player;

                   }

            }

        }



        if(!arr[0][n]) {

            cout << "JELLY" << endl;

        } else {

            cout << "JACK" << endl;

        }

    }

    return 0;

}

Top-down (Segfault, I think due to recursion):

#include <iostream>

using namespace std;



char arr[2][10000001];



bool solve(int n, bool player) {

    if(arr[player][n] != -1)

        return arr[player][n];

    if(solve(n-1,!player) == player ||

       solve(n-2,!player) == player ||

       solve(n-4,!player) == player) {

           arr[player][n] = player;

    } else {

        arr[player][n] = !player;

    }

    return arr[player][n];

}



int main() {

    int t, n;

    cin >> t;

    while(t--) {

        cin >> n;

        for(int i=0;i<2;i++) {

            for(int j=0;j<n+1;j++) {

                arr[i][j] = -1;

            }

        }



        arr[0][1]=arr[0][2]=arr[0][4]=0;

        arr[1][1]=arr[1][2]=arr[1][4]=1;

        arr[0][0]=arr[0][3]=1;

        arr[1][0]=arr[1][3]=0;



        solve(n, false);



        if(!arr[0][n]) {

            cout << "JELLY" << endl;

        } else {

            cout << "JACK" << endl;

        }

    }

    return 0;

}

I have found the answer myself. It is actually testing the game theory. If we see the pattern then only when n is a multiple of 3 then only whoever starts the game first will loose and in all other cases who starts the game will win. The working code is given below.

#include <iostream>

using namespace std;



int main() {

    int t, n;

    cin >> t;

    while(t--) {

        cin >> n;

        if( n%3 == 0) {

            cout << "JACK" << endl;

        } else {

            cout << "JELLY" << endl;

        }

    }

    return 0;

}