Can anyone tell me why do i get a wrong answer with this code.
hi all
can you please tell me for which test cases it failed . thanks in advance .
http://www.codechef.com/viewsolution/4087673
I still can’t figure where I was wrong, and I do appreciate your kind help
#include <cstdio>
// GCD: function to calculate the greatest common divisor
long long GreatestCommonDivisor(long long a, long long b) {
long long tmp;
while (b != 0) {
tmp = a % b;
a = b;
b = tmp;
}
return a;
}
int main() {
int testcases;
long long n, m, gcd;
long long odd_sum_cases;
long long total_cases;
scanf("%d", &testcases);
for (int i = 0; i < testcases; ++i) {
scanf("%lld%lld", &n, &m);
total_cases = n * m;
odd_sum_cases = (n + 1) / 2 * (m / 2) + (m + 1) / 2 * (n / 2);
gcd = GreatestCommonDivisor(total_cases, odd_sum_cases);
// printf("%lld %lld %lld %lld %lld\n", n, m, gcd, total_cases, odd_sum_cases);
printf("%lld/%lld\n", odd_sum_cases / gcd, total_cases / gcd);
}
return 0;
}
I used pen and paper, and the answer was clear within 5 minutes. but I got a tle because I was calculating the reduced fraction, but then 1/2 part clicked. The problem was awesome the combinatronics part was cool.
You can find my attempts at : Guess,abcdexter
You can find my ACeD solution at : AC solution,C++
Thanks
Hi, My solution got accepted for this, formula I used is (oddN * evenM)+(oddM * evenN)/ MN. In this editorial (evenN * oddN)/MN is used and its giving wrong answer.
Eg:
N =2 and M= 3
(evenN * oddN)/M*N will give 1/6 which is wrong. it should be 1/2.
I got the answer right & accepted, but I wish to optimize this solution
if (N & 1 && M & 1){
product = (unsigned long long int)N*M;
printf("%llu/%llu\n", (product - 1) >> 1, product);
}else{
printf("1/2\n");
}
The best time I get is 0.11
If we further process the answer then there can be 4 cases for m & n
- m & n are odd
- m is even, n is odd
- m is odd, n is even
- m & n are even
For the case 1,2 & 3 the answer is always 1/2.
Whereas for the case 4, the ans is (mn)/2 / mn
The code can be as
if(((m+n)&1)|| (!(m&1) && !(n&1)))
printf("1/2\n");
else
printf("%llu/%llu\n",(m*n)/2,m*n);
Can anybody explain this: O(log(N * M)), complexity for the computation of gcd .
Could someone please tell me why my solution is wrong. Uncommenting the currently commented out section and deleting the code between the //----------------- result in a accepted solution, but funny thing is that the code between the
//------------- dashes are equivalent to the currently commented out section.
Here is my solution, sincerely thankful if someone would be kind enough to point out my mistake:
#include "stdio.h"
unsigned long long gcd(unsigned long long a, unsigned long long b){
unsigned long long r;
while(b){
r=a%b;
a=b;
b=r;
}
return a;
}
int main(){
unsigned long long t, n, m;
scanf("%llu", &t);
for(unsigned long long e=0;e<t;e++){
scanf("%llu", &n);
scanf("%llu", &m);
//-----------------
if((n%2)&&(m%2)){
unsigned long long d=gcd((n*m)-1,2*n*m);
printf("%llu", ((n*m)-1)/d);
printf("/%llu\n", (2*n*m)/d);
} else {
printf("%llu",1);
printf("/%llu\n",2);
}
//-----------------
//unsigned long long nodd=(n/2)+(n%2);
//unsigned long long neven=(n/2);
//unsigned long long modd=(m/2)+(m%2);
//unsigned long long meven=(m/2);
//unsigned long long num=(nodd*meven)+(modd*neven);
//unsigned long long den=n*m;
//unsigned long long d=gcd(num, den);
//printf("%llu", num/d);
//printf("/%llu\n", den/d);
//}
}
http://www.codechef.com/viewsolution/4313343
I keep getting WA with this Any idea what mistake i am making??
Please provide the code so that it is readable.
Check my code
If you dont understand anything feel free to ask
http://www.codechef.com/viewsolution/3976338
Happy Coding
Please provide the code so that at-least we can read it.
Or please send the link…
Happy Coding
Maybe because you not using long long int for M and N you’re not getting correct answer.
Your Code: http://ideone.com/JWuav5.
My Code: http://ideone.com/x7AEbg.
Test case used
t=1
m = n = 999999999
Hint : your code doesn’t pass this test case (t=1 m=n=999999999). Correct answer for this is 499999999000000000/999999998000000001.
Your Code gives 499999998000000002/999999998000000001
Yeah…it was just because of not using long long int. Thanks
same solution when i am executing it is showing AC check this link CodeChef: Practical coding for everyone
you have used too many loops i think you will get TLE …try to use pen and paper … just a little thinking and boom you will get the answer or try to follow editorial note…