#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; }
Year: 2014
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) {
459
This problem can be solved using dfs,bfs or union find algorithm, BFS solution: #include <iostream> #include <stdio.h> #include <string.h> #include <map> #include <queue> #include <string> using namespace std; int to; bool visit[26]; int graph[26][26]; void bfs(int a) { int b; queue<int> q; q.push(a); while(!q.empty()) { b =q.front(); q.pop(); visit[b]=1; for(int i=0;i<=to;i++) { if(graph[b][i]==1 && visit[i]==0)
11137
#include <iostream> #define ll long long using namespace std; int arr[23]={0,1,8,27,64,125,216,343,512,729, 1000,1331,1728,2197,2744,3375,4096,4913,5832, 6859,8000,9261 }; ll ways[10005]; int main() { for(int j=0;j<10005;j++) ways[j]= 0; ways[0]=1; for(int i=1;i<=21;i++) { for(int j=arr[i];j<10005;j++) ways[j]+=ways[j-arr[i]]; } int n; while(cin>>n) { //cout<<calc(1,n)<<"\n"; cout<<ways[n]<<"\n"; } return 0; }