Link to contest : SPC — Final Contest : )
If you can't see the tutorial then click on above link first.
A. Fruits
Problem Author : Cheata
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 998244353
void solve()
{
int n;
cin>>n;
string s;
cin>>s;
vector<int>a,o,b;
for(int i=0;i<n;i++)
{
if(s[i]=='a') a.pub(i);
if(s[i]=='b') b.pub(i);
if(s[i]=='o') o.pub(i);
}
for(auto i :a) cout<<i+1<<" ";
cout<<"\n";
for(auto i :b) cout<<i+1<<" ";
cout<<"\n";
for(auto i :o) cout<<i+1<<" ";
cout<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
B. Dice Roll
Problem Author : Mantra7
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
void solve()
{
int a,b;
cin>>a>>b;
cout<< a+b+7 << "\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
C. Selfie with Tourist
Problem Author : kuki22102002
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
long long int T;
cin>>T;
while(T--)
{
long long int N,k,a,b;
long long int minimum=1e18;
cin>>N>>k>>a>>b;
long long int friends[N],diff;
for(long long int j=0;j<N;j++)
{
cin>>friends[j];
diff=abs(a-friends[j]) + abs(b-friends[j]);
minimum=min(minimum,diff);
}
cout<< minimum <<endl;
}
return 0;
}
D. Strong Arrays
Problem Author : Abdullah010
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
void solve()
{
int n; cin >> n;
int a[n];
for(int i=0; i<n; i++){
cin >> a[i];
if(a[i] >=0) a[i] = -a[i]-1;
}
int ans = 1;
if(n%2==0){
for(int i=0; i<n; i++){
a[i] = abs(a[i]);
ans = (ans*a[i])%mod;
}
cout << ans%mod << endl;
}
else{
sort(a,a+n);
a[0] = -a[0]-1;
for(int i=0; i<n; i++){
a[i] = abs(a[i]);
ans = (ans*a[i])%mod;
}
cout << ans%mod << endl;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
E. El Clasico
Problem Author : iowiz
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 998244353
void solve()
{
int n; cin >> n;
int a=0,b=0;
for(int i=0; i<n; i++){
int x,y,z; cin >> x >> y >> z;
if(x==1){
ya;
a = y; b= z;
}
else{
int mn1 = min(a,b);
int mx1 = max(a,b);
int mn2 = min(y,z);
int mx2 = max(y,z);
if(y==z){
ya; a=y; b=z; continue;
}
if(mn2 >= mx1){
na; continue;
}
ya;
if(a==mx1) {a = mx2; b = mn2;}
else{a = mn2; b = mx2;}
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
F. Array Uniformity
Problem Author : sapta0506
Tutorial
Tutorial is loading...
Solution
#include <cmath>
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<b; ++i)
#define all(x) x.begin(),x.end()
const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;
void solve()
{
int n; cin >> n;
int s[n];
for(int i=0; i<n; i++) cin >> s[i];
map<int,int> m;
int ans = 0;
for(int i = n-1; i>=1; i--){
if(s[i]==s[i-1]){
int x = n-1-i-m[s[i]];
m.clear();
ans += x;
m[s[i]] += n-1-i;
}
m[s[i]]++;
}
cout << ans << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1; cin >> t;
while(t--) solve();
return 0;
}
G. Singleton Code (Easy Version)
Problem Author : sapta0506, KDVinit
Tutorial
Tutorial is loading...
Solution
/*
Mantra's code :)
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
int sof(int x)
{
if(x/10==0) return x;
int ans=0;
while(x>0)
{
ans+=x%10;
x/=10;
}
return sof(ans);
}
void solve()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int ans=sof(a[0]);
for(int i=1;i<n;i++)
{
ans*=a[i];
ans=sof(ans);
}
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
H. Singleton Code (Hard version)
Problem Author : sapta0506, KDVinit
Tutorial
Tutorial is loading...
Solution
/*
Mantra's code :)
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
int sof(int x)
{
if(x/10==0) return x;
int ans=0;
while(x>0)
{
ans+=x%10;
x/=10;
}
return sof(ans);
}
void solve()
{
int n;
cin>>n;
int flag0=0;
int flag1=0;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
if(a[i]==0) flag0=1;
if(i>0 && a[i]>1) flag1=1;
}
if(flag0)
{
cout<<"1\n";
return;
}
int x=sof(a[0]);
if(n==1)
{
cout<<x<<"\n";
return;
}
if(x==0 || x==1 || x==9)
{
cout<<x<<"\n";
}
if(x==6 || x==3)
{
if(flag1==0)
{
cout<<x<<"\n";
}
else
{
cout<<"9\n";
}
}
if(x==8)
{
int rem=a[1]%2;
for(int i=2;i<n;i++)
{
rem*=(a[i]%2);
}
if(rem==0) cout<<"1\n";
else cout<<"8\n";
}
if(x==4 || x==7)
{
int rem=a[1]%3;
for(int i=2;i<n;i++)
{
rem*=(a[i]%3);
rem%=3;
}
if(rem==2) cout<<(x==4 ? 7 : 4)<<"\n";
if(rem==1) cout<<(x==4 ? 4 : 7)<<"\n";
if(rem==0) cout<<(x==4 ? 1 : 1)<<"\n";
}
if(x==2 || x==5)
{
int rem=a[1]%6;
for(int i=2;i<n;i++)
{
rem*=(a[i]%6);
rem%=6;
}
if(rem==5) cout<<(x==2 ? 5 : 2)<<"\n";
if(rem==4) cout<<(x==2 ? 7 : 4)<<"\n";
if(rem==3) cout<<(x==2 ? 8 : 8)<<"\n";
if(rem==2) cout<<(x==2 ? 4 : 7)<<"\n";
if(rem==1) cout<<(x==2 ? 2 : 5)<<"\n";
if(rem==0) cout<<(x==2 ? 1 : 1)<<"\n";
}
return;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
I. Find The String
Problem Author : Mantra7
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
#define Fact_Length 500001 //Max length here is 519160
/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
int Power(int a,int b)
{
int result=1; a%=mod;
while(b) { if(b%2==1) result*=a; a*=a; a%=mod; result%=mod; b/=2; }
return result;
}
/** It give the modulo inverse of a, (1/a)%mod **/
int Mod_Inv(int a)
{
a%=mod; a=Power(a,mod-2); return a;
}
int Factorial[Fact_Length];
/** It make the above Factorial array to i! array**/
int Make_Factorial()
{
Factorial[0]=1;
for(int i=1;i<Fact_Length;i++) { Factorial[i]=i*Factorial[i-1]; Factorial[i]%=mod; } return 0;
}
int Implement_Make_Factorial=Make_Factorial(); //To Implement Make_Factorial
void solve()
{
string s;
cin>>s;
int n=s.size();
int freq[26]={0};
for(int i=0;i<n;i++)
{
freq[s[i]-'a']++;
}
int inc=Factorial[n];
for(int j=0;j<26;j++)
{
inc*=Mod_Inv(Factorial[freq[j]]);
inc%=mod;
}
int ans=0;
for(int i=0;i<n;i++)
{
if(i!=0)
{
inc*=freq[s[i-1]-'a']+1;
inc%=mod;
}
inc*=Mod_Inv(n-i);
inc%=mod;
for(int j=0;j<s[i]-'a';j++)
{
int cur_inc=inc*freq[j];
cur_inc%=mod;
ans+=cur_inc;
ans%=mod;
}
freq[s[i]-'a']--;
}
cout<<(ans+1)%mod<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
J. Musical Chairs
Problem Author : sapta0506
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pub push_back
#define pob pop_back
#define ya cout<<"YES\n"
#define na cout<<"NO\n"
#define imp cout<<"Impossible\n"
#define mod 1000000007
void solve()
{
int n;
cin>>n;
int t[n];
for(int i=1;i<n;i++)
{
cin>>t[i];
}
t[0]=0;
int cur=0;
for(int i=n-1;i>0;i--)
{
int delta=t[i]-t[i-1];
delta%=(n-i+1);
int prev=(cur+1+(n-i+1)-delta)%(n-i+1);
cur=prev;
}
cout<<cur+1<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
}
K. Saving the Programming Club
Problem Author : AdC_AB2
Tutorial
Tutorial is loading...
Solution
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl "\n"
#define sz(a) (int)a.size()
const ll mod = 1000000007;
#define NN 1000001
#define Fact_Length 500001 //Max length here is 519160
/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
ll Power(ll aaa,ll bbb)
{
ll result=1; aaa%=mod;
while(bbb) { if(bbb%2==1) result*=aaa; aaa*=aaa; aaa%=mod; result%=mod; bbb/=2; }
return result;
}
/** It give the modulo inverse of a, (1/a)%mod **/
ll Mod_Inv(ll aaa)
{
aaa%=mod; aaa=Power(aaa,mod-2); return aaa;
}
bool prime_chk[NN];
vector<ll> p;
int sieve()
{
for(ll i=2;i<NN;i++)
{
prime_chk[i]=true;
}
prime_chk[0]=false;
prime_chk[1]=false;
for(ll i=2;i<NN;i++)
{
if(prime_chk[i]==true)
{
p.push_back(i);
for(ll j=i*i;j<NN;j+=i)
{
prime_chk[j]=false;
}
}
}
return(0);
}
void solv()
{
ll a,m;
cin>>a>>m;
map<ll,ll> ap, mp;
ll t1=a,i=0;
while(t1>1 && i<sz(p))
{
while(t1%p[i]==0)
{
ap[p[i]]++;
t1/=p[i];
}
i++;
}
ll t2=m;i=0;
while(t2>1 && i<sz(p))
{
while(t2%p[i]==0)
{
mp[p[i]]++;
t2/=p[i];
}
i++;
}
ll ans=1, pro=1,c=1;
ll tt;
for(ll i=0; i<sz(p); i++)
{
if(ap[p[i]]>mp[p[i]])
{
pro*=Power(p[i],ap[p[i]]);
pro%=mod;
}
else if(mp[p[i]]>0)
{
tt=Power(p[i],mp[p[i]]+1)-1+mod;
tt*=Mod_Inv(p[i]-1);
tt%=mod;
ans*=tt;
ans%=mod;
c*=mp[p[i]]+1;
c%=mod;
}
}
if(t1!=t2)
pro*=t1%mod;
if(t2!=1)
{
ans*=(t2+1)%mod;
c*=2;
c%=mod;
}
ans%=mod, pro%=mod;
ll ff=(ans)*(pro)-(c)*(a%mod)+mod*mod;
ff%=mod;
cout<<ff<<endl;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll test_cases=sieve();
cin>>test_cases;
for(ll loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}
L. Can anyone solve it?
Problem Author : AdC_AB2, KDVinit
Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)(a.size())
const int mod = 1000000007;
/**Takes a&b as input and Returns : The power (a,b), (a^b)%mod **/
int Power(int aaa,int bbb)
{
int result=1; aaa%=mod;
while(bbb) { if(bbb%2==1) result*=aaa; aaa*=aaa; aaa%=mod; result%=mod; bbb/=2; }
return result;
}
/** It give the modulo inverse of a, (1/a)%mod **/
int Mod_Inv(int aaa)
{
aaa%=mod; aaa=Power(aaa,mod-2); return aaa;
}
int gcd(int a, int b)
{
if(b==0)
return a;
return gcd(b, a%b);
}
int sum_pwr(int b,int p) //Computes b+b^2+b^3+...+b^p
{
int ans;
if(b==1)
{
ans=p%mod;
return ans;
}
ans=Power(b,p+1)-1+mod; ans%=mod;
ans*=Mod_Inv(b-1); ans%=mod;
ans+=mod-1; ans%=mod;
return ans;
}
int AGP(int b,int p) //Computes 1b+ 2(b^2) + 3(b^3) +...+ p(b^p)
{
int ans;
if(b==1)
{
p%=mod;
ans=p*(p+1); ans%=mod;
ans*=Mod_Inv((int)2); ans%=mod;
return ans;
}
int tmp=(p%mod)*Power(b,p+1); tmp%=mod;
tmp+=mod-sum_pwr(b,p); tmp%=mod;
tmp*=Mod_Inv(b-1);
ans=tmp%mod;
return ans;
}
void solv()
{
int n,a,b;
cin>>n>>a>>b;
int gc = gcd(a,b);
if(n>=a+b)
{
n/=gc;
int b1=Power(2,gc), b2=Power(5,gc),ans=0, tmp;
ans+=sum_pwr(b1,n); ans%=mod;
ans+=sum_pwr(b2,n); ans%=mod;
tmp=AGP(b1,n)+AGP(b2,n); tmp%=mod;
tmp*=(3*gc)%mod; tmp%=mod;
ans+=tmp;
ans%=mod;
cout<<ans<<endl;
return;
}
n = n/gc;
a = a/gc;
b = b/gc;
vector<int> vi(n+1,0);
queue<int> lvl;
if(n>=a)
{
lvl.push(a);
vi[a]=1;
}
if(n>=b && !vi[b])
{
lvl.push(b);
vi[b]=1;
}
vector<int> save;
int lvl_rn,cnt=0;
while(!lvl.empty())
{
cnt++;
lvl_rn=lvl.front();
save.push_back(lvl_rn);
lvl.pop();
if(lvl_rn+a<=n && !vi[lvl_rn+a])
{
lvl.push(lvl_rn+a);
vi[lvl_rn+a]=1;
}
if(lvl_rn-a>0 && !vi[lvl_rn-a])
{
lvl.push(lvl_rn-a);
vi[lvl_rn-a]=1;
}
if(lvl_rn+b<=n && !vi[lvl_rn+b])
{
lvl.push(lvl_rn+b);
vi[lvl_rn+b]=1;
}
if(lvl_rn-b>0 && !vi[lvl_rn-b])
{
lvl.push(lvl_rn-b);
vi[lvl_rn-b]=1;
}
}
int ans=0,cc;
int b1=Power(2,gc),b2=Power(5,gc);
for(int i=0; i<sz(save); i++)
{
cc=Power(b1,save[i])+Power(b2,save[i]); cc%=mod;
cc*=(1+3*save[i]*gc)%mod; cc%=mod;
ans+=cc; ans%=mod;
}
cout<<ans<<endl;
return;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test_cases=1;
//cin>>test_cases;
for(int loop_var=1;loop_var<=test_cases;loop_var++)
{
solv();
}
return 0;
}