|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <iostream> #include <cstdio> #include <fstream> #define INF 100000000 #define ll long long using namespace std; int m,n,MX; int main() { int tt; ll dp; int MN_Rem,MXR; while(scanf("%d%d%d",&m,&n,&tt)!=EOF) { if(m>tt && n>tt) { cout<<0<<" "<<tt<<"\n"; continue; } MX =0; bool f =false; MN_Rem = INF; MXR = 0; for(int i=0;i<=10005;i++) { for(int j=0;j<=10005;j++) { dp =tt-(i*m+j*n); if(i==0 && j==0) continue; if(dp<0)//dp[i][j] break; if(dp==0)//dp[i][j] { if(MX<(i+j)) MX = i+j; f=1; } if(dp>0)//dp[i][j] { if(dp<MN_Rem)//dp[i][j] { MN_Rem = dp;//dp[i][j] MXR = i+j; } else if(dp==MN_Rem)//dp[i][j] { if(MXR<(i+j)) MXR = i+j; } } }//2nd for }//1st for if(f) cout<<MX<<"\n"; else cout<<MXR<<" "<<MN_Rem<<"\n"; } //out.close(); } |
Month: January 2015
793
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <string.h> #include <vector> #include <cstdio> #define SZ 1000001 using namespace std; int par[SZ]; void init() { for(int i=0;i<SZ;i++) par[i]=i; } int find(int a) { if(par[a]==a) return a; else return find(par[a]); } int main() { int t; int n,a,b; int Ycnt,Ncnt; char cmnd,ch; bool f=false; cin>>t; getchar(); while(t--) { cin>>n; init(); getchar(); Ycnt=0; Ncnt=0; while((cmnd=getchar()) && isalpha(cmnd)) { //scanf("%d %d",&a,&ch,&b); getchar(); cin>>a; getchar(); cin>>b; getchar(); int p =find(a); int pp = find(b); if(cmnd=='c') { par[p]=pp; //par[a]=b; } else { if(p==pp) Ycnt++; else Ncnt++; } } if(f) cout<<"\n"; f=1; cout<<Ycnt<<","<<Ncnt<<"\n"; } return 0; } |
280
This also can be solved using bfs or dfs.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#include <iostream> #include <string.h> #include <vector> #define INF 1000000000 using namespace std; int gr[105][105]; int n,from,to; int tt; vector<int> vb; void init() { for(int i=0;i<105;i++) for(int j=0;j<105;j++) { gr[i][j]=INF; } } void floyd() { for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(gr[i][j]>gr[i][k]+gr[k][j]) gr[i][j] = gr[i][k]+gr[k][j]; } } } } int main() { int ch; while(cin>>n) { if(n==0) break; init(); while(cin>>from) { if(from==0) break; while(cin>>to) { if(to==0) break; gr[from][to]=1; } } floyd(); cin>>tt; while(tt--) { cin>>ch; vb.clear(); for(int x=1;x<=n;x++) if(gr[ch][x]==INF) vb.push_back(x); cout<<vb.size(); for(int x=0;x<vb.size();x++) cout<<" "<<vb[x]; cout<<"\n"; } } return 0; } |
10313
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
#include <iostream> #include <string> #include <sstream> #define ll long long using namespace std; ll ways[400][400]; ll findways(int a,int b) { ll r=0; if(ways[a][b]!=-1) return ways[a][b]; if(a==0) return 1; else { r = 0; for(int i=b;i>=1;i--) if(a-i>=0) { r+=findways(a-i,i); //ways[a-i][i]=r; } ways[a][b]=r; } return r; } int main() { int a[3],b,c,n; string s; stringstream ss; for(int i=0;i<400;i++) for(int j=0;j<400;j++) ways[i][j]=-1; while(getline(cin,s)) { int k=0; //getline(cin,s); ss.clear(); ss<<s; while(ss>>n) { if(n>300) n=300; a[k++]=n; } if(k==1) { cout<<findways(a[0],a[0])<<"\n"; } if(k==2) { cout<<findways(a[0],a[1])<<"\n"; } else if(k==3) { cout<<findways(a[0],a[2])-findways(a[0],a[1]-1)<<"\n"; } } return 0; } |
260
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
#include <iostream> #include <map> #include <stack> #include <queue> #include <string> #include <cstring> #define INF 1000000000 using namespace std; string row[205]; bool trace[205][205]; int N; struct node{ int x; int y; }; int floodFillDfs(node a) { //stack<node> s; queue<node> s; map<int,int> mp; s.push(a); int i,j; int r =0; while(!s.empty()) { node t= s.front();//s.top(); s.pop(); i=t.x; j=t.y; if(i>=N || i<0) continue; if(j>=N || j<0) continue; if(trace[i][j]) continue; trace[i][j]=1; if(row[i][j]=='w') { mp[j]=1; //cout<<"ij = "<<i<<" "<<j<<"\n"; } t.x =i-1; t.y = j; if(row[i][j]=='w') s.push(t); t.x =i-1; t.y = j-1; if(row[i][j]=='w') s.push(t); t.x =i+1; t.y = j+1; if(row[i][j]=='w') s.push(t); t.x =i+1; t.y = j; if(row[i][j]=='w') s.push(t); t.x =i; t.y = j-1; if(row[i][j]=='w') s.push(t); t.x =i; t.y = j+1; if(row[i][j]=='w') s.push(t); } return mp.size(); } int main() { int res; bool flag=false; int kase = 1; while(cin>>N) { if(N==0) break; for(int i=0;i<N;i++) { cin>>row[i]; } for(int i=0;i<205;i++) for(int j=0;j<205;j++) trace[i][j]=false; flag =false; for(int i=0;i<N && flag==false;i++) { if(row[i][0]=='w') { res=0; memset(trace,false,sizeof(trace)); node t; t.x=i;t.y=0; res=floodFillDfs(t); //cout<<res<<"\n"; if(res==N) { flag=1; //cout<<"i "<<i<<"\n"; break; } } } if(flag) cout<<kase++<<" W\n"; else cout<<kase++<<" B\n"; } return 0; } |
This can be done using both stack or queue.
10724
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
#include <iostream> #include <map> #include <cmath> #include <string> #include <vector> #include <cstring> #define INF 1000000000 #define EP 1e-6 using namespace std; struct point{ int x; int y; }; struct DD{ int i,j; double cst,edge; DD(double cst,double edge,int i,int j):cst(cst),edge(edge),i(i),j(j){ } bool operator < (const DD& d )const{ if(abs(cst-d.cst)>=EP) return cst<d.cst; if(abs(edge-d.edge)>=EP) return edge>d.edge; if(i!=d.i) return i>d.i; if(j!=d.j) return j>d.j; return false; } }; vector<DD> vb; double gr[55][55]; double road[55][55]; point P[55]; int main() { int N,M; int a,b; while(cin>>N) { cin>>M; if(N+M==0) break; for(int i=1;i<=N;i++) { cin>>a>>b; P[i].x = a; P[i].y = b; } for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(i==j) { gr[i][j]=0; road[i][j]=0; } else { gr[i][j]=INF; road[i][j]=INF; } } } for(int i=1;i<=M;i++) { cin>>a>>b; double d = (P[a].x-P[b].x)*(P[a].x-P[b].x)+(P[a].y-P[b].y)*(P[a].y-P[b].y); d = sqrt(d); road[a][b]=1; road[b][a]=1; gr[a][b]=d; gr[b][a]=d; } for(int k=1;k<=N;k++) { for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(gr[i][j]>gr[i][k]+gr[k][j]) gr[i][j] = gr[i][k]+gr[k][j]; } } }//end of warshall double cost; double tempedge; DD ans(0,0,0,0); for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { if(road[i][j]==1) continue; cost = 0; tempedge = sqrt((P[i].x-P[j].x)*(P[i].x-P[j].x) + (P[i].y-P[j].y)*(P[i].y-P[j].y)); for(int u=1;u<=N;u++) { for(int v=1;v<=N;v++) { cost+= (gr[u][v]- min(gr[u][v],min(gr[u][i]+tempedge+gr[j][v],gr[v][i]+tempedge+gr[j][u]))); } } DD dd = DD(cost,tempedge,i,j); ans = max(ans,dd); } } if(ans.cst-1>EP) cout<<ans.i<<" "<<ans.j<<"\n"; else cout<<"No road required\n"; } return 0; } |
247
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <iostream> #include <map> #include <string> #include <cstring> #define INF 1000000000 using namespace std; int gr[30][30]; map<string,int> mp; map<int,string> np; int visit[30]; int main() { int n,m,c=0; int kase = 1; string s1,s2; while(cin>>n) { cin>>m; if(n+m==0) break; for(int i=0;i<26;i++) { for(int j=0;j<26;j++) { if(i==j) gr[i][j]=0; else { gr[i][j]=INF; } } } mp.clear(); np.clear(); int K=1; for(int i=0;i<m;i++) { cin>>s1>>s2; if(mp[s1]==0) { mp[s1]=K; np[K]=s1; K++; } if(mp[s2]==0) { mp[s2]=K; np[K]=s2; K++; } gr[mp[s1]][mp[s2]]=1; //gr[mp[s2]][mp[s1]]=1; } for(int k=1;k<=n;k++) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(gr[i][k]!=INF && gr[k][j]!=INF) gr[i][j]=1; } } } if(c) cout<<"\n"; c=1; cout<<"Calling circles for data set "<<kase++<<":\n"; memset(visit,false,sizeof(visit)); int total =n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(gr[i][j]==INF) gr[j][i]=INF; } } for(int i=1;i<=n;i++) { bool first=true; for(int j=1;j<=n;j++) { if(gr[i][j]!=INF) { if(visit[j]==0) { if(first) { cout<<np[j]; first =false; } else { cout<<", "<<np[j]; } visit[j]=1; } } } if(!first) cout<<"\n"; } } return 0; } |
10793
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 |
#include <iostream> #include <map> #include <vector> #define INF 1000000000 using namespace std; int L,D; int gr[105][105]; map<int,int> mp; int main() { int kase=1; int t,u,v,c; cin>>t; while(t--) { for(int i=0;i<105;i++) { for(int j=0;j<105;j++) { if(i==j) gr[i][j]=0; else gr[i][j]=INF; } } cin>>L>>D; for(int i=1;i<=D;i++) { cin>>u>>v>>c; if(gr[u][v]>c) { gr[u][v]=c; gr[v][u]=c; } } for(int k=1;k<=L;k++) { for(int i=1;i<=L;i++) { for(int j=1;j<=L;j++) { if(gr[i][j]>gr[i][k]+gr[k][j]) gr[i][j] = gr[i][k]+gr[k][j]; } } } mp.clear(); for(int i=1;i<=L;i++) { if(gr[1][i]!=INF && gr[1][i]==gr[2][i] && gr[1][i]==gr[3][i] && gr[1][i]==gr[4][i] && gr[1][i]==gr[5][i]) { mp[i]=gr[1][i]; } } /*cout<<"sz "<<mp.size()<<"\n"; for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii) cout<<ii->first<<" "<<ii->second<<"\n"; */ if(mp.size()==0) { cout<<"Map "<<kase++<<": "; cout<<"-1\n"; } else { //int MN = INF; int mx =-1; int Mmx =INF; for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii) { int val =ii->first; mx =-1; for(int j=1;j<=L;j++) { if(gr[j][val]>mx) mx = gr[j][val]; } //cout<<"m "<<mx<<"\n"; if(Mmx>mx) Mmx = mx; } cout<<"Map "<<kase++<<": "; if(Mmx==INF) cout<<-1<<"\n"; else cout<<Mmx<<"\n"; } } return 0; } |
222
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#include <iostream> #include <cstdio> #include <queue> #define INF 1000000 using namespace std; struct state{ int presnt; double rem_gas; double cost; }; double d[55],price_gal[55]; double gr[55][55],dst[55][55]; bool visit[55]; int L; double dist,cango; double capacity,dist_pergal,price; int station; double MN; int recurs(state a) { int pos = a.presnt; double gaso = a.rem_gas; double cst = a.cost; state t; if(pos==L) { if(MN>cst) MN = cst; return 0; } if(gaso>=capacity/2) { bool flag = true; for(int i=pos+1;i<=L;i++) { if(visit[i]) continue; double distance = dst[i][pos]; if((dist_pergal*gaso)>=distance) { t.presnt = i; t.cost = cst; t.rem_gas= gaso - distance/dist_pergal; visit[i]=1; recurs(t); visit[i]=0; flag=0; } } if(flag) { a.presnt = pos; a.cost = cst + (capacity-gaso)*price_gal[pos]+2; a.rem_gas = capacity; recurs(a); visit[pos]=0; } } else { for(int i=pos+1;i<=L;i++) { if(visit[i]) continue; double distance = dst[i][pos]; if((dist_pergal*gaso)>=distance) { t.presnt = i; t.cost = cst; t.rem_gas= gaso - distance/dist_pergal; visit[i]=1; recurs(t); visit[i]=0; } } a.presnt = pos; a.cost = cst + (capacity-gaso)*price_gal[pos]+2; a.rem_gas = capacity; recurs(a); visit[pos]=0; } return 0; } int main() { int kase=1; while(cin>>dist) { if(dist<0) break; cin>>capacity>>dist_pergal>>price; cango = capacity/dist_pergal; cin>>station; L=1; for(int i=0;i<55;i++) { visit[i]=false; for(int j=0;j<55;j++) { if(i==j) dst[i][j]=0; else dst[i][j]=INF; } } d[0]=0; price_gal[0]=price/capacity; while(station--) { cin>>d[L]>>price_gal[L]; price_gal[L]/=100; for(int i=0;i<L;i++) { dst[L][i]=d[L]-d[i]; } L++; } if(d[L-1]<dist) { d[L] = dist; for(int i=0;i<L;i++) { dst[L][i]=d[L]-d[i]; } } MN = INF; state s; s.presnt = 0; s.rem_gas = capacity; s.cost = price; visit[0]=1; recurs(s); visit[0]=0; cout<<"Data Set #"<<kase++<<"\n"; printf("minimum cost = $%.2lf\n",MN); } return 0; } |
10075
Theory: Distance This uses the ‘haversine’ formula to calculate the great-circle distance between two points – that is, the shortest distance over the earth’s surface – giving an ‘as-the-crow-flies’ distance between the points (ignoring any hills they fly over, of course!). Haversine formula: a = sin²(Δφ/2) + cos φ1 * cos φ2 * sin²(Δλ/2) c = 2