禮拜三去聽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
下午到晚上就在家裡玩瑪奇,
公會還遇到不太好的事件= =
就不多說了~
本站遷移
因為我最近租用了網路空間以及網域,
故本站已遷移至新網站~
這邊的資訊已經正在進行搬移的工作~
希望各位可以到新網站去逛XD
New Website:
http://knightzone.org/
搜尋此網誌
2011年3月28日 星期一
2011年3月21日 星期一
[生活趣事/生活週記]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)
希望兒童品格營的籌備能夠非常順利呀>_<
下午晚上沒什麼事情,
瑪奇度過...耶!?
講述關於島嶼分割所導致的物種獨特性與滅絕的書,
試著把它看完中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)
希望兒童品格營的籌備能夠非常順利呀>_<
下午晚上沒什麼事情,
瑪奇度過...耶!?
2011年3月20日 星期日
2011年3月19日 星期六
[UVa]10010:Where's Waldorf?
這題要注意的有幾個點:
1.尋找字串的時候雖然有八方位,
但是凡決定要走哪個方位後,
就只能朝著同一個方位走,
不能彎來彎去。
2.字母相等不分大小寫。
3.要以左上方為優先,
就要以斜線的方法來定X和Y,
相信被8皇后題目訓練過,
就會知道要用X+Y來搜尋XD
[C](0.008)
1.尋找字串的時候雖然有八方位,
但是凡決定要走哪個方位後,
就只能朝著同一個方位走,
不能彎來彎去。
2.字母相等不分大小寫。
3.要以左上方為優先,
就要以斜線的方法來定X和Y,
相信被8皇后題目訓練過,
就會知道要用X+Y來搜尋XD
[C](0.008)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月18日 星期五
[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)
假設今天有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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]11342:Three-square
這題請建表。
建表有兩個方式:
一個是像質數篩法那樣,
將a*a+b*b+c*c的那格填入答案。
另外一個是比較慢,也是下面的程式碼的作法,
直觀地真的去找每個數的答案,
但是要注意a,b,c的範圍避免TLE。
[C](0.568)
建表有兩個方式:
一個是像質數篩法那樣,
將a*a+b*b+c*c的那格填入答案。
另外一個是比較慢,也是下面的程式碼的作法,
直觀地真的去找每個數的答案,
但是要注意a,b,c的範圍避免TLE。
[C](0.568)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月17日 星期四
[UVa]10394:Twin Primes
建質數表得解。
[C](1.492)
[C](1.492)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月16日 星期三
[UVa]10192:Vacation
LCS(Longest common subsequence)的問題。
[C](0.012)
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]264:Count on Cantor
找出第幾斜排以及第幾斜排的最末項還有第n項的分母與分子這四者的關係,
即可得解。
[C](0.012)
即可得解。
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10405:Longest Common Subsequence
LCS(Longest common subsequence)的問題。
[C](0.048)
[C](0.048)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月15日 星期二
[UVa]10066:The Twin Towers
LCS(Longest common subsequence)的問題。
[C](0.008)
[C](0.008)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10684:The jackpot
DP題,
利用另外一個陣列記錄到從前面連續到目前這格贏最多的錢是多少,
再找這裡面全部最多錢的即是答案。
[C](0.088)
利用另外一個陣列記錄到從前面連續到目前這格贏最多的錢是多少,
再找這裡面全部最多錢的即是答案。
[C](0.088)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10258:Contest Scoreboard
照著題目說的做即可得解。
要注意,當某題目被AC後,
後面如果同組有再送同樣那題,
就不用再去增加那題的懲罰時間。
(不過個人不確定會不會有這種可能性就是了。)
[C++](0.016)
要注意,當某題目被AC後,
後面如果同組有再送同樣那題,
就不用再去增加那題的懲罰時間。
(不過個人不確定會不會有這種可能性就是了。)
[C++](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]11689:Soda Surpler
這題要注意的是:換完後的汽水罐,等喝完後還可以再換,所以不是只能換一次這樣。
[C](0.012)
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]11661:Burger Time?
從頭開始搜尋,
一直不斷比較最後找到的D和R的間距是否為最小的即是解答。
(當然如果裡面有Z,那答案一定是0)
[C](0.356)
一直不斷比較最後找到的D和R的間距是否為最小的即是解答。
(當然如果裡面有Z,那答案一定是0)
[C](0.356)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月14日 星期一
[UVa]11185:Ternary
利用平常轉換位數的方法來轉換成3進位。
[C](0.008)
[C](0.008)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10963:The Swallowing Ground
直接檢查每個y的裂痕是否相等即可得解。
[C](0.016)
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10929:You can say 11
1.此題數字過大,需用字串存取,
轉成數值必須經過ASCII碼的換算。
2.判斷11的倍數:偶數位和與奇數位和之差需要是11的倍數。
3.判斷N是否為0,必須判斷N[0]=='0'和N[1]=='\0',不然會WA。
[C](0.016)
轉成數值必須經過ASCII碼的換算。
2.判斷11的倍數:偶數位和與奇數位和之差需要是11的倍數。
3.判斷N是否為0,必須判斷N[0]=='0'和N[1]=='\0',不然會WA。
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]11059:Maximum Product
直接Brute Force去尋找乘積最大的連續數字。
[C](0.012)
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月12日 星期六
[UVa]10903:Rock-Paper-Scissors Tournament
趙著題目要求做即可得解。
[C](0.208)
[C](0.208)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10812:Beat the Spread!
暴力法得解。
[C](0.012)
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10789:Prime Frequency
利用質數表和ASCII碼就可以快速解完此題。
[C](0.016)
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10673:Play with Floor and Ceil
首先,要先知道兩個括號的意義:
┌ ┐ => 取無條件進位(即是取ceil值)
└ ┘ => 取無條件捨去(即是取floor值)
接著p和q就刷過各種可能即可得解。
[C](1.528)
┌ ┐ => 取無條件進位(即是取ceil值)
└ ┘ => 取無條件捨去(即是取floor值)
接著p和q就刷過各種可能即可得解。
[C](1.528)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月11日 星期五
[UVa]10589:Area
計算點距離四邊點的距離是否都在a以內即可得解。
[C](0.112)
[C](0.112)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10550:Combination Lock
此題感覺很簡單,
但是請你一定要想一想,
如果你順時針轉數字鎖的時候,
數字卻是會逆時針轉動的!= =
我被這個騙了三次......
[C](0.016)
但是請你一定要想一想,
如果你順時針轉數字鎖的時候,
數字卻是會逆時針轉動的!= =
我被這個騙了三次......
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[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)
因為與原本的價格一樣。
分2塊的時候,表面積會比原本球的表面積多2塊半圓,
一塊半圓會佔利潤的25%(π*r/4*π*r=1/4=25%),
所以2塊的時候是50%的利潤。
分3塊的時候,表面積會比原本球的表面積多3塊半圓=>75%。
分4塊的時候,表面積會比原本球的表面積多4塊半圓=>100%。
以此類推......
[C](0.044)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月9日 星期三
[幻想迷宮]第四關完工
雖然說其實我兩天前就做完了,
而且也已經請河水(后羿射月亮)測試過了,
但今天才把一些Bug修訂完成。
第四關的特色在於不能把木板再度拔起來利用,
對於要直接過關不拿盡頭的人來說,
木板數會是剛剛好的。
而對於要拿盡頭的人來說,
也得考慮先走哪的情形才不會卡關喔!
這關還出現了可以一次拿到兩塊木板的盡頭,
這是之前幾關沒有的,
這是為了補足要拿到所有盡頭的木板數。
(其實實際上全部一塊也是夠,
不過測試員認為還是多一點感覺比較不會刁難玩家XD)
最後當然是破關圖啦!(照例沒有拿到所有盡頭=D)
題外話:
出現了秘密的角色喔!
他會是誰呢?XD
而且也已經請河水(后羿射月亮)測試過了,
但今天才把一些Bug修訂完成。
第四關的特色在於不能把木板再度拔起來利用,
對於要直接過關不拿盡頭的人來說,
木板數會是剛剛好的。
而對於要拿盡頭的人來說,
也得考慮先走哪的情形才不會卡關喔!
這關還出現了可以一次拿到兩塊木板的盡頭,
這是之前幾關沒有的,
這是為了補足要拿到所有盡頭的木板數。
(其實實際上全部一塊也是夠,
不過測試員認為還是多一點感覺比較不會刁難玩家XD)
最後當然是破關圖啦!(照例沒有拿到所有盡頭=D)
題外話:
出現了秘密的角色喔!
他會是誰呢?XD
[UVa]10473:Simple Base Conversion
利用C++的<iomanip>中的setbase()快速過關。=D
[C++](0.064)
[C++](0.064)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10370:Above Average
照著題目算即可得解。
[C](0.020)
[C](0.020)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10340:All in All
利用兩個變數i,j,
i從t開始搜,
搜到與s[j]一樣就讓j++,
這樣到最後如果j與s字串的長度一樣,
即表示答案是Yes,
反之則是No。
[C](0.012)
i從t開始搜,
搜到與s[j]一樣就讓j++,
這樣到最後如果j與s字串的長度一樣,
即表示答案是Yes,
反之則是No。
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10300:Ecological Premium
只要把農場面積和環境等級相乘即是解答。
[C](0.016)
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10222:Decode the Mad man
先把鍵盤輸入成一個字元陣列,這樣比較好轉換。
[C](0.016)
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[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)
令邊長為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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月8日 星期二
[UVa]10141:Request for Proposal
照著題目要求的做即可。
[C](0.012)
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10107:What is the Median?
將數值一直由小到大插入陣列中,即可得其中位數。
[C](0.044)
[C](0.044)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10082:WERTYU
先把鍵盤打成一個陣列,這樣比較好得解。
[C](0.016)
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]750:8 Queens Chess Problem
8皇后問題,利用backtracking得解。
[C](0.012)
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月7日 星期一
[UVa]291:The House Of Santa Claus
利用backtracking把所有解都跑一遍即可。
[C](0.008)
[C](0.008)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]439:Knight Moves
八種可能的走法去BFS得解。
[C](0.012)
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]532:Dungeon Master
三維的BFS即可得解。
[C](0.016)
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]11195:Another n-Queen Problem
這題要用點bitwise運算的概念,
把原本用陣列記錄列、斜線的放置,
改成用bits來記錄。
由於有點複雜,
我稍微解釋一下程式碼。
不可以放置皇后的位置('*')用0來記錄。
那y_board這個陣列是以row(y)來當索引值,
然後col的部份用bits來記錄。
簡單來說就是把j位置的1改成0。
並且x的n個位數都是1,表示目前都可以擺,
而斜線部分的2*n-1個位數也都是1,也表示目前都可以擺。
例如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進位)來。
y_board[]檢查是否為*,
x檢查是否這個col被放置皇后,
nowslash1檢查是否這條斜線被放置皇后,
nowslash2檢查另外一種斜線是否被放置皇后,
如果全部都是1,就表示這格可以放置皇后。
而我就從這最低位的1開始放置皇后,
那麼x就要記錄放置皇后,
而slash1和slash2也要記錄放置了皇后,
最後再將這個1從canputqueen裡面去除,
再繼續把皇后放在下一個1的位置。
我不知道這樣是否有助於讓你了解這題,
如果還是不了解就底下留言問,
或是先自行推演看看,
或是問其他你認識的人討論這樣XD
這題我剛開始就直接backtracking,
結果時間就爆掉了= ="
後來看到討論都說要用bitmask,
我就用了,
然後一直RE,
結論是我沒加return 0; = =""""""
[C](0.956)
把原本用陣列記錄列、斜線的放置,
改成用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運算,y_board[i] ^= (1<<j);
簡單來說就是把j位置的1改成0。
backtracking( n, 0, (1<<n)-1, (1;<<(2*n-1))-
1, (1<<(2*n-1))-1);
這邊把記錄x和記錄兩種斜線的bits丟進去backtracking,1, (1<<(2*n-1))-1);
並且x的n個位數都是1,表示目前都可以擺,
而斜線部分的2*n-1個位數也都是1,也表示目前都可以擺。
int nowslash1 = slash1 >> y;
int nowslash2 = slash2 >> (n-y-1);
將目前跑到那行row的斜線號碼全部抓出來,int nowslash2 = slash2 >> (n-y-1);
例如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,{
xput = canputqueen & (-canputqueen);
backtracking( n, y+1, x^xput, slash1^(xput<<y), slash2^(xput<<(n-y-1)) );
canputqueen ^= xput;
}
而我就從這最低位的1開始放置皇后,
那麼x就要記錄放置皇后,
而slash1和slash2也要記錄放置了皇后,
最後再將這個1從canputqueen裡面去除,
再繼續把皇后放在下一個1的位置。
如果還是不了解就底下留言問,
或是先自行推演看看,
或是問其他你認識的人討論這樣XD
這題我剛開始就直接backtracking,
結果時間就爆掉了= ="
後來看到討論都說要用bitmask,
我就用了,
然後一直RE,
結論是我沒加return 0; = =""""""
[C](0.956)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月5日 星期六
[UVa]10048:Audiophobia
這題是all-pairs shortest paths的問題,
我用Floyd-Warshall Algorithm解決掉XD
[C](0.028)
我用Floyd-Warshall Algorithm解決掉XD
[C](0.028)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[幻想迷宮]第三關完工
第三關完工!
第三關的特色是水上傳送迷宮。
剛開始做的時候爆LAG,
害我去找了好多防止EVENT過多而導致LAG的腳本,
目前是好多了!
放幾張圖給各位看看吧!
另外我去掉了Shift加速的功能,讓剛開始就是加速的速度,
還有多加了ESC就可以重新開始的功能,
這是為了第四關先做好的!XD
最後來張破關圖,感謝各位期待,
下次進度再見了喔!^^/
第三關的特色是水上傳送迷宮。
剛開始做的時候爆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
2011年3月4日 星期五
[UVa]10285:Longest Run on a Snowboard
利用DFS來解即可。
另外不一定要從大往小走,
也可以反向變成從小往大走,
這樣可以在陣列第0列和第0行的地方加入一排0,
讓DFS可以把判斷是否走出陣列的地方給簡化。
還有就是每個點走完最長路線可以記在陣列裡,
這樣就可以直接拿來用。
[C](0.040)
另外不一定要從大往小走,
也可以反向變成從小往大走,
這樣可以在陣列第0列和第0行的地方加入一排0,
讓DFS可以把判斷是否走出陣列的地方給簡化。
還有就是每個點走完最長路線可以記在陣列裡,
這樣就可以直接拿來用。
[C](0.040)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10327:Flip Sort
即是計算Bubble Sort的交換次數。
[C](0.088)
[C](0.088)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]10336:Rank the Languages
利用BFS或是DFS把每塊區塊都找出來即可。
P.S. 寒訓比賽我用BFS,但到了看到這題來解的時候我改用DFS了XD"
[C](0.012)
P.S. 寒訓比賽我用BFS,但到了看到這題來解的時候我改用DFS了XD"
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月3日 星期四
[UVa]167:The Sultan's Successors
典型8皇后問題,利用backtracking即可得解。
[C](0.016)
[C](0.016)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月2日 星期三
[UVa]534:Frogger
此題是最短路徑問題,
可以利用dijkstra法來解決。
[C](0.012)
可以利用dijkstra法來解決。
[C](0.012)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
2011年3月1日 星期二
[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)
要先知道數學式子:(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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[UVa]386:Perfect Cubes
硬爆解,每個都試試看就可以算出答案了。
[C](0.136)
[C](0.136)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[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)
利用質因數分解的結果求出所有因數之和,
將所有因數之和扣除掉自己本身,再比較大小即是答案。
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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[生活趣事/生活週記]3/1-讀馬太二章&程式設計能力檢定(初級)
今天早上上完數位邏輯,
我跟著聖別學長到邵弟兄加吃飯讀經,
今日是讀馬太2章,
我藉著這次讀經才總算懂這個星象家原來是先走錯路,
之後才藉著聖經走回正確的路上,
之前這段好像看過去只覺得是星象家找到耶穌而已,
好深的含意在裡面都沒發現呀>_<
感謝主,今天的內容我得著了很多!
下午跟著聖別學長回到分部,
我就到PC室繼續解ACM~XD
解的差不多,
順應3月的到來,
我也順便把Blog背景換成春季綠意盎然的樣子了~
希望各位會喜歡!
晚上就是程式設計能力檢定(初級),
有三題,
我都是硬爆XD"""
然後在快到8點的時候解完了,
接著我就回家了。
今天看來幻想迷宮是沒什麼進度就是了~XD
我跟著聖別學長到邵弟兄加吃飯讀經,
今日是讀馬太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)
有幾種組合的算法,
由於可能會有重覆算到的關係,
所以要先加入最小的零錢(此題是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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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", ¢s ) != 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; | |
} |
[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)
有幾種組合的算法,
由於可能會有重覆算到的關係,
所以要先加入最小的零錢(此題是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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
[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)
假設我現在要算第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)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
訂閱:
文章 (Atom)