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; }
490
#include <iostream> #include <string.h> #include <fstream> using namespace std; char s[105][105]; int main() { int k=0; int len,mx=0; //ofstream out; //out.open("out.txt"); for(int i=0;i<105;i++) for(int j=0;j<105;j++) s[i][j]=' '; while(gets(s[k])) { len = strlen(s[k]); s[k][len] =' '; if(len>mx) mx = len; k++; } for(int j=0;j<mx;j++) { for(int i=k-1;i>=0;i–) { cout<<s[i][j]; //out<<s[i][j]; } cout<<endl; //out<<endl; } //out.close(); return
12241
Theory: We know that, From 0-9, each digit occurs once From 0-99, each digit occurs 20 times (10x in position 1 and 10x in position 2) From 0-999, each digit occurs 300 times (100x in P1, 100x in P2, 100x in P3) If the range is from 0 to a power of 10 then occurrence
12403
#include <iostream> #include <stdio.h> #include <string.h> using namespace std; int main() { int t,n; char str[100],s[20]; cin>>t; getchar(); int sum=0; while(t–) { gets(str); if(strcmp(str,"report")==0) { sprintf(s,"%d",sum); puts(s); } else { sscanf(str,"%s %d",s,&n); sum+=n; } } return 0; }
10887
#include <iostream> #include <string> #include <string.h> #include <stdio.h> #include <sstream> #define SZ 10000017 using namespace std; char b[30]; char str[3000000][25];//3000000 int parent[10000017]; int strmap[3000000]; int gethash(char s[]) { int seed=31; int v=0; for(int i=0;i<strlen(s);i++) { v= v*seed+(s[i]-'0'); } return (v&0x7FFFFFFF)%SZ; } bool insert(int position) { int _hash = gethash(str[position]); int next=parent[_hash]; while(next!=-1) { if(!strcmp(str[position],str[next])) break;
11362
#include <iostream> #include <stdio.h> #include <vector> using namespace std; struct node{ bool endofmark; node *next[11]; node() { endofmark=false; for(int i=0;i<10;i++) next[i]=NULL; } }*root; int insert(string str) { node *curr=root; int id; int created=0; for(int i=0;i<str.size();i++) { id=str[i]-'0'; if(curr->next[id]==NULL) { curr->endofmark=false; curr->next[id]=new node(); created =1; } curr=curr->next[id]; } if(created==0) curr->endofmark=false; else curr->endofmark=true; return created; } bool
12506
#include <iostream> #include <string> #include <queue> using namespace std; int res; struct node{ int cont; node *next[26]; node() { cont=0; for(int i=0;i<26;i++) next[i]=NULL; } }*root; void insert(string s) { node *tmp= root; int len=s.size(); int idx; for(int i=0;i<len;i++) { idx= s[i]-'a'; if(tmp->next[idx]==NULL) tmp->next[idx]=new node(); tmp->next[idx]->cont++; tmp = tmp->next[idx]; } } void del(node *r) { for(int