#include <iostream> #include <string.h> #include <stdio.h> #include <map> #define INF 1000000000 using namespace std; map<int,int> m; int graph[105][105]; int sum[105]; double total; int main() { int a,b,cnt; int kase =1; while(cin>>a) { cin>>b; if(a==0 && b==0) break; for(int i=1;i<101;i++) { sum[i]=0; for(int j=1;j<101;j++) { graph[i][j]=INF; if(i==j) graph[i][j]=0; } } cnt=1; m.clear(); m[a]=cnt; if(m[b]==0) { cnt+=1;
Category: Algorithm
11015
#include <iostream> #include <string.h> #include <vector> #include <map> #define ll long long #define INF 1000000000 using namespace std; int graph[25][25]; int N,M,MiN; int sum[25]; map<int,string> m; int main() { int t,kase=1; int a,b,c,res; string s; //cin>>t; while(cin>>N) { cin>>M; if(N==0 ) break; //mp.clear(); m.clear(); int x=1; for(int i=1;i<25;i++) { sum[i]=0; for(int j=1;j<25;j++) { graph[i][j]=INF; if(i==j)
1189
#include <stdio.h> int main() { int n,t; while(scanf("%d",&n)) { if(n==0) break; int c[205]={}; t = 1%n; int i=0; while(1) { i++; if(c[t]) { for(int j=c[t];j<i;j++) printf("1"); for(int j=c[t]-1;j>=0;j–) printf("0"); printf("\n"); break; } c[t]=i; t =(t*10+1)%n; } } return 0; }
193
#include <iostream> #include <string.h> #include <vector> using namespace std; int visit[110]; int r[110]; int graph[110][110]; vector<int> vb; int mx; int n,k; int judge(int a) { for(int i=1;i<=n;i++) { if(graph[a][i]) { if(visit[i]==1 && i!=a) return 0; } } return 1; } int backtrack(int node) { if(node>n) { vb.clear(); int cnt=0; for(int i=1;i<=n;i++) { if(visit[i]) { cnt++;
714
Using binary search to find the minimum value, #include <iostream> #include <string.h> #include <vector> #define ll long long using namespace std; ll b[505]; vector<int> res[505]; int main() { int t; int books,writer; cin>>t; while(t–) { cin>>books>>writer; ll total=0,minwrk=0,mid=0; for(int i=0;i<books;i++) { cin>>b[i]; total+=b[i]; if(minwrk<b[i]) minwrk = b[i]; } //bin search while(minwrk<total) { int required=1; ll
11151
#include <stdio.h> #include <string.h> #include <string> #include <iostream> using namespace std; int table[1001][1001]; int main() { int n,len; string s; cin>>n; getchar(); while(n–) { getline(cin,s); if(s=="") { cout<<0<<"\n"; continue; } memset(table,0,sizeof(table)); len = s.size(); for(int i=0;i<=len;i++) { table[i][i]=1; } for(int length=2;length<=len;length++) { for(int i=0;i<=len-length+1;i++) { int end=i+length-1; if(end<0 || end>=len) continue; if(s[i]==s[end] && length==2) {
1152
Meet in the middle and binary search algorithm is used to solve this problem. #include <iostream> #include <string.h> #include <algorithm> #include <map> using namespace std; int A[4001]; int B[4001]; int C[4001]; int D[4001]; int E[16008001]; int F[16008001]; //map<int,int> mp; struct myHash { int value; int valueOccuredNumberOfTimes; }FF[16008001]; int main() { int t,n,x,cnt,a; int low,mid,high; int
208
#include <iostream> #include <string.h> #include <stdio.h> #include <vector> #include <algorithm> using namespace std; int mat[25][25]; int dist[25][25]; vector<int> vb[25]; bool visit[25]; int fire; int kase=1; int mx=0,cnt=0; int res[25]; void dfs(int s,int k) { if(s==fire) { cnt++; for(int i=0;i<k;i++) { cout<<res[i]<<(i==(k-1)?"\n":" "); } return; } //for(int i=0;i<vb[s].size();i++) for(int i=1;i<=mx;i++) { if(visit[i]) continue; if(!mat[s][i]) continue; if(!dist[i][fire])
539
Theory: This is an np-hard problem. As the degree of each node can be at most 3 so using dfs ,it can be solved. Follow the link #include <iostream> #include <stdio.h> #include <vector> #include <string.h> using namespace std; //vector<int> vb[30]; int mat[30][30]; int visit[30]; int n,m; int length; void search(int a,int len) { if(len>length) length
524
#include <iostream> #include <stdio.h> using namespace std; int prime[40]={0,0,2,3,0,5,0,7,0,0,0,11, 0,13,0,0,0,17,0,19,0,0, 0,23,0,0,0,0,0,29,0,31,0, 0,0,0,0,37,0,0}; bool visit[17]; int numbers[17]; int n; int search(int step) { if(step==n) { if(prime[1+numbers[step-1]]) { for(int i=0;i<n;i++) cout<<numbers[i]<<((i==(n-1))?"\n":" "); } } for(int i=1;i<=n;i++) { if(prime[numbers[step-1]+i] && !visit[i]) { visit[i]=1; numbers[step]=i; search(step+1); visit[i]=0; } } } int main() { int kase=1; int c=0; while(cin>>n) {