Idea:Yugandhar_Master
If $$$n=1$$$, There is only one possible $$$\it{Lucky \ array}$$$. It is guaranteed that the given array is $$$\it{Lucky \ array}$$$ so there is no other $$$\it{Lucky \ array}$$$ to output. Hence the answer is $$$-1$$$.
For $$$n>1$$$, it is easy to see that there are more than one possible $$$\it{Lucky \ array}$$$. So we can use the following pattern to construct the $$$\it{Lucky \ array}$$$ :
$$$ 0 \ 1 \ 0 \ 1 \ 0 \ 1 \ ....$$$
If this constructed array is equal to the given array then we can swap the elements in $$$2^{nd}$$$ and $$$3^{rd}$$$ positions if $$$n>2$$$, otherwise we can just set the $$$2^{nd}$$$ to $$$0$$$.
Note that there are many possible constructions, the above mentioned is one of them
Time Complexity : $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
if(n==1) cout<<"-1\n";
else if(n==2){
if(a[1]==1) cout<<"0 0\n";
else cout<<"0 1\n";
}
else{
vector<int> b(n,0);
for(int i=1;i<n;i+=2) b[i]=1;
if(a==b) swap(b[1],b[2]);
for(auto i:b) cout<<i<<" ";
cout<<"\n";
}
}
}
Idea:Yugandhar_Master
Let's call array $$$c$$$ good if it contains non-positive integers. Now our task is to make array $$$c$$$ good using minimum number of given operations.
It is always optimal to choose the largest element in $$$c$$$ and decrease it by $$$a$$$ and decrease all other elements by $$$b$$$ until array $$$c$$$ becomes good. But this solution is very slow. We can optimise the solution by using the fact that if we can make the array good using $$$x$$$ operations then we can definitely make the array good using $$$x+1$$$ operations because if all elements in the array are non-positive then using extra operation will not make any element positive. So we can use binary search on our answer.
Binary search follows for fixed $$$m$$$ like decrease all elements by $$$bm$$$ and decrease the remaining positive elements by $$$(a-b)$$$ until it becomes non-positive, call these as extra operations, if the extra operations are not greater than $$$m$$$ decrease the upper bound of the answer, otherwise increase the lower bound of the answer.
Time Complexity : $$$O(nlog(\frac{M}{b}))$$$. where $$$M$$$ is the maximum element in the array $$$c$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n,a,b;
cin>>n>>a>>b;
vector<ll> v(n);
for(ll i=0;i<n;i++) cin>>v[i];
ll l=0,r=1e9,ans=1e9;
while(l<=r){
ll m=(l+r)/2;
ll ops=0;
for(ll i=0;i<n;i++){
if(v[i]>b*m){
ops+=((v[i]-b*m+(a-b-1))/(a-b));
}
}
if(ops<=m){
ans=m;
r=m-1;
}
else l=m+1;
}
cout<<ans<<"\n";
}
}
Idea:Yugandhar_Master
The Optimal strategy to use more number of spells is as follows:
- Take $$$x=1$$$ until the first monster health becomes $$$1$$$.
- Take $$$x=2$$$ or ($$$x=3$$$, if the health of the monster we are going to attack is odd) until monster health becomes 2.
- Take $$$x=3$$$ or ($$$x=4$$$, if the health of the monster we are going to attack is multiple of $$$3$$$) until monster health becomes 3.
Continue this process until any monster is alive.
Time Complexity : $$$O(n)$$$.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
vector<ll> a(n);
for(ll i=0;i<n;i++) cin>>a[i];
ll ans=0,val=1;
for(ll i=0;i<n;i++){
ll res=(a[i]-1)/val;
if(res>0){
ans+=res;
a[i]=1;
}
if(val==a[i]) val++;
}
ans++;
cout<<ans<<"\n";
}
}
Idea:wuhudsm
Coming soon...
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T;
ll n,m;
int tag[N];
int main()
{
//freopen("test.in","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d",&n,&m);
ll mx=n*(n+1)/2-2,mn=-mx,sum=mn,cur1,cur2;
vector<ll> v[2];
if(m<mn||m>mx||((mx&1)^(m&1)))
{
printf("NO\n");
continue;
}
printf("YES\n");
tag[1]=1;
for(int i=2;i<=n;i++) tag[i]=0;
for(int i=2;i<=n;i++)
{
tag[i]=1;
sum+=2*i;
if(sum>=m)
{
tag[(sum-m)/2]=0;
break;
}
}
for(int i=1;i<=n;i++) v[tag[i]].push_back(i);
cur1=v[1][0];
for(int i=1;i<v[0].size();i++)
{
printf("%I64d %I64d\n",cur1,v[0][i]);
cur1-=v[0][i];
}
cur2=v[0][0];
for(int i=1;i<v[1].size();i++)
{
printf("%I64d %I64d\n",cur2,v[1][i]);
cur2-=v[1][i];
}
printf("%I64d %I64d\n",cur1,cur2);
}
//fclose(stdin);
return 0;
}
E: Mr.Wow and Hidden Permutation
Idea:Yugandhar_Master
Coming soon...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int n;
int query(vector<int> v){
cout<<"? ";
for(int i=0;i<(int)v.size();i++) cout<<v[i]+1<<" ";
cout<<endl;
int x;
cin>>x;
if(x>(n/2)) return 1;
return 0;
}
int sol(int j){
vector<int> v(n/2);
for(int i=0;i<n/2;i++) v[i]=i+j;
return query(v);
}
int main(){
fast;
ll t;
cin>>t;
while(t--){
cin>>n;
int l=0,r=n/2;
int vl=sol(0),vr=sol(n/2);
while(l+1<r){
int m=(l+r)/2;
int vm=sol(m);
if(vm==vl) l=m;
else r=m;
}
vector<int> v2,v3;
for(int i=r;i<(r+(n/2)-1);i++){
v2.push_back(i);
v3.push_back((i+(n/2))%n);
}
vector<int> ans(n);
ans[l]=vl;
ans[l+(n/2)]=vr;
for(int i=0;i<(int)v2.size();i++){
vector<int> v=v3;
v.push_back(v2[i]);
ans[v2[i]]=query(v);
}
for(int i=0;i<(int)v3.size();i++){
vector<int> v=v2;
v.push_back(v3[i]);
ans[v3[i]]=query(v);
}
vector<int> even,odd;
for(int i=0;i<n;i++){
if(ans[i]==0) even.push_back(i+1);
else odd.push_back(i+1);
}
cout<<"! ";
for(int i=0;i<(int)even.size();i++){
cout<<even[i]<<" ";
cout<<odd[i]<<" ";
}
cout<<endl;
}
}
Idea:Yugandhar_Master
Coming soon...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
int main(){
fast;
ll t;
cin>>t;
while(t--){
ll n;
cin>>n;
vector<ll> a(n);
for(ll i=0;i<n;i++) cin>>a[i];
ll maxi=0;
for(ll i=0;i<(n/2);i++) maxi=max(maxi,a[i]+a[i+(n/2)]);
ll l=maxi-1,r=1e14;
while(r-l>1){
ll m=(l+r)/2;
vector<ll> v1(n/2),v2(n/2);
for(ll i=0;i<(n/2);i++){
v1[i]=m-a[i+(n/2)];
v2[i]=-a[i];
}
vector<ll> dp11((n/2)+1,1e18),dp12((n/2)+1,1e18),dp21((n/2)+1,1e18),dp22((n/2)+1,1e18);
dp12[0]=0;
dp21[0]=0;
for(ll i =0;i<(n/2);i++){
dp11[i+1]=min(dp11[i],dp12[i]+v2[i]);
dp12[i+1]=min(dp12[i],dp11[i]+v1[i]);
dp21[i+1]=min(dp21[i],dp22[i]+v2[i]);
dp22[i+1]=min(dp22[i],dp21[i]+v1[i]);
}
if(dp11[n/2]>=-m && dp22[n/2]>=0){
r=m;
}
else{
l=m;
}
}
cout<<r<<"\n";
}
}
