# Number Game

This is a companion discussion topic for the original entry at https://toph.co/p/number-game

why RTE? ``````#include<bits/stdc++.h>
using namespace std;
int dp;
int func(int n){
if(n==0)return 0;
if(dp[n]!=-1)return dp[n];
if(n==1)return 1;
if(n%2==0)return dp[n]=func(n/2)+1;
else return dp[n]=func(n*3+1)+1;
}
int main(void){
int n1, n2, t, game, Montu, Jhontu, Draw;
memset(dp, -1, sizeof(dp));
scanf("%d", &t);
for(int tc=0; tc<t; tc++){
Montu=0;
Jhontu=0;
Draw=0;
scanf("%d", &game);
for(int i=0;i<game;i++){
scanf("%d%d", &n1, &n2);
if(func(n1)<func(n2)){
Montu++;
}else if(func(n2)<func(n1)){
Jhontu++;
}else
Draw++;
}
printf("Game No %d: Montu %d, Jhontu %d, Draw %d\n", tc+1, Montu, Jhontu, Draw);
}
return 0;
}
``````

The reason for RTE here is probably the array index being out of range.
Suppose the limit of n1 and n2 is 10 in your code. So, if n1 is `10` and n2 is `9`, the process is,

``````10 > 5 > 16 > 8 > 4 > 2 > 1

9 > 28 > 14 > 7 > 22 > 11 > 34 > 17 > 52 > 26 > 13 > 40 > 20 > 10 > 5 > 16
> 8 > 4 > 2 > 1
``````

So, the point is, as you can see here, for n1 = 10 your function will try to access `dp` and for n2 = 9 your function will try to access `dp`, `dp`, `dp`, `dp` etc… and all of them are out of the maximum value range of n1 and n2.

So, taking an `array` with length `1000100` will not work. In fact, we do not know, taking which length will work perfectly for this problem.

I personally tried to implement your code and got plenty of RE and CLE.
Now tell me, if the following line of code does not work, then what can you do?

``````int dp; // which is 100x of your array.
// it took 401 MB of memory to run to finally offer me RE
// the memory limit is 512 MB
``````

I solved this problem using Brute force a long time ago.

1 Like

Yeah… I got this…!!!

Thanks for giving time,However, I should try with another procedure, the previous one does not work…

1 Like
``````#include <stdio.h>

int main()
{
int cases,rounds,montu,jhontu,count_m=0,count_j=0,count1=0,count2=0,count3=0,i=0;
scanf("%d",&cases);

while(cases--){

scanf("%d",&rounds);

while(rounds--){
scanf("%d %d",&montu,&jhontu);
while(1){
if((montu==1)||(jhontu==1)) break;

if(montu%2) montu=(montu*3)+1;
else montu/=2;

if(jhontu%2) jhontu=(jhontu*3)+1;
else jhontu/=2;
}
if(montu==jhontu) count3++;
else if(montu==1) count1++;
else count2++;
}
printf("Game No %d: Montu %d, Jhontu %d, Draw %d\n",i+1,count1,count2,count3);
i++;

count1=count2=count3=count_m=count_j=0;

}
return 0;
}
``````

``````#include <stdio.h>
long long int z;
long long int collatz(int n)
{
long long int steps = 0, a = n, flag = 0;
while (n > 1)
{
if (n < a && n > 1)
{
z[a] = steps + z[n];
flag = 1;
break;
}
else
{

if (n % 2 == 0)
{
n = (n / 2);
}
else
{
n = (3 * n) + 1;
}
steps++;
}
}
if (flag==0)
{
z[a] = steps;
}
}
int main()
{
long int n, t, i, j, k, montu = 0, jhontu = 0, draw = 0;
long long int in,x,y;
for (in = 1; in <= 1000001; in++)
{
collatz(in);
}
scanf("%ld", &t);
for (i = 1; i <= t; i++)
{
montu = 0, jhontu = 0, draw = 0;
scanf("%ld", &n);
for (j = 0; j < n; j++)
{
scanf("%lld %lld", &x, &y);
if (z[x] < z[y])
{
montu += 1;
}
else if (z[x] > z[y])
{
jhontu += 1;
}
else
{
draw += 1;
}
}
printf("Game No %ld: Montu %ld, Jhontu %ld, Draw %ld\n", i, montu, jhontu, draw);
}
}
``````

getting RTE. It runs well on my pc and on online compilers. How to solve?
And also, I can’t access the discussion from the question page. it’s showing “This content is blocked. Contact the site owner to fix the issue.”