120-Stacks of Flapjacks

<br /> /* <br /> "Stacks of Flapjacks"<br /> Level:5.5<br /> Date:2007/5/29<br /> 技巧：<br /> input:利用getline讀入字串，再用strtok()將空白清除。<br /> process:<br /> 1.將最大的元素先reverse至top of stack<br /> 2.再將top of stack reverse到bottom<br /> 3.將次大元素reverse至top of stack<br /> 4.再將top of stack reverse到bottom-1<br /> repeat...until (bottom ==1)<br /> <br /> Bill Gaze大一寫的論文，就是提出多種Flapjacks problem及解法，<br /> 後來主要被應用在生物資訊的DNA字串比對。<br /> */<br /> <br /> #include <iostream><br /> #include <vector><br /> #include <algorithm><br /> #include <string><br /> <br /> using namespace std;<br /> <br /> int main(){<br /> string str;<br /> char *s, *str2char;<br /> vector<int> ivec;<br /> vector<int>::iterator iter;<br /> vector<int>::iterator iter_end;<br /> vector<int>::iterator spatula; //要翻的煎餅，翻的位置要+1, <br /> <br /> int max; //暫存bottom以上最大的element. <br /> int bottom; //bottom以上皆未排序. <br /> <br /> while(getline(cin,str)){<br /> str2char = new char[str.size()+1];<br /> strcpy(str2char, str.c_str()); <br /> ivec.clear();<br /> <br /> //將input string清掉空白,並一一丟入int array <br /> for(s = strtok(str2char, " "); s!= NULL; s=strtok(NULL, " ")){<br /> ivec.push_back(atoi(s));<br /> }<br /> iter = ivec.begin();<br /> iter_end = ivec.end();<br /> <br /> bottom = ivec.size(); <br /> cout << str << endl; while(1){ if(bottom ==1){ cout << "0" << endl; break; } iter = ivec.begin(); //如果top element是最大者,便從bottom以上做reverse,並將bottom向上移動一層 if(ivec[0] == (max = *max_element(iter, iter+bottom))){ if(ivec[0] == ivec[bottom-1]){ --bottom; continue; } reverse(iter, iter+bottom); cout << ivec.size()-bottom+1 << " "; --bottom; } /*否則從bottom以上找最大元素，並從最大元素下做reverse， *以將最大元素移至top element. */ else{ spatula = find(iter, iter+bottom, max); /*如果最大元素正好在bottom的上方， *便無須reverse，並將bottom向上移動一層. */ if(ivec[spatula-iter] == ivec[bottom-1]){ --bottom; continue; } reverse(iter, spatula+1); cout << ivec.size() - (spatula-iter) << " "; } } } }

793-Network Connections

<br /> /* <br /> "Network Connections"<br /> Level:4.0<br /> Date:2007/3/2<br /> 技巧: <br /> 利用Union-Find Algorithm & path compresssion<br /> 'c': union(node1,node2)<br /> 'q': Find_Set(node1) == Find_Set(node2) <br /> */<br /> <br /> #include <iostream><br /> #include <stdio.h><br /> <br /> using namespace std;<br /> <br /> int Find_Set(int); //回傳該node所屬的集合的代表node. <br /> void Link(int,int); //相連兩個集合樹. <br /> void Union(int,int); //聯集(呼叫前兩個function). <br /> <br /> const int MAX_N = 30001;<br /> <br /> int p[MAX_N], //儲存每個node的parent. <br /> rank[MAX_N]; //儲存每個node的高度.<br /> <br /> int main()<br /> {<br /> int num,n,node1,node2,yes,no;<br /> char op;<br /> char input[6]; <br /> <br /> cin >> num;<br /> <br /> while(num--)<br /> { <br /> yes = no = 0; <br /> cin >> n;<br /> for(int i=1; i <= n; i++){ p[i]=i; rank[i]=0; } cin.ignore(); while(gets(input) != NULL && sscanf(input,"%c %d %d",&op,&node1,&node2)==3) { if(op == 'c') Union(node1,node2); else if(op == 'q'){ if(Find_Set(node1) == Find_Set(node2)) yes++; else no++; } } cout << yes << "," << no << endl; if(num) cout << endl; } // while(1); } int Find_Set(int x) { //若x不是root, 便將parent指向root, 並回傳root node. if(x != p[x]) p[x] = Find_Set(p[x]); //recursive find root. return p[x]; } void Link(int x, int y) { if( x == y) //x,y屬同一個Set, 不需相連. return; //小樹串到大樹下. if(rank[x] > rank[y]){<br /> p[y] = x;<br /> } <br /> else{<br /> p[x] = y;<br /> if(rank[x] == rank[y]) //兩棵樹一樣高時, 合成樹的高度會長高一個單位. <br /> rank[y]++; <br /> } <br /> }<br /> <br /> void Union(int x, int y)<br /> { <br /> Link(Find_Set(x),Find_Set(y)); //找到兩個node分屬的Set, 並將兩個set相連. <br /> }<br />

10608-Friends

<br /> /* <br /> "Friends"<br /> Level:4.0<br /> Date:2007/2/28<br /> 技巧: <br /> 利用Union-Find Algorithm & path compresssion作 Disjoint set.<br /> 並記錄每個node以下有多少個node(friends). <-對此題來說或許過於佔用記憶體. */ #include <iostream><br /> #include <stdio.h><br /> <br /> using namespace std;<br /> <br /> int Find_Set(int); //回傳該node所屬的集合的代表node. <br /> void Link(int,int); //相連兩個集合樹. <br /> void Union(int,int); //聯集(呼叫前兩個function). <br /> <br /> const int MAX_N = 30001;<br /> <br /> int p[MAX_N], //儲存每個node的parent. <br /> rank[MAX_N], //儲存每個node的高度.<br /> number[MAX_N]; //儲存每個node以下的node數. <br /> <br /> int main()<br /> {<br /> int num,n,m,node1,node2,max; <br /> cin>>num;<br /> while(num--)<br /> {<br /> max = 0; <br /> scanf("%d %d",&n,&m);<br /> for(int i=0; i < n; i++){ p[i]=i; rank[i]=0; number[i]=1; } while(m--) { scanf("%d %d", &node1, &node2); Union(node1,node2); } for(int i=0; i < n; i++) { max = max > number[i]? max : number[i]; <br /> }<br /> cout << max << endl; } //while(1); } int Find_Set(int x) { //若x不是root, 便將parent指向root, 並回傳root node. if(x != p[x]) p[x] = Find_Set(p[x]); //recursive find root. return p[x]; } void Link(int x, int y) { if( x == y) //x,y屬同一個Set, 不需相連. return; //小樹串到大樹下. if(rank[x] > rank[y]){<br /> p[y] = x;<br /> number[x]+= number[y];<br /> } <br /> else{<br /> p[x] = y;<br /> number[y] += number[x]; //更新root以下的node數. <br /> if(rank[x] == rank[y]) //兩棵樹一樣高時, 合成樹的高度會長高一個單位. <br /> rank[y]++; <br /> } <br /> }<br /> <br /> void Union(int x, int y)<br /> { <br /> Link(Find_Set(x),Find_Set(y)); //找到兩個node分屬的Set, 並將兩個set相連. <br /> }<br />

459-Graph Connectivity

<br /> /* <br /> "Graph Connectivity"<br /> Level:5.0<br /> Date:2007/2/11<br /> 技巧:<br /> 先建立adjacency matrix, <br /> 再用DFS traversal找sub graph的數目.<br /> 題目的input data可能是夾雜空白的,所以需要對input data filter掉多餘的空白,<br /> read.erase(remove(read.begin(), read.end(), ' '), read.end());<br /> 上面這招很好用,多謝強哥教我....orz..<br /> */<br /> <br /> #include <iostream><br /> #include <string><br /> #include <algorithm><br /> <br /> using namespace std;<br /> int ans, size;<br /> bool visited[26], table[26][26]; <br /> <br /> void DFS(int node){<br /> visited[node] = true;<br /> for(int i=0;i < size;++i){ if(table[node][i] == true && visited[i] == false) DFS(i); } } int main(){ int turn, n1, n2; string c; string read; cin>>turn;<br /> <br /> while(turn--){<br /> ans = 0;<br /> cin>>c;<br /> cin.ignore(); //清除stream裡的多餘字完('\n') <br /> size = c[0] - 'A'+1;<br /> <br /> for(int i=0; i < 26; ++i) for(int j=0; j < 26; ++j) table[i][j] = false; while(1){ //建立adjcent matrix. getline(cin, read); read.erase(remove(read.begin(), read.end(), ' '), read.end()); //filter掉多餘空白. if( read.empty() == true) break; n1 = read[0] - 'A'; n2 = read[1] - 'A'; table[n1][n2] = true; table[n2][n1] = true; } for(int i=0; i < size; ++i){ if(visited[i] == false){ DFS(i); ++ans; } } cout<< ans << endl; if(turn != 0) cout << endl; for(int i=0;i < size;++i) visited[i]= false; } return 0; }

750-8 Queens Chess Problem

<br /> /* <br /> "8 Queens Chess Problem"<br /> Level:6.5<br /> Date:2007/1/28<br /> 技巧: <br /> 先畫出search tree較易分析<br /> 可參考http://programming.im.ncnu.edu.tw/exapmle_for_java/9.htm的search tree.<br /> 這是一種Depth first Search, 但可根據eight queen的規則prune掉一些path.<br /> p.s.只允許output dataset之間有空白行，否則會P.E.到死...>,< */ #include <iostream><br /> using namespace std;<br /> int rowQ[8];<br /> int r,c;<br /> int cnt;<br /> <br /> void addQueen(int row, int col){<br /> //檢查前面column的queen. <br /> for(int i=0;i < col;i++){ //若新增的queen它的row上 or 斜對角線上有其它queen, 則該位置不得addQueen. if(row == rowQ[i] || col-i == abs(row-rowQ[i])){ return; } } rowQ[col]=row; //通過檢驗,在該位置addQueen. if(col < 7){ //若尚未Trace到第七層(即第七個column),則繼續向下trace. for(int i=0;i < 8;i++) addQueen(i,col+1); //測試下一層所有的row是否得以合法addQueen. } else if(rowQ[c-1]==r-1){ //trace完七層,則找到解,但只印出(r,c)有queen的特定解. ++cnt; if(cnt < 10) cout<<" "; cout << cnt << " "; for(int i=0;i < 8;i++) //印出每個column上Queen的row. cout<<" "<< rowQ[i]+1; cout<< endl; } } int main(void){ int num; cin>> num;<br /> int row[num],col[num];<br /> <br /> for(int i=0;i < num;i++){ // cout<< endl; 去掉這行才能AC. cin>>row[i];<br /> cin>>col[i];<br /> }<br /> for(int i=0;i < num;i++){ cout<< "SOLN COLUMN"<< endl; cout<< " # 1 2 3 4 5 6 7 8"<< endl; cout<< endl; r = row[i]; c = col[i]; for(int i=0;i < 8;i++) //trace所有解. addQueen(i,0); cnt=0; if(i != num-1) //加上這行才能AC. cout<< endl; } return 0; }

10784-Diagonal

<br /> /* <br /> "Diagonal"<br /> Level:2.0<br /> Date:2006/10/15<br /> 技巧: 我不知道這個公式怎麼推論出來的,也懶得Google了,<br /> 直接從論壇上copy公式..XD <br /> */<br /> #include <stdio.h><br /> #include <math.h><br /> main(){<br /> long long unsigned input=0;<br /> int n=0; <br /> while(1){<br /> /* %I64u要改成%llu */<br /> scanf("%I64u",&input);<br /> if(input==0) break;<br /> printf("Case %d: %d\n",++n, (int)ceil(1.5+sqrt(2.0*input))); <br /> } <br /> }<br />

10469-To Carry or not to Carry

<br /> /* <br /> "To Carry or not to Carry"<br /> Level:2.0<br /> Date:2006/10/14<br /> 技巧:取XOR<br /> %lu 不可寫成%ul唷 <br /> */<br /> #include <stdio.h><br /> main(){<br /> unsigned long n1=0,n2=0;<br /> while(scanf("%lu %lu",&n1,&n2)==2){<br /> printf("%lu\n",n1^n2); <br /> } <br /> }<br />

499-What's The Frequency, Kenneth?

<br /> /* <br /> "What's The Frequency, Kenneth?"<br /> Level:2.0<br /> Date:2006/10/13<br /> 技巧:利用陣列記錄A-Z,a-z 52個字母出現的頻率,再找最大的. <br /> */<br /> #include <stdio.h><br /> #include <string.h><br /> main(){<br /> int f[52]={0};<br /> char input[100]={0}; <br /> int i=0,max=0;<br /> while(gets(input)){<br /> int max=0;<br /> for(i=0;i<52;i++) f[i]=0; for(i=0;i<strlen(input);i++){ if(input[i]>='A' && input[i]<='Z'){ f[input[i]-'A']++; if(max < f[input[i]-'A']) max = f[input[i]-'A']; } else if(input[i]>='a' && input[i]<='z'){ f[input[i]-'a'+26]++; if(max < f[input[i]-'a'+26]) max = f[input[i]-'a'+26]; } } for(i=0;i<52;i++){ if(f[i]== max){ if(i<26) printf("%c",i+'A'); else if(i>25)<br /> printf("%c",i+'a'-26); <br /> } <br /> }<br /> printf(" %d\n",max); <br /> } <br /> }<br />

445-Marvelous Mazes

<br /> /* <br /> "Marvelous Mazes"<br /> Level:2.0<br /> Date:2006/10/11 <br /> */<br /> #include <stdio.h><br /> #include <ctype.h><br /> main(){<br /> char c=0;<br /> int n=0;<br /> <br /> /*<br /> FILE *fptr;<br /> if((fptr=fopen("test.txt","r"))==NULL)<br /> printf("File can't not be open!\n");<br /> while(!feof(fptr)){<br /> fscanf(fptr,"%c", &c);<br /> */<br /> <br /> while(1){ <br /> scanf("%c",&c);<br /> if(feof(stdin)) /*determine whether the EOF indicator is set*/ <br /> break;<br /> if(isdigit(c))<br /> n += c-'0';<br /> else{<br /> int i=0;<br /> if (c == '!' || c=='\n') <br /> printf("\n"); <br /> else{<br /> if (c == 'b') c=' ';<br /> <br /> for(i=0;i < n;i++) printf("%c",c); n=0; } } } }

541-Error Correction

<br /> /* <br /> "Error Correction"<br /> Level:1.5<br /> Date:2006/10/10<br /> 技巧: Corrupt:有兩列or兩行以上 有error<br /> 只有一列 or 只有一行 有error<br /> Change bit:只有一列 and 只有一行 有error<br /> OK:沒有任何error <br /> */<br /> #include <stdio.h><br /> #define SIZE 100<br /> main(){<br /> int matrix[SIZE][SIZE]={0};<br /> int i=0,j=0,n=0,row=0,column=0,sum=0;<br /> <br /> BEGIN:<br /> while(scanf("%d",&n)==1 && n!=0){<br /> column = row = 0; <br /> for(i=0;i < n;i++) for(j=0;j < n;j++) scanf("%d",&matrix[i][j]); for(i=0;i < n;i++){ sum=0; for(j=0;j < n;j++){ sum += matrix[i][j]; } if(sum%2 != 0 && row == 0) row = i+1; /* 記錄第幾列有error */ else if(sum%2 !=0 && row > 0){<br /> printf("Corrupt\n");<br /> goto BEGIN;<br /> } <br /> }<br /> <br /> for(j=0;j < n;j++){ sum = 0; for(i=0;i < n;i++){ sum += matrix[i][j]; } if(sum%2 != 0 && column == 0) column = j+1; /* 記錄第幾行有error */ else if(sum%2 !=0 && column >0){<br /> printf("Corrupt\n");<br /> goto BEGIN;<br /> } <br /> }<br /> if(row > 0){<br /> if(column > 0)<br /> printf("Change bit (%d,%d)\n",row,column);<br /> else<br /> printf("Corrupt\n"); <br /> goto BEGIN; <br /> }<br /> if(column > 0)<br /> printf("Corrupt\n");<br /> else<br /> printf("OK\n"); <br /> } <br /> }<br />

146-ID Codes

<br /> /* <br /> "ID Codes"<br /> Level:1.5<br /> Date:2006/10/10<br /> 技巧:使用algorithm STL<br /> http://tinyurl.com/fmqyv<br /> http://support.microsoft.com/kb/157870/zh-cn<br /> 若非使用STL,此題應有Level 3.0以上 <br /> */<br /> #include <iostream><br /> #include <string><br /> #include <algorithm><br /> using namespace std;<br /> main(){<br /> string input; <br /> while(cin >> input && input != "#"){<br /> if(next_permutation(input.begin(),input.end()))<br /> cout << input << endl; else cout << "No Successor" << endl; } }

10286-Trouble with a Pentagon

<br /> /* <br /> "Trouble with a Pentagon"<br /> Level:1.5<br /> Date:2006/10/8<br /> 技巧: sin(108)/sin(63)*F<br /> http://ken.duisenberg.com/potw/archive/arch98/981113sol.html <br /> 參數是弳度,<br /> 要用double,float會WA. <br /> */<br /> #include <stdio.h><br /> #include <math.h><br /> #define pi 3.1415926535897932384626433832795<br /> main(){<br /> double input=0.0;<br /> while(scanf("%lf",&input)==1){<br /> printf("%.10lf\n",sin(108*pi/180.0)/sin(63*pi/180.0)*input); <br /> } <br /> }<br />

10370-Above Average

<br /> /* <br /> "Above Average"<br /> Level:1.5<br /> Date:2006/10/7<br /> 技巧: 要印%,要用"%%" <br /> */<br /> #include <stdio.h><br /> main(){<br /> int n = 0, people = 0, i = 0,p = 0;<br /> float av = 0.0f;<br /> int grade[1000]={0};<br /> scanf("%d",&n);<br /> while(n-- >0){<br /> scanf("%d",&people);<br /> for(i=0;i < people;i++){ scanf("%d",&grade[i]); av += grade[i]; } av/=people; for(i=0;i < people;i++) if(grade[i] > av)<br /> p++; <br /> printf("%.3f%%\n",(float)p/people*100); <br /> av=p=0;<br /> } <br /> }<br />

10327-Flip Sort

<br /> /* <br /> "Flip Sort"<br /> Level:1.5<br /> Date:2006/10/7<br /> 技巧:求前面比自己大的數有幾個,加總後便是inversion所需的次數. <br /> */<br /> #include <stdio.h><br /> main(){<br /> int n=0,i=0,j=0,tmp=0,times=0;<br /> int input[1000]={0};<br /> while(scanf("%d",&n)==1){<br /> for(i=0;i < n;i++) scanf("%d",&input[i]); for(i=0;i < n;i++) for(j=0;j < i;j++) if(input[j] > input[i])<br /> times++; <br /> printf("Minimum exchange operations : %d\n",times); <br /> times=0;<br /> } <br /> }<br />

10656-Maximum Sum II

<br /> /* <br /> "Maximum Sum II"<br /> Level:1.5<br /> Date:2006/10/6<br /> 技巧: 因為都是正整數的sequence,只有零不印.<br /> */<br /> #include <stdio.h><br /> main(){<br /> int n=0,input=0,flag=0;<br /> while(scanf("%d",&n)==1 && n!=0){<br /> flag=0;<br /> while(n-- >0){<br /> scanf("%d",&input); <br /> if(input == 0) continue;<br /> if(flag != 0)<br /> printf(" ");<br /> printf("%d",input);<br /> flag=1;<br /> }<br /> if(flag == 1)<br /> printf("\n");<br /> else<br /> printf("0\n"); /* 全部integer都是0的case */<br /> }<br /> }<br />

10696-Problem A - f91

<br /> /* <br /> "Problem A - f91"<br /> Level:1.0<br /> Date:2006/10/4<br /> 技巧:本來應該寫成recursion的,但當input不大於100時,f91的output都是91.<br /> 所以投機取巧下,這題就變白爛題. <br /> */<br /> #include <stdio.h><br /> main(){<br /> long int n=0;<br /> while(scanf("%ld",&n)==1){<br /> if(n==0)<br /> break;<br /> if(n<=100) printf("f91(%ld) = 91\n",n); else printf("f91(%ld) = %ld\n",n,n-10); } }

10783-Odd Sum

<br /> /* <br /> "Odd Sum"<br /> Level:1.0<br /> Date:2006/10/3<br /> */<br /> #include <stdio.h><br /> main(){<br /> int n=0,a=0,b=0,sum=0,i=0,k=1;<br /> scanf("%d",&n);<br /> while(n-->0){<br /> scanf("%d",&a);<br /> scanf("%d",&b);<br /> for(i=a;i<=b;i++){ if(i%2 != 0) sum+=i; } printf("Case %d: %d\n",k++,sum); sum=0; } }

10300-Ecological Premium

<br /> /* <br /> "Ecological Premium"<br /> Level:0.5<br /> Date:2006/10/3<br /> */<br /> <br /> #include <stdio.h><br /> main(){<br /> int n=0,f=0,area=0,animal=0,level=0,sum=0;<br /> scanf("%d",&n);<br /> while(n-- > 0){<br /> scanf("%d",&f);<br /> while(f-- > 0){<br /> scanf("%d %d %d",&area,&animal,&level);<br /> sum += area*level;<br /> }<br /> printf("%d\n",sum);<br /> sum=0;<br /> } <br /> }<br />

10071-Back to High School Physics

<br /> /* <br /> "Back to High School Physics"<br /> Level:0.5<br /> Date:2006/10/3<br /> */<br /> <br /> #include <stdio.h><br /> main(){<br /> int v=0,t=0;<br /> while(scanf("%d %d",&v,&t)==2){<br /> printf("%d\n",v*2*t);<br /> }<br /> }<br />

10302-Let Me Count The Ways

<br /> /* <br /> "Let Me Count The Ways"<br /> Level:0.5<br /> Date:2006/10/2<br /> 技巧:根本是考數學，公式是從forum找來的，也不知道為什麼用這公式， <br /> 此外input,sum都一定要用long long type　否則會WA.<br /> 上傳ACM %I64d要改成%llu <br /> */<br /> #include<stdio.h><br /> main(){<br /> long long input=0;<br /> long long sum=0;<br /> while(scanf("%I64d",&input)==1){<br /> sum = (input*input*(input+1)*(input+1))/4; <br /> printf("%I64d\n",sum);<br /> } <br /> }<br /> <br />