PROBLEM LINK:Author: Lalit Kundu DIFFICULTY:Simple PREREQUISITES:ad hoc, simple combinatorics. PROBLEM:You are selecting two numbers x and y such that 1 <= x <= N and 1 <= y <= M. How many (x, y) pairs satisfy the condition that x + y is odd. QUICK EXPLANATION
EXPLANATIONNotice the following simple facts.
Fact number 1 is very easy to prove. Let us prove fact 2, first part. Base Case: Induction Hypothesis: Now Let us assume that formula is true up to N such that N is odd, then we need to prove the formula for N + 1. Notice that N + 1 will be even. Hence number of even numbers increase by 1, hence they will be equal to floor(N / 2) + 1. As we know if N is odd, then floor(N / 2) + 1 = floor((N + 1)/ 2). Hence we are done for this case too. Note that instead of proving it formally, you can just see the above observation by observing the pattern for small numbers. Proof of second part of fact 2 (Number of odd numbers from 1 to N are ceiling(N / 2).) will also go exactly along the same lines. So finally our answer will be (floor(N / 2) * ceiling(N / 2)) / (N * M). We need to print this fraction in its irreducible form, so we have to divide both the numerator and denominator by their gcd.
Complexity Things to Take Care
AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 16 Jun '14, 15:01

If we further process the answer then there can be 4 cases for m & n
For the case 1,2 & 3 the answer is always 1/2.
answered 20 Jun '14, 08:23

Can anyone tell me why do i get a wrong answer with this code. answered 16 Jun '14, 16:35
Check my code If you dont understand anything feel free to ask http://www.codechef.com/viewsolution/3976338 Happy Coding
(16 Jun '14, 16:58)
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
(16 Jun '14, 23:49)
Yeah..it was just because of not using long long int. Thanks :)
(17 Jun '14, 10:23)

hi all can you please tell me for which test cases it failed . thanks in advance . http://www.codechef.com/viewsolution/4087673 answered 17 Jun '14, 01:22

I still can't figure where I was wrong, and I do appreciate your kind help :)
answered 17 Jun '14, 05:26
same solution when i am executing it is showing AC check this link http://www.codechef.com/viewsolution/4109240
(17 Jun '14, 15:50)

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 ^_^ answered 17 Jun '14, 14:37

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. answered 17 Jun '14, 18:45

I got the answer right & accepted, but I wish to optimize this solution
The best time I get is 0.11 answered 19 Jun '14, 00:10

Can anybody explain this: O(log(N * M)), complexity for the computation of gcd . answered 21 Jun '14, 11:06

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:
}
} answered 10 Jul '14, 03:20

http://www.codechef.com/viewsolution/4313343 I keep getting WA with this :( Any idea what mistake i am making?? answered 13 Jul '14, 02:42

I am getting WA...whats wrong with my code...pls reply me.... answered 08 Aug '14, 12:36

Why did I get a WA with this code.. Plz reply (ignore the #incl.. ) using namespace std;typedef unsigned long long ull;ull den;ull num;inline ull hcf(ull x,ull y){if(y==0)return x; else return hcf(y,x%y);}int main(){unsigned int tCases;long long int n,m;scanf("%d",&tCases); while(tCases){scanf("%lld lld",&n,&m);if(n%2==0)printf("1/2\n");else{if(m%2==0)printf("1/2\n");else{den=nm;n/=2;m/=2;num=(2n*m) + m n;if(num==0) printf("0/1\n");else{ull h=hcf(den,num);num/=h;den/=h;printf("%lld/%lld\n",num,den);}}}}return 0;} answered 16 Jun '14, 15:53

how could You say answer will be (floor(N / 2) * ceiling(N / 2)) / (N * M) ??? for n=10 and m=10 answer is 1/4 while correct answer is 1/2.