#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int main() { int n; char s[26]; while (scanf("%d",&n)==1) { if (!n) return 0; int max_x=0; int total_x=0; getchar(); for (int i=0;i<n;i++) { gets(s); int cnt=0; for (int j=0;j<25;j++) { if (s[j]=='X') cnt++; } total_x+=cnt; max_x=max(max_x,cnt); } int ans=max_x*n-total_x; printf("%d\n",ans); } return 0; }
Wednesday, October 5, 2016
UVA 414 - Machined Surfaces Solution
Friday, September 23, 2016
UVA 10101 - Bangla Numbers Solution
#include<cstdio> #include<cstring> using namespace std; int main() { long long int tc=0,n; while (scanf("%lld",&n)!=EOF) { printf("%4lld.",++tc); if (n==0){ printf(" 0\n"); continue;} int a[20]={0},i=14; while (n) { a[i--]=n%10; n/=10; } //printf("%d\n",i); int b=a[0]; if (b) printf(" %d kuti",b); b=a[1]*10+a[2]; if (b) printf(" %d lakh",b); b=a[3]*10+a[4]; if (b) printf(" %d hajar",b); b=a[5]; if (b) printf(" %d shata",b); b=a[6]*10+a[7]; if (b) printf(" %d",b); if (i<7) printf(" kuti"); b=a[8]*10+a[9]; if (b) printf(" %d lakh",b); b=a[10]*10+a[11]; if (b) printf(" %d hajar",b); b=a[12]; if (b) printf(" %d shata",b); b=a[13]*10+a[14]; if (b) printf(" %d",b); printf("\n"); } return 0; }
UVA 11503 - Virtual Friends Solution
#include<iostream> #include<cstdio> #include<string> #include<vector> #include<map> #include<algorithm> using namespace std; class DS{ private: vector<int>parent,rank,setSize; int numSets; public: DS(int n) { numSets=n; parent.assign(n,0); rank.assign(n,0); setSize.assign(n,1); for (int i=0;i<n;i++) parent[i]=i; } int findParent(int i) { return parent[i]==i?i:parent[i]=findParent(parent[i]); } bool isSame(int i,int j) { return findParent(i)==findParent(j);} void unionSet(int x,int y) { int xRoot=findParent(x); int yRoot=findParent(y); if (xRoot==yRoot) return; if (rank[xRoot]>rank[yRoot]) { setSize[xRoot]+=setSize[yRoot]; parent[yRoot]=xRoot; } else { setSize[yRoot]+=setSize[xRoot]; parent[xRoot]=yRoot; if (rank[xRoot]==rank[yRoot]) rank[yRoot]++; } numSets--; } int numDisjointSet(){ return numSets; } int SizeOfSet(int i) { return setSize[findParent(i)]; } }; map<string,int>m; int main() { int testcases; scanf("%d",&testcases); while (testcases--) { int friendships; scanf("%d",&friendships); DS u(friendships*2); m.clear(); string s1,s2; int indexing=0; while (friendships--) { cin>>s1>>s2; if (!m.count(s1)) m[s1]=indexing++; if (!m.count(s2)) m[s2]=indexing++; u.unionSet(m[s1],m[s2]); printf("%d\n",u.SizeOfSet(m[s1])); } } return 0; }
Tuesday, September 20, 2016
Codeforces 716A Solution
#include<bits/stdc++.h> using namespace std; int main() { int n,c; scanf("%d%d",&n,&c); int ans=0; int d=0; while (n--) { int t; scanf("%d",&t); if (t-d>c) ans=1; else ans++; d=t; } printf("%d\n",ans); return 0; }
Wednesday, August 24, 2016
UVA 10009 - All Roads Lead Where - Solution
#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V){this->V=V; adj=new list<int>[V]; } ~Graph() {delete []adj;} void addEdge(int u,int v){adj[u].pb(v); adj[v].pb(u); } void BFS(int s,int dest) { bool visited[V]; int parent[V]; memset(visited,false,sizeof(visited)); list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; parent[s]=s; while (!q.empty()) { s=q.front(); q.pop_front(); for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); parent[*i]=s; visited[*i]=true; if (*i==dest) { print(parent,dest); return; } } } } } void print(int parent[],int dest) { vector<int>path; while (parent[dest]!=dest) { path.pb(dest); dest=parent[dest]; } path.pb(dest); int l=path.size(); for (int i=l-1;i>-1;--i) printf("%C",path[i]+'A'); printf("\n"); } }; int main() { int tc,n,q,s,d; string a,b; scanf("%d",&tc); while (tc--) { Graph g(30); scanf("%d%d",&n,&q); getchar(); while (n--) { cin>>a>>b; s=a[0]-'A'; d=b[0]-'A'; g.addEdge(s,d); } while (q--) { cin>>a>>b; s=a[0]-'A'; d=b[0]-'A'; g.BFS(s,d); } if (tc) printf("\n"); } return 0; }
UVA 924 - Spreading The News- Solution
#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V){this->V=V; adj=new list<int>[V];} ~Graph(){delete []adj;} void addEdge(int u,int v){ adj[u].pb(v);} void BFS(int s) { if (adj[s].size()==0) {printf("0\n"); return;} bool visited[V]; memset(visited,false,sizeof(visited)); int level[V]; int cnt[V]={0}; list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; level[s]=0; int d,m=0; while (!q.empty()) { s=q.front(); q.pop_front(); cnt[level[s]]++; for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); visited[*i]=true; level[*i]=level[s]+1; } } } for (int j=1;j<=level[s];j++) if (m<cnt[j]) { m=cnt[j]; d=j; } printf("%d %d\n",m,d); return; } }; int main() { int e; while (scanf("%d",&e)!=EOF) { Graph g(e); int n,v; for (int i=0;i<e;i++) { scanf("%d",&n); while (n--) { scanf("%d",&v); g.addEdge(i,v); } } int t,s; scanf("%d",&t); while (t--) { scanf("%d",&s); g.BFS(s); } } return 0; }
UVA 762 - We Ship Cheap -Solution
#include<bits/stdc++.h> using namespace std; #define pb push_back map<string,int>msi; map<int,string>mis; class Graph{ int V; list<int>*adj; public: Graph(int V){this->V=V; adj=new list<int>[V]; } ~Graph() {delete []adj;} void addEdge(int u,int v){adj[u].pb(v); adj[v].pb(u); } void BFS(int s,int dest) { bool visited[V]; int parent[V]; memset(visited,false,sizeof(visited)); list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; parent[s]=s; while (!q.empty()) { s=q.front(); q.pop_front(); for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); parent[*i]=s; visited[*i]=true; if (*i==dest) { print(parent,dest); return; } } } } printf("No route\n"); } void print(int parent[],int dest) { vector<int>path; while (parent[dest]!=dest) { path.pb(dest); dest=parent[dest]; } path.pb(dest); int l=path.size(); for (int i=l-1;i>0;--i) cout<<mis[path[i]]<<" "<<mis[path[i-1]]<<endl; } }; int main() { int n,f=0; string a,b; while (scanf("%d",&n)!=EOF) { Graph g(2000); getchar(); int ind=-1; while (n--) { cin>>a>>b; if (msi.find(a)==msi.end()) { msi[a]=++ind; mis[ind]=a; } if (msi.find(b)==msi.end()) { msi[b]=++ind; mis[ind]=b; } g.addEdge(msi[a],msi[b]); } cin>>a>>b; if (f) cout<<endl; if (msi.find(a)==msi.end() || msi.find(b)==msi.end()) printf("No route\n"); else g.BFS(msi[a],msi[b]); f=1; msi.clear(); mis.clear(); } return 0; }
UVA 627 - The Net -Solution
#include<bits/stdc++.h> using namespace std; #define pb push_back class Graph{ int V; list<int>*adj; public: Graph(int V); ~Graph(); void addEdge(int u, int v); void BFS(int s,int dest); }; Graph::Graph(int V) //construtor { this->V=V; adj=new list<int >[V]; } Graph::~Graph() //destructor { delete []adj; } void Graph::addEdge(int u,int v) { adj[u].pb(v); } void Graph::BFS(int s,int dest) { bool visited[V]; int parent[V]; memset(visited,false,sizeof(visited)); list<int>q; list<int>::iterator i; q.pb(s); visited[s]=true; parent[s]=s; while (!q.empty()) { s=q.front(); q.pop_front(); for (i=adj[s].begin();i!=adj[s].end();++i) { if (!visited[*i]) { q.pb(*i); visited[*i]=true; parent[*i]=s; if (*i==dest) { vector<int>path; int t=*i; while (parent[t]!=t) { path.pb(t); t=parent[t]; } path.pb(t); t=path.size(); for (int j=t-1;j>-1;j--) { printf("%d",path[j]); if (j) printf(" "); else printf("\n"); } return; } } } } printf("connection impossible\n"); return; } int main() { int routers; while (scanf("%d",&routers)!=EOF) { Graph g(routers+1); char s[1000]; getchar(); while (routers--) { gets(s); char *pch; pch=strtok(s,"-,"); int id=atoi(pch); pch=strtok(NULL,"-,"); while (pch!=NULL) { int sees=atoi(pch); g.addEdge(id,sees); pch=strtok(NULL,"-,"); } } int m; scanf("%d",&m); printf("-----\n"); while (m--) { int s,dest; scanf("%d%d",&s,&dest); g.BFS(s,dest); } } return 0; }
Subscribe to:
Posts (Atom)