UVAlive Solutions

 

[Solutions]

»7001 – Bus Problem

Posted in Uncategorized | Leave a comment

7001 – Bus Problem

Problem Link

Algorithm:

Kruskal

 

View Code

#include <bits/stdc++.h>
using namespace std;

#define INF 10000000

typedef unsigned long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end()) // for set,map
#define present(c,x) (find(all(c),x) != (c).end()) // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)
#define mx 10010
struct edge{
int u,v,w;
bool operator<(const edge x) const{
return w<x.w; } }e[100010]; int pr[mx]; int find(int r) { if(pr[r]!=r) return pr[r]=find(pr[r]); else return r; } int main() { int t,n,m; cin>>t;
while(t–)
{
for(int i=0;i<=mx;i++) pr[i]=i; ll s=0; cin>>n>>m;
for(int i=0;i<m;i++) { cin>>e[i].u>>e[i].v>>e[i].w;

s+=(1ll*e[i].w);
}

sort(e,e+m);

for(int i=0;i<m;i++)
{
int u=find(e[i].u);
int v=find(e[i].v);
if(u!=v)
{
pr[v]=u;
s-=(1ll)*e[i].w;

}
}
cout<<s<<endl;

}

}

 

Posted in Uncategorized | Leave a comment

CSTREET

Problem Link

Algorithm:

                    Kruskal

 

View Code

#include <bits/stdc++.h>
using namespace std;

#define INF 10000000
//=======================Starts===========================
typedef unsigned long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end())  // for set,map
#define present(c,x) (find(all(c),x) != (c).end())  // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)

//=======================Ends===========================
#define mx 10010
struct edge{
ll u,v,w;

};
bool cmp(edge &a,edge &b)
{
return a.w<b.w;

}
ll pr[mx];
void makeset(ll n)
{
for(ll i=0;i<=n;i++)
pr[i]=i;
}
ll find(ll r)
{
if(pr[r]!=r)
return pr[r]=find(pr[r]);
else return r;

}

vector<edge>e;
ll mst(ll n)
{
ll s=0,c=0;
sort(e.begin(),e.end(),cmp);
makeset(n);
for(ll i=0;i<e.size();i++) { ll u=find(e[i].u); ll v=find(e[i].v); if(u!=v) { pr[v]=u; c++; s+=e[i].w; } if(c==n-1) return s; } return -1; } int main() { ll t,p,n,m; cin>>t;
while(t–)
{
cin>>p>>n>>m;

while(m–){
ll u,v,w;
cin>>u>>v>>w;
edge get;
get.u=u;
get.v=v;
get.w=w;
e.pb(get);
}

ll s=mst(n);
cout<<s*p<<endl;
}

}

 

Posted in Uncategorized | Leave a comment

1232: Coin Change (II)

It’s a classic problem

Ref: Geeksforfgeeks

View code

#include <bits/stdc++.h>
using namespace std;

#define INF 10000000

typedef long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end()) // for set,map
#define present(c,x) (find(all(c),x) != (c).end()) // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)
const int mod=100000007;

int coin;
const int N=10010;
ll dp[N];
int ar[N],m;
int coinchange(int ar[],int m,int n)
{

memset(dp,0,sizeof dp);
dp[0]=1;
for(int i=0;i<m;i++)
for(int j=ar[i];j<=n;j++) dp[j]=(dp[j]+dp[j-ar[i]])%mod; return dp[n]%mod; } int main() { int t,cs=1; cin>>t;
while(t–)
{
cin>>m>>coin;
for(int i=0;i<m;i++) { cin>>ar[i];
}
cout<<“Case “<<cs++<<“: “<<coinchange(ar,m,coin)<<endl;
}

}

 

Similar problem: uva 674

 

Posted in Uncategorized | Leave a comment

275C. k-Multiple Free Set

Problem Link

 

In this problem,a subset consists of some numbers which number is not divisible by k and in the set there will be no number which is multiple of k

First sort all the numbers. Also consider an empty set of integers S, which represents the output. For each integer x in the sequence, If it’s not divisible by k, just pick it and insert it into S. Otherwise if it’s divisible by k check if x / k is in S or not. If it’s not in S insert x into S otherwise skip x.

View Code

 #include <bits/stdc++.h>
using namespace std;
//==========================================================================================================
#define INF 10000000

typedef long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(si ::iterator it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end()) // for set,map
#define present(c,x) (find(all(c),x) != (c).end()) // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)
//==========================================================================================================
si st;

int main()
{
int n,k;
cin>>n>>k;
int a[n];
fr(i,0,n-1)
{int x;
cin>>a[i];
}
sort(a,a+n);

fr(i,0,n-1)
{
if(a[i]%k!=0)
st.insert(a[i]);

else {
int x=a[i]/k;

if(!spresent(st,x))
st.insert(a[i]);

}
}
cout<<st.size()<<endl;
}

 

Posted in Codeforces, Uncategorized | Tagged | Leave a comment

371C Hamburgers

Problem Link

In this problem, it’s very simple problem real life problem

Here,you need to make max number of hamburgers

How to do it :

  Here , first you need to count how many bread ,sausage and cheese will be used to make One Hamburgers and question is how many?

               There is an efficient approach , use binary search to find the amounts 😛

and the cost will be in your budget ,it is a greedy problem 😉

 

View Code

#include<bits/stdc++.h>
using namespace std;
int co=0;

map<char,int>mp;

int main()
{
long long nc,nb,ns,ps,pb,pc,p;

string s;long long mn=0;
cin>>s;
for(int i=0;i<s.size();i++) ++mp[s[i]]; cin>>nb>>ns>>nc;
cin>>pb>>ps>>pc;
cin>>p;
long long mx=1e15;
long long cost;
while(mn+1<mx) { long long md=(mx+mn)>>1;
long long cb=pb*((mp[‘B’]*md>nb)?mp[‘B’]*md-nb:0);

long long cs=ps*((mp[‘S’]*md>ns)?mp[‘S’]*md-ns:0);
long long cc=pc*((mp[‘C’]*md>nc)?mp[‘C’]*md-nc:0);

cost=cs+cb+cc;
if(cost<=p) mn=md;
else mx=md;
}

cout<<mn<<endl;

}

 

Posted in Uncategorized | Leave a comment

0-1 Knapsack Problem / UVa 10130

It’s a well known greedy algorithm, if you are not known with this algo,

You can go through a tutorial ,here is the link

Click this

If you are from bangladesh-flag-3d-icon-16 ,then you should go to Shafaet vaiya’s blog , click it

Implementation of this algorithm

http://www.geeksforgeeks.org/dynamic-programming-set-10-0-1-knapsack-problem/

Now  solution of Supersale

 

View Code

#include
using namespace std;

int knapsack(int W,int wt[],int val[],int n)
{
int i,j;
int k[n+1][W+1];
for(int i=0;i<=n;i++)
{
for(int w=0;w<=W;w++)
{
if(i==0 ||w==0)
k[i][w]=0;
else if(wt[i-1]<=w) k[i][w]=max(val[i-1]+k[i-1][w-wt[i-1]],k[i-1][w]); else k[i][w]=k[i-1][w]; }   } return k[n][W];   }   int main() { int t; cin>>t;
while(t–){

int m,W=-1;

cin>>m;
long long res=0;
int wt[m],val[m];
for(int i=0;i<m;i++) cin>>val[i]>>wt[i];
int n=0;
cin>>n;
while(n–)
{

cin>>W;
res+=knapsack(W,wt,val,m);
}

cout<<res<<endl;

}
}

 

  • Same Problem

→  The Knapsack

Large Knapsack

And more

A

 

Posted in Uncategorized, uva | Tagged , | Leave a comment