PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: kryptonix171
Tester: Abhinav Sharma, Lavish Gupta
Editorialist: Devendra Singh
DIFFICULTY:
1305
PREREQUISITES:
None
PROBLEM:
Ashish gave you two positive integers N and K . You have a circular sequence 1, 2, 3, 4, 5.....N-1, N . That means the number after N is 1 .
In one operation you remove the kth element towards right starting from the position of the smallest element in sequence at that time. After N-1 operations, only one element remains in the sequence.
Tell the parity of the last element left in the sequence.
EXPLANATION:
There are three cases:
Case 1 K = 1: All numbers starting from 1 to N-1 will be deleted. N is the last remaining element. The parity of N is the answer is this case.
Case 2 K=2: All numbers starting from 2 to N will be deleted. 1 is the last remaining element. Answer in this case is ODD.
Case 3 K>=3 :All numbers from K to N will be deleted first. Now numbers from 1 to K-1 remain in the list. K^{th} number from 1 is 1. 1 will be deleted. Now numbers from 2 to K-1 are present. Now K^{th} number from 2 is 3.
Since the size of the list decreases by 1 after each iteration and number of numbers till the next odd number also decreases by 1. Therefore only odd numbers starting from 1 are deleted till there are no odd numbers left in the list. Hence only an even number must be left in the end. Answer for this case is EVEN.
TIME COMPLEXITY:
O(1) for each test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
#define int long long int
#define debug cout<<"K"
#define mod 1000000007
using namespace std;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t>0)
{
int n,k;
cin>>n>>k;
if((k==2)||(n%2==1&&k==1))
cout<<"ODD\n";
else
cout<<"EVEN\n";
t--;
}
return 0;
}
Editorialist's solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
ll n, k;
cin >> n >> k;
if (k == 1)
{
if (n % 2)
cout << "ODD\n";
else
cout << "EVEN\n";
}
else if (k == 2)
{
cout << "ODD\n";
}
else
{
cout << "EVEN\n";
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}