Amaru and Kapkan were playing Rainbow 6 Siege in which Kapkan strategically placed N bombs all over the map.
Each bomb has 3 numbers associated to it X, L and R and can only be defused by finding the maximum value of (X ⊕ Y) where ⊕ represents the bitwise xor operation and Y can be any number in the interval [L,R].
Amaru is a dumb player who only rushes in, so can you help her in winning by finding the maximum value of (X ⊕ Y) for all the N bombs?
1 <= N <= 5000
1 <= L <= R <= 1019
1 <= X <= 10^9
•[execution time limit] 1 seconds (cpp)
•[input] integer n
•[input] array.integer x
•[input] array.integer I
•[input] array.integer r
•[output] array.integer
Zasho is a popular genie. Being a genie, he's in the business of granting wishes, and a lot of people ask him for help. However, his power is limited - currently it is p units.
To grant the i-th wish, Zasho needs to have at least x units of power. After a wish is granted, his rating changes by y (y can be positive or negative). Of course, his power should not dip below zero - otherwise he won't be able to grant any wishes. He can choose to grant wishes in any order.
Zasho wants to grant the maximum number of wishes possible so that he remains popular. Can you help him figure out how many wishes he should grant?
In other words, find the maximum possible size of the subset of wishes so that Zasho has enough power before starting each, and has non-negative power after completing each wish.
• 1 ≤ n ≤ 100, 1 ≤ p ≤ 30000
• The next n lines contain the wishes, one per line. The i-th wish is represented as a pair of integers x and y (1 ≤ x ≤ 30000, -300 ≤ y ≤ 300)
If the input is
3 5
4 -5
4 -2
1 3
The output is 3 because a possible order <2, 3, 1> exists for Zasho to fulfill every wish.
•[execution time limit] 1 seconds (cp)
•[input] integer p
•[input] array.integer x
•[input] array.integer y
•[output] integer
[C++] Syntax Tips
Overview
Solution
We will iterate from the largest set bit in R to the lowest (0th Bit). The following two cases can arise for each bit:
If the bit is not set, i.e. 0 in X, we will try to set it in Y. If setting this bit to 1 results in Y exceeding R, then we will not set it.
If the bit is set, i.e. 1 in X, then we will try not to set it in Y.
Code
ll n;
cin >> n;
for (ll i = 0; i < n; i++)
{
ll x, l, r;
cin >> x >> l >> r;
ll y = 0;
for (ll j = 30; j >= 0; j--)// iterate from largest to smallest bit
{
ll val = (1ll << j);
if (x & val)// if the current bit is set in x
{
if (y + val - 1 < l)// Even if after setting all the next bits, the value of y remains less than r than we have to set the current bit
{
y += val;// we have to forcefully set the current bit
}
}
else// if the current bit is not set in x
{
if (y + val <= r)// if setting the current bit doesn't exceeds r
{
y += val;// set the current bit
}
}
}
cout << (x ^ y) << endl;
}
return;
We are given n wishes (x,y), and an initial power p. We can give the wish If x <= p and p-y>=0. p changes to p-y after giving a wish.
Find maximum size of subset of the wishes we can give.
Complexity : O(n^2*log(n))
int solve(int n,int p,vector<pair<int,int>> a)
{
set<pair<int,int>,greater<pair<int,int>>> s;
vector<int> done(n);
for(int i = 0;i < n;i++)
{
if(a[i].first<=p)
s.insert({a[i].second,i});
}
int ans=0;
while(!s.empty())
{
auto x=*s.begin();
s.erase(x);
if(p-x.first<0)
{
break;
}
p+=x.first;
done[x.second]=1;
ans++;
for(int i = 0;i < n;i++)
{
if(done[i])
continue;
if(a[i].first<=p)
s.insert({a[i].second,i});
}
}
return ans;
}