We have two players who have values JS and TS. We keep dividing them by 2. If at any point one is even and the other is odd, the player corresponding to the even value wins. If both are even, we continue dividing by 2. If both are odd, it’s a tie.
Given player 2’s value, TS \leq 10^{18} find number of JS \leq TS for player 1, such that player 1 wins.
QUICK EXPLANATION:
Let i be the greatest integer such that 2^i | TS. ANS = \left \lfloor{\frac{x}{2^{i+1}}}\right \rfloor
EXPLANATION:
Subtask 1
For each testcase, iterate over all JS \leq TS and simulate the process.
Subtask 2
Observation 1
Any number x can be written as x = 2^{k}*y where 2^k is the highest power of 2 dividing x.
Implication?
y must be odd
Observation 2
if 2^k is the highest power of 2 that divides TS then 2^{k+1} must be the minimum power of 2 that divides JS, else player 2 won’t win.
Just to be clear ...
It does not imply that if JS = 2^{k+1}*y then y is odd. y can be a multiple of 2 as well.
Full Solution
Find 2^k such that k is the highest power of 2 which divides TS. Divide TS by 2^{k+1} and take the floor. Let that be z. z is the number of possible values of JS.
Relating to the above expressions, we can say that JS = 2^{k+1}*y, and the value of y can be 1,2,3 \dots z such that 2^{k+1}*(z+1) > TS. This is the precise z that we are getting, hence the answer is z. (Since all values from 1 \dots z are possible, hence there are exactly z values.)
Time Complexity
Since we have to find the maximum 2^i, our time complexity is O(log(TS)) per test case.
QUICK REMINDERS:
long long int is good for your health.
SOLUTIONS:
Setter's Code
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define db long double
#define pb push_back
#define all(a) a.begin(), a.end()
#define mod 1000000007
#define out cout<<
#define in cin>>
#define w(param) out #param<<" is : "<<param<<"\n"
#define fi first
#define sec second
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define vdb vector<db>
#define vbool vector<bool>
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define pll pair<long long,long long>
#define plll pair<long long,pair<long long,long long>>
#define maxn 100005
#define invv(v,from,to) for(int i=from;i<=to;i++) \
in v[i];
#define inv(v) for(int i=0;i<v.size();i++) \
in v[i];
#define printv(v) out #v<<" is :\n"; \
for(int i=0;i<v.size();i++) \
out " "<<v[i];\
nl;
#define printvv(v,from,to) out #v<<" is :\n"; \
for(int i=from;i<=to;i++) \
out " "<<v[i];\
nl;
#define inmax INT_MAX
#define llmax LONG_LONG_MAX
#define nl out "\n"
#define nll out "\n\n"
#define pdd pair<double,double>
using namespace std;
ll g(ll p){
while(p%2 == 0){
p /= 2;
}
p /= 2;
return p;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll q;
in q;
while(q--){
ll ts;
in ts;
out g(ts) << "\n";
}
nl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
long long int a;
cin>>a;
if(a%2==1)
{
cout<<(a-1)/2<<"\n";
}
else
{
long long int ans =a;
long long int x=0;
while(a%2==0)
{
x++;
a=a/2;
}
long long int y = pow(2,x+1);
cout<<(int)ans/y<<"\n";
}
}
}
whats wrong with my code seems like i have done it like editorial during contest time only subtask 1 passed subtask 2 failed… please explain someone
Hi!
After reading your solution I got to know that I misunderstood the question, however even after reading the question now once again I still can’t seem to find why my understanding is wrong. Please guide me where I went wrong with respect to the question statement.
Here’s my pseudo code:
START
Input test case, and for each test case repeat the following process:
Input TS
If TS is odd, answer is TS//2
If TS is even, JS can have all the even values from 2 to TS, for each combination of TS and JS do the following:
- Divide both TS and JS by 2 till one of them becomes odd,
- If TS becomes odd first then increment a counter (ctr ++)
- If JS becomes odd first then do nothing.
please format your code from now on
Also, read the question carefully…divide TS by 2 till it is odd and JS can have all values such that JS divided by same number (2**n) will be even
copy pasted from vscode it looks formatted there used preformatted text here several times in edit didnt work… how to format it correctly?
UPD: done formatting
proceed to next turn with above JS
divide TS by 2 and all Possible JS choices by 2
TS/2 = 5
JS/2 = 1 2 3 4 5
Winning entries = 2 4 (from choices 6 and 8) (N = (N-1)/2)
// for last turn we do (N-1)/2 instead of N/2 due to inclusion of TS as upper bound in choice of JS
Code:-
count =(found by counting trailing 0’s in TS’s binary rep)
ie How many times I have to divide this number to get an odd num so jerry wins with an even num on that turn
long possibleJSChoices =(TS)/2;//all even nums between 1 and TS so that game proceeds
long N = possibleJSChoices
for(int i = 0 ; i < count;i++)
{
if(i==count-1)
N = (N-1)/2;
else
N = (N)/2;
}
System.out.println(""+N);
Dividing TS till an odd number is reached and counting the number of divisions (count).
In order for JS to win, the smallest such number will have to be divided the same number of times till even. (Resulting in TS being odd and JS being even, so JS wins - first such occurrence)
Smallest such number will therefore be 2^(count +1)
Winning numbers will be a list of multiples of this smallest number and less than TS.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long int T, TS, result, ts, count, divisor, i;
cin >> T;
for (i = 0;i<T;i++){
cin >> TS;
if (TS % 2 != 0){
result = TS/2;
cout << result<<'\n';
}
else{
ts = TS;
count = 0;
while (ts % 2 == 0){
ts = ts/2;
count ++;
}
count++;
divisor = pow(2,count);
result = TS/divisor;
cout << result<<'\n';
}
}
}
