Uva 10415: Eb Alto Saxophone Player

解題心得

暴力解

程式碼

#include <iostream>
using namespace std;

int main()
{
	string c="0111001111", d="0111001110", e="0111001100", f="0111001000", g="0111000000",
		a="0110000000", b="0100000000", C="0010000000", D="1111001110", E="1111001100",
		F="1111001000", G="1111000000", A="1110000000", B="1100000000";
	int t;
	cin>>t;
	while(t--)
	{
		string s, now="0000000000", next;
		int count[10]={0};
		cin>>s;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='c') next=c;
			else if(s[i]=='d') next=d;
			else if(s[i]=='e') next=e;
			else if(s[i]=='f') next=f;
			else if(s[i]=='g') next=g;
			else if(s[i]=='a') next=a;
			else if(s[i]=='b') next=b;
			else if(s[i]=='C') next=C;
			else if(s[i]=='D') next=D;
			else if(s[i]=='E') next=E;
			else if(s[i]=='F') next=F;
			else if(s[i]=='G') next=G;
			else if(s[i]=='A') next=A;
			else if(s[i]=='B') next=B;
			
			for(int i=0;i<10;i++)
			{
				if(now[i]=='0'&&next[i]=='1')
					count[i]++;
			}
			now=next;
			
		}
		
		for(int i=0;i<10;i++)
		{
			if(i!=9) cout<<count[i]<<" ";
			else cout<<count[i]<<endl;
		}
	}
	return 0;
}

Uva 10188: Automated Judge Script

解題心得

比對解答與提交答案的部分，主要是一個字元一個字元檢查。如果兩個字元都一樣，那就往下一個字元繼續看；如果其中一個是空白但另一個不是，則可能是PE，就先標記起來然後跳過空白；如果字元不一樣，而且也不是因為空白，那就是WA，可以直接跳出迴圈。

比較麻煩的是換行的部分，會造成PE誤判成AC，因為好像檢查不到「\n」。我想說這種狀況，會出現在原本被判AC，但因為換行，導致解答跟提交答案的行數不同，就從這裡判斷就好了。

程式碼

#include <iostream>
#include <string>
using namespace std;

int main()
{
	int n, m, count = 1;
	while (cin >> n)
	{
		if (n == 0) break;

		cin.ignore();
		string solution[100], team_output[100];
		int solution_len = 0;

		// read input
		for (int i = 0; i < n; i++)
		{
			getline(cin, solution[i]);
			solution_len += solution[i].size();
		}
		cin >> m;
		cin.ignore();
		for (int i = 0; i < m; i++)
			getline(cin, team_output[i]);

		// judge
		bool pe = false, wa = false;
		int i = 0, j = 0, len1 = 0, len2 = 0;
		while (i < n)
		{
			while (len1 < solution[i].size()) // && len2<team_output[i].size()
			{
				if (solution[i][len1] == team_output[j][len2])
					len1++, len2++;
				else if (solution[i][len1] == ' ' || solution[i][len1] == '\n')
				{
					len1++;
					pe = true;
				}
				else if (team_output[j][len2] == ' ' || team_output[j][len2] == '\n')
				{
					len2++;
					pe = true;
				}
				else
				{
					wa = true;
					break;
				}

				if (len2 >= team_output[j].size())
					j++, len2 = 0;
			}
			i++; len1 = 0;
		}
		cout << "Run #" << count++ << ": ";
		if (wa)
			cout << "Wrong Answer ";
		else if (pe || n!=m)
			cout << "Presentation Error ";
		else
			cout << "Accepted ";
		cout << solution_len << endl;

	}
	return 0;
}

Uva11689 Soda Surpler

解題心得

照著題目敘述寫就好了

程式碼

#include <iostream>
using namespace std;

int main()
{
	int N;
	cin>>N;
	while(N--)
	{
		int e, f, c, total=0,bottle=0;
		cin>>e>>f>>c;
		bottle = e+f;
		
		while(bottle>=c)
		{
			int tmp = bottle/c; // can buy now many soda

			bottle -= tmp*c; // use the empty bottle to buy soda
			bottle += tmp; // new empty bottle
			total += tmp; // update drink soda amount
		}
		cout<<total<<endl;
	}
	return 0;
}

b563: 3.魔法學校交換生問題

解題心得

檢查b校有沒有a校的申請，有的話案件成立數加一，沒有的話紀錄下來a校想去b校。

程式碼

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main()
{
	int n;
	while (cin >> n)
	{
		map<int, map<int,int>> record;
		int total = 0;
		while (n--)
		{
			int a, b;
			cin >> a >> b;
			
			if (record.count(b) && record[b].count(a) && record[b][a] > 0)
			{
				total++;
				record[b][a]--;
			}
			else
			{
				if (!record.count(a) || !record[a].count(b))
					record[a][b] = 1;
				else
					record[a][b]++;
			}
		}
		cout << total << endl;
		
	}
	return 0;
}

a121: 質數又來囉

解題心得

注意1的狀況。

程式碼

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int a, b;
	while (cin >> a >> b)
	{
		int count = 0;
		for (int i = a; i <= b; i++)
		{
			if (i == 1) continue;
			bool isPrime = true;
			for (int j = 2; j <= sqrt(i); j++)
			{
				if (i % j == 0)
				{
					isPrime = false;
					break;
				}
			}
			if (isPrime) count++;
		}
		cout << count << endl;
	}
	return 0;
}

UVA725

解題心得

一開始看到這題完全沒有頭緒，看了CPE提供的解說影片才有想法。

首先，用列舉的方式窮舉所有可能，如果該數字組合符合等式，再檢查數字是否重複。判斷等式成立與否也未必要用除的，用分母乘以N得到分子，這樣能縮小窮舉範圍。

思考到這裡，剩下的就是枚舉所有可能的分母，只要乘以N必定能讓等式成立，而分母的窮舉範圍其實可以進一步縮減到01234~98765。

太久沒解題，最後還卡在換行上XD

程式碼

#include <iostream>
using namespace std;

bool isValid(int a, int b)
{
	if(a>99999 || b>99999) return false;
	
	int count[10] = {0};
	if(a<10000) count[0]++;
	if(b<10000) count[0]++;
	while(a>0)
	{
		count[a%10]++;
		a/=10;
	}
	while(b>0)
	{
		count[b%10]++;
		b/=10;
	}
	for(int i=0;i<10;i++)
	{
		if(count[i]!=1)
			return false;
	}
	return true;
}

int main()
{
	int n;
	bool isFirst=true;
	
	while(cin>>n)
	{
		if(n==0) break;
		
		bool hasAns=false;
		
		if(isFirst) isFirst=false;
		else cout<<endl;
		
		for(int i=1234;i<=98765;i++)
		{
			int j = i * n;
			if(isValid(i, j))
			{
				hasAns=true;
				if(j<10000) cout<<"0"<<j<<" / ";
				else cout<<j<<" / ";
				if(i<10000) cout<<"0"<<i<<" = "<<n<<endl;
				else cout<<i<<" = "<<n<<endl;
			}
		}
		if(!hasAns) cout<<"There are no solutions for "<<n<<"."<<endl;
		
		
	}
	return 0;
}

UVA12218

解題心得

照著題目敘述做。

如果輪到誰，誰卻跳出迴圈，就代表輸了。

程式碼

#include <iostream>
using namespace std;

int sum_of_digits(string s)
{
	int sum=0;
	for(int i=0;i<s.length();i++)
		sum+=s[i]-'0';
	return sum;
}
int can_remove(string s)
{
	if(s.length()==0) return -1;
	
	int sum=sum_of_digits(s);
	for(int i=0;i<s.length();i++)
	{
		if((sum-(s[i]-'0'))%3==0)
			return i;
	}
	return -1;
}

int main()
{
	int T;
	cin>>T;
	
	for(int round=1;round<=T;round++)
	{
		bool isT=false; // s first
		string s;
		cin>>s;
		
		while(1){
			int index=can_remove(s);
			if(index==-1) break;
			s=s.erase(index,1);
			isT=!isT;
		}
		
		cout<<"Case "<<round<<": ";
		cout<< (isT ? "S" : "T") << endl;
	}
	return 0;
}

UVA10921

解題心得

照著題目敘述寫就好了。

程式碼

#include <iostream>
using namespace std;

int find_table(char c)
{
	if(c=='A' || c=='B' || c=='C') return 2;
	else if(c=='D' || c=='E' || c=='F') return 3;
	else if(c=='G' || c=='H' || c=='I') return 4;
	else if(c=='J' || c=='K' || c=='L') return 5;
	else if(c=='M' || c=='N' || c=='O') return 6;
	else if(c=='P' || c=='Q' || c=='R' || c=='S') return 7;
	else if(c=='T' || c=='U' || c=='V') return 8;
	else if(c=='W' || c=='X' || c=='Y' || c=='Z') return 9;
}
int main()
{
	string s;
	while(cin>>s)
	{
		int capital=0, hyphen=0;
		for(int i=0;i<s.length();i++)
		{
			if(s[i]=='-' || s[i]=='1' || s[i]=='0')
				cout<<s[i];
			else
				cout<<find_table(s[i]);
				
			if(s[i]=='-') hyphen++;
			if(isupper(s[i])) capital++; 
		}
		cout<<" "<<capital<<" "<<hyphen<<endl;
	}
	return 0;
}

UVA12019

解題心得

好久沒碰日期相關的題目了，真的好討厭這類型......

程式碼

#include <iostream>
using namespace std;

int main()
{
	int calander[366]={0}, today=6, months[13]={0,31,59,90,120,151,181,212,243,273,304,334,365};
	for(int i=1;i<=365;i++)
	{
		calander[i]=today;
		today++;
		if(today==8) today=1;
	}
	
	int T, M, D;
	cin>>T;
	
	while(T--)
	{
		cin>>M>>D;
		int day=calander[months[M-1]+D];
		if(day==1) cout<<"Monday"<<endl;
		else if(day==2) cout<<"Tuesday"<<endl;
		else if(day==3) cout<<"Wednesday"<<endl;
		else if(day==4) cout<<"Thursday"<<endl;
		else if(day==5) cout<<"Friday"<<endl;
		else if(day==6) cout<<"Saturday"<<endl;
		else cout<<"Sunday"<<endl;
	}
	return 0;
}

UVa380

程式碼

因為自己電腦用瘋狂程式寫code好像無法使用c++11的編譯器(?)，所以才自己寫了stoi。

我用 struct 來紀錄怎麼forward，用vector紀錄全部的forward資訊，以及forward的過程中經過哪些電話號碼，如果會forward到已經記錄過的就回傳9999。

至於判斷時間起迄的部分，除了一般的狀況外，還要考慮時間可能跨到明年，也就是結束時間比開始時間小的情況。

還有一個部份是要確認長長的forward鍊已經到了最後，要怎麼確認呢？我的想法是只要該輪有被更動過，下次就要再檢查一次，直到某輪把所有forward資訊看過一次都不用，那就結束。

解題心得

#include <iostream>
#include <vector>
using namespace std;

struct forward_call
{
	string source, target;
	int start, end;
};

int stoi(string s)
{
	int n=0;
	for(int i=0;i<s.length();i++)
	{
		n=n*10+s[i]-'0';
	}
	return n;
}
bool in_history(vector<string> history, string s)
{
	for(int i=0;i<history.size();i++)
	{
		if(history[i]==s)
			return true;
	}
	return false;
}

bool in_time(int start, int end, string time)
{
	if(start<=end)
		if(start<=stoi(time) && stoi(time)<=end) return true;
	else
		if(!(end<=stoi(time) && stoi(time)<=start)) return true;
	return false;
}
int main()
{
	int T;
	cin>>T;
	
	cout<<"CALL FORWARDING OUTPUT"<<endl;
	for(int round=1; round<=T; round++)
	{
		string s, t, d, target;
		string time, extension;
		vector<forward_call> sys;
		
		cout<<"SYSTEM "<<round<<endl;
		while(cin>>s)
		{
			if(s=="0000")
				break;
			cin>>t>>d>>target;
			forward_call call;
			call.source=s;call.target=target;call.start=stoi(t);call.end=stoi(t)+stoi(d);
			sys.push_back(call);
		}
		while(cin>>time)
		{
			if(time=="9000")
				break;
			cin>>extension;
			string initial_extension=extension;
			vector<string> history;
			history.push_back(initial_extension);
			
			bool isFin=true;
			
			do{
				isFin=true;
				for(int i=0;i<sys.size();i++)
				{
					if(sys[i].source==extension && 
					sys[i].start <= stoi(time) && stoi(time) <= sys[i].end)
					{
						isFin=false;
						if(in_history(history, sys[i].target))
						{
							extension = "9999";
							break;
						}
						extension=sys[i].target;
						history.push_back(sys[i].target);
					}
				}
			}while(!isFin);
			
			cout<<"AT " << time << " CALL TO " << initial_extension << " RINGS " << extension << endl;
		}
	}
	cout<<"END OF OUTPUT"<<endl;
	return 0;
}

UVa12869

解題心得

第一次解這種類型的題目。

題目問在給定範圍的階乘內數字結尾有幾個連續的零。我們都知道零代表著10，也就是2*5，如此可推論每當有一組2跟5時就會多一個零。只要能知道有多少個2、5就能知道答案，又因為5是每五個數字出現一次，2只要每2個數字就會出現一次，可知5才是主宰零出現次數的關鍵。

因此這題只要算5出現了幾次，也就是除以5就好了。

程式碼

#include <iostream>
using namespace std;

int main()
{
	long long int low, high;
	while(cin>>low>>high)
	{
		if(low==0&&high==0) break;
		
		cout<<high/5 - low/5 + 1<<endl;
	}
	return 0;
}

UVa12970

解題心得

表面上看起來很容易，但牽扯到數字約分就比較複雜。

要記得gcd怎麼寫。

程式碼

#include <iostream>
using namespace std;

long long int gcd(long long int a, long long int b)
{
	while((a%=b)!=0 && (b%=a)!=0);
	return a+b;
}
int main()
{
	int count=1;
	long long int v1, d1, v2, d2;
	while(cin>>v1>>d1>>v2>>d2)
	{
		if(v1==0 && d1==0 && v2==0 && d2==0) break;
		
		cout<<"Case #"<<count++<<": ";
		if(float(d1)/v1 < float(d2)/v2)
			cout<<"You owe me a beer!"<<endl;
		else
			cout<<"No beer for the captain."<<endl;
			
		cout<<"Avg. arrival time: ";
		long long int up, down,_gcd;
		up=d1*v2 + d2*v1;
		down=2*v1*v2;
		_gcd=gcd(up,down);
		
		up/=_gcd, down/=_gcd;
		if(down==1)
			cout<<up<<endl;
		else
			cout<<up<<"/"<<down<<endl;
	}
	return 0;
}

git 指令筆記

push a folder

git remote add origin https://gitlab.com/xxxxx/test.git

git add .

git commit -m “Initial commit”

git push -u origin master  # git push <remote-repo> <branch-name>

view repo's history

git log

git log --oneline

git log --stat # display the files that have been changed in the commit, as well as the number of lines that have been added or deleted

git log -p # display the actual changes made to a file

git log -p <SHA>

git show

git show <SHA>

git diff # see changes that have been made but haven't been committed

git log --oneline --graph --decorate --all

git log --author="Richard Kalehoff"

git log --grep="border radius issue in Safari"

branch

git branch # list all branch

git branch sidebar # create new branch called sidebar

git checkout sidebar # switch to branch sidebar

git branch -d sidebar # delete

git checkout -b footer master # create new branch and switch to it

git checkout -b footer <SHA>

merge

git merge <branch-name> # merge <branch-name> into current branch

# to fix conflict:

# open editor and fixed it

# commit again

amend commit

git commit --amend

# if  Working Directory is clean

# change the commit message

# else

# update all change within the staging area

git revert <SHA-of-commit-to-revert>

Udacity Git Commit Message Style Guide

UVa10222

解題心得

太久沒寫C++，差點忘了字串處理的部分。

程式碼

#include <iostream>
using namespace std;

int main()
{
	string table = "qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
	int T;
	cin>>T;
	cin.ignore();
	
	while(T--)
	{
		string s;
		getline(cin,s);
		
		for(int i=0;i<s.length();i++)
		{
			if(isupper(s[i])) s[i] = (s[i]-'A')+'a';
			if(s[i]==' ')
			{
				cout<<" ";
				continue;
			}
			
			for(int j=0;j<table.length();j++)
			{
				if(table[j]==s[i])
				{
					cout<<table[((j-2)+table.length())%table.length()];
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

UVa12959

解題心得

沒有心得

程式碼

#include <iostream>
using namespace std;

int main()
{
	int T;
	cin>>T;
	
	while(T--)
	{
		int n, max=0, ans=-999999,temp;
		cin>>n;

		for(int i=0;i<n;i++)
		{
			cin>>temp;
			
			if(i==0)
			{
				max = temp;
				continue;
			}
			
			if(max-temp>ans)
				ans = max-temp;
			if(temp>max)
				max=temp;
		}
		cout<<ans<<endl;
	}
	return 0;
}

UVa11078

解題心得

不能用暴力解，會TLE。

可以一邊讀新的數字進來，一邊紀錄是不是目前遇到的最大值，並且把之前紀錄的最大值跟當下吃到的數字比較，如果比較大就記起來。

程式碼

#include <iostream>
using namespace std;

int main()
{
	int T;
	cin>>T;
	
	while(T--)
	{
		int n, max=0, ans=-999999,temp;
		cin>>n;

		for(int i=0;i<n;i++)
		{
			cin>>temp;
			
			if(i==0)
			{
				max = temp;
				continue;
			}
			
			if(max-temp>ans)
				ans = max-temp;
			if(temp>max)
				max=temp;
		}
		cout<<ans<<endl;
	}
	return 0;
}

UVa118

解題心得

嗚嗚

程式碼

#include <iostream>
using namespace std;

int main()
{
	int Xmax, Ymax, x, y, grid[51][51] = { 0 };
	char orient;
	string s;

	cin >> Xmax >> Ymax;
	while (cin >> x >> y >> orient)
	{
		bool isLost = false;

		cin >> s;
		for (int i = 0; i < s.length(); i++)
		{
			if (s[i] == 'L')
			{
				if (orient == 'N') orient = 'W';
				else if (orient == 'E') orient = 'N';
				else if (orient == 'S') orient = 'E';
				else if (orient == 'W') orient = 'S';
			}
			else if (s[i] == 'R')
			{
				if (orient == 'N') orient = 'E';
				else if (orient == 'E') orient = 'S';
				else if (orient == 'S') orient = 'W';
				else if (orient == 'W') orient = 'N';
			}
			else
			{
				int next_x = x, next_y = y;
				if (orient == 'N') next_y++;
				else if (orient == 'E') next_x++;
				else if (orient == 'S') next_y--;
				else if (orient == 'W') next_x--;

				if (next_x<0 || next_y<0 || next_x>Xmax || next_y>Ymax)
				{
					if (grid[x][y] == 1)
						continue;

					isLost = true;
					grid[x][y] = 1;
					break;
				}
				x = next_x, y = next_y;
			}
			
		}
		cout << x << " " << y << " " << orient;
		if (isLost)
			cout << " LOST";
		cout << endl;
	}
	return 0;
}

UVa11728

解題心得

暴力解

程式碼

#include <iostream>
using namespace std;

int factor_sum(int n)
{
	int sum = 0;
	
	for (int i = 1; i <= n; i++)
	{
		if (n % i == 0)
			sum += i;
	}
	return sum;
}

int main()
{
	int S, count = 1;
	while (cin >> S)
	{
		if (S == 0) break;
		cout << "Case " << count++ << ": ";

		int ans = -1;
		for (int i = 1; i < S; i++)
		{
			if (factor_sum(i) == S)
			{
				ans = i;
			}
		}
		if (S == 1)
			ans = 1;
		cout << ans << endl;
	}
	return 0;
}

UVa1260

解題心得

沒有心得

程式碼

#include <iostream>
using namespace std;

int main()
{
	int T, n;
	cin>>T;
	while(T--)
	{
		cin>>n;
		int sales[1001]={0};
		for(int i=0;i<n;i++)
		{
			cin>>sales[i];
		}
		int ans=0;
		for(int i=1;i<n;i++)
		{
			for(int j=0;j<i;j++)
			{
				if(sales[j]<=sales[i])
					ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

UVa12650

解題心得

沒有心得

程式碼

#include <iostream>
using namespace std;

int main()
{
	int N,R;
	while(cin>>N>>R)
	{
		int card[N+1]={0}, flag=0;
		for(int i=0;i<R;i++)
		{
			cin>>flag;
			card[flag]=1;
		}
		if(N==R)
			cout<<"*"<<endl;
		else
		{
			for(int i=1;i<=N;i++)
			{
				if(card[i]==0)
					cout<<i<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}