why my code is getting wrong answer??And what is the problem in the code?plz explain clearlyyy ( beginer level APPY AND CONTEST problem)

general
, ,
1

#include<stdio.h>
int main()
{
int N,A,B,K;
int tc,i,j=1,count=0;
scanf("%d",&tc);
for(i=1;i<=tc;i++)
{

    scanf("%d%d%d%d",&N,&A,&B,&K);
    while(j<=N)
    {
        if((j%A==0)&&(j%B!=0))
        count++;
        if((j%A!=0)&&(j%B==0))
        count++;
        j=j+1;
    }
    //cout<<"\ncount= "<<count;
    if(count>=K)
    printf("Win");
    else printf("Lose");
    	printf("\n");
    	 //printf("\ncount is %d",count);
}

return 0;

}

2

pls check the output form of the question again. you should not print “count” and after this you will get TLA vedict, you need to change your approach for to get AC.

3

You are getting Wrong answer in subtask 1 and Time limit exceeded in subtask 2. Let’s take a look at each of these cases individually :slight_smile:

Subtask 1: (WA)

I have modified your code so that it passes subtask 1 -


[1].  
Compare it with your original code. You'll find that you initialised *j* and *count* only once, outside the tc loop. You need to initialise them everytime **inside** the tc loop. Doing this alone will make your code pass the first subtask.  

### Subtask 2: (TLE)  
Notice that for this subtask, *K* and *N* can be as high as $10^{18}$. In your code, j loop runs from 1 to N, and thus - from 1 to $10^{18}$, which is the reason for the **TLE**. Instead, you need to find a way such that it counts, without any loops, all numbers from 1 to N,

1) Which are divisible by A  **(x)**  
2) Divisible by B  **(y)**  
3) Divisible by both A and B  **(z)**  

Then the count will be **x+y-2z**;  

 - **x** is nothing but N/A
 - **y** is nothing but N/B
 - Now we need to find out **z**, which is, number of numbers from 1 to N divisible by both A and B. To find **z**, we need to find the **LCM** of A and B. We can find the LCM if we find out the GCD of A and B  (Remember LCM = (A*B)/GCD). You can read about finding the GCD [here][2]. Once we have the LCM, then **z** = N/LCM.

[Here][3] is my AC code for this problem. Feel free to ask if you have any more doubts.

Hope this helped :)


  [1]: https://www.codechef.com/viewsolution/23182821
  [2]: https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/
  [3]: https://www.codechef.com/viewsolution/22713434
2 Likes