PROBLEM LINK:
Author: Shivam Thakur
Tester: Rajnish
Editorialists: Akshit Dhoundiyal, Akshita Saxena
DIFFICULTY:
Easy
PREREQUISITE:
Logical reasoning, Basic mathematics
PROBLEM:
Given 2 integers n_1, n_2. Find the number of ways in which we can choose odd/even combinations from them.
EXPLANATION:
Once we have the inputs n_1, n_2, k, p, we begin with determining the number of even numbered faces on Rick’s and Morty’s dice.
n_1/2 gives the number of even faces on Rick’s dice. Let’s name it x. Similarly, let y be the number of even faces on Morty’s dice given by n_2/2.
Using the conditions given in the question, we can formulate four cases:
Case 1: p=1 and k is even ( Number of ways for Morty to win an even round)
For Morty to win this round, he should get an even number on his dice. Getting such a number is possible in y ways. Rick has to lose this round in x ways by getting an even number.
So total possible cases are x*y.
Case 2: p=1 and k is odd ( Number of ways for Morty to win an odd round)
For Morty to win this round, he should get an odd number on his dice. Getting such a number is possible in y or (y+1) ways depending upon n_2. If n_2 is odd then there are y+1 ways else y ways. So we check n_2 (if odd we increment y by 1). Rick has to lose this round by getting an odd number.
Similarly for Rick, getting an odd number is possible in x or (x+1) ways depending upon n_1. If n_1 is odd then there are x+1 ways else x ways. So we check n_1 (if odd we increment x by 1).
So total possible ways actually becomes x*y.
Case 3: p=0 and k is even ( Number of ways for Rick to win an even round)
For Rick to win this round, he should get an odd number on his dice. Getting such a number is possible in x or (x+1) ways depending upon n_1. If n_1 is odd then there are x+1 ways else x ways. So we check n_1 (if odd we increment x by 1). Morty has to lose this round by getting an odd number. Similarly for Morty, getting an odd number is possible in y or (y+1) ways depending upon n_2. If n_2 is odd then there are y+1 ways else y ways. So we check n_2 (if odd we increment y by 1).
So total possible ways actually becomes x*y.
Case 4: p=0 and k is odd ( Number of ways for Rick to win an odd round)
For Rick to win this round, he should get an even number on his dice. Getting such a number is possible in x ways. Morty has to lose this round in y ways by getting an even number.
So total possible cases are x*y.
Solution:
Setter’s Solution:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n1,n2,k,p;
cin>>n1>>n2>>k>>p;
long long x=n1/2;
long long y=n2/2;
if(p)
{
if(k%2==0)
{
cout<<(x*y)%1000000007<<endl;
}
else
{
if(n1%2==1)
{
x++;
}
if(n2%2==1)
{
y++;
}
cout<<(x*y)%1000000007<<endl;
}
}
else
{
if(k%2==0)
{
if(n1%2==1)
{
x++;
}
if(n2%2==1)
{
y++;
}
cout<<(x*y)%1000000007<<endl;
}
else
{
cout<<(x*y)%1000000007<<endl;
}
}
}
return 0;
}
Editorialist’s Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define sz(s) (ll)s.size()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fora(i,a,b) for(int i = a; i < b; ++i)
#define forr(i, a, b) for(int i = a; i >= b; --i)
#define pll pair<ll, ll>
#define all(a) a.begin(),a.end()
#define allr(a) a.rbegin(),a.rend()
#define rep(i,a) for(auto &i : a)
#define in insert
#define ff first
#define ss second
const long double pi = 2 * acos(0.0);
const int mod = 1e9 + 7;
const int maxn = 1e5;
void solve(){
ll n1, n2, k, p;
cin >> n1 >> n2 >> k >> p;
ll ans = 0;
if(p){
if(k % 2){
ans = ((n1 + 1) / 2) * ((n2 + 1) / 2) % mod;
}
else{
ans = (n1 / 2) * (n2 / 2) % mod;
}
}
else{
if(k % 2 == 0){
ans = ((n1 + 1) / 2) * ((n2 + 1) / 2) % mod;
}
else{
ans = (n1 / 2) * (n2 / 2) % mod;
}
}
cout << ans << '\n';
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while (t--){
solve();
}
return 0;
}
Feel free to share your approach. Suggestions are welcome!