1.CAM5 - prayatna PR Spoj Solution
TAG-
graph theory,Disjoint set union,dfs.
Explanation-
We have to group the people which are connected in any other way and there is hint when we talk about grouping .
One way to solve the problem is using DFS or Disjoint set union.
Solution Using DFS-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
bool vis[1000010];
void dfs(ll src,vector<ll>adj[])
{
vis[src]=true;
for(auto u:adj[src])
{
if(!vis[u])
dfs(u,adj);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
ll n,m;
cin>>n>>m;
memset(vis,false,sizeof(vis));
vector<ll>adj[n+1];
for(int i=0;i<m;i++)
{
ll a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
ll ct=0;
for(int i=0;i<n;i++)
{
if(!vis[i])
{
ct++;
dfs(i,adj);
}
}
cout<<ct<<"\n";
}
}
Solution using Disjoint Set Union-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
ll parent[1000000];
ll find_parent(ll a)
{
return a==parent[a]?a:parent[a]=find_parent(parent[a]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
ll n,m;
cin>>n>>m;
ll total=n,a,b;
for(int i=0;i<n;i++)
parent[i]=i;
for(int i=0;i<m;i++)
{
cin>>a>>b;
ll x=find_parent(a);
ll y=find_parent(b);
if(x!=y)
{
total--;
parent[x]=y;
}
}
cout<<total<<"\n";
}
}
2.BUGLIFE - A Bug’s Life Spoj Solution
TAG-
graph theory , bipartite graph ,vertex coloring
Explantion-
We have to divide the vertex in two group and every edge connect the vertex of two group .So basically we have to check can this graph is bipartite or not?
How to check bipartite ?
We have to dfs(Depth first search) on every child and keep two colors if parent is color red then all child must be blue and if this condition satisfy throughout the graph then graph is bipartite otherwise not.
SOLUTION-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
bool vis[1000010];
ll col[1000010];
bool dfs(ll src,vector<ll>adj[],ll c)
{
vis[src]=true;
col[src]=c;
for(auto u:adj[src])
{
if(!vis[u])
{
if(dfs(u,adj,c^1)==false)
return false;
}
else
{
if(src!=u&&col[src]==col[u])
{
return false;
}
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
for(int j=1;j<=t;j++)
{
ll n,m;
cin>>n>>m;
vector<ll>adj[n+10];
for(int i=1;i<=n;i++)
{
vis[i]=false;
col[i]=-1;
}
for(int i=0;i<m;i++)
{
ll a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
ll f=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
if(!dfs(i,adj,0))
{ //cout<<i<<"\n";
f=1;
break;
}
}
}
cout<<"Scenario #"<<j<<":\n";
if(f)
cout<<"Suspicious bugs found!"<<"\n";
else
cout<<"No suspicious bugs found!"<<"\n";
}
}
3.ZSUM - Just Add It Spoj Solution
Tag-
Binary Exponantion,Math
Explanation-
PART 1-
in ZSUM problem on spoj we have to find the answer for-(Zn + Zn-1 - 2Zn-2) %10000007
where Zn = Sn + Pn
Sn = 1k + 2k + 3k + … + nk
Pn = 11 + 22 + 33 + … + nn.
when we try to solve
Zn+Zn-1-2Zn-2 = Sn+Pn+Sn-1+Pn-1-2*(Sn-2+Pn-2)
now try to solve this
=>(1^k+2^k+....n^k+1^1+2^2+..n^n)+(1^k+2^k+....+(n-1)^k+ 1^1+2^2+...+(n-1)^n-1)
-2*(1^k+2^k+....+(n-2)^k+ 1^1+2^2+...+(n-2)^n-2)
=>(n-1)^k+n^k+(n-1)^(n-1)+n^n+(n-1)^k+(n-1)^(n-1)
=>n^k+n^n+2*((n-1)^k+(n-1)^(n-1))
now we have done the most of part of zsum .
PART 2-
In ZSUM problem on spoj point to come how to calculate power
anwer is binary exponation.If you don't know about binary exponation k=no problem there are lot of good articles written on internet because if we use bruteforce instead of binary exponantion result will be TLE so avoid TLE we have to used binary exponantion because it is efficient and time complexity is less.
SOLUTION OF ZSUM-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ch char
#define vc vector
#define str string
#define mod 10000007
ll binary_expo(ll base,ll n,ll result)
{
if(n==0)
return result;
if(n%2==0)
{
return binary_expo((base*base)%mod,n/2,result%mod);
}
else
{
return binary_expo(base,n-1,(result*base)%mod);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll k,n,result=1;
while(1)
{
cin>>n>>k;
ll s=0,p=0,s1,s2,p1,p2;
if(n==0&&k==0)break;
s1=(binary_expo(n,k,result))%mod;
p1=(binary_expo(n,n,result))%mod;
s2=binary_expo(n-1,k,result)%mod;
p2=binary_expo(n-1,n-1,result)%mod;
cout<<(s1+p1+2*s2+2*p2)%mod<<"\n";
}
}
Happy coding 😍.
If you like this blog you can follow us.
4.WILLITST - Will it ever stop Spoj Solution
Tag-
ad-hoc
Explanation-
In WILLITST problem spoj this problem is pretty nice problem .What you have to done that you have to find that is loop will stop of run infinitely .This problem can be done if you try to draw run some test then definitely you will get answer.
You will find if in any step if 12 is occurred then it will run infinitely.
But how 12 why not others?
If you try to dry run then you will get answer early for WILLITST.
let run for 12-
step1-12 is divisible by 2 then
n=12/2;
n=6;
step 2-6 is divisible by 2 then
n=6/2;
n=3;
step 3- 3 is not divisible by 2 then
n=3*3+3;//n=3*n+3
n=12
we will reach where is start it this is a predestination 😂 .
so if any step if 12 is occurred we have to break at that point otherwise is will not run infinitely.
SOLUTION-
#include<stdio.h>
int main()
{ int k=0;
long long int n;
scanf("%lld",&n);
while(n>1)
{
if(n%2==0)
n=n/2;
else
n=n*3+3;
if(n%12==0)
{
k=1;
break;
}
}
if(k==0)
printf("TAK");
else
printf("NIE");
}
5.VENOM - Touch of Venom Spoj Solution
Tag-
Implementation , Bruteforce
Trick-Use scanf/printf instead of cin/cout [for c or cpp language users]
Explanation-
In VENOM problem on spoj you are given 3 things intial health,poison,and heal value you have to figure out survival time for our hero.There is nothing other then implementation.Hero will we killed if
hero health is less then or equal to zero .
for better understanding you can look at the explanation given in the problem.
SOLUTION OF VENOM-
#include<stdio.h>
int main()
{
long long int t,h,p,k,a,count,i;
scanf("%lld",&t);
while(t--)
{ i=1,count=0;
scanf("%lld%lld%lld",&h,&p,&a);
while(h!=0)
{
k=i*p;
i++;
h=h-k;
count++;
if(h>0)
{
h=h+a;
count++;
}
}
else
break;
}
printf("%lld\n",count);
}
}
UPDATEIT - Update the array ! Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ch char
#define vc vector
#define str string
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
scanf("%lld",&t);
while(t--)
{
ll n,m;
scanf("%lld%lld",&n,&m);
ll d[n+1];
memset(d,0,sizeof(d));
for(ll i=0;i<m;i++)
{
ll l,r,v;
scanf("%lld%lld%lld",&l,&r,&v);
d[l]+=v;
d[r+1]-=v;
}
for(int i=1;i<n;i++)
{
d[i]+=d[i-1];
}
ll p,x;
scanf("%lld",&p);
for(int i=0;i<p;i++)
{
scanf("%lld",&x);
printf("%lld\n",d[x]);
}
}
}
UFPR14D - Inquire Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{long long int n,i,A,B,sum=0,a[100000],q;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
scanf("%lld",&q);
while(q--)
{
scanf("%lld%lld",&A,&B);
sum=0;
for(i=A;i<=B;i++)
{
sum=sum+a[i];
}
printf("%lld\n",sum);
}
}
TRIKA - Training for final Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ch char
#define vc vector
#define str string
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,m,x,y;
cin>>n>>m>>x>>y;
ll dp[n+1][m+1];
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>dp[i][j];
}
}
for(int i=x;i<=n;i++)
{
for(int j=y;j<=m;j++)
{
if(i==x&&j==y)
continue;
if(i==x)
{
if(j!=1)
{
dp[i][j]=dp[i][j-1]-dp[i][j];
}
}
else if(j==y)
{
if(i!=1)
{
dp[i][j]=dp[i-1][j]-dp[i][j];
}
}
else
{
dp[i][j]=max(dp[i-1][j]-dp[i][j],dp[i][j-1]-dp[i][j]);
}
}
}
if(dp[n][m]>=0)
{
cout<<"Y "<<dp[n][m];
}
else
cout<<"N";
}
TRICOUNT - Counting Triangles Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
long long unsigned num,sum;
scanf("%llu",&num);
if(num%2==0)
sum=(num*(num+2)*((2*num)+1))/8;
else
sum=((num*(num+2)*((2*num)+1))-1)/8;
printf("%llu\n",sum);
}
return 0;
}
TRGRID - Traversing Grid Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{ long long int a,b,t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&a,&b);
if(a==b)
{
if(a%2==0&&b%2==0)
printf("L\n");
else if(a%2!=0&&b%2!=0)
printf("R\n");
}
else if(a>b)
{
if(a%2==0&&b%2==0)
printf("U\n");
else if(a%2!=0&&b%2!=0)
printf("D\n");
else if(a%2==0&&b%2!=0)
printf("D\n");
else if(a%2!=0&&b%2==0)
printf("U\n");
}
else if(a<b)
{
if(a%2==0&&b%2!=0)
printf("L\n");
else if(a%2!=0&&b%2==0)
printf("R\n");
if(a%2==0&&b%2==0)
printf("L\n");
if(a%2!=0&&b%2!=0)
printf("R\n");
}
}
}
TOANDFRO - To and Fro Spoj Solution
SOLUTION-
#include<bits/stdc++.h>
using namespace std;
int main()
{ char a[20000];
int n,l,i,j,x;
while(1)
{cin>>n;
if(n==0)
{
break;
}
else
{
scanf("%s",a);
l=strlen(a);
x=(n-1)*2+1;
int m=1;
for(j=0;j<n;j++)
{
for(i=j;i<l;i=i+m)
{
cout<<a[i];
i=i+x;
if(i<l)
cout<<a[i];
}
x=x-2;
m=m+2;
}
cout<<endl;
}
}
}
TIPTOP - Tip Top Game Spoj Solution
SOLUTION-
#include<stdio.h>
#include<math.h>
int main()
{long long int t,i,n,k;
scanf("%lld",&t);
for(i=1;i<=t;i++)
{ scanf("%lld",&n);
k=sqrt(n);
if(k*k==n)
{ printf("Case %lld: Yes",i);
printf("\n");
}
else
{printf("Case %lld: No",i);
printf("\n");
}
}
}
SUMFOUR - 4 values whose sum is 0 Spoj Solution
SOLUTION-
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int A[4000],B[4000],C[4000],D[4000],d,c,i,j;
unordered_map<int ,int>m1;
m1.reserve(20000000);
for(i=0;i<n;i++)
{ scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
c=A[i]+B[j];
m1[c]++;
}
}
int ans=0;
for( i=0;i<n;i++){
for( j=0;j<n;j++){
d=C[i]+D[j];
if(m1.find(-d)!=m1.end()){
ans+=m1[(-d)];
}
}
}
printf("%d\n",ans);
}
STPAR - Street Parade Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll n,i,x;
while(1){
cin>>n;
stack<ll>s;
ll a[n+100];
if(n==0)
break;
else
{
for(i=1;i<=n;i++)
cin>>a[i];
x=1;
for(i=1;i<=n;i++)
{ if(s.size()>0&&s.top()==x)
{
while(s.top()==x)
{
x++;
s.pop();
if(s.size()==0)
break;
}
s.push(a[i]);
}
else if(a[i]==x)
x++;
else
s.push(a[i]);
}
ll k=s.size();
ll flag=0;
for(i=0;i<k;i++)
{
ll p=s.top();
// cout<<p<<" "<<x;
if(p==x)
x++;
else
{flag=1;
break;
}
s.pop();
}
if(flag==1)
cout<<"no\n";
else
cout<<"yes\n";
}
}
}
SPEED - Circular Track Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{long long int t,a,g,b,r,k;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&a,&b);
g=abs(a-b);
while(b!=0)
{ r=b;
b=a%b;
a=r;
}
k=abs(g/a);
printf("%lld\n",k);
}
}
SPCQ - Gopu and Digits Divisibility Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{
int j,i,x,sum=0;
long long int n,p;
long int k;
scanf("%ld",&k);
for(j=0;j<k;j++)
{
scanf("%lld",&n);
p=n;
for(i=0;;i++)
{
n=p;
sum=0;
while(n!=0)
{
x=n%10;
n=n/10;
sum=sum+x;
}
if(p%sum==0)
{
printf("%lld\n",p);
break;
}
else
p++;
}
}
return 0;
}
TEST - Life, the Universe, and Everything Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{ int a;
while(1)
{
scanf("%d",&a);
if(a==42)
{break;}
else{ printf("%d\n",a);}
}
return 0;
}
STAMPS - Stamps Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{long long int n,m,i,j,t,p,k;
scanf("%lld",&t);
for(k=1;k<=t;k++)
{
scanf("%lld%lld",&m,&n);
long long int a[n],count=0,sum=0;
for(i=0;i<n;i++)
scanf("%lld",&a[i]);
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]<a[j+1])
{
p=a[j+1];
a[j+1]=a[j];
a[j]=p;
}
}
}
for(i=0;i<n;i++)
{
sum=sum+a[i];
count++;
if(sum>=m)
{
printf("Scenario #%lld:\n",k);
printf("%lld\n",count);
printf("\n");
break;
}
}
if(sum<m)
{
printf("Scenario #%lld:\n",k);
printf("impossible\n");
printf("\n");
}
}
}
SHAKTI - SHAKTIMAN AND KILWISH Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{ int i;
long long int k,n;
scanf("%lld",&k);
for(i=0;i<k;i++)
{
scanf("%lld",&n);
if(n%2==0)
{
printf("Thankyou Shaktiman\n");
}
else
{
printf("Sorry Shaktiman\n");
}
}
}
SEUG - Seetha’s Unique Game Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{
int t,a[100000],l,b,q,h,w,i,j,k,n,temp;
scanf("%d",&q);
while(q--)
{
scanf("%d%d%d%d",&l,&b,&h,&w);
int count =0,sum=0;
k=h-w;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]<a[j+1])
{t=a[j+1];
a[j+1]=a[j];
a[j]=t;
}
}
}
for(i=0;i<n;i++)
{
sum=sum+a[i];
count++;
if(sum>k)
{
break;
}
}
printf("%d\n",count);
}
}
SAMER08F - Feynman Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{
int i,n,k,j;
for(i=0;;i++)
{
scanf("%d",&n);
k=0;
if(n==0)
break;
for(j=0;j<=n-1;j++)
{
k=k+(n-j)*(n-j);
}
printf("%d\n",k);
}
return 0;
}
SAMER08D - DNA Sequences Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ch char
#define vc vector
#define mod 1000000007
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
while(1)
{
ll k;
cin>>k;
if(k==0)
break;
string s1,s2;
cin>>s1>>s2;
int n=s1.length();
int m=s2.length();
int le[1010][1010],dp[1010][1010];
le[0][0]=0;
for(int i=0;i<1010;i++)
dp[i][0]=dp[0][i]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
if(s1[i-1]==s2[j-1])
le[i][j]=le[i-1][j-1]+1;
else
le[i][j]=0;
if(le[i][j]>=k)
{
for(int p=k;p<=le[i][j];p++)
{
dp[i][j]=max(dp[i][j],dp[i-p][j-p]+p);
}
}
}
}
cout<<dp[n][m]<<"\n";
}
}
SAMER08C - Candy Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main() {
while(1)
{ int n,m;
cin>>n>>m;
int ans[n+1];
if(n==0&&m==0)
break;
int a[n+1][m+1],dp[n+1][m+1],f[n+1];
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>a[i][j];
}
for(int i=0;i<n;i++)
{
int ma=INT_MIN;
for(int j=0;j<m;j++)
{
if(j<2)
dp[i][j]=a[i][j];
else
{
dp[i][j]=a[i][j]+max(dp[i][j-1]-a[i][j-1],dp[i][j-2]);
}
ma=max(ma,dp[i][j]);
}
f[i]=ma;
}
int ma=INT_MIN;
for(int i=0;i<n;i++)
{
if(i<2)
ans[i]=f[i];
else
{
ans[i]=f[i]+max(ans[i-1]-f[i-1],ans[i-2]);
}
ma=max(ma,ans[i]);
//cout<<ans[i]<<" ";
}
cout<<ma<<"\n";
}
}
SABBIRGAME - Sabbir and Game Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll t,n,i,k,sum;
cin>>t;
while(t--)
{
cin>>n;
k=-1;
ll a[n+100];
ll flag=0;
ll sum=0,s=0;
for(i=0;i<n;i++)
{cin>>a[i];
s+=a[i];
if(s<=0)
{
sum+=(s-1);
s=1;
// cout<<sum<<"\n"<<i<<"\n";
flag=1;
}
}
if(sum>0||flag==0)
cout<<"0\n";
else
cout<<((abs(sum)))<<"\n";
}
}
ROOTCIPH - Decipher Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{int t;
long long int z,a,b,k,l,c;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&a,&b,&c);
k=-a;
l=b;
z=k*k-2*l;
printf("%lld\n",z);
}
}
RENT - Rent your airplane and make money Spoj Solution
Solution-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ch char
#define vc vector
#define mod 1000000007
struct sa
{
ll st,en,pr;
};
ll n;
bool compare(sa s1,sa s2)
{
return s1.en<s2.en;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t,y;cin>>t;
while(t--)
{
cin>>n;
sa a[n];
ll dp[n];
for(int i=0;i<n;i++)
{
cin>>a[i].st>>y>>a[i].pr;
a[i].en=y+a[i].st;
}
sort(a,a+n,compare);
ll ans=INT_MIN;
for(int i=0;i<n;i++)
{
dp[i]=a[i].pr;
ll ma=dp[i];
for(int j=0;j<i;j++)
{
if(a[j].en<=a[i].st)
ma=max(ma,dp[i]+dp[j]);
}
dp[i]=max(ma,dp[i]);
ans=max(dp[i],ans);
}
cout<<ans<<"\n";
}
}
REAYZCODETST - Coding Test Spoj Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll t,n,k;
cin>>t;
for(ll j=1;j<=t;j++)
{
map<ll,ll>mp;
cin>>n>>k;
ll a[n+10];
for(ll i=0;i<n;i++)
{
cin>>a[i];
mp[a[i]]++;
}
ll sum=0;
for(ll i=0;i<n;i++)
{
ll r=(k+a[i]);
if(k==0)
{
sum+=mp[r]-1;
}
else
sum+=mp[r];
}
cout<<"Case "<<j<<": "<<sum<<"\n";
}
}
RCB - Richest_Beggar Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
void update(ll D[],ll x,ll y)
{
D[x-1]+=1;
D[y]-=1;
}
int main() {
ll n,k,x,y,i;
cin>>n>>k;
ll a[n]={0};
ll D[n]={0};
while(k--)
{ cin>>x>>y;
update(D,x,y);
}
ll ma=INT_MIN;
vector<ll>v;
for(i=0;i<n;i++)
{
if(i==0)
{a[i]=D[i];
}
else
a[i]=D[i]+a[i-1];
if(a[i]>ma)
ma=a[i];
}
for(i=0;i<n;i++)
{v.push_back(a[i]);
}
sort(v.begin(),v.end(),greater<ll>());
cout<<v[0]<<"\n";
for(i=0;i<n;i++)
{
if(a[i]==v[0])
cout<<i+1<<" ";
}
cout<<"\n";
}
QUADAREA - Maximal Quadrilateral Area Spoj Solution
SOLUTION-
#include <stdio.h>
#include<math.h>
int main(void)
{
double a,b,c,d,k,s;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
s=(a+b+c+d)/2;
k=sqrt((s-a)*(s-b)*(s-c)*(s-d));
printf("%0.2lf\n",k);
}
}
PT07Y - Is it a tree Spoj Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ch char
#define vc vector
#define mod 1000000007
bool visited[100000];
vector<int>adj[100000];
void dfs(int src)
{
visited[src]=true;
for(auto u:adj[src])
{
if(!visited[u])
dfs(u);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,m,a,b;
cin>>n>>m;
for(int i=0;i<m;i++)
{
cin>>a>>b;
a--;
b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
int ct=0;
for(int i=0;i<n;i++)
{
if(!visited[i])
{
dfs(i);
ct++;
}
}
if(ct==1&&m==n-1)
cout<<"YES";
else
cout<<"NO";
}
PRIME1 - Prime Generator Spoj Solution
SOLUTION-
#include<stdio.h>
#include<math.h>
int main()
{int t;
long long int l,h,i,flag;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&l,&h);
while(l<=h)
{
flag=0;
for(i=2;i<=sqrt(l);i++)
{ if(l%i==0)
{
flag=1;
break;
} }
if(flag==0)
{ if(l!=1)
printf("%lld\n",l);
}
l++;
}
printf("\n");
}
return 0;
}
PRADIPSUM - Easy Math Spoj Solution
#include<stdio.h>
int main()
{ long long int a,b,i,sum=0,temp=0;
while(scanf("%lld%lld",&a,&b)!=EOF)
{ sum=0;
if(a>b)
{
temp=a;
a=b;
b=temp;
}
for(i=a;i<=b;i++)
sum=sum+i;
printf("%lld\n",sum);
fflush(stdin);
}
return 0;
}
PKPLOL - Lord of Light Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{ int i,k,a;
scanf("%d",&k);
for(i=1;i<=k;i++)
{
scanf("%d",&a);
switch (a)
{
case 0:
printf("Case %d: abcdef\n",i);
break;
case 1:
printf("Case %d: bc\n",i);
break;
case 2:
printf("Case %d: abdeg\n",i);
break;
case 3:
printf("Case %d: abcdg\n",i);
break;
case 4:
printf("Case %d: bcfg\n",i);
break;
case 5:
printf("Case %d: acdfg\n",i);
break;
case 6:
printf("Case %d: acdefg\n",i);
break;
case 7:
printf("Case %d: abc\n",i);
break;
case 8:
printf("Case %d: abcdefg\n",i);
break;
case 9:
printf("Case %d: abcdfg\n",i);
break;
}}
return 0;
}
ONP - Transform the Expression Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
void inf(string s)
{
stack<char>st;
int l=s.length();
string ns;
for(int i=0;i<l;i++)
{
if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z'))
{
ns+=s[i];
}
else if(s[i]=='(')
st.push('(');
else if(s[i]==')')
{
while(!st.empty()&&st.top()!='(')
{
char c=st.top();
st.pop();
ns+=c;
}
if(st.top()=='(')
{
//char c=st.top();
st.pop();
}
}
else
{//=st.top();
while(!st.empty()&&prec(s[i])<=prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
// pp=st.top();
}
st.push(s[i]);
}
}
while(!st.empty())
{
char c = st.top();
st.pop();
ns += c;
}
cout<<ns<<"\n";
}
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
inf(s);
// return 0;
}
return 0;
}
OLOLO - Onotole needs your help Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll int
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n,i;
scanf("%d",&n);
ll a[n+100];
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
for(i=0;i<n;i+=2)
{
if(a[i]!=a[i+1])
{
printf("%d",a[i]);
break;
}
}
}
NY10A - Penney Game Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{char a[100];
int t,i,k,b,c,d,e,f,g,j,h,p;
scanf("%d",&t);
while(t--)
{
scanf("%d",&j);
scanf("%s",a);
int k=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0;
for(i=0;i<38;i++)
{
if(a[i]=='T' && a[i+1]=='T' && a[i+2]=='T')
k++;
else if(a[i]=='T' && a[i+1]=='T' && a[i+2]=='H')
b++;
else if(a[i]=='T' && a[i+1]=='H' && a[i+2]=='T')
c++;
else if(a[i]=='T' && a[i+1]=='H' && a[i+2]=='H')
d++;
else if(a[i]=='H' && a[i+1]=='T' && a[i+2]=='T')
e++;
else if(a[i]=='H' && a[i+1]=='T' && a[i+2]=='H')
f++;
else if(a[i]=='H' && a[i+1]=='H' && a[i+2]=='T')
g++;
else if(a[i]=='H' && a[i+1]=='H' && a[i+2]=='H')
h++;
}
printf("%d %d %d %d %d %d %d %d %d\n",j,k,b,c,d,e,f,g,h);
}
return 0;
}
NAKANJ - Minimum Knight moves !!! Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main() {
// vector<int>adj[10];
int t,i,j;
cin>>t;
while(t--)
{ string s1,s2;
cin>>s1>>s2;
int lev[9][9];
for(i=1;i<=8;i++)
{ //fill(lev[i]+1,lev[i]+9,1e4);
for(j=1;j<=8;j++)
lev[i][j]=10000;
}
int x1=int(s1[0])-96;
int y1=int(s1[1])-'0';
int x2=int(s2[0])-96;
int y2=int(s2[1])-'0';
// cout<<x2<<y2;
queue<pair<int,int>>q;
q.push({x1,y1});
lev[x1][y1]=0;
while(!q.empty())
{
pair<int,int>pr=q.front();
int x=pr.first,y=pr.second;
// if(x==x2&&y==x2)break;
q.pop();
if(x>0&&x<9&&y>0&&y<9){
if(x+1>0&&x+1<9&&y-2>0&&y-2<9&&(lev[x+1][y-2]>(lev[x][y]+1))){
q.push(make_pair(x+1,y-2));
lev[x+1][y-2]=min(lev[x][y]+1,lev[x+1][y-2]);}
if(x+1>0&&x+1<9&&y+2>0&&y+2<9&&(lev[x+1][y+2]>lev[x][y]+1)){
q.push(make_pair(x+1,y+2));
lev[x+1][y+2]=min(lev[x][y]+1,lev[x+1][y+2]);}
if(x-1>0&&x-1<9&&y-2>0&&y-2<9&&lev[x-1][y-2]>lev[x][y]+1){
q.push(make_pair(x-1,y-2));
lev[x-1][y-2]=min(lev[x][y]+1,lev[x-1][y-2]);}
if(x-1>0&&x-1<9&&y+2>0&&y+2<9&&lev[x-1][y+2]>lev[x][y]+1){
q.push(make_pair(x-1,y+2));
lev[x-1][y+2]=min(lev[x][y]+1,lev[x-1][y+2]);}
if(x+2>0&&x+2<9&&y-1>0&&y-1<9&&lev[x+2][y-1]>lev[x][y]+1){
q.push(make_pair(x+2,y-1));
lev[x+2][y-1]=min(lev[x][y]+1,lev[x+2][y-1]);}
if(x+2>0&&x+2<9&&y+1>0&&y+1<9&&lev[x+2][y+1]>lev[x][y]+1){
q.push(make_pair(x+2,y+1));
lev[x+2][y+1]=min(lev[x][y]+1,lev[x+2][y+1]);}
if(x-2>0&&x-2<9&&y-1>0&&y-1<9&&lev[x-2][y-1]>lev[x][y]+1){
q.push(make_pair(x-2,y-1));
lev[x-2][y-1]=min(lev[x][y]+1,lev[x-2][y-1]);}
if(x-2>0&&x-2<9&&y+1>0&&y+1<9&&lev[x-2][y+1]>lev[x][y]+1){
q.push(make_pair(x-2,y+1));
lev[x-2][y+1]=min(lev[x][y]+1,lev[x-2][y+1]);
}
}
}
cout<<lev[x2][y2]<<"\n";
}
}
NABILISU - Billing Issue Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{ int t,k,i;
long int a,b;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%ld%ld%d",&a,&b,&k);
if(a>b && a==b+k)
{
printf("Case %d: YES\n",i);
}
else
{
printf("Case %d: NO\n",i);
}
}
}
SYNC13C - WHAT A CO-ACCIDENT Spoj Solution
SOLUTION-
#include <stdio.h>
int main(void)
{
long long int a,b,t;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&a,&b);
if(a%2==0&&b%2==0)
printf("Suresh\n");
else if(a%2!=0&&b%2!=0)
printf("Ramesh\n");
else
printf("Suresh\n");
}
}
PIGBANK - Piggy-Bank Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ch char
#define vc vector
#define mod 1000000007
struct sa
{
int m,w;
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t,e,f,n;
cin>>t;
while(t--)
{
cin>>e>>f>>n;
f-=e;
sa arr[n
+100];
int dp[f+100];
for(int i=0;i<n;i++)
{
cin>>arr[i].m>>arr[i].w;
}
dp[0]=0;
for(int i=1;i<=f;i++)
{
dp[i]=0;
int ma=INT_MAX;
for(int j=0;j<n;j++)
{
if(i>=arr[j].w)
{
int k=i-arr[j].w;
if(k>=0&&dp[k]!=-1)
ma=min(ma,arr[j].m+dp[k]);
}
}
if(ma==INT_MAX)
dp[i]=-1;
else
dp[i]=ma;
}
// for(int i=1;i<=f;i++)
// cout<<i<<" "<<dp[i]<<"\n";
if(dp[f]<0)
cout<<"This is impossible.\n";
else
{
cout<<"The minimum amount of money in the piggy-bank is "<<dp[f]<<"."<<"\n";
}
}
}
OPCPIZZA - Pizzamania Spoj Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{int t,n,k,start,last,mid,x,count,i;
cin>>t;
while(t--)
{
cin>>n>>k;
int a[n+1000];
for(i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
count=0;
for(i=0;i<n;i++)
{
x=k-a[i];
start=0;
last=n-1;
while(start<=last)
{
mid=(start+last)/2;
if(a[mid]==x)
{
count++;
break;
}
else if(x>a[mid])
{
start=mid+1;
}
else
{
last=mid-1;
}
}
}
cout<<(count)/2<<"\n";
}
}
MSCHED - Milk Scheduling Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
struct Job
{
int profit,deadline;
};
bool Compare(Job s1,Job s2)
{
return s1.profit>s2.profit;
}
void Select(Job a[],int n)
{
sort(a,a+n,Compare);
int slot[n];
for(int i=0;i<n;i++)
slot[i]=false;
int sum=0;
for(int i=0;i<n;i++)
{
for(int j=min(n,a[i].deadline)-1;j>=0;j--)
{
if(slot[j]==false)
{
sum=sum+a[i].profit;
slot[j]=true;
break;
}
}
}
cout<<sum;
}
int main() {
int n,i;
cin>>n;
Job a[n];
for(i=0;i<n;i++)
{
cin>>a[i].profit>>a[i].deadline;
}
Select(a,n);
}
MINSTACK - Smallest on the Stack Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main() {
int t,n,m;
char s[100];
stack<int>s1;
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
if(s[1]=='U')
{scanf("%d",&n);
if(s1.empty())
{
s1.push(n);
m=n;
}
else if(n<m){
s1.push(2*n-m);
m=n;
}
else
s1.push(n);
}
else if(s[1]=='O')
{ if(s1.empty()){
printf("EMPTY\n");
}
else{
int h=s1.top();
s1.pop();
if (h< m)
{
m= 2*m- h;
}
}}
else
{ if(s1.empty()){
printf("EMPTY\n");
}
else
printf("%d\n",m);
}
}
}
MCOINS - Coins Game Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll k,l,n;
cin>>k>>l>>n;
ll a[1000000],p[n+100];
ll ma=INT_MIN;
for(int i=0;i<n;i++)
{
cin>>p[i];
ma=max(p[i],ma);
}
a[0]=0;
a[1]=1;
int flag=0;
for(int i=2;i<=ma;i++)
{
if(a[i-1]==0)
flag=1;
if(i>=k&&a[i-k]==0)
flag=1;
if(i>=l&&a[i-l]==0)
flag=1;
if(flag==1){
a[i]=1;
flag=0;
}
else{
a[i]=0;
flag=1;
}
}
for(int i=0;i<n;i++)
{
if(a[p[i]]==1)
cout<<"A";
else
cout<<"B";
}
//cout<<a[p[i]];
}
MAXLN - THE MAX LINES Spoj Solution
SOLUTION-
#include<stdio.h>
#include<math.h>
int main()
{int t,i;
long long int r;
double s;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%lld",&r);
s=(4*r*r)+0.25;
printf("Case %d: %0.2lf",i,s);
printf("\n");
}
}
MANGOES - Real Mangoes for Ranjith Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main()
{ long long int t,n,s,j,k,a,p,l;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&j);
l=j-2;
if(l%2==0)
{
n=l/2;
s=n*n;
}
else
{
n=(l/2)+1;
s=n*n;
}
p=s%j;
printf("%lld\n",p);
}
}
MAJOR - Majority Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main() {
int t,n,i,count,m;
cin>>t;
while(t--)
{
cin>>n;
int a[n+100];
for(i=0;i<n;i++)
{
cin>>a[i];
}
m=0;
count=1;
for(i=1;i<n;i++)
{
if(a[m]==a[i])
count++;
else
count--;
if(count==0)
{
m=i;
count=1;
}
}
int count1=0;
for(i=0;i<n;i++)
{
if(a[i]==a[m])
count1++;
}
if(count1>n/2)
{
printf("YES %d\n",a[m]);
}
else
printf("NO\n");
}
}
LENGFACT - Factorial length Spoj Solution
SOLUTION-
#include<stdio.h>
#include<math.h>
int main()
{
int t;
long long int ans,n;
scanf("%d",&t);
while(t--)
{
ans=0;
scanf("%lld",&n);
if(n<3)
printf("1\n");
else{
ans=ceil(log10(2*3.141592653589793*n)/2 + n*log10(n/2.7182818284590452353));
printf("%lld\n",ans);
}
}
return 0;
}
LASTDIG - The last digit Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll powe(ll a,ll b,ll x)
{
if(a==0)
{
return 0;
}
if(b==0)
{
return 1;
}
else
{
if(b%2==0)
{
return (powe(a,b/2,x)%x*powe(a,b/2,x)%x)%x;
}
else
{
return (a%x*powe(a,b/2,x)%x*powe(a,b/2,x)%x)%x;
}
}
}
int main() {
ll t,a,b;
cin>>t;
while(t--)
{
ll x=10;
cin>>a>>b;
ll k=powe(a,b,x);
cout<<k<<"\n";
}
}
JC15A - Windy Cannon Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{
char wd;
int cp,tp,cbs,ws;
double t;
scanf("%d%d%d%d %c",&cp,&tp,&cbs,&ws,&wd);
if(cp>tp)
{
if(wd=='L')
{
t=(double)(cp-tp)/(cbs+ws);
printf("%0.6lf",t);
}
else
{
if(ws>cbs)
{
printf("Impossible");
}
else
{
t=(double)(cp-tp)/(cbs-ws);
printf("%0.6lf",t);
}
}
}
else if(cp<tp)
{
if(wd=='L')
{
if(ws>cbs)
{ printf("Impossible");
}
else
{
t=(double)(tp-cp)/(cbs-ws);
printf("%0.6lf",t);
}
}
else
{
t=(double)(tp-cp)/(cbs+ws);
printf("%0.6lf",t);
}
}
else
printf("0.000000");
}
IITKWPCN - Playing With Balls Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{long long int t,n,m;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
if(n==m)
{
if(n%2==0&&m%2==0)
printf("0.000000\n");
else
printf("1.000000\n");
}
else if(n>m)
{
if(n%2!=0&&m%2!=0)
printf("1.000000\n");
else if(n%2!=0&&m%2==0)
printf("0.000000\n");
else if(n%2==0&&m%2==0)
printf("0.000000\n");
else if(n%2==0&&m%2!=0)
printf("1.000000\n");
}
else if(n<m)
{
if(m%2!=0)
printf("1.000000\n");
else
printf("0.000000\n");
}
}
}
IIITD1 - Those College Days! Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll t;
cin>>t;
while(t--)
{ string s,k;
cin>>s;
//cout<<int(s[0]-48);
if(s[0]!='-'){
cout<<"1";
for(ll i=0;i<s.length()-1;i++)
{
cout<<"0";
}}
else
{
k+='1';
for(ll i=0;i<s.length()-2;i++)
{
k+='0';
}
ll p=stoi(s);
ll j=stoi(k);
ll y=abs(p)+j;
//cout<<y<<endl;
cout<<(y-p)<<endl;
}
cout<<endl;
}
}
ICANDIES - Candies Spoj Solution
SOLUTION-
#include <iostream>
using namespace std;
#define ll long long int
int main() {ll t,i,j,n;
cin>>t;
for(j=1;j<=t;j++)
{
cin>>n;
ll flag=0;
for(i=n-5;i>=1;i--)
{
if(i%3==0&&(n-i)%5==0)
{
printf("Case %lld: %lld\n",j,i);
flag=1;
break;
}
}
if(flag==0)
{
printf("Case %lld: -1\n",j);
}
}
}
HOTELS - Hotels Along the Croatian Coast Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main()
{int n,k,i,r;
cin>>n>>k;
int a[n+100];
for(i=0;i<n;i++)
{
cin>>a[i];
}
int sum=0,j=0;
r=INT_MIN;
for(i=0;i<n;i++)
{
sum=sum+a[i];
if(sum>k&&j<n)
{
while(sum>k)
{
sum=sum-a[j];
j++;
if(sum<=k)
{
r=max(sum,r);
}
}
}
else
r=max(sum,r);
}
cout<<r;
}
HMBY - Hablu Wants to Buy Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{long long int a,b,c,d,e,x,w;
scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e,&w);
x=a*2+b*4+c*8+d*16+e*32;
if(w%2==0 && w<x)
printf("YES");
else
printf("NO");
}
HLP_RAMS - Topper Rama Rao Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main() {
long long int t,n,a,b,c,count;
cin>>t;
while(t--){
cin>>n;
b=n;
if(n==0)
cout<<"0 1\n";
else{
count=0;
while(n>0)
{
if(n&1==1)
count++;
n=n>>1;
}
a=pow(2,count);
c=b-a;
cout<<(c+1)<<" "<<a<<endl;
}
}
}
HISTOGRA - Largest Rectangle in a Histogram Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main()
{long long int n,i,area,max,tp;
while(1)
{
stack<int>s;
cin>>n;
if(n==0)
break;
else
{
long long int a[n+1000];
for(i=0;i<n;i++)
{
cin>>a[i];
}
i=0,max=-1;
while(i<n)
{
if(s.empty()||a[i]>=a[s.top()])
s.push(i++);
else
{
tp=s.top();
s.pop();
area=a[tp]*(s.empty()?i:(i-s.top()-1));
if(area>max)
{
max=area;
}
}
}
while(!s.empty())
{
tp = s.top();
s.pop();
area = a[tp] * (s.empty() ? i :i - s.top() - 1);
if(area>max)
{
max=area;
}
}
cout<<max<<"\n";
}
}
}
HC - Happy Coins Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main()
{int t,n,i,count;
cin>>t;
while(t--)
{
cin>>n;
char s[n+100];
char s1[]="lxh";
count=0;
for(i=0;i<n;i++)
{
cin>>s;
if(strcmp(s,s1)==0)
count++;
}
if(count%2!=0)
{
cout<<"lxh"<<"\n";
}
else
{
cout<<"hhb"<<"\n";
}
}
}
HARISH_PUZZLE - Harish and his rooks puzzle Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll t,i,j;
cin>>t;
while(t--)
{ ll row[10];
ll column[10];
memset(row,0,sizeof(row));
memset(column,0,sizeof(column));
ll flag=0,r=0;
for(i=0;i<8;i++)
{ string s;
cin>>s;
for(j=0;j<8;j++)
{
if(s[j]=='R')
{
if(column[j]==1||row[i]==1)
{
//cout<<"YES";
flag=1;
break;
}
else
{
column[j]=1,row[i]=1;
r++;
// cout<<i<<" "<<j<<"\n";
}
}
}
}
//cout<<flag;
if(flag==0&&r==8)
cout<<"YES\n";
else
cout<<"NO\n";
}
}
HANGOVER - Hangover Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{float n,k,i;
int count,j;
while(scanf("%f",&n)!=EOF)
if(n==0)
break;
else
{count=0;
k=0,j=0;
for(i=1;;i++)
{
if((k+1/(i+1))<n)
{
k=k+1/(i+1);
count++;
}
else
break;
}
j=count+1;
printf("%d card(s)\n",j);
}
}
HANGOVER - Hangover Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{float n,k,i;
int count,j;
while(scanf("%f",&n)!=EOF)
if(n==0)
break;
else
{count=0;
k=0,j=0;
for(i=1;;i++)
{
if((k+1/(i+1))<n)
{
k=k+1/(i+1);
count++;
}
else
break;
}
j=count+1;
printf("%d card(s)\n",j);
}
}
HACKRNDM - Hacking the random number generator Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll n,k,x,i,p;
scanf("%lld%lld",&n,&k);
vector<ll>a;
for( i=0;i<n;i++){
//scanf("%lld",x);
cin>>x;
a.push_back(x);
}
//for(i=0;i<n;i++)
//cout<<a[i]<<" ";
sort(a.begin(),a.end());
ll count=0;
for(i=0;i<n;i++)
{ p=a[i]+k;
if(binary_search(a.begin(),a.end(),p))
count++;
}
cout<<count;
}
GIRLSNBS - Girls and Boys Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int main()
{double g,b,f;
double x;
while(1)
{
cin>>g>>b;
if(g==-1&&b==-1)
{
break;
}
else
{
if(g>b)
{
x=g/(b+1);
f=ceil(x);
cout<<f<<"\n";
}
else
{
x=b/(g+1);
f=ceil(x);
cout<<f<<"\n";
}
}
}
}
GGD - Mr Toothless and His GCD Operation Spoj Solution
Solution-
#include<stdio.h>
int main()
{ int t,i;
long long int n,k,x;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%lld",&n);
if(n%2==0)
{x=n/2;
printf("Case %d: %lld %lld",i,x,n);
printf("\n");
}
else if(n==1)
{
if(n==1)
printf("Case %d: 0 1",i);
printf("\n");
}
else if(n==3)
{
if(n==3)
printf("Case %d: 2 3",i);
printf("\n");
}
else
{
k=n-1;
x=k/2;
printf("Case %d: %lld %lld",i,x,k);
printf("\n");
}
}
return 0;
}
GERGOVIA - Wine trading in Gergovia Spoj Solution
Solution-
#include <stdio.h>
#include <math.h>
int main(void) {
while(1){
int n;
scanf("%d",&n);
if(n==0)
break;
int i,a[n],j,g;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
long long int s=0;
for(i=0;i<n;i++){
g=abs(a[i]);
s=s+g;
a[i+1]=a[i+1]+a[i];
}
printf("%lld\n",s);
}
return 0;
}
GDCOFTI - Greatest Common Divisor Of Three Integers Spoj Solution
Solution-
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
int findGCD(int arr[], int n)
{
int result = arr[0];
for (int i = 1; i < n; i++)
result = gcd(arr[i], result);
return result;
}
int main()
{ int a,b,c,arr[100],n;
cin>>a>>b>>c;
arr[0]=a;
arr[1]=b;
arr[2]=c;
n=3;
cout << findGCD(arr, n) << endl;
return 0;
}
FUNPROB - Yanu in Movie theatre Spoj Solution
Solution-
#include <stdio.h>
#include<math.h>
int main(void)
{
double k,f,j, n,m;
while(1)
{
scanf("%lf%lf",&n,&m);
if(n==0&&m==0)
{
break;
}
else
{
if(m>=n)
{
f=(m+1-n)/(m+1);
printf("%0.6lf\n",f);
}
else
{
printf("0.000000\n");
}
}
}
}
FENCE1 - Build a Fence Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{
double l,a;
while(scanf("%lf",&l)!=EOF)
{ if(l==0)
break;
else
a=l*l/6.28318;
printf("%0.2lf\n",a);
}
}
FCTRL2 - Small factorials Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int num;
int i,k=0,j,carry=0,arr[1000]={1};
scanf("%d",&num);
for(i=1;i<=num;i++)
{
for(j=0;j<=k;j++)
{
arr[j]=arr[j]*i+carry;
carry=arr[j]/10;
arr[j]=arr[j]%10;
}
while(carry)
{
k++;
arr[k]=carry%10;
carry/=10;
}
}
for(i=k;i>=0;i--)
printf("%d",arr[i]);
printf("\n");
}
return 0;
}
FAVDICE - Favorite Dice Spoj Solution
Solution-
#include <iostream>
using namespace std;
int main()
{int t;
float i,n,k;
scanf("%lld",&t);
while(t--)
{
scanf("%f",&n);
k=0;
for(i=0;i<n;i++)
{
k=k+n/(n-i);
}
printf("%0.2f\n",k);
}
}
FASHION - Fashion Shows Spoj Solution
Solution-
#include<stdio.h>
int main()
{int m[1001],w[1001],i,j,temp,t,n;
scanf("%d",&t);
while(t--)
{ int sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&m[i]);
}
for(i=0;i<n;i++)
{
scanf("%d",&w[i]);
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
if(m[i]>m[j])
{
temp=m[i];
m[i]=m[j];
m[j]=temp;
}
}
for(i=0;i<n-1;i++)
{
for(j=i;j<n;j++)
if(w[i]>w[j])
{
temp=w[i];
w[i]=w[j];
w[j]=temp;
}
}
for(i=0;i<n;i++)
{ sum=sum+m[i]*w[i];
}
printf("%d\n",sum);
}
}
ETF - Euler Totient Function Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ch char
#define vc vector
#define mod 1000000007
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll ans[1000010];
bool vis[1000010];
for(int i=2;i<=1000000;i++)
{
vis[i]=false;
ans[i]=i;
}
for(int i=2;i<=1000000;i++)
{ if(!vis[i])
{
for(int j=i;j<=1000000;j+=i)
{
vis[j]=true;
ans[j]-=ans[j]/i;
}
}
}
ans[0]=1;
ans[1]=1;
ll t;cin>>t;
while(t--)
{
ll n;
cin>>n;
cout<<ans[n]<<"\n";
}
}
ENIGMATH - PLAY WITH MATH Spoj Solution
Solution-
#include<stdio.h>
int main()
{ long long int t,a,b,c,d,m,n,l,x;
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&a,&b);
m=a;
n=b;
while(b!=0)
{
x=a%b;
a=b;
b=x;
}
l=(m*n)/a;
c=l/m;
d=l/n;
printf("%lld %lld",c,d);
printf("\n");
}
}
EKO - Eko Spoj Solution
Solution-
#include<iostream>
using namespace std;
int main()
{ long long int i,n,m,b,e,mid,cut,max,h;
cin>>n>>m;
long long int a[n+100];
for(i=0;i<n;i++)
{
cin>>a[i];
if(a[i]>max)
{
max=a[i];
}
}
b=0;
h=0;
e=max;
while(b<=e)
{
mid=(b+e)/2;
cut=0;
for(i=0;i<n;i++)
{
if(a[i]-mid>0)
{
cut=cut+(a[i]-mid);
}
}
if(cut>m)
{
b=mid+1;
if(mid>h)
{
h=mid;
}
}
else if(cut<m)
{
e=mid-1;
}
else
{
h=mid;
break;
}
}
cout<<h<<"\n";
}
EIGHTS - Triple Fat Ladies Spoj Solution
SOLUTION-
#include<stdio.h>
int main()
{
long long int t,n,k;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
k=192+(n-1)*250;
printf("%lld\n",k);
}
}
EDIST - Edit distance Spoj Solution
SOLUTION-
#include <bits/stdc++.h>
using namespace std;
int min(int x,int y,int z)
{
return min(min(x,y),z);
}
int edit(string str1,string str2,int m,int n)
{
int dp[3000][3000];
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(i==0)
{
dp[i][j]=j;
}
else if(j==0)
{
dp[i][j]=i;
}
else if(str1[i-1]==str2[j-1])
{
dp[i][j]=dp[i-1][j-1];
}
else
{
dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]);
}
}
}
return dp[m][n];
}
int main()
{ int t,p,q;
char str1[3000],str2[3000];
cin>>t;
while(t--)
{
cin>>str1;
cin>>str2;
p=strlen(str1);
q=strlen(str2);
cout<<edit(str1,str2,p,q)<<"\r\n";
}
}
DQUERY - D-query Spoj Solution
SOLUTION-
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define str string
#define pb push_back
#define vc vector
#define ci cin
#define co cout
#define blk 555
// remove fropen in online judge
struct sa
{
ll l,r,idx;
};
bool comp(sa s1,sa s2)
{
if(s1.l/blk==s2.l/blk)
return s1.r<s2.r;
return s1.l/blk<s2.l/blk;
}
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
// freopen("error.txt","w",stderr);
// #endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
ll fr[1000000]={0};
ll a[n];
for(int i=0;i<n;i++)
cin>>a[i];
ll q;
cin>>q;
sa qu[q];
for(int i=0;i<q;i++)
{
cin>>qu[i].l>>qu[i].r;
qu[i].l--;
qu[i].r--;
qu[i].idx=i;
}
sort(qu,qu+q,comp);
ll ct=0;
ll ans[q];
ll lp=0,rp=-1;
for(int i=0;i<q;i++)
{
ll L=qu[i].l;
ll R=qu[i].r;
ll id=qu[i].idx;
while(rp<R)
{
rp++;
fr[a[rp]]++;
if(fr[a[rp]]==1)
ct++;
// rp++;
}
while(lp>L)
{
lp--;
fr[a[lp]]++;
if(fr[a[lp]]==1)
ct++;
//lp--;
}
while(rp>R)
{
//rp--;
fr[a[rp]]--;
if(fr[a[rp]]==0)
ct--;
rp--;
}
while(lp<L)
{ //lp++;
fr[a[lp]]--;
if(fr[a[lp]]==0)
ct--;
lp++;
}
// cout<<id<<" "<<ct<<"";
ans[id]=ct;
}
for(int i=0;i<q;i++)
cout<<ans[i]<<"\n";
}
DOL - Largest Odd Divisor Spoj Solution
Solution-
#include <iostream>
using namespace std;
#define ll long long int
int main() {
ll t,i,j,n,x;
cin>>t;
for(j=1;j<=t;j++){
cin>>n;
if(n%2!=0)
{cout<<"Case "<<j<<": "<<n;
cout<<endl;}
else
{ while(n%2==0)
{
n=n/2;
}
cout<<"Case "<<j<<": "<<n;
cout<<endl;
}
}
}
DIGOKEYS - Find the Treasure Spoj Solution
Solution-
#include <bits/stdc++.h>
using namespace std;
void addEdge(int a,int b,vector<int>adj[])
{
adj[a].push_back(b);
}
int main() {
int t,i,j,n,m;
cin>>t;
while(t--)
{
cin>>n;
vector<int>adj[n+1];
for(i=1;i<=n-1;i++)
{
scanf("%d",&m);
int b[m+10];
for(j=0;j<m;j++)
{
scanf("%d",&b[j]);
}
sort(b,b+m);
for(j=0;j<m;j++)
{
addEdge(i,b[j],adj);
}
}
int parent[n+1],level[n+1];
bool visited[n+1];
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++)
level[i]=INT_MAX;
queue<int>q;
q.push(1);
parent[1]=1;
level[1]=0;
// cout<<adj[3].size();
int flag=0;
while(!q.empty())
{
int x=q.front();
visited[x]=true;
q.pop();
if(x==n)
{
flag=1;
break;
}
for(int i=0;i<adj[x].size();i++)
{ if(adj[x][i]==n)
flag=1;
if(visited[adj[x][i]]==false&&level[adj[x][i]]>(level[x]+1))
{
//cout<<adj[x][i]<<" ";
parent[adj[x][i]]=x;
q.push(adj[x][i]);
level[adj[x][i]]=level[x]+1;
}
}
}
if(flag==1){
vector<int>v;
int x=parent[n];
while(x!=1)
{
v.push_back(x);
x=parent[x];
}
v.push_back(1);
cout<<level[n]<<"\n";
for(int i=v.size()-1;i>=0;i--)
printf("%d ",v[i]);
printf("\n");
}
else
printf("-1\n");
}
}
CUBEFR - Cube Free Numbers Spoj Solution
Solution-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll b[1000000],j;
ll v[1000001];
void sol()
{ memset(b,0,sizeof(b));
for(ll i=2;i*i*i<=1000000;i++)
{ ll y=i*i*i;
if(b[i]==0)
{
for(j=y;j<=1000000;j+=y)
{
b[j]=1;
}
}
}
}
int main() {
ll t;
sol();
ll k=1;
for(ll i=1;i<=1000000;i++)
{
if(b[i]==0)
{
v[i]=k++;
}
}
cin>>t;
for(ll u=1;u<=t;u++)
{ll n;
cin>>n;
if(b[n]==1)
{
cout<<"Case "<<u<<": "<<"Not Cube Free"<<"\n";
}
else
cout<<"Case "<<u<<": "<<v[n]<<"\n";
// cout<<(v[n])<<"\n";
}
}
CRZYSMKR - Crazy Smoker Spoj Solution
SOLUTION-
#include<stdio.h>
#include<math.h>
int main()
{long long int t,n,l,j,k;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
k=30*n+33;
l=k;
while(l%11!=0)
{
l++;
}
j=l-k;
printf("%lld\n",j);
}
}
CRDS - Cards Spoj Solution
Solution-
#include<stdio.h>
int main()
{ long long int t,n,s,k;
scanf("%lld",&t);
while(t--)
{
scanf("%lld",&n);
k=(n-1);
s=2*n+((6+(k-1)*3)*k)/2;
printf("%lld\n",s%1000007);
}
}
COMDIV - Number of common divisors Spoj Solution
Solution-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define lp long double
int main() {
ll t,i;
cin>>t;
while(t--)
{ ll a,b,count=0,n;
scanf("%lld%lld",&a,&b);
n=__gcd(a,b);
for(i=1;i<=sqrt(n);i++)
{ if(n%i==0){
if(n/i==i)
count++;
else
count+=2;
}
}
// cout<<count<<"\n";
printf("%lld\n",count);
}
}
COINS - Bytelandian gold coins Spoj Solution
Solution-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
ll sum=0;
ll find(ll n,ll a[])
{
if(n==0||n==1)
{
a[n]=n;
return n;
}
if(a[n]!=0)
{
return a[n];
}
a[n]=max(find(n/2,a)+find(n/3,a)+find(n/4,a),n);
return a[n];
}
int main() {
ll n;
while(cin>>n){
ll *a=new ll[n+1];
cout<<find(n,a)<<"\n";
}
}
CODCHESS - Naya Shatranj (New Chess) Spoj Solution
SOLUTION-
#include <iostream>
using namespace std;
int main()
{ long long int t,n;
cin>>t;
while(t--)
{
cin>>n;
if(n%2==0)
{
cout<<"1"<<"\n";
}
else
cout<<"0"<<"\n";
}
}
CNTDO - Count Doubles Spoj Solution
Solution-
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main() {
ll t,n,i;
cin>>t;
while(t--)
{
cin>>n;
ll a[n+100];
for(i=0;i<n;i++)
cin>>a[i];
ll count=0;
sort(a,a+n);
for(i=0;i<n;i++)
{ ll x=2*a[i];
if(binary_search(a,a+n,x))
count++;
}
cout<<count<<"\n";
}
}
CIRCLE_E - Three Circle Problem (EASY) Spoj Solution
Solution-
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
int main()
{double a,b,c,t;
double r;
scanf("%lf",&t);
while(t--)
{
scanf("%lf%lf%lf",&a,&b,&c);
if(a>0&&b>0&&c>0)
{ r=a*b*c/(2*sqrt(a*b*c*(a+b+c))+a*b+b*c+c*a);
printf("%lf\n",r);
}
}
}
I really appreciate your support on this.
ReplyDeleteLook forward to hearing from you soon.
I’m happy to answer your questions, if you have any.
คาสิโน
คาสิโน
แจกเครดิตฟรี ฝากถอนง่าย