FINDPR - Editorial

[Practice ] Find The Pair | CodeChef
Setter: virtual_worm
Tester: rounak_rocco
Editorialist: codechef_ciem

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

Two positive integers X and Y are given. Find the number of pairs of positive integers (P,Q) such that 1≤P≤X,1≤Q≤Y for every P+Q is even.

QUICK EXPLANATION:

  • When is the sum of two numbers even? The answer is when either both of the numbers are even or both of them are odd.
  • Thus, count the number of even-even pairs and odd-odd pairs and add them to get the answer.

TIME COMPLEXITY:

O(1) for each testcase.

SOLUTION(C++)

#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin >> t;
while (t–)
{
int p, q;
cin >> p >> q;
long even_p = p / 2;
long even_q = q / 2;
long odd_p = (p + 1) / 2;
long odd_q = (q + 1) / 2;
long ans = even_p * even_q + odd_p * odd_q;
cout << ans << endl;
}
return 0;
}