本站遷移

因為我最近租用了網路空間以及網域,
故本站已遷移至新網站~
這邊的資訊已經正在進行搬移的工作~
希望各位可以到新網站去逛XD

New Website:
http://knightzone.org/

搜尋此網誌

2011年3月28日 星期一

[生活趣事/生活週記]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

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

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)
希望兒童品格營的籌備能夠非常順利呀>_<

下午晚上沒什麼事情,
瑪奇度過...耶!?

2011年3月20日 星期日

[UVa]105:The Skyline Problem

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

2011年3月19日 星期六

[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

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)
#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

2011年3月17日 星期四

[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

2011年3月16日 星期三

[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

2011年3月15日 星期二

[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

2011年3月14日 星期一

[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

2011年3月12日 星期六

[幻想迷宮]第五關完工

第五關總算是完工了!
也算是除了隱藏關卡以外,全部關卡都完成了!
看來發佈日指日可待~
這關特色第一個是迷宮變得比前幾關來得複雜且長。
第二個特色就是......水上倉庫番!?
最後來個結尾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

2011年3月11日 星期五

[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

2011年3月9日 星期三

[幻想迷宮]第四關完工

雖然說其實我兩天前就做完了,
而且也已經請河水(后羿射月亮)測試過了,
但今天才把一些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

2011年3月8日 星期二

[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

2011年3月7日 星期一

[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

2011年3月5日 星期六

[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

2011年3月4日 星期五

[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

2011年3月3日 星期四

[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

2011年3月2日 星期三

[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

2011年3月1日 星期二

[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