[生活趣事/生活週記]3/20~3/26-吉他社學術例會－Echo回聲樂團

禮拜三去聽Echo回聲樂團拍的照片，
還蠻特別的一次體驗XD

[3/20](日)
早上去參加主日聚會，
中午在體育館附近念聖經，
一直到下午就去家教XD
然後就回家了～
似乎很平靜的過完一天！？

[3/21](一)
早上是離散數學、英文，
中午的貓咪果醬聚會改成探討未來發展的聚會XD
下午是程式設計，
上完後，就先弄獎學金的事情，
之後找教官談某個Project的事情，
接著我就和晉嘉兄跑去本部綜合大樓上Vocal班，
上完後就陪晉嘉兄去買肉串吃XD
然後就回家了～

[3/22](二)
上午是數位邏輯，
中午換新路哥哥載我到邵弟兄家，
新路哥哥騎車比聖別快很多>_<
剛開始不太習慣就是了～
這週讀了馬太五章，
提到很多種人都有福了，
我們應當操練成為這樣的人。
下午回家，
我媽在家裡，
我很累了就去睡，
結果睡過頭就沒去桌球= ="

[3/23](三)
早上晨興，
講到我們都可以從生命之泉源歡然取水，
很棒的體驗！
接著是自然探索課，
我還是搞不懂心得要交啥QQ
中午去聽了日文學程的說明會，
了解了一些規條，
接著就趕快趕去分部PC室，
然後就跟大家一起到B102上程式設計課。
晚上跟映竹搭車到本部，
去英文自學教室，
他後來先走，
我大概也只又待一下子就離開了，
然後到圖書館找書，
沒找到想要的，
接著就趕去綜合大樓，
去聽這次的例會，
也就是Echo回聲樂團來我們學校的Live Online，
很特別的一次體驗呢！XD

[3/24](四)
今天早上是邏輯概論，
將作業交出去了～XD
中午是照常貓咪果醬例會，
但是我們教學股也開會，
所以就先去教學股了解資工營的部份的狀況，
然後再去開例會，
開一下又趕去排演明天國文的戲。
下午是微積分，
聽了三個鐘頭結束後，
本來想去畫畫，
又想說作業好多，
而且我畫畫好爛= =
所以就回家去了。

結論是我趕作業趕到26:00= =...

[3/25](五)
早上是國文，
換我們這組演戲，
老師說我們演得很棒，
但是因為上次晉嘉兄那組晉嘉兄撞到頭，
所以還是只能獲得第二名，
第一名就被奪去了XD
不過也因此晉嘉兄沒去上課的事情就被發現了XDDDDDDD
接著是離散數學，
中場下課系主任來發問卷，
是要藉問卷來實施一個實驗，
就是可以讓部分同學不用來上離散數學，
自己找個時間去某間固定的教室看錄影帶來上課，
讓你可以挑有精神的時間去聽課，
感覺很棒的措施！
Ψω還說這是專門為他設計的XD

中午先交了一些獎學金要交的資料，
下午是數位邏輯還有實驗課，
我們還算早的就做完了，
然後我去繳交獎學金剩下來未繳交的資料，
也就是教授的意見，
因此我就上五樓去找蔣教授簽名，
然後就聊到TOI的事情，
聽到教授有去上課，
我才發覺TOI開始了XD
不知道元元、唯辰兄和盛文兄會不會保送呀XD~~

[3/26](六)
今天早上是生服社社課，
是上關於親的部份，
上完後，
聖別學長跟我談了申言是什麼，
我才比較明白申言XD

下午到晚上就在家裡玩瑪奇，
公會還遇到不太好的事件= =
就不多說了～

[生活趣事/生活週記]3/13~3/19 大三家聚

我通識課用的課本－多多鳥之歌，
講述關於島嶼分割所導致的物種獨特性與滅絕的書，
試著把它看完中XD

[3/13](日)
早上先帶河水和他的大學同學到師大的綜合大樓去上課，
接著趕去三會所參加全部不分區的主日聚會，
也是我第一次參加這種聚會XD
超多人！XD

中午和河水以及他的大學同學吃飯，
吃完我念了一下馬太福音，
接著下午就去家教，
不過家教的學生身體不適，
就沒有講太多。

晚上回家趕離散數學的作業...Orz
考慮是否要用紙寫，
去光華商場買了一疊A4紙，
有這疊真的讓我覺得超好用的XD

[3/14](一)
早上超早到，
這是為了要交離散數學的作業XD"
接著英文課，
教授說我們回去一定沒有做作業，
結果留了一點時間給我們做，
真是太棒了！XD
只是某晉嘉兄加上學期翹英文課共5次，
結果教授都沒點到他，
讓某庭書兄很氣憤XD

中午貓咪果醬聚會，
我們的團長晉嘉兄沒來，
我就教映竹和克里一些Ruby語言這樣。

下午程式設計，
還是睡著了(掩面)...

之後先回家，
然後到了快7點再趕到綜合大樓去上吉他社Vocal班的社課，
這個課超棒，
我超喜歡的XD

[3/15](二)
今天上午是數位邏輯的課，
接著聖別學長接我到邵弟兄家，
不過兩位家主人都不在，
我們就在邵弟兄家裡吃PIZZA，
讀了馬太四章，
告訴我們要多讀聖經，
這樣我們才能活用在生活上！

下午先去英語自學教室，
然後回家，
拿到了「多多鳥之歌」這本書！！
晚上接著又趕去男三舍的地下室桌球場打桌球，
我的基本動作又...Orz
球拍真的好想買新的呀！！！！！（吶喊

[3/16](三)
早上到弟兄之家晨興，
內容是要我們多接觸主！！

接著去上自然探索，
終於開始口頭心得報告了，
我的書才剛拿到還沒看呀～
不過還要很久才會輪到我。

中午趕去PC室，
晉嘉兄拿了一疊RGSS的程式碼給我，
我囧！
超大本的！
超難攜帶！

下午程式設計，
實在不知道該說什麼，
就只能說又睡著了Orz......

晚上去吃大三家聚，
去捷運大坪林那邊吃到飽的燒烤店，
還蠻好吃的！
某毓偉兄果然還是冰淇淋從頭吃到尾，
某庭書兄果然還是受不了誘惑XD(?

[3/17](四)
早上邏輯概論，
喉嚨開始不舒服...

中午貓咪果醬會議完後，
越來越不舒服= =

下午微積分，
不舒服到最高點...Orz

晚上到本部，和浩庭、安偉、映竹吃師大美食館，
還遇到吉他社的人XD
有阿緯(學長XD!!)、阿徹以及社長，
另外第四位似乎浩庭知道是誰！？
後來因為實在不舒服，就沒去動漫社社課了XD

[3/18](五)
一整天還是不舒服，
幸好國文不是我們這組要演戲，
不然我就......(汗
離散數學我實在又撐不住，
可是又要寫練習題，
真的很痛苦Orz...

下午數位邏輯，
還有實驗！XD
又碰到熟悉的東西了～
我們這組做的還算快，
做完後就離開了，
唯一沒事放學可以直接回家的，
就只有禮拜五晚上了XD！

[3/19](六)
早上還是不太舒服，
不過我還是去了生服社的社課，
還讓我吃了兩頓早餐XD
(出門前一頓，到教會一頓XD)
希望兒童品格營的籌備能夠非常順利呀>_<

下午晚上沒什麼事情，
瑪奇度過...耶！？

[UVa]105:The Skyline Problem

新站連結於http://knightzone.org/?p=1565

[UVa]10010:Where's Waldorf?

這題要注意的有幾個點：
1.尋找字串的時候雖然有八方位，
但是凡決定要走哪個方位後，
就只能朝著同一個方位走，
不能彎來彎去。
2.字母相等不分大小寫。
3.要以左上方為優先，
就要以斜線的方法來定X和Y，
相信被8皇后題目訓練過，
就會知道要用X+Y來搜尋XD

[C](0.008)

	#include<stdio.h>
	#include<string.h>
	#include<ctype.h>
	int m, n;
	char letter[55][55];
	int search( int path, char find[], int now, int find_length, int X, int Y )
	{
	if( find_length == now ) return 1;
	if( X < 0 || X > m || Y < 0 || Y > n ) return 0;
	if( tolower(find[now]) != tolower(letter[X][Y]) ) return 0;
	int ok = 0;
	if( !path )
	{
	ok = search( 1, find, now+1, find_length, X+1, Y );
	ok = (ok) ? 1 : search( 2, find, now+1, find_length, X, Y+1 );
	ok = (ok) ? 1 : search( 3, find, now+1, find_length, X-1, Y );
	ok = (ok) ? 1 : search( 4, find, now+1, find_length, X, Y-1 );
	ok = (ok) ? 1 : search( 5, find, now+1, find_length, X-1, Y-1 );
	ok = (ok) ? 1 : search( 6, find, now+1, find_length, X+1, Y+1 );
	ok = (ok) ? 1 : search( 7, find, now+1, find_length, X+1, Y-1 );
	ok = (ok) ? 1 : search( 8, find, now+1, find_length, X-1, Y+1 );
	}
	else
	{
	switch( path )
	{
	case 1:
	return search( 1, find, now+1, find_length, X+1, Y );
	break;
	case 2:
	return search( 2, find, now+1, find_length, X, Y+1 );
	break;
	case 3:
	return search( 3, find, now+1, find_length, X-1, Y );
	break;
	case 4:
	return search( 4, find, now+1, find_length, X, Y-1 );
	break;
	case 5:
	return search( 5, find, now+1, find_length, X-1, Y-1 );
	break;
	case 6:
	return search( 6, find, now+1, find_length, X+1, Y+1 );
	break;
	case 7:
	return search( 7, find, now+1, find_length, X+1, Y-1 );
	break;
	case 8:
	return search( 8, find, now+1, find_length, X-1, Y+1 );
	break;
	}
	}
	if( ok )
	printf( "%d %d\n", X, Y );
	return ok;
	}
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int i, j, k;
	for( i = 0 ; i < N ; i++ )
	{
	if( i )
	printf( "\n" );
	scanf( "%d%d", &m, &n );
	getchar();
	for( j = 1 ; j <= m ; j++ )
	{
	for( k = 1 ; k <= n ; k++ )
	letter[j][k] = getchar();
	getchar();
	}
	scanf( "%d", &k );
	getchar();
	char find[55];
	for( j = 1 ; j <= k ; j++ )
	{
	gets(find);
	int slash, X;
	int ok = 0;
	int find_length = strlen(find);
	for( slash = 2 ; slash <= m+n && !ok ; slash++ )
	for( X = 1 ; slash - X > 0 && !ok ; X++ )
	ok = search( 0, find, 0, find_length, X, slash-X );
	}
	}
	}
	return 0;
	}

view raw UVa10010.c hosted with ❤ by GitHub

[UVa]679:Dropping Balls

這題我是用二進位的方式去表示，
假設今天有4層：
第一顆球會落在2進位的1000，也就是10進位的8的位置。
第二顆球會落在2進位的1100，也就是10進位的12的位置。
第三顆球會落在2進位的1010，也就是10進位的10的位置。
第四顆球會落在2進位的1110，也就是10進位的14的位置。
...以此類推。
各位會發現到答案其實就是2的(層數-1)次方加上2進位倒過來的(次數-1)，
例如4層的第一顆球就是2^(4-1)+倒置(1-1)=8+0=8。
4層的第二顆球就是2^(4-1)+倒置(2-1)=8+倒置(001(2進位))=8+(100(2進位))=8+4=12，
這樣即可得解。

[C](0.052)

	#include<stdio.h>
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int i;
	for( i = 0 ; i < N ; i++ )
	{
	int D, I;
	scanf( "%d%d", &D, &I );
	I--;
	int j, k;
	int tree = 1 << (D-1);
	int route = 0;
	for( j = D-2 ; j >= 0 ; j-- )
	{
	route ^= (I % 2) << j;
	I /= 2;
	}
	tree ^= route;
	printf( "%d\n", tree );
	}
	}
	return 0;
	}

view raw UVa679.c hosted with ❤ by GitHub

[UVa]11342:Three-square

這題請建表。
建表有兩個方式：
一個是像質數篩法那樣，
將a*a+b*b+c*c的那格填入答案。
另外一個是比較慢，也是下面的程式碼的作法，
直觀地真的去找每個數的答案，
但是要注意a,b,c的範圍避免TLE。

[C](0.568)

	#include<stdio.h>
	#include<math.h>
	#define ERROR 0.0000001
	int main()
	{
	int answer[50005][3] = {0};
	int n;
	for( n = 1 ; n <= 50000 ; n++ )
	{
	unsigned int a, b, c;
	int ok = 0;
	for( a = 0 ; a*a <= n/3 ; a++ )
	{
	for( b = a ; b*b <= (n - b*b - a*a) ; b++ )
	{
	double temp = sqrt((double)(n-b*b-a*a));
	c = temp + ERROR;
	if( (double)c == temp )
	{
	ok = 1;
	break;
	}
	if( ok )
	break;
	}
	if( ok )
	break;
	}
	if( ok )
	{
	answer[n][0] = a;
	answer[n][1] = b;
	answer[n][2] = c;
	}
	else
	answer[n][0] = -1;
	}
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int i;
	unsigned int K;
	for( i = 0 ; i < N ; i++ )
	{
	scanf( "%u", &K );
	if( answer[K][0] == -1 )
	printf( "-1\n" );
	else
	printf( "%d %d %d\n", answer[K][0], answer[K][1], answer[K][2] );
	}
	}
	return 0;
	}

view raw UVa11342.c hosted with ❤ by GitHub

[UVa]10394:Twin Primes

建質數表得解。

[C](1.492)

	#include<stdio.h>
	int prime[20000001] = { 1, 1, 0 };
	int answer[100005] = {0};
	int allanswer = 1;
	int main()
	{
	long long i, j;
	for( i = 3 ; i < 20000000L && allanswer <= 100000 ; i+=2 )
	if( !prime[i] )
	{
	for( j = i*i ; j < 20000000L ; j += i )
	prime[j] = 1;
	if( !prime[i] && !prime[i-2] )
	answer[allanswer++] = i-2;
	}
	int S;
	while( scanf( "%d", &S ) != EOF )
	printf( "(%d, %d)\n", answer[S], answer[S]+2 );
	return 0;
	}

view raw UVa10394.c hosted with ❤ by GitHub

[UVa]116:Unidirectional TSP

新站連結於http://knightzone.org/?p=2204

[UVa]10192:Vacation

LCS(Longest common subsequence)的問題。

[C](0.012)

	#include<stdio.h>
	#include<string.h>
	int main()
	{
	char s1[105], s2[105];
	int dataset = 1;
	while( gets(s1) && !( s1[0] == '#' && s1[1] == '\0' ) )
	{
	gets(s2);
	int LCS[105][105] = {0};
	int citynum1 = strlen(s1);
	int citynum2 = strlen(s2);
	int i, j;
	for( i = 1 ; i <= citynum1 ; i++ )
	for( j = 1 ; j <= citynum2 ; j++ )
	if( s1[i-1] == s2[j-1] )
	LCS[i][j] = LCS[i-1][j-1]+1;
	else
	LCS[i][j] = ( LCS[i-1][j] > LCS[i][j-1] )? LCS[i-1][j] : LCS[i][j-1];
	printf( "Case #%d: you can visit at most %d cities.\n", dataset++, LCS[citynum1][citynum2] );
	}
	return 0;
	}

view raw UVa10192.c hosted with ❤ by GitHub

[UVa]264:Count on Cantor

找出第幾斜排以及第幾斜排的最末項還有第n項的分母與分子這四者的關係，
即可得解。

[C](0.012)

	#include<stdio.h>
	int main()
	{
	int n;
	while( scanf( "%d", &n ) != EOF )
	{
	int slash = 1;
	int term = 1;
	while( term < n )
	term += (++slash);
	int up, down;
	if( slash % 2 )
	{
	up = ( term - n ) + 1;
	down = slash - ( term - n );
	}
	else
	{
	up = slash - ( term - n );
	down = ( term - n ) + 1;
	}
	printf( "TERM %d IS %d/%d\n", n, up, down );
	}
	return 0;
	}

view raw UVa264.c hosted with ❤ by GitHub

[UVa]10405:Longest Common Subsequence

LCS(Longest common subsequence)的問題。

[C](0.048)

	#include<stdio.h>
	#include<string.h>
	int LCS[1005][1005] = {0};
	int main()
	{
	char s1[1005], s2[1005];
	while( gets(s1) )
	{
	gets(s2);
	memset( LCS, 0, sizeof(LCS) );
	int s1_length = strlen(s1);
	int s2_length = strlen(s2);
	int i, j;
	for( i = 1 ; i <= s1_length ; i++ )
	for( j = 1 ; j <= s2_length ; j++ )
	if( s1[i-1] == s2[j-1] )
	LCS[i][j] = LCS[i-1][j-1]+1;
	else
	LCS[i][j] = ( LCS[i-1][j] > LCS[i][j-1] )? LCS[i-1][j] : LCS[i][j-1];
	printf( "%d\n", LCS[s1_length][s2_length] );
	}
	return 0;
	}

view raw UVa10405.c hosted with ❤ by GitHub

[UVa]10066:The Twin Towers

LCS(Longest common subsequence)的問題。

[C](0.008)

	#include<stdio.h>
	int main()
	{
	int N1, N2;
	int dataset = 1;
	while( scanf( "%d%d", &N1, &N2 ) != EOF && N1 != 0 && N2 != 0 )
	{
	int stone1[105] = {0}, stone2[105] = {0};
	int i, j;
	for( i = 1 ; i <= N1 ; i++ )
	scanf( "%d", &stone1[i] );
	for( i = 1 ; i <= N2 ; i++ )
	scanf( "%d", &stone2[i] );
	int LCS[105][105] = {0};
	for( i = 1 ; i <= N1 ; i++ )
	for( j = 1 ; j <= N2 ; j++ )
	if( stone1[i] == stone2[j] )
	LCS[i][j] = LCS[i-1][j-1]+1;
	else
	LCS[i][j] = ( LCS[i-1][j] > LCS[i][j-1] )? LCS[i-1][j] : LCS[i][j-1];
	printf( "Twin Towers #%d\n", dataset++ );
	printf( "Number of Tiles : %d\n\n", LCS[N1][N2] );
	}
	return 0;
	}

view raw UVa10066.c hosted with ❤ by GitHub

[UVa]10684:The jackpot

DP題，
利用另外一個陣列記錄到從前面連續到目前這格贏最多的錢是多少，
再找這裡面全部最多錢的即是答案。

[C](0.088)

	#include<stdio.h>
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF && N != 0 )
	{
	int money[10005] = {0};
	int dp[10005] = {0}, max = 0;
	int i;
	for( i = 1 ; i <= N ; i++ )
	{
	scanf( "%d", &money[i] );
	if( dp[i-1]+money[i] > money[i] )
	dp[i] = dp[i-1]+money[i];
	else
	dp[i] = money[i];
	max = ( dp[i] > max )? dp[i] : max;
	}
	if( max )
	printf( "The maximum winning streak is %d.\n", max );
	else
	printf( "Losing streak.\n" );
	}
	return 0;
	}

view raw UVa10684.c hosted with ❤ by GitHub

[UVa]10258:Contest Scoreboard

照著題目說的做即可得解。
要注意，當某題目被AC後，
後面如果同組有再送同樣那題，
就不用再去增加那題的懲罰時間。
(不過個人不確定會不會有這種可能性就是了。)

[C++](0.016)

	#include<iostream>
	#include<sstream>
	using namespace std;
	struct Contest{
	int id;
	int problem[10][2];
	int AC;
	int time;
	bool have;
	};
	bool cmp( Contest a, Contest b )
	{
	if( a.AC > b.AC )
	return 1;
	else if( a.AC == b.AC && a.time < b.time )
	return 1;
	else if( a.AC == b.AC && a.time == b.time && a.id < b.id )
	return 1;
	return 0;
	}
	int main()
	{
	int N;
	while( cin >> N )
	{
	string s;
	stringstream ss;
	cin.get();
	getline( cin, s );
	for( int i = 0 ; i < N ; i++ )
	{
	if( i )
	cout << endl;
	int contestant, problem, time;
	char L;
	Contest team[105];
	for( int j = 0 ; j < 105 ; j++ )
	{
	team[j].id = j;
	memset( team[j].problem, 0, sizeof(team[j].problem) );
	team[j].AC = 0;
	team[j].time = 0;
	team[j].have = 0;
	}
	while( getline( cin, s ) && s != "" )
	{
	ss.clear();
	ss.str(s);
	ss >> contestant >> problem >> time >> L;
	team[contestant].have = 1;
	if( L == 'C' && team[contestant].problem[problem][0] != -1 )
	{
	team[contestant].problem[problem][1] = time + team[contestant].problem[problem][0] * 20;
	team[contestant].problem[problem][0] = -1;
	}
	else if( L == 'I' && team[contestant].problem[problem][0] != -1 )
	team[contestant].problem[problem][0]++;
	}
	for( int j = 0 ; j < 105 ; j++ )
	if( team[j].have )
	for( int k = 0 ; k < 10 ; k++ )
	if( team[j].problem[k][0] == -1 )
	{
	team[j].AC++;
	team[j].time += team[j].problem[k][1];
	}
	sort( team, team+105, cmp );
	for( int j = 0 ; j < 105 ; j++ )
	if( team[j].have )
	cout << team[j].id << ' ' << team[j].AC << ' ' << team[j].time << endl;
	}
	}
	return 0;
	}

view raw UVa10258.cpp hosted with ❤ by GitHub

[UVa]11689:Soda Surpler

這題要注意的是：換完後的汽水罐，等喝完後還可以再換，所以不是只能換一次這樣。

[C](0.012)

	#include<stdio.h>
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int e, f, c;
	int i;
	for( i = 0 ; i < N ; i++ )
	{
	int soda = 0;
	scanf( "%d%d%d", &e, &f, &c );
	int temp = (e+f)/c, other = (e+f)%c, tmp;
	while( temp )
	{
	soda += temp;
	tmp = (temp+other)%c;
	temp = (temp+other)/c;
	other = tmp;
	}
	printf( "%d\n", soda );
	}
	}
	return 0;
	}

view raw UVa11689.c hosted with ❤ by GitHub

[UVa]11661:Burger Time?

從頭開始搜尋，
一直不斷比較最後找到的D和R的間距是否為最小的即是解答。
(當然如果裡面有Z，那答案一定是0)

[C](0.356)

	#include<stdio.h>
	#include<math.h>
	int main()
	{
	int L;
	while( scanf( "%d", &L ) != EOF && L != 0 )
	{
	getchar();
	char road[2000005] = {0};
	gets( road );
	int i, j;
	int min = 2147483647;
	int Z = 0;
	int D = -1, R = -1;
	for( i = 0 ; i < L && !Z ; i++ )
	{
	if( road[i] == 'D' )
	D = i;
	if( road[i] == 'R' )
	R = i;
	if( road[i] == 'Z' )
	Z = 1;
	if( D >= 0 && R >= 0 )
	min = ( abs(D-R) < min )? abs(D-R) : min;
	}
	if( Z )
	printf( "0\n" );
	else
	printf( "%d\n", min );
	}
	return 0;
	}

view raw UVa11661.c hosted with ❤ by GitHub

[UVa]11185:Ternary

利用平常轉換位數的方法來轉換成3進位。

[C](0.008)

	#include<stdio.h>
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF && !(N < 0) )
	{
	int temp = N;
	int answer[105] = {0}, answer_l = 0;
	int i;
	while( temp )
	{
	answer[answer_l++] = temp % 3;
	temp /= 3;
	}
	if( answer_l == 0 )
	printf( "0" );
	else
	for( i = answer_l-1 ; i >= 0 ; i-- )
	printf( "%d", answer[i] );
	printf( "\n" );
	}
	return 0;
	}

view raw UVa11185.c hosted with ❤ by GitHub

[UVa]10963:The Swallowing Ground

直接檢查每個y的裂痕是否相等即可得解。

[C](0.016)

	#include<stdio.h>
	int main()
	{
	int N;
	int print = 0;
	while( scanf( "%d", &N ) != EOF )
	{
	int i;
	for( i = 0 ; i < N ; i++ )
	{
	if( print )
	printf( "\n" );
	print = 1;
	int W;
	scanf( "%d", &W );
	int y1, y2;
	int ok = 1;
	scanf( "%d%d", &y1, &y2 );
	int gap = y1-y2;
	int j;
	for( j = 1 ; j < W ; j++ )
	{
	scanf( "%d%d", &y1, &y2 );
	if( y1-y2 != gap )
	ok = 0;
	}
	if( ok )
	printf( "yes\n" );
	else
	printf( "no\n" );
	}
	}
	return 0;
	}

view raw UVa10963.c hosted with ❤ by GitHub

[UVa]10929:You can say 11

1.此題數字過大，需用字串存取，
轉成數值必須經過ASCII碼的換算。

2.判斷11的倍數：偶數位和與奇數位和之差需要是11的倍數。

3.判斷N是否為0，必須判斷N[0]=='0'和N[1]=='\0'，不然會WA。

[C](0.016)

	#include<stdio.h>
	#include<string.h>
	#include<math.h>
	int main()
	{
	char N[1005];
	while( gets(N) && !(N[0] == '0' && N[1] == '\0') )
	{
	int odd = 0, even = 0, i;
	int N_length = strlen(N);
	for( i = 0 ; i < N_length ; i++ )
	if( i % 2 )
	odd += N[i] - '0';
	else
	even += N[i] - '0';
	if( !(abs(odd - even) % 11 ) )
	printf( "%s is a multiple of 11.\n", N );
	else
	printf( "%s is not a multiple of 11.\n", N );
	}
	return 0;
	}

view raw UVa10929.c hosted with ❤ by GitHub

[UVa]11059:Maximum Product

直接Brute Force去尋找乘積最大的連續數字。

[C](0.012)

	#include<stdio.h>
	int main()
	{
	int N;
	int M = 1;
	while( scanf( "%d", &N ) != EOF )
	{
	long long S[20] = {0};
	int i;
	for( i = 0 ; i < N ; i++ )
	scanf( "%lld", &S[i] );
	long long P = 0, temp;
	int j;
	for( i = 0 ; i < N ; i++ )
	{
	temp = S[i];
	P = ( temp > P ) ? temp : P;
	for( j = i+1 ; j < N ; j++ )
	{
	temp *= S[j];
	P = ( temp > P ) ? temp : P;
	}
	}
	printf( "Case #%d: The maximum product is %lld.\n\n", M++, P );
	}
	return 0;
	}

view raw UVa11059.c hosted with ❤ by GitHub

[幻想迷宮]第五關完工

第五關總算是完工了！
也算是除了隱藏關卡以外，全部關卡都完成了！
看來發佈日指日可待～
這關特色第一個是迷宮變得比前幾關來得複雜且長。

第二個特色就是......水上倉庫番!?

最後來個結尾XD

[UVa]10903:Rock-Paper-Scissors Tournament

趙著題目要求做即可得解。

[C](0.208)

	#include<stdio.h>
	#include<string.h>
	int win( char *m1, char *m2 )
	{
	if( (m1[0] == 'r' && m2[0] == 's') || (m1[0] == 's' && m2[0] == 'p') || (m1[0] == 'p' && m2[0] == 'r') )
	return 1;
	return 0;
	}
	int main()
	{
	int n, k;
	int print = 0;
	while( scanf( "%d", &n ) != EOF && n != 0 )
	{
	scanf( "%d", &k );
	if( print )
	printf( "\n" );
	print = 1;
	int people[105][2] = {0};
	int p1, p2;
	char m1[10], m2[10];
	int i;
	for( i = 0 ; i < k*n*(n-1)/2 ; i++ )
	{
	scanf( "%d%s%d%s", &p1, m1, &p2, m2 );
	if( win( m1, m2 ) )
	{
	people[p1][0]++;
	people[p2][1]++;
	}
	else if( win( m2, m1 ) )
	{
	people[p1][1]++;
	people[p2][0]++;
	}
	}
	for( i = 1 ; i <= n ; i++ )
	if( people[i][0]+people[i][1] != 0 )
	printf( "%.3lf\n", (double)(people[i][0])/(double)(people[i][0]+people[i][1]) );
	else
	printf( "-\n" );
	}
	return 0;
	}

view raw UVa10903.c hosted with ❤ by GitHub

[UVa]10812:Beat the Spread!

暴力法得解。

[C](0.012)

	#include<stdio.h>
	#include<math.h>
	int main()
	{
	int n;
	while( scanf( "%d", &n ) != EOF )
	{
	int s, d;
	int i, j;
	for( i = 0 ; i < n ; i++ )
	{
	scanf( "%d%d", &s, &d );
	int ok = 0;
	for( j = s ; j >= s-j ; j-- )
	{
	if( abs(s-2*j) == d )
	{
	printf( "%d %d\n", j, s-j );
	ok = 1;
	}
	}
	if( !ok )
	printf( "impossible\n" );
	}
	}
	return 0;
	}

view raw UVa10812.c hosted with ❤ by GitHub

[UVa]10789:Prime Frequency

利用質數表和ASCII碼就可以快速解完此題。

[C](0.016)

	#include<stdio.h>
	#include<string.h>
	int main()
	{
	int prime[2005] = {1, 1, 0, 0};
	int i, j;
	for( i = 2 ; i < 2001 ; i++ )
	if( !prime[i] )
	for( j = i*i ; j < 2001 ; j += i )
	prime[j] = 1;
	int T;
	while( scanf( "%d", &T ) != EOF )
	{
	getchar();
	char str[2005];
	for( i = 1 ; i <= T ; i++ )
	{
	gets( str );
	int strlength = strlen( str );
	int ASCII[256] = {0};
	for( j = 0 ; j < strlength ; j++ )
	ASCII[str[j]]++;
	printf( "Case %d: ", i );
	int ok = 0;
	for( j = 0 ; j < 128 ; j++ )
	if( !prime[ASCII[j]] )
	{
	ok = 1;
	printf( "%c", j );
	}
	if( !ok )
	printf( "empty" );
	printf( "\n" );
	}
	}
	return 0;
	}

view raw UVa10789.c hosted with ❤ by GitHub

[UVa]10673:Play with Floor and Ceil

首先，要先知道兩個括號的意義：
┌ ┐ => 取無條件進位(即是取ceil值)
└ ┘ => 取無條件捨去(即是取floor值)
接著p和q就刷過各種可能即可得解。

[C](1.528)

	#include<stdio.h>
	#include<math.h>
	int main()
	{
	int n;
	while( scanf( "%d", &n ) != EOF )
	{
	int i;
	for( i = 0 ; i < n ; i++ )
	{
	double x, k;
	while( scanf( "%lf%lf", &x, &k ) != EOF )
	{
	double p, q, xk_floor = floor(x/k), xk_ceil = ceil(x/k);
	int ok = 0;
	for( p = 0 ; !ok ; p++ )
	for( q = 0 ; p*xk_floor + q*xk_ceil <= x && !ok ; q++ )
	if( p*xk_floor + q*xk_ceil == x )
	ok = 1;
	p--;
	q--;
	printf( "%.0lf %.0lf\n", p, q );
	}
	}
	}
	return 0;
	}

view raw UVa10673.c hosted with ❤ by GitHub

[UVa]10589:Area

計算點距離四邊點的距離是否都在a以內即可得解。

[C](0.112)

	#include<stdio.h>
	double distance( double x1, double y1, double x2, double y2 )
	{
	return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
	}
	int main()
	{
	int N, a;
	while( scanf( "%d%d", &N, &a ) != EOF && N != 0 && a != 0 )
	{
	int i;
	int M = 0;
	for( i = 0 ; i < N ; i++ )
	{
	double x, y;
	scanf( "%lf%lf", &x, &y );
	if( distance( x, y, 0.0, 0.0 ) <= (double)(a*a) )
	if( distance( x, y, 0.0, (double)a ) <= (double)(a*a) )
	if( distance( x, y, (double)a, (double)a ) <= (double)(a*a) )
	if( distance( x, y, (double)a, 0.0 ) <= (double)(a*a) )
	M++;
	}
	printf( "%.5lf\n", (double)M/(double)N*(double)a*(double)a );
	}
	return 0;
	}

view raw UVa10589.c hosted with ❤ by GitHub

[UVa]10550:Combination Lock

此題感覺很簡單，
但是請你一定要想一想，
如果你順時針轉數字鎖的時候，
數字卻是會逆時針轉動的！= =
我被這個騙了三次......

[C](0.016)

	#include<stdio.h>
	int main()
	{
	int start, pw1, pw2, pw3;
	while( scanf( "%d%d%d%d", &start, &pw1, &pw2, &pw3 ) != EOF )
	{
	if( start == 0 && pw1 == 0 && pw2 == 0 && pw3 == 0)
	break;
	int angle = 1080;
	angle += ( start - pw1 < 0 )? (start - pw1 + 40) * 9 : (start - pw1) * 9;
	angle += ( pw2 - pw1 < 0 )? (pw2 - pw1 + 40) * 9 : (pw2 - pw1) * 9;
	angle += ( pw2 - pw3 < 0 )? (pw2 - pw3 + 40) * 9 : (pw2 - pw3) * 9;
	printf( "%d\n", angle );
	}
	return 0;
	}

view raw UVa10550.c hosted with ❤ by GitHub

[UVa]10499:The Land of Justice

如果是沒切的情形(1塊)利潤就是0%，
因為與原本的價格一樣。

分2塊的時候，表面積會比原本球的表面積多2塊半圓，
一塊半圓會佔利潤的25%(π*r/4*π*r=1/4=25%)，
所以2塊的時候是50%的利潤。

分3塊的時候，表面積會比原本球的表面積多3塊半圓=>75%。
分4塊的時候，表面積會比原本球的表面積多4塊半圓=>100%。
以此類推......

[C](0.044)

	#include<stdio.h>
	int main()
	{
	int n;
	while( scanf( "%d", &n ) != EOF && n > 0 )
	if( n == 1 )
	printf( "0%\n");
	else
	printf( "%.0lf%%\n", (double)n*25.0 );
	return 0;
	}

view raw UVa10499.c hosted with ❤ by GitHub

[幻想迷宮]第四關完工

雖然說其實我兩天前就做完了，
而且也已經請河水（后羿射月亮）測試過了，
但今天才把一些Bug修訂完成。

第四關的特色在於不能把木板再度拔起來利用，
對於要直接過關不拿盡頭的人來說，
木板數會是剛剛好的。
而對於要拿盡頭的人來說，
也得考慮先走哪的情形才不會卡關喔！

這關還出現了可以一次拿到兩塊木板的盡頭，
這是之前幾關沒有的，
這是為了補足要拿到所有盡頭的木板數。
(其實實際上全部一塊也是夠，
不過測試員認為還是多一點感覺比較不會刁難玩家XD)

最後當然是破關圖啦！(照例沒有拿到所有盡頭=D)

題外話：
出現了秘密的角色喔！

他會是誰呢？XD

[UVa]10473:Simple Base Conversion

利用C++的<iomanip>中的setbase()快速過關。=D

[C++](0.064)

	#include<iostream>
	#include<iomanip>
	using namespace std;
	int main()
	{
	int input;
	while( 1 )
	{
	if( '-' == cin.peek() )
	break;
	else if( '0' == cin.peek() )
	{
	cin >> setbase(16) >> input;
	cout << setbase(10) << input << endl;
	}
	else
	{
	cin >> setbase(10) >> input;
	cout << "0x" << setbase(16) << uppercase << input << endl;
	}
	cin.get();
	}
	return 0;
	}

view raw UVa10473.cpp hosted with ❤ by GitHub

[UVa]10370:Above Average

照著題目算即可得解。

[C](0.020)

	#include<stdio.h>
	int main()
	{
	int C;
	while( scanf( "%d", &C ) != EOF )
	{
	while( C-- )
	{
	int N;
	scanf( "%d", &N );
	int score[1005] = {0};
	int i;
	double average = 0;
	for( i = 0 ; i < N ; i++ )
	{
	scanf( "%d", &score[i] );
	average += score[i];
	}
	average /= N;
	int high = 0;
	for( i = 0 ; i < N ; i++ )
	if( score[i] > average )
	high++;
	printf( "%.3lf%%\n", (double)high/(double)N*100.0 );
	}
	}
	return 0;
	}

view raw UVa10370.c hosted with ❤ by GitHub

[UVa]10340:All in All

利用兩個變數i,j，
i從t開始搜，
搜到與s[j]一樣就讓j++，
這樣到最後如果j與s字串的長度一樣，
即表示答案是Yes，
反之則是No。

[C](0.012)

	#include<stdio.h>
	#include<string.h>
	int main()
	{
	char s[100000] = {0}, t[100000] = {0};
	while( scanf( "%s%s", s, t ) != EOF )
	{
	int slength = strlen(s);
	int tlength = strlen(t);
	int i, j;
	for( i = 0, j = 0 ; i < tlength && j < slength ; i++ )
	if( t[i] == s[j] )
	j++;
	if( j == slength )
	printf( "Yes\n" );
	else
	printf( "No\n" );
	}
	return 0;
	}

view raw UVa10340.c hosted with ❤ by GitHub

[UVa]10300:Ecological Premium

只要把農場面積和環境等級相乘即是解答。

[C](0.016)

	#include<stdio.h>
	int main()
	{
	int n;
	while( scanf( "%d", &n ) != EOF )
	{
	while( n-- )
	{
	int f;
	int sum = 0;
	scanf( "%d", &f );
	while( f-- )
	{
	int size, animal, env;
	scanf( "%d%d%d", &size, &animal, &env );
	sum += size * env;
	}
	printf( "%d\n", sum );
	}
	}
	return 0;
	}

view raw UVa10300.c hosted with ❤ by GitHub

[UVa]10222:Decode the Mad man

先把鍵盤輸入成一個字元陣列，這樣比較好轉換。

[C](0.016)

	#include<stdio.h>
	int main()
	{
	const char keyboard[] = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
	char input;
	while( (input = getchar()) != EOF )
	{
	if( input == ' ' || input == '\n' )
	{
	putchar( input );
	continue;
	}
	int i;
	for( i = 0 ; input != keyboard[i] ; i++ );
	putchar( keyboard[i-2] );
	}
	return 0;
	}

view raw UVa10222.c hosted with ❤ by GitHub

[UVa]10209:Is This Integration ?

要算面積，
令邊長為a，
一塊斜線的面積為x，
一塊點狀的面積為y，
一塊格子狀的面積為z。

則首先
正方形的面積減去四分之一以a為半徑的圓的面積
= a*a - a*a*π/4 = y+2*z ->(1)

再來六分之一以a為半徑的圓的面積減去以a為邊長的正三角形(想想看在哪裡...)
= a*a*π/6 - a*a*sqrt(3.0)/4 = 假設為某個面積w(想想看在哪裡...) ->(2)

接著把四分之一以a為半徑的圓的面積減去六分之一以a為半徑的圓的面積
= a*a*π/4 - a*a*π/6 = y+z+w ->(3)

則z=(y+2*z)-(y+z+w)+w=(1)-(3)+(2)就出來了，
那麼y=(y+2*z)-(2*z)=(1)-2*z也出來了，
而x=a*a-4*y-4*z也跟著出來了！

[C](0.056)

	#include<stdio.h>
	#include<math.h>
	#define PI 2.0*acos(0.0)
	int main()
	{
	double a;
	while( scanf( "%lf", &a ) != EOF )
	{
	double x, y, z;
	z = a*a - a*a*PI/4;
	z -= a*a*PI/4 - a*a*PI/6 - ( a*a*PI/6 - a*a*sqrt(3.0)/4 );
	y = a*a - a*a*PI/4 - 2*z;
	x = a*a - 4*y - 4*z;
	printf( "%.3lf %.3lf %.3lf\n", x, 4*y ,4*z );
	}
	return 0;
	}

view raw UVa10209.c hosted with ❤ by GitHub

[UVa]10141:Request for Proposal

照著題目要求的做即可。

[C](0.012)

	#include<stdio.h>
	struct proposal
	{
	char name[100];
	double price;
	int item;
	};
	typedef struct proposal Proposal;
	int main()
	{
	int dataset = 1;
	int n, p;
	while( scanf( "%d%d", &n, &p ) != EOF && n != 0 && p != 0 )
	{
	if( dataset > 1 )
	printf( "\n" );
	getchar();
	char recycle[100];
	int i, j;
	for( i = 0 ; i < n ; i++ )
	gets(recycle);
	Proposal list;
	Proposal best;
	best.price = 0;
	best.item = 0;
	for( i = 0 ; i < p ; i++ )
	{
	gets(list.name);
	scanf( "%lf%d", &list.price, &list.item );
	getchar();
	for( j = 0 ; j < list.item ; j++ )
	gets( recycle );
	if( list.item > best.item )
	best = list;
	else if( list.item == best.item )
	{
	if( list.price < best.price )
	best = list;
	}
	}
	printf( "RFP #%d\n", dataset );
	printf( "%s\n", best.name );
	dataset++;
	}
	return 0;
	}

view raw UVa10141.c hosted with ❤ by GitHub

[UVa]10107:What is the Median?

將數值一直由小到大插入陣列中，即可得其中位數。

[C](0.044)

	#include<stdio.h>
	int main()
	{
	int n;
	int median[10005], allnum = 0;
	while( scanf( "%d", &n ) != EOF )
	{
	int i, j;
	for( i = 0 ; i < allnum ; i++ )
	if( n > median[i] )
	{
	for( j = allnum ; j >= i ; j-- )
	median[j] = median[j-1];
	break;
	}
	median[i] = n;
	allnum++;
	if( allnum % 2 )
	printf( "%d\n", median[allnum/2] );
	else
	printf( "%d\n", (median[allnum/2-1]+median[allnum/2]) / 2);
	}
	return 0;
	}

view raw UVa10107.c hosted with ❤ by GitHub

[UVa]10082:WERTYU

先把鍵盤打成一個陣列，這樣比較好得解。

[C](0.016)

	#include<stdio.h>
	int main()
	{
	const char keyboard[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
	char input;
	while( ( input = getchar() ) != EOF )
	{
	int i;
	if( input == ' ' || input == '\n' )
	{
	printf( "%c", input );
	continue;
	}
	for( i = 0 ; keyboard[i] != input ; i++ );
	printf( "%c", keyboard[i-1] );
	}
	return 0;
	}

view raw UVa10082.c hosted with ❤ by GitHub

[UVa]10038:Jolly Jumpers

新站連結於http://knightzone.org/?p=1230。

[UVa]10035:Primary Arithmetic

新站連結於http://knightzone.org/?p=1227。

[UVa]10018:Reverse and Add

新站連結於http://knightzone.org/?p=1223。

[UVa]913:Joana and the Odd Numbers

新站連結於：http://knightzone.org/?p=1220。

[UVa]750:8 Queens Chess Problem

8皇后問題，利用backtracking得解。

[C](0.012)

	#include<stdio.h>
	int solution = 0;
	void backtracking( int n, int row, int col, int x[], int y[], int slash1[], int slash2[] )
	{
	int i;
	if( n == col )
	{
	backtracking( n+1, row, col, x, y, slash1, slash2 );
	return;
	}
	if( n == 9 )
	{
	solution++;
	printf( "%2d ", solution );
	for( i = 1 ; i <= 8 ; i++ )
	{
	printf( " %d", x[i] );
	}
	printf( "\n" );
	return;
	}
	for( i = 1 ; i <= 8 ; i++ )
	{
	if( !y[i] && !slash1[i+n] && !slash2[i-n+8] )
	{
	x[n] = i;
	y[i] = 1;
	slash1[i+n] = 1;
	slash2[i-n+8] = 1;
	backtracking( n+1, row, col, x, y, slash1, slash2 );
	x[n] = 0;
	y[i] = 0;
	slash1[i+n] = 0;
	slash2[i-n+8] = 0;
	}
	}
	}
	int main()
	{
	int dataset;
	while( scanf( "%d", &dataset ) != EOF )
	{
	int i;
	int print = 0;
	for( i = 1 ; i <= dataset ; i++ )
	{
	if( print )
	printf( "\n" );
	print = 1;
	int row, col;
	scanf( "%d%d", &row, &col );
	int x[15] = {0}, y[15] = {0}, slash1[20] = {0}, slash2[20] = {0};
	x[col] = row;
	y[row] = 1;
	slash1[row+col] = 1;
	slash2[row-col+8] = 1;
	printf( "SOLN COLUMN\n");
	printf( " # 1 2 3 4 5 6 7 8\n\n" );
	solution = 0;
	backtracking( 1, row, col, x, y, slash1, slash2 );
	}
	}
	return 0;
	}

view raw UVa750.c hosted with ❤ by GitHub

[UVa]291:The House Of Santa Claus

利用backtracking把所有解都跑一遍即可。

[C](0.008)

	#include<stdio.h>
	int house[6][6] = {0};
	int path[10] = {0}, pathsize = 0;
	void backtracking( int point )
	{
	path[pathsize++] = point;
	int i;
	if( pathsize == 9 )
	{
	for( i = 0 ; i < pathsize ; i++ )
	printf( "%d", path[i] );
	printf( "\n" );
	pathsize--;
	return;
	}
	for( i = 1 ; i <= 5 ; i++ )
	{
	if( house[point][i] )
	{
	house[point][i] = house[i][point] = 0;
	backtracking( i );
	house[point][i] = house[i][point] = 1;
	}
	}
	pathsize--;
	}
	int main()
	{
	house[1][2] = house[2][1] = 1;
	house[1][3] = house[3][1] = 1;
	house[1][5] = house[5][1] = 1;
	house[2][3] = house[3][2] = 1;
	house[2][5] = house[5][2] = 1;
	house[3][4] = house[4][3] = 1;
	house[3][5] = house[5][3] = 1;
	house[4][5] = house[5][4] = 1;
	backtracking( 1 );
	return 0;
	}

view raw UVa291.c hosted with ❤ by GitHub

[UVa]439:Knight Moves

八種可能的走法去BFS得解。

[C](0.012)

	#include<stdio.h>
	int main()
	{
	char start[5], finish[5];
	while( scanf( "%s%s", start, finish ) != EOF )
	{
	int startrow = start[1]-'1';
	int startcol = start[0]-'a';
	int finishrow = finish[1]-'1';
	int finishcol = finish[0]-'a';
	if( startrow == finishrow && startcol == finishcol )
	{
	printf( "To get from %s to %s takes 0 knight moves.\n", start, finish );
	continue;
	}
	int label[10][10] = {0};
	int BFS[100][3] = {0}, bfs_num = 0;
	BFS[bfs_num][0] = startrow;
	BFS[bfs_num][1] = startcol;
	BFS[bfs_num][2] = 0;
	bfs_num++;
	int i;
	int answer = 0;
	for( i = 0 ; i < bfs_num ; i++ )
	{
	int y = BFS[i][0];
	int x = BFS[i][1];
	int step = BFS[i][2];
	if( ((x+1 == finishcol) && (y+2 == finishrow)) ||
	((x-1 == finishcol) && (y+2 == finishrow)) ||
	((x+1 == finishcol) && (y-2 == finishrow)) ||
	((x-1 == finishcol) && (y-2 == finishrow)) ||
	((x+2 == finishcol) && (y+1 == finishrow)) ||
	((x-2 == finishcol) && (y+1 == finishrow)) ||
	((x+2 == finishcol) && (y-1 == finishrow)) ||
	((x-2 == finishcol) && (y-1 == finishrow)) )
	{
	answer = step+1;
	break;
	}
	if( x+1 < 8 && y+2 < 8 && !(label[y+2][x+1]) )
	{
	BFS[bfs_num][0] = y+2;
	BFS[bfs_num][1] = x+1;
	BFS[bfs_num][2] = step+1;
	label[y+2][x+1] = 1;
	bfs_num++;
	}
	if( x-1 >= 0 && y+2 < 8 && !(label[y+2][x-1]) )
	{
	BFS[bfs_num][0] = y+2;
	BFS[bfs_num][1] = x-1;
	BFS[bfs_num][2] = step+1;
	label[y+2][x-1] = 1;
	bfs_num++;
	}
	if( x+1 < 8 && y-2 >= 0 && !(label[y-2][x+1]) )
	{
	BFS[bfs_num][0] = y-2;
	BFS[bfs_num][1] = x+1;
	BFS[bfs_num][2] = step+1;
	label[y-2][x+1] = 1;
	bfs_num++;
	}
	if( x-1 >= 0 && y-2 >= 0 && !(label[y-2][x-1]) )
	{
	BFS[bfs_num][0] = y-2;
	BFS[bfs_num][1] = x-1;
	BFS[bfs_num][2] = step+1;
	label[y-2][x-1] = 1;
	bfs_num++;
	}
	if( x+2 < 8 && y+1 < 8 && !(label[y+1][x+2]) )
	{
	BFS[bfs_num][0] = y+1;
	BFS[bfs_num][1] = x+2;
	BFS[bfs_num][2] = step+1;
	label[y+1][x+2] = 1;
	bfs_num++;
	}
	if( x-2 >= 0 && y+1 < 8 && !(label[y+1][x-2]) )
	{
	BFS[bfs_num][0] = y+1;
	BFS[bfs_num][1] = x-2;
	BFS[bfs_num][2] = step+1;
	label[y+1][x-2] = 1;
	bfs_num++;
	}
	if( x+2 < 8 && y-1 >= 0 && !(label[y-1][x+2]) )
	{
	BFS[bfs_num][0] = y-1;
	BFS[bfs_num][1] = x+2;
	BFS[bfs_num][2] = step+1;
	label[y-1][x+2] = 1;
	bfs_num++;
	}
	if( x-2 >= 0 && y-1 >= 0 && !(label[y-1][x-2]) )
	{
	BFS[bfs_num][0] = y-1;
	BFS[bfs_num][1] = x-2;
	BFS[bfs_num][2] = step+1;
	label[y-1][x-2] = 1;
	bfs_num++;
	}
	}
	printf( "To get from %s to %s takes %d knight moves.\n", start, finish, answer );
	}
	return 0;
	}

view raw UVa439.c hosted with ❤ by GitHub

[UVa]532:Dungeon Master

三維的BFS即可得解。

[C](0.016)

	#include<stdio.h>
	int min( int a, int b )
	{
	return ( a < b ) ? a : b;
	}
	int main()
	{
	int L, R, C;
	while( scanf( "%d%d%d", &L, &R, &C ) != EOF && L != 0 && R != 0 && C != 0 )
	{
	char map[35][35][35] = {0};
	char s[35];
	int i, j, k;
	int BFS[30000][5] = {0}, bfs_num = 0;
	int label[35][35][35] = {0};
	for( i = 1 ; i <= L ; i++ )
	for( j = 1 ; j <= R ; j++ )
	{
	scanf( "%s", s );
	for( k = 1 ; k <= C ; k++ )
	{
	map[i][j][k] = s[k-1];
	if( s[k-1] == 'S' )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = 0;
	label[i][j][k] = 1;
	bfs_num++;
	}
	}
	}
	int n;
	int answer = 0;
	for( n = 0 ; n < bfs_num ; n++ )
	{
	i = BFS[n][0];
	j = BFS[n][1];
	k = BFS[n][2];
	int minute = BFS[n][3];
	if( map[i+1][j][k] == 'E' ||
	map[i-1][j][k] == 'E' ||
	map[i][j+1][k] == 'E' ||
	map[i][j-1][k] == 'E' ||
	map[i][j][k+1] == 'E' ||
	map[i][j][k-1] == 'E' )
	{
	answer = minute+1;
	break;
	}
	if( map[i+1][j][k] == '.' && !(label[i+1][j][k]) )
	{
	BFS[bfs_num][0] = i+1;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = minute+1;
	label[i+1][j][k] = 1;
	bfs_num++;
	}
	if( map[i-1][j][k] == '.' && !(label[i-1][j][k]) )
	{
	BFS[bfs_num][0] = i-1;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = minute+1;
	label[i-1][j][k] = 1;
	bfs_num++;
	}
	if( map[i][j+1][k] == '.' && !(label[i][j+1][k]) )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j+1;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = minute+1;
	label[i][j+1][k] = 1;
	bfs_num++;
	}
	if( map[i][j-1][k] == '.' && !(label[i][j-1][k]) )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j-1;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = minute+1;
	label[i][j-1][k] = 1;
	bfs_num++;
	}
	if( map[i][j][k+1] == '.' && !(label[i][j][k+1]) )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k+1;
	BFS[bfs_num][3] = minute+1;
	label[i][j][k+1] = 1;
	bfs_num++;
	}
	if( map[i][j][k-1] == '.' && !(label[i][j][k-1]) )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k-1;
	BFS[bfs_num][3] = minute+1;
	label[i][j][k-1] = 1;
	bfs_num++;
	}
	}
	if( answer )
	printf( "Escaped in %d minute(s).\n", answer );
	else
	printf( "Trapped!\n" );
	}
	return 0;
	}

view raw UVa532.c hosted with ❤ by GitHub

[UVa]11195:Another n-Queen Problem

這題要用點bitwise運算的概念，
把原本用陣列記錄列、斜線的放置，
改成用bits來記錄。
由於有點複雜，
我稍微解釋一下程式碼。

y_board[i] = (1<<n)-1;

這裡是讓可以放置皇后的位置用1來記錄，
不可以放置皇后的位置('*')用0來記錄。
那y_board這個陣列是以row(y)來當索引值，
然後col的部份用bits來記錄。

if( s[j] == '*' )
　　y_board[i] ^= (1<<j);

這裡就是讓*的位置用1來做XOR運算，
簡單來說就是把j位置的1改成0。

backtracking( n, 0, (1<<n)-1, (1;<<(2*n-1))-
1, (1<<(2*n-1))-1);

這邊把記錄x和記錄兩種斜線的bits丟進去backtracking，
並且x的n個位數都是1，表示目前都可以擺，
而斜線部分的2*n-1個位數也都是1，也表示目前都可以擺。

int nowslash1 = slash1 >> y;
int nowslash2 = slash2 >> (n-y-1);

將目前跑到那行row的斜線號碼全部抓出來，
例如8皇后的第一個row(row[0])，
x+y種類的斜線編號分別是
0+0=0,0+1=1,0+2=2,0+3=3......0+7=7，
也就是說用slash1 >> 0，
這樣即可讓slash1從個位數(2進位)開始的7個位數都剛好對應每一格。
而x-y+(2*n-1)種類的斜線編號分別是
0-0+15=15,0-1+15=14........0-7+15=8，
正好是從高位數(2進位)數過來0位數，
那為了推到個位數(2進位)，
就變成slash2 >> 8-0-1，
這樣就可以讓高位數(2進位)的7個位數推到個位數(2進位)來。

int canputqueen = y_board[y] & x & nowslash1 & nowslash2;

用&看看每一格是否能夠放置皇后，
y_board[]檢查是否為*，
x檢查是否這個col被放置皇后，
nowslash1檢查是否這條斜線被放置皇后，
nowslash2檢查另外一種斜線是否被放置皇后，
如果全部都是1，就表示這格可以放置皇后。

while( canputqueen )
{
　　xput = canputqueen & (-canputqueen);
　　backtracking( n, y+1, x^xput, slash1^(xput<<y), slash2^(xput<<(n-y-1)) );
　　canputqueen ^= xput;
}

第一行自己&負自己，可以得到二進位最低位的1，
而我就從這最低位的1開始放置皇后，
那麼x就要記錄放置皇后，
而slash1和slash2也要記錄放置了皇后，
最後再將這個1從canputqueen裡面去除，
再繼續把皇后放在下一個1的位置。

我不知道這樣是否有助於讓你了解這題，
如果還是不了解就底下留言問，
或是先自行推演看看，
或是問其他你認識的人討論這樣XD

這題我剛開始就直接backtracking，
結果時間就爆掉了= ="
後來看到討論都說要用bitmask，
我就用了，
然後一直RE，
結論是我沒加return 0; = =""""""

[C](0.956)

	#include<stdio.h>
	int y_board[20] = {0};
	int answer = 0;
	void backtracking( int n, int y, int x, int slash1, int slash2 )
	{
	if( y == n )
	{
	answer++;
	return;
	}
	int nowslash1 = slash1 >> y;
	int nowslash2 = slash2 >> (n-y-1);
	int canputqueen = y_board[y] & x & nowslash1 & nowslash2;
	int xput;
	while( canputqueen )
	{
	xput = canputqueen & (-canputqueen);
	backtracking( n, y+1, x^xput, slash1^(xput<<y), slash2^(xput<<(n-y-1)) );
	canputqueen ^= xput;
	}
	}
	int main()
	{
	int n;
	int casenumber = 1;
	while( scanf( "%d", &n ) != EOF && n != 0 )
	{
	int i, j;
	char s[20] = {0};
	for( i = 0 ; i < n ; i++ )
	{
	scanf( "%s", s );
	y_board[i] = (1<<n)-1;
	for( j = 0 ; j < n ; j++ )
	if( s[j] == '*' )
	y_board[i] ^= (1<<j);
	}
	answer = 0;
	backtracking( n, 0, (1<<n)-1, (1<<(2*n-1))-1, (1<<(2*n-1))-1);
	printf( "Case %d: %d\n", casenumber, answer );
	casenumber++;
	}
	return 0;
	}

view raw UVa11195.c hosted with ❤ by GitHub

[UVa]10048:Audiophobia

這題是all-pairs shortest paths的問題，
我用Floyd-Warshall Algorithm解決掉XD

[C](0.028)

	#include<stdio.h>
	#define MAX_VALUE 2147483647
	int max( int a, int b )
	{
	return ( a > b )? a : b;
	}
	int min( int a, int b )
	{
	return ( a < b )? a : b;
	}
	int main()
	{
	int print = 0;
	int casenumber = 1;
	int C, S, Q;
	int point[105][105] = {0};
	while( scanf( "%d%d%d", &C, &S, &Q ) != EOF && C != 0 && S != 0 && Q != 0 )
	{
	if( print )
	printf( "\n" );
	print = 1;
	int i, j, k;
	for( i = 1 ; i <= C ; i++ )
	for( j = 1 ; j <= C ; j++ )
	{
	if( i != j )
	point[i][j] = MAX_VALUE;
	else
	point[i][j] = 0;
	}
	int point1, point2;
	for( i = 1 ; i <= S ; i++ )
	{
	scanf( "%d%d", &point1, &point2 );
	scanf( "%d", &point[point1][point2] );
	point[point2][point1] = point[point1][point2];
	}
	for( k = 1 ; k <= C ; k++ )
	for( i = 1 ; i <= C ; i++ )
	for( j = 1 ; j <= C ; j++ )
	{
	point[i][j] = min( point[i][j], max( point[i][k], point[k][j] ) );
	}
	printf( "Case #%d\n", casenumber );
	for( i = 1 ; i <= Q ; i++ )
	{
	scanf( "%d%d", &point1, &point2 );
	if( point[point1][point2] != MAX_VALUE )
	printf( "%d\n", point[point1][point2] );
	else
	printf( "no path\n" );
	}
	casenumber++;
	}
	return 0;
	}

view raw UVa10048.c hosted with ❤ by GitHub

[幻想迷宮]第三關完工

第三關完工！
第三關的特色是水上傳送迷宮。
剛開始做的時候爆LAG，
害我去找了好多防止EVENT過多而導致LAG的腳本，
目前是好多了！
放幾張圖給各位看看吧！

另外我去掉了Shift加速的功能，讓剛開始就是加速的速度，
還有多加了ESC就可以重新開始的功能，
這是為了第四關先做好的！XD

最後來張破關圖，感謝各位期待，
下次進度再見了喔！^^/

[生活趣事/生活週記]3/2~3/4 晨興的禮拜三與忙碌的禮拜四

呃...其實我是照著我的大頭貼畫的，
我知道我畫的很爛，
不過這是在這段期間畫的就是了，
也補起Blog文章的圖片XD"

[3/2](三)
早上在弟兄之家和聖別學長晨興，
今次的內容讓我了解到傳福音就是為了要延續這個基督的生命，
讓這個基督的生命能夠延續下去，
蠻寶貝這個以賽亞書五三章10~11節這裡的這部份：「祂必看見後裔，並且延長年日。」
感謝主！

接著就去上自然探索，
今天聽到了教授的遊記和看到了教授出外遊玩的照片以及他的畫，
他用畫的來畫出日記，
超有趣！

因為比較早下課，
所以就到生服的攤位去發傳單，
發傳單超難！
完全不敢過去發Orz...
不過我還是有發到幾張，
感謝邵淮和蓉圓願意拿傳單XD

中午趕去上丹丹大大的簡報課，
我聽到很多好用的功能XD
我決定要來設計屬於自己的簡報Style了！

下午是程式設計（二），
教授講解作業怎麼寫，
然後他已經幾乎要上完Tree了，
超快！XD

晚上，我和浩庭去光華商場挑他要買的外接硬碟，
很碰巧地遇到我媽要幫她的朋友買MP3/MP4，
買完後我們就去吃麻醬麵，
小碗還是很大一碗= =""
然後浩庭到我家，玩我現在幻想迷宮的進度，
玩完後，我還給他看了VVVVVV和Magicka，
還有讓他玩了Clickr。XD

[3/3](四)
早上爬起來，
就趕緊去上邏輯概論，
然後老師說：「雖然我們學校是定9:00上課，
不過因為連三堂的關係，
我們第一節課從9:10上到10:00這樣。」
把下課都壓在10分鐘，
然後可以晚一點到，
好棒！！XD

中午是貓咪果醬的會議，
大概是討論各組要怎麼規劃我們將來的行程，
如此等等。

下午是微積分課，
在還沒上課前，我就畫了上面那張圖XD"
畫的還蠻糟的，繼續加油Orz......
微積分教授上的也蠻快的，
不過講得都很清晰，
能了解他在講什麼。=D

晚上是動漫社的社課，
我請Honey Bee學長訂的書來了XD
是一本骨架書，還蠻難翻的。
我覺得光要畫好軀幹的骨架就難翻天了Orz...
結果我一整堂都在研究軀幹骨架XD""""""

[3/4](五)
早上是國文，分組又要演戲，
不過演戲放在期初，真的比較好，
可以比較有時間準備！
接著是離散數學，
教授沒來，我們用教授原本錄好的影片上課XD
還有做練習題XD

中午去申請了成績單，
然後到學七吃燒臘，
燒臘部超棒！！
吃完就去找我們的前班代(現任副班代)，
教他程式設計作業的部份。

下午是吳老大的數位邏輯，
上的很開心，
因為當他講到OR、AND運算的時候，
我們在離散跟邏概都很熟了，
現在最主要要看的是如何利用這些運算表現數位電路的運作，
感覺還蠻棒的XD

上完課後，
我、威豪、維倫、安偉、ψω還有映竹就到公館去，
去光南買東西，
最主要是映竹要買他的Eee PC的「小」外接鍵盤，
還有安偉要買的東西。
買完後就回家了=D

[UVa]10285:Longest Run on a Snowboard

利用DFS來解即可。

另外不一定要從大往小走，
也可以反向變成從小往大走，
這樣可以在陣列第0列和第0行的地方加入一排0，
讓DFS可以把判斷是否走出陣列的地方給簡化。

還有就是每個點走完最長路線可以記在陣列裡，
這樣就可以直接拿來用。

[C](0.040)

	#include<stdio.h>
	int map[105][105] = {0};
	int longest[105][105] = {0};
	int DFS( int x, int y )
	{
	int result[4] = {0};
	if( map[y][x+1] > map[y][x] )
	{
	if( longest[y][x+1] )
	result[0] = 1+longest[y][x+1];
	else
	result[0] = 1+DFS(x+1,y);
	}
	if( map[y][x-1] > map[y][x] )
	{
	if( longest[y][x-1] )
	result[1] = 1+longest[y][x-1];
	else
	result[1] = 1+DFS(x-1,y);
	}
	if( map[y+1][x] > map[y][x] )
	{
	if( longest[y+1][x] )
	result[2] = 1+longest[y+1][x];
	else
	result[2] = 1+DFS(x,y+1);
	}
	if( map[y-1][x] > map[y][x] )
	{
	if( longest[y-1][x] )
	result[3] = 1+longest[y-1][x];
	else
	result[3] = 1+DFS(x,y-1);
	}
	int answer = 1;
	int i;
	for( i = 0 ; i <= 3 ; i++ )
	if( answer < result[i] )
	answer = result[i];
	return answer;
	}
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int i;
	for( i = 0 ; i < N ; i++ )
	{
	char S[100];
	int R, C;
	scanf( "%s%d%d", S, &R, &C );
	int i, j;
	for( i = 1 ; i <= R ; i++ )
	for( j = 1 ; j <= C ; j++ )
	{
	scanf( "%d", &map[i][j] );
	longest[i][j] = 0;
	}
	int answer = 0;
	for( i = 1 ; i <= R ; i++ )
	for( j = 1 ; j <= C ; j++ )
	{
	longest[i][j] = DFS( j, i );
	if( answer < longest[i][j] )
	answer = longest[i][j];
	}
	printf( "%s: %d\n", S, answer );
	}
	}
	return 0;
	}

view raw UVa10285.c hosted with ❤ by GitHub

[UVa]10327:Flip Sort

即是計算Bubble Sort的交換次數。

[C](0.088)

	#include<stdio.h>
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int array[1005] = {0};
	int i, j;
	for( i = 0 ; i < N ; i++ )
	scanf( "%d", &array[i] );
	int swap = 0;
	for( i = 0 ; i < N ; i++ )
	for( j = N-1 ; j > i ; j-- )
	if( array[j] < array[j-1] )
	{
	array[j] ^= array[j-1] ^= array[j] ^= array[j-1];
	swap++;
	}
	printf( "Minimum exchange operations : %d\n", swap );
	}
	return 0;
	}

view raw UVa10327.c hosted with ❤ by GitHub

[UVa]10336:Rank the Languages

利用BFS或是DFS把每塊區塊都找出來即可。

P.S. 寒訓比賽我用BFS，但到了看到這題來解的時候我改用DFS了XD"

[C](0.012)

	#include<stdio.h>
	#include<string.h>
	char map[1000][1000] = {0};
	int maparea[1000][1000] = {0};
	void DFS( int number, int x, int y )
	{
	maparea[y][x] = 1;
	if( map[y][x+1] == number && !maparea[y][x+1] )
	DFS( number, x+1, y );
	if( map[y][x-1] == number && !maparea[y][x-1] )
	DFS( number, x-1, y );
	if( map[y+1][x] == number && !maparea[y+1][x] )
	DFS( number, x, y+1 );
	if( map[y-1][x] == number && !maparea[y-1][x] )
	DFS( number, x, y-1 );
	}
	int main()
	{
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int H, W;
	int i;
	char s[1000] = {0};
	char maxdata = 0;
	for( i = 1 ; i <= N ; i++ )
	{
	scanf( "%d%d", &H, &W );
	int j, k;
	for( j = 1 ; j <= H ; j++ )
	{
	scanf( "%s", s );
	for( k = 0 ; k < W ; k++)
	{
	map[j][k+1] = s[k];
	maparea[j][k+1] = 0;
	maxdata = ( s[k] > maxdata )? s[k] : maxdata;
	}
	}
	int ASCII[256] = {0}, maxarea = 0;
	for( j = 1 ; j <= H ; j++ )
	for( k = 1 ; k <= W ; k++ )
	if( !maparea[j][k] )
	{
	DFS( map[j][k], k, j );
	ASCII[map[j][k]]++;
	maxarea = ( ASCII[map[j][k]] > maxarea )? ASCII[map[j][k]] : maxarea;
	}
	printf( "World #%d\n", i );
	for( j = maxarea ; j >= 1 ; j-- )
	for( k = 0 ; k <= maxdata ; k++ )
	if( j == ASCII[k] )
	printf( "%c: %d\n", k, j );
	}
	}
	return 0;
	}

view raw UVa10336.c hosted with ❤ by GitHub

[UVa]167:The Sultan's Successors

典型8皇后問題，利用backtracking即可得解。

[C](0.016)

	#include<stdio.h>
	int queen[8][8] = {0};
	int answer = 0;
	void backtracking( int sum, int x, int y[], int slash1[], int slash2[] )
	{
	if( x == 8 )
	{
	if( sum > answer )
	answer = sum;
	return;
	}
	int i;
	for( i = 0 ; i < 8 ; i++ )
	{
	if( !y[i] && !slash1[(i+x)%15] && !slash2[(i-x+15)%15] )
	{
	y[i] = 1;
	slash1[(i+x)%15] = 1;
	slash2[(i-x+15)%15] = 1;
	backtracking( sum+queen[x][i], x+1, y, slash1, slash2 );
	y[i] = 0;
	slash1[(i+x)%15] = 0;
	slash2[(i-x+15)%15] = 0;
	}
	}
	}
	int main()
	{
	int k;
	while( scanf( "%d", &k ) != EOF )
	{
	int n;
	for( n = 1 ; n <= k ; n++ )
	{
	int y[8] = {0}, slash1[15] = {0}, slash2[15] = {0};
	int i, j;
	for( j = 0 ; j < 8 ; j++ )
	for( i = 0 ; i < 8 ; i++ )
	scanf( "%d", &queen[j][i] );
	answer = 0;
	backtracking( 0, 0, y, slash1, slash2 );
	printf( "%5d\n", answer );
	}
	}
	return 0;
	}

view raw UVa167.c hosted with ❤ by GitHub

[UVa]534:Frogger

此題是最短路徑問題，
可以利用dijkstra法來解決。

[C](0.012)

	#include<stdio.h>
	#include<math.h>
	double min( double a, double b )
	{
	return ( a < b )? a : b;
	}
	double distance( double ax, double ay, double bx, double by )
	{
	return sqrt( ((ax-bx)*(ax-bx)) + ((ay-by)*(ay-by)) );
	}
	int main()
	{
	int n;
	int sets = 1;
	while( scanf( "%d", &n ) != EOF && n != 0 )
	{
	int i;
	double stone[205][5] = {0};
	for( i = 0 ; i < n ; i++ )
	scanf( "%lf%lf", &stone[i][0], &stone[i][1] );
	int now = 0;
	double dijkstra[205][5] = {0};
	for( i = 0 ; i < 205 ; i++ )
	dijkstra[i][0] = 2147483647;
	dijkstra[0][1] = 1;
	double maxdistance = 0;
	int temp = 1;
	while( now != 1 )
	{
	temp = 1;
	for( i = 0 ; i < n ; i++ )
	if( dijkstra[i][1] == 0 )
	{
	dijkstra[i][0] = min( distance(stone[now][0],stone[now][1],stone[i][0],stone[i][1] ), dijkstra[i][0] );
	if( dijkstra[i][0] < dijkstra[temp][0] )
	temp = i;
	}
	now = temp;
	maxdistance = ( dijkstra[now][0] > maxdistance )? dijkstra[now][0] : maxdistance;
	dijkstra[now][1] = 1;
	}
	printf( "Scenario #%d\n", sets++ );
	printf( "Frog Distance = %.3lf\n\n", maxdistance );
	}
	return 0;
	}

view raw UVa534.c hosted with ❤ by GitHub

[UVa]494:Kindergarten Counting Game

新站連結於http://knightzone.org/?p=1211。

[UVa]488:Triangle Wave

新站連結於http://knightzone.org/?p=1208。

[UVa]478:Points in Figures: Rectangles, Circles, Triangles

新站連結於http://knightzone.org/?p=1205。

[UVa]477:Points in Figures: Rectangles and Circles

新站連結於http://knightzone.org/?p=1202。

[UVa]476:Points in Figures: Rectangles

新站連結於http://knightzone.org/?p=1197。

[UVa]374:Big Mod

首先，
要先知道數學式子：(A*B)%C = (A%C) * (B%C)。
因此我就可以不用把B^P算完再去對M取餘數，
但是如果是((((B%M)*B)%M)*B)%M.....的話，
會TLE的，
所以算次方請用次方除二相乘的遞迴來算次方，
也就是 (B^P)%M = (B^(P/2)%M) * (B^(P/2)%M) 這樣遞迴。

[C](0.012)

	#include<stdio.h>
	long long modpow( long long B, long long P, long long M )
	{
	if( P == 0 )
	return 1;
	else if( P == 1 )
	return B%M;
	else
	{
	long long result = modpow( B, P/2, M );
	if( P % 2 )
	return result * result * B % M;
	else
	return result * result % M;
	}
	}
	int main()
	{
	long long B, P, M;
	while( scanf( "%lld%lld%lld", &B, &P, &M ) != EOF )
	{
	long long i = 0;
	long long R = modpow( B, P, M );
	printf( "%lld\n", R );
	}
	return 0;
	}

view raw UVa374.c hosted with ❤ by GitHub

[UVa]386:Perfect Cubes

硬爆解，每個都試試看就可以算出答案了。

[C](0.136)

	#include<stdio.h>
	int main()
	{
	int a, b, c, d;
	for( a = 2 ; a <= 200 ; a++ )
	for( b = 2 ; b < a ; b++ )
	for( c = b ; c < a ; c++ )
	for( d = c ; d < a ; d++ )
	if( a*a*a == b*b*b + c*c*c + d*d*d )
	printf( "Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d );
	return 0;
	}

view raw UVa386.c hosted with ❤ by GitHub

[UVa]382:Perfection

先建質數表，將輸入值給質因數分解，
利用質因數分解的結果求出所有因數之和，
將所有因數之和扣除掉自己本身，再比較大小即是答案。

P.S. 利用質因數分解的結果求出所有因數之和是數學的公式，
是每一個質因數從自己的0次方加到自己在質因數分解中的最高次方，
接著在把求出來所有的和相乘起來即可得解。
Ex. 12: 2^2 * 3^1
12所有因數之和：(2^0+2^1+2^2)*(3^0+3^1) = (1+2+4) * (1+3) = 28
驗證：12之因數：1,2,3,4,6,12
12所有因數之和：1+2+3+4+6+12=28

[C](0.016)

	#include<stdio.h>
	#include<math.h>
	#define ERROR 0.0000001
	int main()
	{
	int prime[60005] = {1,1,0};
	int i, j;
	for( i = 2 ; i <= 60000 ; i++ )
	if( !prime[i] )
	for( j = i+i ; j <= 60000 ; j += i )
	prime[j] = 1;
	int N;
	printf( "PERFECTION OUTPUT\n" );
	while( scanf( "%d", &N ) != EOF && N != 0 )
	{
	int divisor[60005] = {0};
	int temp = N;
	int sqrt_N = (int)( sqrt((double)N) + ERROR );
	for( i = 2 ; i <= sqrt_N ; i++ )
	if( !prime[i] )
	while( temp % i == 0 )
	{
	temp /= i;
	divisor[i]++;
	}
	int product = 1;
	int powsum, singlepow;
	for( i = 2 ; i <= sqrt_N ; i++ )
	if( divisor[i] )
	{
	powsum = 1;
	singlepow = 1;
	for( j = 1 ; j <= divisor[i] ; j++ )
	{
	singlepow *= i;
	powsum += singlepow;
	}
	product *= powsum;
	}
	if( temp != 1 )
	product *= temp+1;
	product -= N;
	printf( "%5d ", N );
	if( product == N )
	printf( "PERFECT\n" );
	else if( product > N )
	printf( "ABUNDANT\n" );
	else
	printf( "DEFICIENT\n" );
	}
	printf( "END OF OUTPUT\n" );
	return 0;
	}

view raw UVa382.c hosted with ❤ by GitHub

[生活趣事/生活週記]3/1-讀馬太二章&程式設計能力檢定(初級)

今天早上上完數位邏輯，
我跟著聖別學長到邵弟兄加吃飯讀經，
今日是讀馬太2章，
我藉著這次讀經才總算懂這個星象家原來是先走錯路，
之後才藉著聖經走回正確的路上，
之前這段好像看過去只覺得是星象家找到耶穌而已，
好深的含意在裡面都沒發現呀>_<
感謝主，今天的內容我得著了很多！

下午跟著聖別學長回到分部，
我就到PC室繼續解ACM～XD
解的差不多，
順應3月的到來，
我也順便把Blog背景換成春季綠意盎然的樣子了～
希望各位會喜歡！

晚上就是程式設計能力檢定(初級)，
有三題，
我都是硬爆XD"""
然後在快到8點的時候解完了，
接著我就回家了。

今天看來幻想迷宮是沒什麼進度就是了～XD

[UVa]357:Let Me Count The Ways

這題是DP的找零錢問題。

有幾種組合的算法，
由於可能會有重覆算到的關係，
所以要先加入最小的零錢(此題是1cent)進去，
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
接著再把次小的零錢(此題是5cents)放進去，
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
這樣以此類推到最大的零錢，
這樣我在算最後一個零錢是5cents的組合的時候，
我只會找出1cent跟5cents的組合，
不會找出配上10cents啦...25cents啦...或是50cents之類的組合。
等到我在算最後一個零錢是10cents的組合的時候，
我只會找出10cents跟5cents跟1cent的組合，
不會找出配上25cents啦...或是50cents之類的組合。
(如果看不懂以上內容，可以翻閱關於DP找零錢問題的教學文章。)

P.S. 這題要用long long Orz...

[C](0.020)

	#include<stdio.h>
	int main()
	{
	long long dp[30005] = {1};
	int money[5] = {1, 5, 10, 25, 50};
	int i, j;
	for( i = 0 ; i < 5 ; i++ )
	for( j = money[i] ; j <= 30000 ; j++ )
	dp[j] += dp[j-money[i]];
	int cents;
	while( scanf( "%d", &cents ) != EOF )
	if( dp[cents] == 1 )
	printf( "There is only 1 way to produce %d cents change.\n", cents );
	else
	printf( "There are %lld ways to produce %d cents change.\n", dp[cents], cents );
	return 0;
	}

view raw UVa357.c hosted with ❤ by GitHub

[UVa]147:Dollars

這題是DP的找零錢問題。

有幾種組合的算法，
由於可能會有重覆算到的關係，
所以要先加入最小的零錢(此題是5c)進去，
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
接著再把次小的零錢(此題是10c)放進去，
看看各個值(小於等於300.00)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
這樣以此類推到最大的零錢，
這樣我在算最後一個零錢是10c的組合的時候，
我只會找出5c跟10c的組合，
不會找出配上20c啦...50c啦...或是1元之類的組合。
等到我在算最後一個零錢是20c的組合的時候，
我只會找出5c跟10c跟20c的組合，
不會找出配上50c啦...或是1元之類的組合。
(如果看不懂以上內容，可以翻閱關於DP找零錢問題的教學文章。)

再來應該要建dp表，我們不可能用小數當索引值，
所以我們可以把該值乘上100在對應dp的那格為其答案，
但是浮點數乘法再配上轉成整數是避不開誤差的Orz...
因此請善用兩個整數來存值XD

[C](0.020)

	#include<stdio.h>
	int main()
	{
	long long dp[30005] = {1};
	long long possible[15] = { 5, 10, 20, 50,
	100, 200, 500,
	1000, 2000, 5000,
	10000};
	int i, j;
	for( i = 0 ; i < 11 ; i++ )
	for( j = possible[i] ; j <= 30000 ; j++ )
	dp[j] += dp[j-possible[i]];
	int money1, money2;
	while( scanf( "%d.%d", &money1, &money2 ) != EOF && !( money1 == 0 && money2 == 0 ) )
	printf( "%3d.%02d%17lld\n", money1, money2, dp[money1*100+money2] );
	return 0;
	}

view raw UVa147.c hosted with ❤ by GitHub

[UVa]136:Ugly Numbers

這題要算第1500個Ugly Number是誰，
假設我現在要算第N項，
那麼我就找前面這N-1項中找出：
「乘2會大於第N-1項的那項」以及「乘3會大於第N-1項的那項」還有「乘5會大於第N-1項的那項」。
找出來後比較他們三個的大小，
最小的就是第N項。

接著要找N+1項，
我再從前N項中一樣找出：
「乘2會大於第N項的那項」以及「乘3會大於第N項的那項」還有「乘5會大於第N項的那項」。
那其實你再找「乘2會大於第N項的那項」，
你可以從「乘2會大於第N-1項的那項」開始往後搜，
就不用再從第0項開始搜。
找「乘3會大於第N項的那項」還有「乘5會大於第N項的那項」也可以比照辦理、以此類推。

這樣就可以很快速的找到第1500個Ugly Number了。^^

[C](0.020)

	#include<stdio.h>
	#define min( a, b ) ( (a < b)? a : b )
	int main()
	{
	int uglynumbers[1505] = {1};
	int m2 = 0, m3 = 0, m5 = 0;
	int i = 1;
	int pre_n = 1;
	for( i = 1 ; i < 1500 ; i++ )
	{
	for( ; m2 < i ; m2++ )
	if( uglynumbers[m2]*2 > pre_n )
	break;
	for( ; m3 < i ; m3++ )
	if( uglynumbers[m3]*3 > pre_n )
	break;
	for( ; m5 < i ; m5++ )
	if( uglynumbers[m5]*5 > pre_n )
	break;
	pre_n = min( uglynumbers[m5]*5, min( uglynumbers[m2]*2 , uglynumbers[m3]*3 ) );
	uglynumbers[i] = pre_n;
	}
	printf( "The 1500'th ugly number is %d.\n", uglynumbers[1499] );
	system( "pause" );
	return 0;
	}

view raw UVa136.c hosted with ❤ by GitHub

[UVa]102:Ecological Bin Packing

新站連結於http://knightzone.org/?p=1465