UVa 11038 How many 0's?

題目連結
想法：
　　將問題簡化為求1~m 0的總數，以及1~n 0的總數，然後最後再相減。
　　求1~n 0的總數，要將n分別算每個位數0的個數，舉例如30324：

• 先從右邊第一位'4'開始，其左邊為3032，表示1~30320在"第一位"總共有3032*1=3032個0
• 換第二位數'2'，其左邊為303，表示總共有303*10(右邊有1位)=3030個0
• 再換第三位數也是一樣，30*100=3000個0，
• 注意第四位數為'0'，因此原本應該是3*1000，但第3個1000其實只到324而以，所以為2*1000+324+1=2325個0 (+1是因為別忘了0~324是325個)
• 最後一位'3'，它是最高位數，因此不會有0
• 所以總共為3032+3030+3000+2325=11387

因此，此演算法從最低位(i==1)開始到最高位(i==k)結束，如果第i位不為0，直接左邊數字x10^(i-1)，如果第i位為0，那麼(左邊數字-1)x10^(i-1)+右邊數字+1，最後把每位數的0總數加起來即可。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef long long int llt;
	llt sum0 (llt n)
	{
	llt N = n,sum = 0;
	int left=1,mid,right=1;
	while (N >= 10){
	mid = N%10;
	N /= 10;
	if (mid) sum += (N * left);
	else sum += ((N-1)*left + n%right +1);
	left *= 10;
	right *= 10;
	}
	return sum;
	}
	int main()
	{
	llt m,n;
	while (scanf("%lld%lld",&m,&n)){
	if (m < 0) break;
	llt ans = sum0(n) - sum0(m-1);
	if (m == 0) ans++; // 函數是從1~m，如果m==0會少算
	printf("%lld\n",ans);
	}
	return 0;
	}

view raw UVa 11038 How many 0's.cpp hosted with ❤ by GitHub

UVa 620 Cellular Structure

題意：給定O為一條細胞序列

• 若O僅僅為'A'，那麼是simple
• 若O為'OAB'的型態，則OAB的O需要符合O的3種型態的其中一種，如果符合則為Fully-Grown，否則為Mutant。
• 若O為'BOA'的型態，則BOA的O需要符合O的3種型態的其中一種，如果符合則為Mutagenic，否則為Mutant。

想法：

　　用遞迴式parsing來分析O為哪種型態，如果為第2種和第3種，則要繼續呼叫遞迴分析O的型態，只要分析過程中只要O不符合3種的其中一種，則不用再分析，直接回傳Mutant。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	char APU[1000];
	int parsing (int front, int back)
	{
	// 0:Mutant
	// 1:Simple
	// 2:Fully-Grown
	// 3:Mutagenic
	if (front==back && APU[front]=='A') return 1;
	if (APU[back]=='B' && APU[back-1]=='A'){ // 判斷是否為Fully Grown
	if (front == back-1) return 0; // 如果為"AB"，那麼是Mutant
	else if (parsing (front,back-2) != 0) return 2;
	}
	if (APU[front]=='B' && APU[back]=='A'){ // 判斷是否為Mutagenic
	if (front+1 == back) return 0; // 如果為"BA"，那麼是Mutant
	else if (parsing (front+1,back-1) != 0) return 3;
	}
	return 0; // O不符合上面3種任一種型態，回傳0
	}
	int main()
	{
	int Case;
	scanf("%d",&Case);
	while (Case--){
	scanf("%s",APU);
	int t = parsing (0,strlen(APU)-1);
	switch (t){
	case 0: printf("MUTANT\n"); break;
	case 1: printf("SIMPLE\n"); break;
	case 2: printf("FULLY-GROWN\n"); break;
	case 3: printf("MUTAGENIC\n"); break;
	}
	}
	return 0;
	}

view raw [UVa] 620 Cellular Structure.cpp hosted with ❤ by GitHub

UVa 10101 Bangla Numbers

想法：
　　透過遞迴求出答案。

	#include <cstdio>
	using namespace std;
	void bangla(long long int n)
	{
	if (n >= 10000000){
	bangla (n / 10000000);
	printf (" kuti");
	n %= 10000000;
	}
	if (n >= 100000){
	bangla (n / 100000);
	printf (" lakh");
	n %= 100000;
	}
	if (n >= 1000){
	bangla (n / 1000);
	printf (" hajar");
	n %= 1000;
	}
	if (n >= 100){
	bangla (n / 100);
	printf (" shata");
	n %= 100;
	}
	if (n)
	printf (" %d",n);
	}
	int main()
	{
	long long int n;
	int Case=1;
	while (scanf("%lld",&n)!=EOF){
	printf ("%4d.",Case++);
	if (n==0) printf(" 0");
	bangla (n);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10101 Bangla Numbers.cpp hosted with ❤ by GitHub

UVa 10696 f91

想法：
　　典型的DP題目，把需要遞迴計算的答案用陣列存起來即可。

	#include <cstdio>
	using namespace std;
	int fn[101]={0};
	int f91 (int N){
	if (N > 100) return N-10;
	if (fn[N] != 0) return fn[N];
	fn[N] = f91(f91(N+11));
	return fn[N];
	}
	int main()
	{
	int n;
	while (scanf("%d",&n)){
	if (!n) break;
	printf("f91(%d) = %d\n",n,f91(n));
	}
	return 0;
	}

view raw [UVa] 10696 f91.cpp hosted with ❤ by GitHub

UVa 136 & POJ 1338 Ugly Number

想法：
　　下一個數必定是從之前的某個數x2或x3或x5而來的，因此要找第n個數(N[n])，就把前n-1個數x2,x3,x5，找出大於(N[n-1])的最小值。
　　另外找第n個數的時候，乘以2不用每次都從第0個開始乘，每次紀錄2乘到哪個位置，以後就從這個位置往後找即可。例如12是從6這個數字乘以2而來，那麼要找12以後的number的時候，只要從6以後的數字乘以2開始找，因為6以前的數字乘以2不可能大於12，乘以3和乘以5也是同樣道理。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	unsigned long long int N[1501];
	N[1]=1;
	int p2=1,p3=1,p5=1;
	for (int n=2; n<=1500; n++){
	while (N[p2]*2 <= N[n-1]) p2++;
	while (N[p3]*3 <= N[n-1]) p3++;
	while (N[p5]*5 <= N[n-1]) p5++;
	N[n] = min (N[p2]*2, min (N[p3]*3, N[p5]*5));
	}
	printf("The 1500'th ugly number is %llu.\n",N[1500]);
	}

view raw [UVa] 136 Ugly Number.cpp hosted with ❤ by GitHub

UVa 495 Fibonacci Freeze

想法：
　　本題單純求費柏那西數列，因為n值很大，所以要做大數加法，可以以1000為一個位數，提升效率。

	#include <cstdio>
	using namespace std;
	int Fib[5001][500]={0};
	int main()
	{
	Fib[1][0]=1;
	for (int i=2; i<=5000; i++){
	for (int j=0; j<500; j++){
	Fib[i][j] += Fib[i-1][j]+Fib[i-2][j];
	if (Fib[i][j]>=1000){
	Fib[i][j] -= 1000;
	Fib[i][j+1]++;
	}
	}
	}
	int n;
	while (scanf("%d",&n)!=EOF){
	printf("The Fibonacci number for %d is ",n);
	if (!n) printf("0\n");
	else {
	int i=500;
	while (Fib[n][--i]==0);
	printf("%d",Fib[n][i--]);
	for (; i>=0; i--) printf("%.3d",Fib[n][i]);
	printf("\n");
	}
	}
	return 0;
	}

view raw [UVa] 495 Fibonacci Freeze.cpp hosted with ❤ by GitHub

UVa 10446 The Marriage Interview

本題連結
想法：
　　依照題意，將算過的答案記錄下來，在遞迴裡面如果已經算過，就直接回傳答案，避免重複計算。

	#include <cstdio>
	using namespace std;
	typedef unsigned long long int ullt;
	ullt C[61][61]={0};
	ullt trib (int n, int back)
	{
	if (n <= 1) return 1;
	if (C[n][back] != 0) return C[n][back];
	C[n][back] = 1;
	for (int i=1; i<=back; i++)
	C[n][back] += trib(n-i,back);
	return C[n][back];
	}
	int main()
	{
	int n, back, Case=1;
	while (scanf("%d%d",&n,&back)){
	if (n > 60) break;
	printf("Case %d: %llu\n",Case++,trib(n,back));
	}
	return 0;
	}

view raw [UVa] 10446 The Marriage Interview.cpp hosted with ❤ by GitHub

UVa 10334 Ray Through Glasses

本題連結

想法：
 　　觀察圖，能造成下次數量變多的折線，其最右邊"尖點"都位在上面那條線或下面那條線，例如a2=3，有'2'個"尖點"位在上面那條線，因此能使得a3比a2多出'2'條摺線(a3=a2+2=5)，在觀察a3，有'3'個尖點，因此能使a4比a3多出3個折線(a4=a3+3=8)。那麼尖點的產生方式在於前一個的折線數量，例如a2的尖點來自於a1的箭頭與上面那條線的交點，所以a2尖點的數量=a1，因此我們可得a3=a2+(a2尖點)=a2+a1。
　　簡而言之，本題為費伯那西數列，a(n)=a(n-1)+a(n-2)，而另外由於n可到1000，因此要自己寫大數加法。

	#include <cstdio>
	using namespace std;
	int fib[1001][501]={0};
	int main()
	{
	fib[0][0]=1;
	fib[1][0]=2;
	for (int i=2; i<=1000; i++){
	for (int j=0; j<500; j++){
	fib[i][j] += fib[i-2][j]+fib[i-1][j];
	if (fib[i][j]>9){
	fib[i][j] -= 10;
	fib[i][j+1]++;
	}
	}
	}
	int n;
	while (scanf("%d",&n)!=EOF) {
	int i = 500;
	while (fib[n][--i] == 0);
	for (; i>=0; i--)
	printf("%d",fib[n][i]);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10334 Ray Through Glasses.cpp hosted with ❤ by GitHub

UVa 900 Brick Wall Pattern

本題連結

想法：
　　我們用－表示橫的磚塊，∣表示直的磚塊，而兩個直的∣∣可以換成兩個橫的＝，以長度為5舉例，一開始我們可以先假設都是直的∣∣∣∣∣，首先我們可以將兩塊直的換成橫的＝，注意現在兩塊橫的有２個空位，分別是左邊和右邊，然後我們剩下3個直的磚塊，因此把這３個直的放到２個空位的方式為Ｈ(2,3)=4。再將兩個直的換成兩塊橫的，變成＝＝，現在４塊橫的有３個空位，然後剩下１個直的，因此為H(3,1)=3，最後全部加起來就是答案了，1+H(2,3)+H(3,1)=8。
　　本題其實寫出排列組合的C函數就完成了，H(m,n)=C(m+n-1,n)，因此可以先去寫UVa 369是C的題目，而注意type要用long long int。

	#include <cstdio>
	using namespace std;
	typedef long long int llt;
	llt H (int m,int n){
	m = (m+n-1);
	if (n > m/2) n = (m-n);
	int M[100],N[100],i,j;
	for (i=0; i<n; i++){
	M[i] = m - i;
	N[i] = i + 1;
	}
	for (i=0; i<n; i++)
	for (j=0; j<n; j++)
	if (N[j]!=1 && M[i]%N[j] == 0){
	M[i] = M[i]/N[j];
	N[j] = 1;
	break;
	}
	llt a=1, b=1;
	for (i=0; i<n; i++) {
	a *= M[i];
	b *= N[i];
	}
	return a/b;
	}
	int main()
	{
	int L;
	llt patterns;
	while (scanf("%d",&L))
	{
	if (!L) break;
	patterns = 1;
	for (int i=1; L-2*i >= 0; i++)
	patterns += H(i+1,L-2*i);
	printf ("%lld\n",patterns);
	}
	return 0;
	}

view raw [UVa] 900 Brick Wall Pattern.cpp hosted with ❤ by GitHub

UVa 10285 Longest Run on a Snowboard

本題連結
題意：
　　本題給予一個區域內的每個點的高度，滑雪只能由高的點往低的點滑，要求出在這個區域內最多能滑幾個點(滑最遠的方式)。

想法：
　　用一一枚舉的方式，也就是每個點都走走看。
我們定義遞迴式int find_longest (i,j,length) 是回傳area[i][j]這個點所能走的最遠長度。把所有點都算出其最遠長度，在從所有點中選出最大值輸出。


    

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N,R,C,area[101][101];
	char name[100];
	// 定義find_longest函數為回傳該點(area[i][j])盡可能走的最遠長度
	int find_longest (int i,int j,int length) // length為目前已經走的長度
	{
	int a=0, b=0, c=0, d=0;
	if (i-1>=0 && area[i-1][j]<area[i][j]) a = find_longest (i-1,j,length+1); //往上走
	if (i+1<R && area[i+1][j]<area[i][j]) b = find_longest (i+1,j,length+1); //往下走
	if (j-1>=0 && area[i][j-1]<area[i][j]) c = find_longest (i,j-1,length+1); //往左走
	if (j+1<C && area[i][j+1]<area[i][j]) d = find_longest (i,j+1,length+1); //往右走
	if (a || b || c || d) { //表示至少還有一個方向能走，回傳最遠的長度
	a = max(a,b); a = max(a,c); a = max(a,d);
	return a;
	}
	else return length; //四個方向都不能在往下走了，表示走到死路，回傳當前長度
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	scanf("%d",&N);
	while (N--)
	{
	scanf("%s%d%d",name,&R,&C);
	for (int i=0; i<R; i++)
	for (int j=0; j<C; j++)
	scanf("%d",&area[i][j]);
	int Max=0;
	for (int i=0; i<R; i++) // 一一枚舉每個點，選出最遠的長度
	for (int j=0; j<C; j++){
	int t = find_longest(i,j,1); // 一開始長度為1(自己也算)
	if (t > Max) Max = t;
	}
	printf("%s: %d\n",name,Max);
	}
	return 0;
	}

view raw [UVa] 10285 Longest Run on a Snowboard.cpp hosted with ❤ by GitHub

UVa 10037 Bridge

本題連結

題意：
　　每個人的移動速度不一樣，兩個人走時間是以較慢那個人，一次只能兩個人走過去橋的對面，然後需要有一個人把手電筒送回來，求耗費時間最少的方法。

想法：
　　先將數列P排序好，時間由小到大，本題可以分為幾種情況：

1. 只有一個人：直接走過去，時間為P[0]。
2. 兩個人：直接走過去，時間為P[1]。
3. 三個人：P[0],P[1],P[2]，時間為P[1]+P[0]+P[2]
      P[0] P[1]
      P[0]
      P[0] P[2]
4. 三個人以上：如果是偶數個人(例如4個人)，可利用P[0],P[1]不斷將最後面兩個人送到橋的對面，這樣就回到第二點，如果是奇數個人，不斷將最後面兩個送過去就回到第三點。
   將最後面兩個送到橋的對面有兩種方式，設時間最少兩人為P[0],P[1]，最後面兩個人為P[X],P[Y]：
   
   方案A(如Example)： 時間為 P[1]+P[0]+P[Y]+P[1]
      P[0] P[1]
      P[0]
      P[X] P[Y]
      P[1]
   方按B：時間為 P[X]+P[0]+P[Y]+P[0]
      P[0] P[X]
      P[0]
      P[0] P[Y]
      P[0]
   
   因此每次送最後兩個人過去的時候，要比較兩種方式的時間，如果(方案A<方案B)就使用方案A，否則使用方案B。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case,N,P[1001],i;
	scanf("%d",&Case);
	while (Case--)
	{
	scanf("%d",&N);
	for (i=0; i<N; i++) scanf("%d",&P[i]);
	sort (P,P+N);
	int sum=0;
	for (i=N-1; i>=3; i-=2){ //三個人以上
	int A = P[1]+P[0]+P[i]+P[1];
	int B = P[i]+P[0]+P[i-1]+P[0];
	if (A<B) sum += A;
	else sum += B;
	}
	if (i == 2) sum += (P[1]+P[0]+P[2]); //三個人
	else if (i == 1) sum += P[1]; //兩個人
	else if (i == 0) sum += P[0]; //一個人
	printf("%d\n",sum);
	for (i=N-1; i>=3; i-=2){
	int A = P[1]+P[0]+P[i]+P[1];
	int B = P[i]+P[0]+P[i-1]+P[0];
	if (A<B) printf("%d %d\n%d\n%d %d\n%d\n",P[0],P[1],P[0],P[i-1],P[i],P[1]);
	else printf("%d %d\n%d\n%d %d\n%d\n",P[0],P[i-1],P[0],P[0],P[i],P[0]);
	}
	if (i == 2) printf("%d %d\n%d\n%d %d\n",P[0],P[1],P[0],P[0],P[2]);
	else if (i == 1) printf("%d %d\n",P[0],P[1]);
	else if (i == 0) printf("%d\n",P[0]);
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 10037 Bridge.cpp hosted with ❤ by GitHub

UVa 642 Word Amalgamation

本題連結
想法：
　　給不同的單字不同的Hash值，在比對Hash值來找。


2014/2/23 更新： C++(11)寫法

	#include <cstdio>
	#include <iostream>
	#include <string>
	#include <algorithm>
	using namespace std;
	struct dictionary{
	string Word;
	int Hash;
	}dic[102];
	bool cmp (dictionary a, dictionary b)
	{
	return a.Word <= b.Word;
	}
	int main(){
	ios::sync_with_stdio(false);
	// freopen ("input.txt","rt",stdin);
	int nOfdic=0,i;
	string str;
	for (i = 0; cin >> str && str != "XXXXXX"; ++i){
	dic[i].Word = str;
	dic[i].Hash = 0;
	for (char c : dic[i].Word)
	dic[i].Hash += (3.56*c*c*c + 2*c*c + 337);
	}
	nOfdic = i;
	sort (dic, dic+nOfdic, cmp);
	while (cin >> str && str != "XXXXXX"){
	int Hash = 0;
	for (char c : str)
	Hash += (3.56*c*c*c + 2*c*c + 337);
	bool valid=0;
	for (i=0; i<nOfdic; i++){
	if (Hash == dic[i].Hash){
	valid = 1;
	cout << dic[i].Word << endl;
	}
	}
	if (!valid) cout << "NOT A VALID WORD" << endl;
	cout << "******" << endl;
	}
	}

view raw [UVa] 642-2 Word Amalgation.cpp hosted with ❤ by GitHub

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct dictionary{
	char w[10];
	int map;
	}dic[102];
	bool cmp (dictionary a,dictionary b){
	for (int i=0; ; i++)
	if (a.w[i] != b.w[i]) return a.w[i] < b.w[i];
	}
	int main(){
	freopen ("input.txt","rt",stdin);
	int nOfdic=0,i;
	for (i=0;;i++){
	gets(dic[i].w);
	if (dic[i].w[0]=='X' && dic[i].w[1]=='X' && dic[i].w[2]=='X' &&
	dic[i].w[3]=='X' && dic[i].w[4]=='X' && dic[i].w[5]=='X') break;
	dic[i].map = 0;
	for (int j=0; dic[i].w[j]; j++){
	int t = dic[i].w[j];
	dic[i].map += (3.56*t*t*t+2*t*t+337);
	}
	}
	nOfdic = i;
	sort (dic,dic+nOfdic,cmp);
	char line[10];
	while (gets(line)){
	if (line[0]=='X' && line[1]=='X' && line[2]=='X' &&
	line[3]=='X' && line[3]=='X' && line[5]=='X') break;
	int n = 0;
	for (i=0; line[i]; i++){
	int t = line[i];
	n += (3.56*t*t*t+2*t*t+337);
	}
	bool valid=0;
	for (i=0; i<nOfdic; i++){
	if (n == dic[i].map){
	valid = 1;
	printf("%s\n",dic[i].w);
	}
	}
	if (!valid) printf("NOT A VALID WORD\n");
	printf("******\n");
	}
	}

view raw [UVa] 642 Word Amalgamation.cpp hosted with ❤ by GitHub

UVa 11489 Integer Game

http://uva.onlinejudge.org/external/114/11489.html
題意：
　　由S先開始，每次拿掉一個數字都要使得剩下的"位數和"是3的倍數，如果找不到數字拿掉就輸了。

想法：
　　我們知道如果數字和為3的倍數，那麼接下來要拿掉的數字必須為3的倍數，才能繼續使得數字和為3的倍數。本題可將一連串的數字分成兩組：3的倍數和非3的倍數，然後有3種情況：

1. 如果非3倍數的數字和是3的倍數：那麼只要看3的倍數的數字個數是奇數個還偶數個就能決定贏家，因為當拿完3的倍數的數字後就無法再拿任何數字了。
2. 如果非3倍數的數字和不是3的倍數：
   那麼需要確認是否能從非3倍數的數字中找出使得數字和為3的倍數，
   ＊如果找的到，那麼就可以回到狀況1
   ＊如果找不到，代表是T獲勝，因為從一開始就無法拿掉任何數字。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int T,Case=1;
	scanf("%d",&T);
	getchar();
	while (T--){
	int N[1001],nOfN=0; //用來存非3的倍數的數字
	int nOf3x = 0; //該位數為3的倍數的個數
	int sum = 0; //非3倍數的和
	while (1){
	char c = getchar();
	if (c == '\n') break;
	else if ((c-'0')%3 == 0) nOf3x++;
	else {
	N[nOfN++] = (c-'0');
	sum += (c-'0');
	}
	}
	int who; //who為偶數代表S,奇數代表T
	if (nOf3x % 2) who = 0;
	else who = 1;
	if (sum%3 !=0) {
	int i;
	for (i=0; i<nOfN; i++)
	if ((sum-N[i])%3 == 0) break;
	if (i==nOfN) who=1;
	else who++;
	}
	printf("Case %d: ",Case++);
	if (who % 2) printf("T\n");
	else printf("S\n");
	}
	return 0;
	}

view raw [UVa] 11489 Integer Game.cpp hosted with ❤ by GitHub

UVa 10189 Minesweeper

題目連結

想法：
　　判斷如果輸入的字元為'*'，就將其八個方向都+1，最後輸出每個位置的數量。

註：本題只有Case與Case之間才有空行

	#include <cstdio>
	using namespace std;
	int n,m;
	char field[105][105];
	void Fill (int x,int y)
	{
	for (int i=-1; i<=1; i++)
	for (int j=-1; j<=1; j++)
	if (field[x+i][y+j]!='*')
	field[x+i][y+j]++;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int T = 1;
	while (scanf("%d %d",&n,&m))
	{
	if (!n && !m) break;
	if (T!=1) printf("\n");
	//初始化數量為0
	for(int i=1; i<=n; i++)
	for (int j=1; j<=m; j++)
	field[i][j]='0';
	//輸入，如果為'*'，則呼叫Fill將其八個方向數量+1
	for(int i=1; i<=n; i++){
	for(int j=1; j<=m; j++){
	char c;
	c = getchar();
	while (c=='\n') c = getchar();
	if (c == '*'){
	field[i][j]='*';
	Fill(i,j);
	}
	}
	}
	//輸出結果
	printf("Field #%d:\n",T++);
	for (int i=1; i<=n; i++){
	for (int j=1; j<=m; j++)
	printf("%c",field[i][j]);
	printf("\n");
	}
	}
	return 0;
	}

view raw [UVa] 10189 Minesweeper.cpp hosted with ❤ by GitHub

UVa 10077 The Stern-Brocot Number System

題目連結

想法：
　　初始化三個數L=0/1, M=1/1, R=1/0，設輸入的分數為a：

• 如果a<M，那麼要往左邊走，
      R = M;
      M = (L分子+M分子)/(L分母+M分母);
• 如果a>M，往右邊走，
      L = M;
      M = (R分子+M分子)/(R分母+M分母);
• 如果a==M，停止。

這題和二分搜尋很類似。

	#include <cstdio>
	using namespace std;
	struct fraction{
	int M; //Molecular 分子
	int D; //Denominator 分母
	};
	int main()
	{
	int m,n;
	while (scanf("%d%d",&m,&n))
	{
	if (m==1 && n==1) break;
	fraction L={0,1},M={1,1},R={1,0};
	while (1){
	long double t1 = (long double)m/n, t2 = (long double)M.M/M.D;
	if (t1 < t2){
	printf("L");
	R = M;
	M.M += L.M;
	M.D += L.D;
	}
	else if (t1 > t2){
	printf("R");
	L = M;
	M.M += R.M;
	M.D += R.D;
	}
	else{
	printf("\n");
	break;
	}
	}
	}
	return 0;
	}

view raw [UVa] 10077 The Stern-Brocot Number System.cpp hosted with ❤ by GitHub

UVa 10050 Hartals

本題題目連結

題意：
　　每個政黨都有發表演講的週期，只要星期日~星期四該天有任何一個政黨演講，hartal數目就+1，最後輸出hartal。
想法：
　　日數從1開始，每天對每個政黨的週期取餘數，若為0代表該日那個政黨有演講，hartal++。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int T,N,P,h[101]; // T: number of cases, N: number of days
	// P: number of parties, h[i]: hartal parameter for party i
	scanf("%d",&T);
	while (T--)
	{
	scanf("%d%d",&N,&P);
	for (int i=0; i<P; i++) scanf("%d",&h[i]);
	int hartal=0;
	for (int i=1; i<=N; i++){
	if (i%7 == 6) { // 跳過星期五和星期六
	i++; continue;
	}
	for (int j=0; j<P; j++){
	if (i%h[j] == 0) {
	hartal++;
	break;
	}
	}
	}
	printf("%d\n",hartal);
	}
	return 0;
	}

view raw [UVa] 10050 Hartals.cpp hosted with ❤ by GitHub

UVa 12192 Grapevine

本題題目連結

題意：
　　N為該矩形範圍的高，M為長，並輸入該範圍內每個數字，Q代表要測試幾次，每次給定L,U，在範圍內求出最大正方形的邊長，該正方形內的數字都要符合L<=H[i][j]<=U，也就是介於L和U之間。

想法：
　　題目給的範圍內的數字是有限制的，同列右邊比左邊大，同行下面比上面大，因此隨便框出一個正方形，其左上角必定為最小，右下角必定為最大，所以我們只要確認左上角>=L，和右下角<=U是否滿足即可。那麼首先從每列開始，在同一列使用二分搜尋找出左上角，然後沿著對角線二分搜尋找出右下角，最後把每列找出的正方形選出邊長最大的即可。

	#include <cstdio>
	using namespace std;
	int N,M,Q,L,U;
	int H[501][501];
	int BS_1 (int i) // 二分搜尋找出每列的符合>=L的最小值
	{
	int left = 0, right = M-1, mid;
	while (left != right){
	mid = (left+right)/2;
	if (H[i][mid] >= L) right = mid;
	else left = mid+1;
	}
	return left;
	}
	int BS_2 (int l_y,int l_x) // 二分搜尋找出右下斜角符合<=U的最大值
	{
	int r_x = l_x+(N-1-l_y); // r_x代表右下角的列index(橫), r_y為行index(直)
	if (r_x >= M) r_x = M-1; // 避免越界
	int r_y = l_y+(r_x-l_x);
	int mid_x,mid_y;
	while (l_x != r_x){
	mid_x = (l_x+r_x+1)/2;
	mid_y = (l_y+r_y+1)/2;
	if (H[mid_y][mid_x] <= U){
	l_x = mid_x;
	l_y = mid_y;
	}
	else {
	r_x = mid_x-1;
	r_y = mid_y-1;
	}
	}
	return l_x;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%d%d",&N,&M))
	{
	if (!N && !M) break;
	for (int i=0; i<N; i++)
	for (int j=0; j<M; j++)
	scanf("%d",&H[i][j]);
	scanf("%d",&Q);
	while (Q--)
	{
	scanf("%d%d",&L,&U);
	int Max_len=0;
	for (int i=0; i<N; i++){ //每次找一列
	int left = BS_1(i); //找出該正方形的左上角
	if (H[i][left] < L) continue; //解答檢查
	int right = BS_2(i,left); //找出該正方形的右下角
	if (H[i+(right-left)][right] > U) continue; //解答檢查
	int length = right-left+1;
	if (length > Max_len) Max_len = length;
	}
	printf ("%d\n",Max_len);
	}
	printf("-\n");
	}
	}

view raw [UVa] 12192 Grapevine.cpp hosted with ❤ by GitHub

UVa 10520 Determine it

本題題目連結

想法：
　　本題就是按照題目規則下去做，從a(n,0),a(n,1)~a(n,n)，然後算a(n-1,0)~a(n-1,n)，一直到a(1,0)~a(1,n)，最後print a(1,n)。

　　另外原本想說就算輸入19,20的答案也還再int的範圍內，沒想到送出去是WA，後來改成long long int就AC了=  ="

	#include <cstdio>
	using namespace std;
	typedef long long int llt;
	llt a[21][21];
	void max_1(llt &A,llt n,llt i,llt j)
	{
	llt Max = 0;
	for (llt k=i+1; k<=n; k++)
	if (a[k][1]+a[k][j] > Max) Max = a[k][1]+a[k][j];
	A += Max;
	}
	void max_2(llt &A,llt n,llt i,llt j)
	{
	llt Max = 0;
	for (llt k=1; k<j; k++)
	if (a[i][k]+a[n][k]) Max = a[i][k]+a[n][k];
	A += Max;
	}
	void max_3(llt &A,llt i,llt j)
	{
	llt Max = 0;
	for (llt k=i; i<j; i++)
	if (a[i][k]+a[k+1][j] > Max) Max = a[i][k]+a[k+1][j];
	A += Max;
	}
	void func(llt &A,llt n,llt i,llt j)
	{
	A = 0;
	if (i >= j){
	if (i < n) max_1(A,n,i,j);
	if (j>0) max_2(A,n,i,j);
	}
	else
	max_3(A,i,j);
	}
	int main()
	{
	llt n,an1;
	while (scanf("%lld%lld",&n,&an1)!=EOF){
	a[n][0] = 0;
	a[n][1] = an1;
	for (llt j=2; j<=n; j++)
	func(a[n][j],n,n,j);
	for (llt i=n-1; i>0; i--)
	for (llt j=0; j<=n; j++)
	func(a[i][j],n,i,j);
	printf("%lld\n",a[1][n]);
	}
	return 0;
	}

view raw [UVa] 10520 Determine it.cpp hosted with ❤ by GitHub

UVa 834 Continued Fraction

本題題目連結

想法：
　　這題可以自己舉幾個例子算出分數，找出規則，解法如下，由題目Example，從(43,19)逆推回去

1. 首先2的話就是43/19=2,43%19=5，那麼現在[2;] & (5,19)
2. 19/5=3,19%5=4，得到[2;3] & (5,4)
3. 倒數的緣故，交換兩數，現在[2;3] & (4,5)
4. 重複2~3步驟，直到第一個數為1

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	int a,b;
	while (scanf("%d%d",&a,&b)!=EOF){ // 43,19
	printf("[%d;",a/b); // [2;
	a %= b; // 5,19
	while(a!=1){
	printf("%d,",b/a); // [2;3, / [2;3,1,
	b %= a; // 5,4 / 4,1
	swap (a,b); // 4,5 / 1,4
	}
	printf("%d]\n",b); // [2;3,4,1]
	}
	return 0;
	}

view raw [UVa] 834 Continued Fraction.cpp hosted with ❤ by GitHub

UVa 494 Kindergarten Counting Game

想法：
　　檢查不是字母的下一個字元是不是字母，如果是數量就加一。對於這種input很多字串的情況，可以使用freopen("input.txt","rt",stdin)在debug時較為方便，但提交時記得刪除。

	#include <cstdio>
	using namespace std;
	char line[100000];
	bool is_word (char a){
	if (a<='z' && a>='a' || a<='Z' && a>='A')
	return 1;
	return 0;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (gets(line)){
	int num;
	num = is_word(line[0]);
	for(int i=0; line[i+1]; i++){
	if (!is_word(line[i])) num += is_word(line[i+1]);
	}
	printf("%d\n",num);
	}
	return 0;
	}

view raw [UVa] 494 Kindergarten Counting Game.cpp hosted with ❤ by GitHub

UVa 846 Steps

題意：
　　給定兩地的位置x,y，其距離為(x-y)，而第一步和最後一步的距離皆規定為1，每次踏下一步的距離只能比上一步的距離多1或少1或一樣，本題求最少走的步數，從Example來看x=45,y=50，距離為5，其最少步數為{1,2,2,1}。

想法：
　　因為本題只要求最少的步數即可，因此過程如何安排就不重要，只要符合規定即可，所以我們可以先一步從起點一步從終點開始往中間走，變成{1,1},{1,2,2,1},{1,2,3,3,2,1}...這樣，舉個例子如果兩地距離為14，那麼剛才的算法到{1,2,3,3,2,1}就會停止，因為已經12了，在+2*4就會超過14，這時候只要判斷12+4<14，再走一步就可以了，我們不管這步應該排在哪個位置，反正這步的距離一定<=4。還要考慮另外兩種情況，分別是兩地距離如果為17，那麼12+4<17，就要再兩步，而如果兩地距離為12，那麼就剛好。

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int N;
	int x,y;
	scanf("%d",&N);
	while (N--){
	scanf("%d%d",&x,&y);
	int steps = 0, length;
	long long int sum = 0, distance = y-x;
	for (length=0;;) {
	length++;
	if (sum + 2*length > distance) break;
	sum += 2*length;
	steps += 2;
	}
	if (sum + length < distance) steps += 2;
	else if (sum != distance) steps += 1;
	printf("%d\n",steps);
	}
	return 0;
	}

view raw [UV] 846 Steps.cpp hosted with ❤ by GitHub

UVa 10038 Jolly Jumpers

題意：
　　N個數的數列中，(1,2,3...,N-1)這些值都要被兩數字的差值涵蓋到，從Example來說，(1,4,2,3)的差值分別為(3,2,1)，所以有涵蓋(1~3)，因此為Jolly，(1,4,2,-1,6)的差值為(3,2,3,5)沒有涵蓋(1~5)所以不是Jolly

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int N;
	while (scanf("%d",&N)!=EOF){
	int s[3001],check[3001]={0};
	bool ok=1;
	scanf("%d",&s[0]);
	for (int i=1; i<N; i++) {
	scanf("%d",&s[i]);
	int temp = abs(s[i]-s[i-1]);
	if (temp<=3000) check[temp]++;
	}
	for (int i=1;i<N;i++)
	if (check[i]==0) { ok = 0; break; }
	if (ok) printf("Jolly\n");
	else printf("Not jolly\n");
	}
	return 0;
	}

view raw [UVa] 10038 Jolly Jumpers.cpp hosted with ❤ by GitHub

UVa 10340 All in All

如果陣列開很大的情況下，要放在global，不然會造成stack overflow，就會看到RuntimeError的出現。

	#include <cstdio>
	using namespace std;
	char s[100000],t[100000];
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%s%s",s,t)!=EOF){
	int i=0,j=0;
	for (;t[i];i++){
	if (t[i] == s[j]) j++;
	}
	if (!s[j]) printf("Yes\n");
	else printf("No\n");
	}
	return 0;
	}

view raw [UVa] 10340 All in All.cpp hosted with ❤ by GitHub

UVa 714 Copying Books

本題題目連結
想法：
　　這題跟UVa 11413 Fill the Containers很類似，題目給定M本書及K個員工(1<=K<=M<=500)，每本書有不同的頁數，同本書只能分配給同個員工，我們用二分搜尋找出每個人的工作量(頁數)的上限，(題目要求工作量越少越好，但如果太少就需要>K個員工)。此外如果有多組解的情況，index越大的員工所分配的書要盡量的多，因此分配書的時候index從後面開始，但注意分配時每個人至少要有一本書，因此如果(剩下的書<=剩下的人)，就算那個人還沒分完，也要直接換下一個人。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int M, K;
	int p[501];
	int ans[501][501],n[501]; // n is the index of ans[i];
	int main()
	{
	int N;
	scanf("%d",&N);
	while (N--){
	scanf ("%d%d",&M,&K);
	long long int Min=0,Max=0,mid;
	for (int i=0;i<M;i++) {
	scanf("%d",&p[i]);
	if (p[i] > Min) Min=p[i];
	Max += p[i];
	}
	while (Min < Max){
	int amount=1;
	long long int sum=0;
	mid = (Min+Max)/2;
	for (int i=0;i<M;i++){
	if (sum+p[i] > mid){
	amount++;
	sum = 0;
	}
	sum += p[i];
	}
	if (amount > K) Min = mid+1;
	else Max = mid;
	}
	fill (n,n+501,0);
	long long sum = 0;
	// 因為如果有多組解，後面的人要分配多一點書，因此i,j從後面開始
	for (int i=M-1, j=K-1; i>=0; i--){ // i: book index, j: scriber index
	if (sum+p[i] > Max || j>i){ // j>i: 因為每個人都至少要有一本書
	j--;
	sum = 0;
	}
	sum += p[i];
	ans[j][n[j]++] = p[i];
	}
	for (int i=0; i<K; i++){
	for (int j=n[i]-1; j>=0; j--){
	if (i!=0 || j!=n[0]-1) printf(" ");
	printf("%d",ans[i][j]);
	}
	if (i != K-1) printf(" /");
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 714 Copying Books.cpp hosted with ❤ by GitHub

UVa 10474 Where is the Marble

本題題目連結
想法：
　　將數列排序好後直接用二分搜尋即可。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N,Q,Case=1;
	int n[10001],q[10001];
	int Search (int q)
	{
	int L=0, R=N-1, mid;
	while (L!=R){
	mid = (L+R)/2;
	if (n[mid] >= q) R = mid;
	else L = mid+1;
	}
	if (n[L] == q) return L+1;
	else return -1;
	}
	int main()
	{
	//freopen ("input.txt","rt",stdin);
	while (scanf("%d%d",&N,&Q)){
	if (!N && !Q) break;
	for (int i=0;i<N;i++) scanf("%d",&n[i]);
	for (int i=0;i<Q;i++) scanf("%d",&q[i]);
	sort (n,n+N);
	printf("CASE# %d:\n",Case++);
	for (int i=0; i<Q; i++){ // q loop
	int position = Search(q[i]);
	if (position == -1) printf("%d not found\n",q[i]);
	else printf("%d found at %d\n",q[i],position);
	}
	}
	return 0;
	}

view raw [UVa] 10474 Where is the Marble.cpp hosted with ❤ by GitHub

UVa 10341 Solve It

本題題目連結
p*e^-x + q*sin(x) + r*cos(x) + s*tan(x) + t*x² + u = 0
0<=p, r<=20 and -20<=q,s,t<=0

想法：
　　因為題目的係數有範圍限制，使得x越大，f(x)的值就越小，為遞減函數，因此可使用二分搜尋逼近答案。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	#define F(x) (p*exp(-x) + q*sin(x) + r*cos(x) + s*tan(x) + t*pow(x,2) + u)
	int main()
	{
	int p, q, r, s, t, u;
	while (scanf("%d %d %d %d %d %d",&p, &q, &r, &s, &t, &u)!=EOF)
	{
	double Min=0.0, Max=1.0, mid;
	for (int i=0; i<100; i++){
	mid = (Min+Max)/2;
	if (F(mid)>0) Min = mid;
	else Max = mid;
	}
	if (fabs(F(mid)-0) > 1e-10) printf ("No solution\n");
	else printf("%.4lf\n",mid);
	}
	return 0;
	}

view raw [UVa] 10341 Solve It.cpp hosted with ❤ by GitHub

UVa 11413 Fill the Containers

題意： 　　
　　給定N個牛奶瓶子，以及M個容器，每個牛奶瓶子n[i]的容積不一樣(題目會給)，我們所要求的是一個"容器"的容積至少要"多少'才能使得只用'M'個就能把那N個牛奶瓶裝完，而裝的時候有幾個規則：第一個牛奶瓶倒入容器後才能換第二個，每個牛奶瓶只能到入同個容器(因此如果該容器還有空間但不夠裝完這個牛奶瓶的話，就只能換下個容器)。
　　從Example來看：5個牛奶瓶子要到入"3"個容器裡(沒錯，題目規定不多不少就是3個)，那麼至少每個容器的容積要6才能滿足該條件{(1,2,3),(4),(5)}。 

想法： 　　
　　使用binary search找出符合的條件，Left=(所有牛奶瓶容積最大的那個)，Right=(所有牛奶瓶的容積)。

	#include<cstdio>
	using namespace std;
	int N,M; // N:牛奶瓶數量 M:容器數量
	int n[1000001]; // 牛奶瓶的個別容積
	int main()
	{
	while (scanf("%d%d",&N,&M)!=EOF){
	int left=0,right=0,mid;
	for (int i=0; i<N; i++) {
	scanf("%d",&n[i]);
	if (n[i]>left) left = n[i];
	right += n[i];
	}
	while (left < right){ //使用二元搜尋找出最小容器的容積能使amount==M
	mid = (left+right)/2;
	int sum=0; // 用來累積每瓶牛奶的容量
	int amount=0; // 用來計數用了多少容器
	for (int i=0; i<N; i++){
	sum += n[i];
	if (sum > mid) {
	amount++;
	sum = n[i];
	}
	else if (sum == mid){
	amount++;
	sum = 0;
	}
	}
	if (sum>0) amount++;
	if (amount > M) left = mid+1; //如果大於題目規定代表我們的容積太小，導致容器太多
	else right = mid;
	}
	printf("%d\n",left);
	}
	return 0;
	}

view raw [UVa] 11413 Fill the Containers.cpp hosted with ❤ by GitHub

UVa 10487 Closest Sums

想法：
　　先將數列n排序好，之後n[j]從j=0開始，搜尋(q-n[j])，如果存在，則代表本題得解，如果不存在，則從最接近(q-n[j])的數字中挑選一個n[k]使得(n[i]+n[k])最接近q，將答案放入ans，然後j=1繼續搜尋...，直到n[j]>(q/2)為止，輸出ans。

	#include <cstdio>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	int N,M;
	int n[1001],q[26];
	int Search(int a,int start){
	int L = start;
	int R = N-1;
	int mid;
	while (L<=R){
	mid = (L+R)/2;
	if (a==n[mid]) return mid;
	if (a>n[mid]) L = mid+1;
	else R = mid-1;
	}
	return mid;
	}
	int Closest(int q,int a,int b){
	if (abs(a-q) <= abs(b-q)) return a;
	else return b;
	}
	int main()
	{
	int Case=1,i,j;
	while (scanf("%d",&N)){
	if (N==0) break;
	for (i=0;i<N;i++) scanf("%d",&n[i]);
	sort (n,n+N);
	scanf("%d",&M);
	for (i=0;i<M;i++) scanf("%d",&q[i]);
	printf("Case %d:\n",Case++);
	for (i=0;i<M;i++){ // q loop
	int ans=n[0]+n[1];
	for (j=0;n[j]<=(q[i]/2) && j+1<N;j++){ // n loop
	int k = Search(q[i]-n[j],j+1);
	if ((n[j]+n[k])==q[i]) { ans = q[i]; break; }
	else {
	if (k-1!=j) ans = Closest(q[i],ans,n[j]+n[k-1]);
	ans = Closest(q[i],ans,n[j]+n[k]);
	if (k+1<N) ans = Closest(q[i],ans,n[j]+n[k+1]);
	}
	}
	printf("Closest sum to %d is %d.\n",q[i],ans);
	}
	}
	return 0;
	}

view raw [UVa] 10487 Closest Sums.cpp hosted with ❤ by GitHub

UVa 11057 Exact Sum

想法：
　　先將書本價錢排序，然後i=0開始，.搜尋(用binary search)確認(M-book[i])是否存在，如果存在就先將該組答案暫時保存，因為題目有說如果有多組答案要寫出差距最小的那組，因為我們已經排序，所以越後面的答案的差距越小。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N,M,i; // N: number of books, M: money Peter has
	int book[10001]; // price of each book
	int Search (int n,int start){ //使用binary search
	int left=start;
	int right=N;
	int mid;
	while (left<=right){
	mid = (left+right)/2;
	if (n==book[mid]) return mid;
	if (n>book[mid]) left=mid+1;
	else right=mid-1;
	}
	return -1;
	}
	int main()
	{
	while (scanf("%d",&N)!=EOF){
	for (i=0;i<N;i++) scanf("%d",&book[i]);
	scanf("%d",&M);
	sort (book,book+N);
	int ans[10000],a=0;
	for (i=0;book[i]<(M/2);i++){
	if (Search(M-book[i],i+1)!=-1) {
	ans[a++]=book[i];
	}
	}
	printf("Peter should buy books whose prices are %d and %d.\n\n",ans[a-1],M-ans[a-1]);
	}
	return 0;
	}

view raw [UVa] 11057 Exact Sum.cpp hosted with ❤ by GitHub

UVa 11520 Fill the Square

題意：
　　如果它不是'.'，那麼該位置的字母已經是固定的了，剩下是'.'的位置就要由我們依照左到右，上到下的順序來分別填入該位置一個英文字母，而填入字母的方式是由'A'開始，如果其上下左右已經有'A'，那麼再換'B'，以此類推....，如果'A'能填就要填，舉個例子：
..B
.B.
...
的解答為
ACB
CBA
ACB
而不是底下這個
BAB
ABA
BAB

想法：
如果該點為'.'，則從'A'開始，檢查其上下左右來決定'A'可否填入，不然就換'B','C'....，一直到可以填入為止

	#include <cstdio>
	using namespace std;
	char square[12][12];
	void Fill (int n,int i,int j){
	char filled = 'A';
	bool up,left,right,down;
	while (filled <= 'Z'){
	if (i-1<0 || square[i-1][j]!=filled) up=1; else up=0;
	if (i+1>=n || square[i+1][j]!=filled) down=1; else down=0;
	if (j-1<0 || square[i][j-1]!=filled) left=1; else left=0;
	if (j+1>=n || square[i][j+1]!=filled) right=1;else right=0;
	if (up && down && left && right){
	square[i][j] = filled;
	printf("%c",filled);
	break;
	}
	else filled += 1;
	}
	}
	int main()
	{
	int t,n,Case=1;
	scanf("%d",&t);
	while (t--)
	{
	scanf("%d",&n);
	gets(square[0]);
	for(int i=0;i<n;i++) gets(square[i]);
	printf("Case %d:\n",Case++);
	for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	if (square[i][j]!='.')
	printf("%c",square[i][j]);
	else Fill(n,i,j);
	}
	printf("\n");
	}
	}
	return 0;
	}

view raw [UVa] 11520 Fill the Square.cpp hosted with ❤ by GitHub

UVa 11729 Commando War

想法：B的總合是固定的，那麼要使得答案最小，就要盡量讓J的時間範圍重疊，因此將J由大排到小

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct soldier{
	int B;
	int J;
	}a[10001];
	bool cmp(soldier a,soldier b){
	return a.J > b.J;
	}
	int main()
	{
	int N,Case=1;
	while (scanf("%d",&N)){
	if (N == 0) break;
	for(int i=0;i<N;i++) scanf("%d%d",&a[i].B,&a[i].J);
	sort (a,a+N,cmp);
	int time=0;
	int ans=0;
	for (int i=0;i<N;i++) {
	time += a[i].B;
	ans = max(ans,time+a[i].J);
	}
	printf("Case %d: ",Case++);
	printf("%d\n",ans);
	}
	return 0;
	}

view raw [Uva] 11729 Commando War.cpp hosted with ❤ by GitHub

UVa 11292 Dragon of Loowater

想法：

1. 排序m[i]與n[i]由小到大
2. 一一找尋並累加money

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	int M,N,i,j; // M: number of heads, N: number of knights
	int m[20010],n[20010]; // m[i]: diameter of head, n[i]: height of knight
	while (scanf("%d %d",&M,&N)){
	if (!M && !N) break;
	for(i=0;i<M;i++) scanf("%d",&m[i]);
	for(i=0;i<N;i++) scanf("%d",&n[i]);
	sort(m,m+M);
	sort(n,n+N);
	long long int paid=0;
	for(i=0,j=0;i<N;i++){
	if(n[i] >= m[j]){
	paid += n[i];
	if(++j == M) break;
	}
	}
	if(j == M) printf("%lld\n",paid);
	else printf("Loowater is doomed!\n");
	}
	return 0;
	}

view raw [UVa] 11292 Dragon of Loowater.cpp hosted with ❤ by GitHub

UVa 11054 Wine trading in Gergovia

想法：
　　舉個例子，5 1 3 2 -11，先假設答案ans=0表示運送所需的單位，那麼

1. 可以看成將第一個人要買的酒移到第二個人，並將ans加上5，ans=5
2. 那麼現在變成6 3 2 -11，繼續將第二個人移到第三個人，ans=11
3. 變成9 2 -11，一樣移到第四個人，ans=20
4. 變成11 -11，移到最後一個人，ans=31，得解

　　再用example作為例子

1. 5 -4 1 -3 1 , ans=0
2. 1 1 -3 1 , ans=5(+5)
3. 2 -3 1 , ans=6(+5+1)
4. -1 1 , ans=8(+5+1+2)
5. 0 , ans=9(+5+1+2+1) //因為是運送的單位，記得加絕對值

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int a[100001];
	int main()
	{
	int n;
	while(scanf("%d",&n)){
	if (n==0) break;
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);
	long long int ans=0;
	for(int i=0;i<n-1;i++){
	ans += abs(a[i]);
	a[i+1] += a[i];
	}
	printf("%lld\n",ans);
	}
	return 0;
	}

view raw [UVa] 11054 Wine trading in Gergovia.cpp hosted with ❤ by GitHub

UVa 10249 The Grand Dinner

題意：
　　有M個隊伍以及N張桌子，每個隊伍的人數與每張桌子的座位均不一樣，現在要將同個隊伍的隊員分配到不同的桌子(同隊的不能在同張桌子，否則輸出0)
想法：

1. 每個隊伍的隊員排的時候都先挑剩餘位子最多的桌子
2. 如果該隊隊伍人數大於桌子數量或是座位不足則跳出並print 0

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct temp_type{
	int *t;
	int index;
	}temp[51];
	bool cmp(temp_type a,temp_type b){
	return *(a.t)>*(b.t);
	}
	int main()
	{
	int M,N; //M:number of teams, N:number of tables
	int m[71],n[51]; //m:number of members of a team, n:seating capacity of a table
	while (scanf("%d %d",&M,&N)){
	if (!M && !N) break;
	int i,j,ans[71][100];
	for(i=0;i<M;i++) scanf("%d",&m[i]);
	for(i=0;i<N;i++) scanf("%d",&n[i]);
	bool ok=1;
	for(i=0;i<M && ok;i++){
	if(m[i]>N) {ok=0; break;} //隊員數量大於桌子數量
	//將桌子的座位數量與index複製到temp
	//並依照剩餘座位數量排序
	for(j=0;j<N;j++) {
	temp[j].t=&n[j];
	temp[j].index=j;
	}
	sort(temp,temp+N,cmp);
	int n_ans=0;
	//隊員m[i]個，排入剩餘位子前m[i]多的桌子
	for(j=0;j<m[i];j++){
	if(*(temp[j].t)<=0) {ok=0; break;}
	else {
	(*(temp[j].t))--;
	ans[i][n_ans++]=temp[j].index;
	}
	}
	sort(ans[i],ans[i]+n_ans); //將index由小排到大
	}
	if(ok){
	printf("1\n");
	for(i=0;i<M;i++) {
	for(j=0;j<m[i];j++)
	printf("%d ",ans[i][j]+1);
	printf("\n");
	}
	}
	else printf("0\n");
	}
	return 0;
	}

view raw [UVa] 10249 The Grrand Dinner.cpp hosted with ❤ by GitHub

UVa 10020 Minimal Converge

題意：
　　數線上有很多條線段，每條線段給左右兩端的座標(L,R)，題目問如何用最少的線段去覆蓋[0,M]這個範圍

想法：

1. 依照L值來排序
2. 第一次left=0，從a[0]開始找(a[i].L要小於0)，找到一個最大R值(Max)的線段a[Max_index]
3. left=Max_index：下次從這開始找
4. right=Max
5. 第二次一樣從left開始找(a[i].L要小於right)，找一個最大R值(Max)的線段a[Max_index]
6. 重複3~5，直到Max大於M

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct line{
	int L;
	int R;
	}a[100001];
	bool cmp(line a,line b){
	if(a.L == b.L) return a.R < b.R;
	return a.L < b.L;
	}
	int main()
	{
	int T,M;
	scanf("%d",&T);
	while (T--){
	scanf("%d",&M);
	int i,j,n=0;
	while (scanf("%d%d", &a[n].L,&a[n].R)){
	if (!a[n].L && !a[n].R) break;
	n++;
	}
	sort(a,a+n,cmp);
	int ans=0,left=0,right=0,Max=0,Max_index; //left是存a_index,right是存max
	int List[100001],l_index=0;
	bool Ans=1;
	while (Max<M){ //不斷靠近M
	right=Max;
	for(i=left;a[i].L<=right && i<n;i++){ /*a[i].L不能>right，不然範圍會沒有覆蓋*/
	if (Max<a[i].R){ //在沒有超過範圍的情況下，不斷找最靠近右邊的R
	Max=a[i].R;
	Max_index=i;
	}
	}
	if (Max==right) {Ans=0; break;} //找不到的情況
	List[l_index++]=Max_index; //將找到的點放入List
	ans++;
	left = i;
	}
	if(Ans){
	printf("%d\n",ans);
	for(i=0;i<l_index;i++)
	printf("%d %d\n",a[List[i]].L,a[List[i]].R);
	}
	else printf("0\n");
	if(T) printf("\n");
	}
	return 0;
	}

view raw [UV] 10020 Minimal Converge.cpp hosted with ❤ by GitHub

UVa 311 Packets

題意：
　　本題共有1x1,2x2,3x3,4x4,5x5,6x6共6種箱子數個(每行Input代表各個的數量)，而它們的高度均一樣，所以本題只考慮平面，而題目問的是，有一個大箱子的大小為6x6，如何使用最少數量的大箱子將上述的6種箱子包裝起來。

想法：

1. 6x6：1個6x6剛好裝滿一個大箱子
2. 5x5：一個5x5搭配11個1x1
3. 4x4：一個4x4搭配5個2x2，如果2x2不夠改用4個1x1代替
4. 3x3：要分別討論1~3個3x3 與2x2和1x1搭配的數量
5. 2x2與1x1：如果有剩下再放進大箱子

	#include <cstdio>
	using namespace std;
	void parcel(int &box,int num[],int &space,int w);
	int main()
	{
	int num[7];
	while(scanf("%d %d %d %d %d %d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6])){
	int i=1;
	for(;i<=6;i++)
	if(num[i]!=0) break;
	if(i==7) break;
	int box=num[6]+num[5]+num[4];
	num[1]-=11*num[5]; //一個5x5搭配11個1x1
	num[2]-=5*num[4]; //一個4x4搭配5個2x2(如果2x2不夠的情況最底下會考慮)
	box+=(num[3]/4); if(num[3]%4) box++;
	switch(num[3]%4){ //3x3情況要特別討論
	case 0: break;
	case 1:
	num[2]-=5;
	num[1]-=7;
	break;
	case 2:
	num[2]-=3;
	num[1]-=6;
	break;
	case 3:
	num[2]-=1;
	num[1]-=5;
	break;
	}
	if (num[2]>0){ //如果2x2還有剩
	box+=num[2]/9; if(num[2]%9) box++;
	num[1]-=(36-(num[2]%9)*4);
	}
	else if (num[2]<0)
	num[1]-=(-num[2])*4; //將不夠的2x2用4個1x1來補
	if (num[1]>0){ //如果1x1還有剩
	box+=(num[1]/36); if(num[1]%36) box++;
	}
	printf("%d\n",box);
	}
	return 0;
	}

view raw [UVa] 311 Packets.cpp hosted with ❤ by GitHub

UVa 10282 & POJ 2503 Babelfish

想法：
　　本題可直接使用STL的map來做string與string的對應，用printf而不用cout可提升效率，因此使用c_str()將c++字串轉為c字串(POJ實測是985ms與766ms)。

	#include <cstdio>
	#include <map>
	#include <string>
	using namespace std;
	int main()
	{
	map<string,string>m;
	char line[200];
	while(gets(line)){
	if (line[0]=='\0') break;
	char a[50],b[50];
	sscanf(line,"%s %s",a,b);
	m[b]=a;
	}
	while(gets(line)){
	if (line[0]=='\0') break;
	if (m[line]=="\0") //map如果沒對應到，其內容為"\0"
	printf("eh\n");
	else
	printf("%s\n",m[line].c_str()); //把C++字串換回C字串
	}
	return 0;
	}

view raw [POJ] 2503 Babelfish.cpp hosted with ❤ by GitHub

UVa 120 Stacks of Flapjacks

　　題目的意思就是要將數字由小到大排序，但排序的方法稱為flip，比如{1,3,4,2}這些數字，如果flip(2) ('4'這個數字)的話，就要把'4'前面的數字做顛倒排序，變成{4,3,1,2}，那再flip(1) ('2'這個數字)的話，就會變成{2,1,3,4}，最後就是想辦法用最少步驟變成{1,2,3,4}

想法：
　　每次都將最大的數字移到最右邊，要移到最右邊，就先判斷

1. 本來就在最右邊：不動，換下一個最大值
2. 在最左邊：直接flip(1)將它換到最右
3. 在中間：先flip(自己的位置)換到最左邊後，再flip(1)換到最右邊

	#include <cstdio>
	using namespace std;
	int stk[32],nOfstk,Max,Max_pos;
	void flip(int n);
	//在code裡為求方便index是從左邊1,2,..,n到右邊，與題目的位置標示相反，在print的時候才換成題目的標示方法
	int main()
	{
	char line[200];
	while(gets(line)){
	nOfstk=0;
	for(int i=0;i<32;i++) stk[i]=0;
	for(int i=0;line[i];i++){
	if(line[i]==' '){
	printf("%d ",stk[nOfstk]);
	nOfstk++;
	}
	else{
	stk[nOfstk]*=10;
	stk[nOfstk]+=(line[i]-'0');
	}
	}
	printf("%d\n",stk[nOfstk]);
	//每次都將最大值放到右邊
	for(int i=nOfstk;i>=0;i--){
	Max=0;
	for(int j=0;j<=i;j++) //找剩下未排序的最大值
	if(stk[j]>Max){ Max=stk[j]; Max_pos=j;}
	if(Max_pos!=i){ //最大值不在最右
	if(Max_pos!=0) //不在最左
	flip(Max_pos); //先翻到最左
	flip(i); //再翻到最右
	}
	}
	printf("0\n");
	}
	return 0;
	}
	void flip(int n)
	{
	printf("%d ",nOfstk-n+1);
	int temp[32];
	for(int i=0;i<=n;i++)
	temp[i]=stk[i];
	for(int i=0,j=n;i<=n;i++,j--){
	stk[i]=temp[j];
	if(stk[i]==Max) Max_pos=i;
	}
	}

view raw [UVa] 120 Stacks of Flapjacks.cpp hosted with ❤ by GitHub

UVa 10245 The Closest Pair Problem

求任兩點的最短距離，如果全部枚舉的話，時間複雜度n^2，一定會TLE。

想法：

• 將所有點依x座標排序
• 從中間切開，將所有點分成左右兩個集合(設line為中線x座標)
• 左右兩邊各求出任兩點最小值a,b，設d為min(a,b)
• 那麼現在只要枚舉(line+-d)這範圍內的點有沒有比d還更小的值即可

遞迴定義：

• divide(point_type a[], low, high)  
• 求出a[low]~a[high]範圍內任兩點的最短距離
• combine(point_type a[], low, mid, high, min_left, min_right)
• d=min(min_left,min_right)
• line=(a[mid].x+a[mid+1].x)/2
• 合併左右兩個集合，並確認在(line+-d)的範圍內有沒有比d更小的值，最後回傳最小值

更詳細圖解可參考KuoE0:http://www.slideshare.net/KuoE0/acmicpc-uva10245

注意輸入輸出皆要用double

	#include <cstdio>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	struct point_type{
	double x;
	double y;
	};
	bool cmp(point_type a,point_type b)
	{
	return a.x<b.x;
	}
	double distance(point_type a,point_type b);
	double divide(point_type a[],int low,int high);
	double combine(point_type a[],int low,int mid,int high,double min_left,double min_right);
	int main()
	{
	int N;
	point_type point[10001];
	while(scanf("%d",&N))
	{
	if (N==0) break;
	for(int i=0;i<N;i++)
	scanf("%lf %lf",&point[i].x,&point[i].y);
	sort(point,point+N,cmp);
	double dis=divide(point,0,N-1);
	if(dis>=10000.0) printf("INFINITY\n");
	else printf("%.4lf\n",dis);
	}
	return 0;
	}
	double Distance(point_type a,point_type b)
	{
	return (double)sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
	}
	double divide(point_type a[],int low,int high)
	{
	if(low>=high) return 99999; //切到只剩1個點，return inf
	int mid=(low+high)/2;
	double min_left=divide(a,low,mid);
	double min_right=divide(a,mid+1,high);
	return combine(a,low,mid,high,min_left,min_right);
	}
	double combine(point_type a[],int low,int mid,int high,double min_left,double min_right)
	{
	double d=(min_left<min_right)?min_left:min_right;
	double line=(double)(a[mid].x+a[mid+1].x)*0.5; //line:左集合與右集合的中間線x座標
	double min_D=d;
	for(int i=mid+1;a[i].x<line+d && i<=high;i++){ //枚舉line+-d範圍內左右集合的點
	for(int j=mid;a[j].x>line-d && j>=low;j--){
	double temp=Distance(a[i],a[j]);
	if(temp<min_D) min_D=temp;
	}
	}
	return min_D;
	}

view raw [UVa] 10245 The Closest Pair Problem.cpp hosted with ❤ by GitHub

UVa 10666 The Eurocup is Here!

題意：

• Team 4贏過Team 6，而Team 6贏過Team 7，那麼表示Team 4確定贏過(優於)Team 7，也可說Team 7比Team 4差。
• Team 0同時贏過Team 4和Team 2，則Team 4和Team 2關係無法確定。
• 因為隊伍與隊伍之間關係有些確定有些不確定，本題要求出Team X可能最佳為第幾名，以及最差為第幾名

想法：

• 1.找最佳：只要找到贏過Team X的共有n隊，那麼n+1即是Team X的最佳名次。
• 1.做法：win(x)函數找到贏過Team X的隊伍(設為a)，再繼續win(a)找到贏過Team a的隊伍(設為b)，一直找到底(Team 0)為止，計算途中總共幾隊。
• 2.找最差：計算比Team X差的隊伍總共有幾隊，那麼Team X的最差名次就是全部隊伍數減掉比Team X還差的隊伍數
• 2.做法：Team X如果在Round r輸掉，那麼比Team X差的隊伍數為(2^(r-1)-1)，可多次觀察樹狀圖r=1,2,3,4...其結果為0,1.3,7...得知

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef long long int llt;
	llt round(llt x){ //Team x到達哪個Round(在哪個Round 輸掉)
	for(llt i=1,j=1;;i*=2,j++)
	if(x%i) return j-1;
	}
	llt win(llt x){ //贏Team x的Team
	return x-pow(2,round(x)-1);
	}
	llt optimistic(llt n,llt x){
	if (x==0) return 1;
	llt num=0; //贏Team X的隊數
	while(1){
	x=win(x);
	num++;
	if(x==0) break;
	}
	return num+1;
	}
	llt pessimistic(llt n,llt x){
	if (x==0) return 1;
	llt all=pow(2,n);
	llt numOfx_worse=pow(2,round(x)-1)-1; //比Team x差的隊數
	return all-numOfx_worse;
	}
	int main()
	{
	llt M,N,X;
	scanf("%lld",&M);
	while(M--){
	scanf("%lld %lld",&N,&X);
	printf("%lld %lld\n",optimistic(N,X),pessimistic(N,X));
	}
	return 0;
	}

view raw [UVa] 10666 The Eurocup is Here!.cpp hosted with ❤ by GitHub

POJ 1664 放蘋果

想法：

　　因為盤子皆一樣，例如(1,1,3)和(1,3,1)是同樣的，所以排的時候以遞增的方式排，只保留(1,1,3)這組，故左邊的數字不大於右邊的數字。在一開始(0,0,0)時，若最左邊的盤子要+1，則右邊兩個也要跟著+1才能使上面的條件成立，照此規則，當某個盤子要+1時，其右邊的盤子也要跟著+1，所以要注意此動作是否會造成蘋果不夠(if(m-i>=0))，而當蘋果剛好分完(m=0)或是只剩最右邊的盤子(n=1)時，遞迴結束。

	#include<cstdio>
	using namespace std;
	long long int sum=0;
	void func(int m,int n);
	int main()
	{
	int t,m,n,i,j;
	scanf("%d",&t);
	while(t--){
	sum=0;
	scanf("%d %d",&m,&n);
	func(m,n);
	printf("%lld\n",sum);
	}
	return 0;
	}
	void func(int m,int n) //m顆蘋果分n堆
	{
	if(m==0 || n==1) {
	sum++;
	return ;
	}
	int i,j;
	for(i=n;i>=1;i++){ //n堆~1堆
	if(m-i>=0)
	func(m-i,i);
	}
	}

view raw [POJ] 1664 放蘋果.cpp hosted with ❤ by GitHub

POJ 1068 Parencodings

S (((()()())))

P-sequence    4 5 6666

W-sequence    1 1 1456

P_seq表示第i個')'前共有n個'('

W_seq表示第i個'( )'裡包含自己有幾個'( )'

想法：用一個parenthes陣列存每個括弧，找到第i個')'就往前找'('形成'( )'，已經配對的'('就跳過，看中間經過幾個已配對'('就是表示總共包含幾個'( )'

	#include <cstdio>
	using namespace std;
	int main()
	{
	int t,n,p_seq[25],parenthes[10000],n_p=0,i,j;
	scanf("%d",&t);
	while(t--){
	scanf("%d",&n);
	for(p_seq[0]=0,i=1,n_p=0;i<=n;i++){
	scanf("%d",&p_seq[i]);
	for(j=0;j<p_seq[i]-p_seq[i-1];j++)
	parenthes[n_p++]=0;
	parenthes[n_p++]=1;
	}
	bool matched[10000]={0}; //1:left parenthes is matched
	for(i=0;i<n_p;i++){
	int num=0;
	if(parenthes[i]==1){
	for(j=1;i-j>=0;j++){
	if(parenthes[i-j]==0 && matched[i-j]==0){
	num++;
	matched[i-j]=1;
	printf("%d ",num);
	break;
	}
	else if(parenthes[i-j]==0 && matched[i-j]==1)
	num++;
	}
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw [POJ] 1068 Parencodings.cpp hosted with ❤ by GitHub

2014/2/17 更新：

用一個diff陣列存每個P値之間的差値，代表兩個')'之間有diff個'('，其他詳見程式碼。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int t,n;
	int p[30];
	int diff[30];
	while (scanf("%d%d" ,&t,&n) != EOF){
	for (int i=0; i<n; i++) scanf("%d",&p[i]);
	diff[0] = p[0];
	for (int i=1; i<n; i++) diff[i] = p[i]-p[i-1];
	printf("1");
	for (int i=1; i<n; i++){
	for (int Count = 1, j = i; j >= 0; --j, ++Count)
	if (diff[j] > 0){
	diff[j]--;
	printf(" %d",Count);
	break;
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw [POJ] 1068-2 Parencodings.cpp hosted with ❤ by GitHub

POJ 3262 Protecting the Flowers

這題與UVa 10026 Shoemaker's Problem是一樣的

	#include<cstdio>
	#include<algorithm>
	using namespace std;
	struct cow{
	int T;
	int D;
	};
	bool cmp(cow a,cow b)
	{
	return (a.D*1.0/a.T)>(b.D*1.0/b.T); //*1.0
	}
	int main()
	{
	int N,i,j;
	long long sum=0,ans=0; //long long int
	cow a[100001];
	while(scanf("%d",&N)!=EOF){
	for (i=0;i<N;i++){
	scanf("%d%d",&a[i].T,&a[i].D);
	sum+=a[i].D;
	}
	sort(a,a+N,cmp);
	for(i=0;i<N;i++){
	sum-=a[i].D;
	ans+=(sum*2*a[i].T);
	}
	printf("%lld\n",ans);
	}
	return 0;
	}

view raw [POJ] 3262 Protecting the Flowers.cpp hosted with ❤ by GitHub

POJ 1007 DNA Sorting

想法：
　　 使用bubble sort時候每交換一次逆序數就+1，最後由逆序數小到大輸出。至於求逆序數更快的算法可參考UVa 10810 Ultra-Quicksort。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct sortedDNA
	{
	int num;
	char *line;
	}a[101];
	int bubble_sort(char a[],int n);
	bool cmp(sortedDNA a,sortedDNA b);
	int main()
	{
	int n,m,i,j;
	char DNA[101][52];
	scanf("%d %d\n",&n,&m);
	for(i=0;i<m;i++){
	gets(DNA[i]);
	a[i].line=DNA[i];
	a[i].num=bubble_sort(DNA[i],n);
	}
	sort(a,a+m,cmp);
	for(i=0;i<m;i++){
	for(j=0;j<n;j++){
	printf("%c",a[i].line[j]);
	}
	printf("\n");
	}
	return 0;
	}
	bool cmp(sortedDNA a,sortedDNA b)
	{
	return a.num<b.num;
	}
	int bubble_sort(char a[],int n)
	{
	int i,j,num=0;
	for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
	if(a[i]>a[j]) num++;
	return num;
	}

view raw [POJ] 1007 DNA Sorting.cpp hosted with ❤ by GitHub

POJ 1035 Spell Checker

想法：

• dic[i],check字數相等的情況
• dic[i],check字數相差1的情況

	#include <cstdio>
	using namespace std;
	struct dictionary
	{
	char l[20];
	int num;
	}dic[10002];
	int main()
	{
	char check[20];
	int i,j,k;
	for(i=0;;i++){
	scanf("%s",dic[i].l);
	if(dic[i].l[0]=='#') break;
	for(dic[i].num=0;dic[i].l[dic[i].num];dic[i].num++); //計算字元數
	}
	int numOfdic=i;
	while(1){
	scanf("%s",check);
	if(check[0]=='#') break;
	int nOfcheck=0;
	for(;check[nOfcheck];nOfcheck++);
	int diff=0,same=0; //same=1表示完全正確
	char *correct[10002]; int nOfcorrect=0;
	for(i=0,diff=0,same=0;i<numOfdic;i++,diff=0){
	if (nOfcheck-dic[i].num>1 || nOfcheck-dic[i].num<-1) continue;
	else if(nOfcheck==dic[i].num){ //字數相等的情況
	for(j=0;check[j];j++)
	if(check[j]!=dic[i].l[j])
	diff++;
	if (diff==0){
	same=1;
	printf("%s is correct\n",check);
	break;
	}
	else if(diff==1) correct[nOfcorrect++]=&dic[i].l[0];
	}
	else{ //字數相差1的情況
	int d_i=0,c_i=0; //dic_index,check_index
	while(dic[i].l[d_i] && check[c_i]){
	if(dic[i].l[d_i]==check[c_i]){d_i++; c_i++;}
	else{
	diff++;
	if(diff>1) break;
	if(nOfcheck>dic[i].num) c_i++;
	else d_i++;
	}
	}
	if(diff<=1) correct[nOfcorrect++]=&dic[i].l[0];
	}
	}
	if(!same){
	printf("%s:",check);
	for(j=0;j<nOfcorrect;j++)
	printf(" %s",correct[j]);
	printf("\n");
	}
	}
	return 0;
	}

view raw [POJ] 1035 Spell Checker.cpp hosted with ❤ by GitHub