Jhontu and Montu are brothers. They tend to skip study and play. So to keep them busy, a senior stud…
Click here to read the complete problem statement.
If you need help solving this problem, mention your approach and ask specific questions. Please avoid sharing your code and asking the Community to figure out “what’s wrong”.
why RTE?
#include<bits/stdc++.h>
using namespace std;
int dp[1000100];
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[16] and for n2 = 9 your function will try to access dp[52], dp[40], dp[34], dp[28] 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[100010000]; // 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.
To, see my submissions using your code, click here.
Yeah… I got this…!!!
Thanks for giving time,However, I should try with another procedure, the previous one does not work…
#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;
}
I’m getting CPU LIMIT EXCEEDED, please help!
#include <stdio.h>
long long int z[1000001];
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.”
def calclute(a, b):
if a == b:
return "d"
if a == 1:
return "m"
if b == 1:
return "j"
if a % 2 == 0:
subA = a // 2
else:
subA = (a * 3) + 1
if b % 2 == 0:
subB = b // 2
else:
subB = (b * 3) + 1
return calclute(subA, subB)
n = int(input())
res = []
for i in range(n):
montu = jontu = draw = 0
m = int(input())
for j in range(m):
a, b = map(int, input().split())
x = calclute(a, b)
if x == "m":
montu += 1
elif x == "j":
jontu += 1
else:
draw += 1
res.append(
"Game No %d: Montu %d, Jhontu %d, Draw %d" % ((i + 1), montu, jontu, draw)
)
for r in res:
print(r)
CPU limit exceeded on test 2
could you please tell me? how do I make it more efficient? I need your help.