2010年4月29日 星期四

Problem 11483 Code Creator,印出字串

這題就是給你 n 行字串,請你寫一個完整的 C 語言程式碼,也就是說,
輸入:Hello World!
輸出:#include<string.h>
#include<stdio.h>
int main()
{
printf("Hello World!\n");
printf("\n");
return 0;
}
其實就只是照實印出,但要注意的就是「\\」和「\"」字元,印出時前面要多加「\\」。C 語言程式碼如下:
int n, caseNum = 1, i, j;
char ch; char str[101];
while (scanf("%d", &n) == 1 && n)
{
printf("Case %d:\n#include<string.h>\n#include<stdio.h>\nint main()\n{\n", caseNum ++);
getchar();
while (n --)
{
gets(str);
printf( "printf(\"" );
for (i = 0; str[i]; i ++)
{
if (str[i] == '\\' || str[i] == '\"')
printf("\\%c", str[i]);
else
printf("%c", str[i]);
}
printf("\\n\");\n");
}
printf("printf(\"\\n\");\nreturn 0;\n}\n");
}

By David.K

p11483題目連結
回ACM題庫目錄
回首頁

2010年4月27日 星期二

Problem 706 LCD Display,LCD 顯示字

此題輸入數字的大小與數字串,將此數字串依照數字的大小印出來。

首先,我是將所有的數字都放到一個二維的字元陣列裡,再一次印出。我們可以利用題目給的公式算出一個字的長度 col 與寬度 row,還有整個數字串需要用到多少長度 len。所以寫成 C 與程式碼如下:
col = size + 2, row = size * 2 + 3;
int len = strlen(numStr);
len = (len - 1) + len * col;
其中,size 為數字的大小,numStr 為數字串。將每個數字傳入一函式 putPrint(int num, int site) 可以將字擺到正確位置,這函式會在每一個數字之間加一個空格。 C 語言程式碼如下:
char printArray[25][120];
void line(int sRow, int sCol)
{
int i;
for (i = 1; i < col - 1; i ++)
printArray[sRow][sCol + i] = '-';
}

void space(int sRow, int sCol)
{
int i;
for (i = 1; i < col - 1; i ++)
printArray[sRow][sCol + i] = ' ';
}

void putPrint(int num, int site)
{
int i, nowSite = site * (col + 1) - 1, j;
if (nowSite > 0)
for (i = 0; i < row; i ++)
printArray[i][nowSite] = ' ';
int sCol = nowSite + 1, sRow = 0;
if (num == 0)
{
printArray[sRow][sCol] = ' ', line(sRow, sCol), printArray[sRow][sCol + col - 1] = ' ', sRow ++;
for (i = 0; i < size; i ++)
printArray[sRow][sCol] = '|', space(sRow, sCol), printArray[sRow][sCol + col - 1] = '|', sRow ++;
printArray[sRow][sCol] = ' ', space(sRow, sCol), printArray[sRow][sCol + col - 1] = ' ', sRow ++;
for (i = 0; i < size; i ++)
printArray[sRow][sCol] = '|', space(sRow, sCol), printArray[sRow][sCol + col - 1] = '|', sRow ++;
printArray[sRow][sCol] = ' ', line(sRow, sCol), printArray[sRow][sCol + col - 1] = ' ', sRow ++;
return;
}
if (num == 1)
{
printArray[sRow][sCol] = ' ', space(sRow, sCol), printArray[sRow][sCol + col - 1] = ' ', sRow ++;
for (i = 0; i < size; i ++)
printArray[sRow][sCol] = ' ', space(sRow, sCol), printArray[sRow][sCol + col - 1] = '|', sRow ++;
printArray[sRow][sCol] = ' ', space(sRow, sCol), printArray[sRow][sCol + col - 1] = ' ', sRow ++;
for (i = 0; i < size; i ++)
printArray[sRow][sCol] = ' ', space(sRow, sCol), printArray[sRow][sCol + col - 1] = '|', sRow ++;
printArray[sRow][sCol] = ' ', space(sRow, sCol), printArray[sRow][sCol + col - 1] = ' ', sRow ++;
return;
}
else if (num == 2)
{
...
...
...
}
...
...
...
}

num 為此次數字,site 為此次數字的位置,site * (col + 1) - 1 即為空格列的位置,因為每個數字之間要加行空白,所以它如果小於 0,就代表它是第一個數字,也就不需要空格列,而 site * (col + 1) 則為每個字要印出的行。再接下來就利用 line(int sRow, int sCol) 函式與 space(int sRow, int sCol) 函式來控制每一個字要印出些甚麼。我只列出 0 和 1 的方法,剩下就請大家去玩玩看吧。還不錯玩。
最後,主程式內只需這樣呼叫:
for (i = 0; i < strlen(numStr) ; i ++)
putPrint(numStr[i] - '0', i);
for (i = 0; i < row; i ++)
printArray[i][len] = '\0';
for (i = 0; i < row; i ++)
puts(printArray[i]);
printf("\n");

By David.K

p706題目連結
回ACM題庫目錄
回首頁

Problem 748 Exponentiation,小數次方

此題是要求出 Rn 次方的數值,每個整數或小數必須精準,所以這是一個大數乘法的運算。

舉個例子,22.24 的 2 次方是 494.6176(22242 = 4946176),當中,本來小數點的左邊數過來的第 2 位,2 次方之後是在第 4 位,我們可以觀察之後的次方並不難發覺小數點跟次方有成正比的相關。3 次方為 11000.295424(22243 = 11000295424)、4 次方為 244646.57022976(22244 = 24464657022976)、 ....等等,所以我們只要能求出 2224 的次方,再將小數點點在正確位置就可以了。

首先,讀入一個 R 字串和 n 整數代表 R 和 n,再將字串顛倒轉為整數陣列,順便記錄小數點的位置。C 語言程式碼如下:
#define MAXLEN 100

主程式內...
int decimal[MAXLEN + 20] = {0}, rInt[8] = {0}, pointSite = -1;
for (i = 5, j = 0; i >= 0; i --)
{
if (R[i] != '.') rInt[j] = R[i] - '0',
decimal[j] = R[i] - '0', j ++;
else pointSite = j;
}
再用大數相乘概念將 decimal 陣列累乘 n 次。 C 語言程式碼如下:
int a = n;
a --;
while (a --)
{
int nowDecimal[MAXLEN + 20] = {0};
for (i = 0; i < j; i ++)
{
for (k = 0; k < MAXLEN; k ++)
{
nowDecimal[i + k] += decimal[k] * rInt[i];
if (nowDecimal[i + k] >= 10)
nowDecimal[i + k + 1] += nowDecimal[i + k] / 10, nowDecimal[i + k] %= 10;
}
}
for (k = 0; k < MAXLEN; k ++)
decimal[k] = nowDecimal[k];
}

print(decimal, n * pointSite);
最後寫一函式 print(int dec[], int pS),將待印出整數陣列 dec[] 與小數點位置 pS 傳入就能將它印出,其中,需要判斷它整數部分是否為 0。如果為 0,就不需要印出數字,直接印出小數點。還有,小數部分如果結尾有 0,甚至有很多個 0,也要剔除。C 語言程式碼如下:
void print(int dec[], int pS)
{
int i, j, end;
for (i = MAXLEN - 1; i >= 0; i --)
if (dec[i] > 0) break;
for (end = 0; ; end ++)
if (dec[end] > 0) break;
if (i - (pS - 1) < 0)
{
printf(".");
for (j = 0; j < (pS-1) - i; j ++)
printf("0");
}
for (j = i; j >= end; j --)
{
if (j == pS - 1) printf(".");
printf("%d", dec[j]);
}
printf("\n");
}

By David.K

p748題目連結
回ACM題庫目錄
回首頁

2010年4月25日 星期日

Problem 10161 Ant on a Chessboard,有著螞蟻的棋盤

以下圖方便講解我解題的方法:
首先,輸入一個值 N 後,先找出 N 在哪一個平方區內,也就是說,10 ~ 16 在 4 平方區,17 ~ 25 在 5 平方區。觀察上圖,10 ~ 16 其中有一個座標為 4,17 ~ 25 其中有一個座標為 5,再求出平方區內「紅色三角形」的數值,就可以很方便的求出座標了。用以下 C 語言程式碼可以找出 N 在哪一個平方區內:
int sqrtN = (int)ceil(sqrt((double)N));
再用以下 C 語言程式碼可以找出此平方區內「紅色三角形」的數值:
int mid = sqrtN * sqrtN - sqrtN + 1;
然後,判斷 N 是不是就是等於 mid ,如果是,座標就是 sqrtN, sqrtN;如果 N > mid,則需再判斷 sqrtN 是否為奇數或偶數,因為在上圖顯示,奇數是由下而上再由右至左,偶數則為由左而右再由上至下,所以當它是奇數時,則座標為sqrtN - (N - mid), sqrtN,而為偶數座標是 sqrtN, sqrtN - (N - mid);如果 N < mid, sqrtN 是奇數的座標為 sqrtN, sqrtN - (mid - N),sqrtN 是偶數的座標為 sqrtN - (mid - N), sqrtN。

By David.K

p10161題目連結
回ACM題庫目錄
回首頁

2010年4月24日 星期六

Problem 10062 Tell me the frequencies!

此題與 Problem 10008 非常類似,只需將 insert(char ch) 函式稍加修改與 struct Word w[26] 改為 struct Word w[300]。讀取 ASCII 字串時使用 gets(),print() 函式字元要印出用整數格式(%d)印出。最後,輸出格式要稍加留意,否則容易吃下 WA。

By David.K

p10062題目連結
回ACM題庫目錄
回首頁

Problem 10079 Pizza Cutting,Pizza 切割

此題問你一個 pizze 在切割了 n 刀之後,最多能切割成幾塊。

可以找出一個公式符合這個題目的算法:
f(0) = 1,當 n > 1時,f(n) = n + f(n - 1)
可以推導公式,f(n) = n + (n - 1) + f(n - 2);
f(n) = n + (n - 1) + (n - 2) + ...
... + 1 + f(0)
所以,f(n) = n * (n + 1) / 2 + 1

(注意:答案要以 long long int 型態來接收。)

By David.K

p10079題目連結
回ACM題庫目錄
回首頁

Problem 10041 Vito's Family

此題需將 n 個數由小到大排列後,找出索引為 n / 2 的值,就是中間數 mid,再將這中間數去與所有其他的數相減曲絕對值,累加起來的值為解。關鍵 C 語言程式碼如下:
mid = doorplate[n / 2];
for (i = 0; i < n; i ++)
{
total += abs(mid - doorplate[i]);
}
printf("%d\n", total);
其中 doorplate 陣列為排序好的數列。

By David.K

p10041題目連結
回ACM題庫目錄
回首頁

2010年4月23日 星期五

Problem 10189 Minesweeper,踩地雷

此題一看就知道這是踩地雷的遊戲,「*」是地雷,「.」則是待填數字,待填數字則是要填在這個格子的周圍,有幾個地雷。

只需建立一個字元陣列 char 並且讀取範圍還有內容,C 語言程式碼如下:
char field[102][102];
for (i = 0; i < n; i ++)
scanf("%s", field[i]);

再來判斷每一個「.」周圍有幾顆地雷,最後印出。C 語言程式碼如下:
for (i = 0; i < n; i ++)
{
for (j = 0; j < m; j ++)
{
if (field[i][j] == '*') continue;
else
{
int count = 0;
/* 上方 */
if (i != 0 && field[i - 1][j] == '*') count ++;
/* 下方 */
if (i != n - 1 && field[i + 1][j] == '*') count ++;
/* 左方 */
if (j != 0 && field[i][j - 1] == '*') count ++;
/* 右方 */
if (j != m - 1 && field[i][j + 1] == '*') count ++;
/* 左上 */
if (i != 0 && j != 0 && field[i - 1][j - 1] == '*') count ++;
/* 右上 */
if (i != 0 && j != m - 1 && field[i - 1][j + 1] == '*') count ++;
/* 左下 */
if (i != n - 1 && j != 0 && field[i + 1][j - 1] == '*') count ++;
/* 右下 */
if (i != n - 1 && j != m - 1 && field[i + 1][j + 1] == '*') count ++;
field[i][j] = count + '0';
}
}
}
printf("Field #%d:\n", caseNum ++);
for (i = 0; i < n; i ++)
printf("%s\n", field[i]);

By David.K

p10189題目連結
回ACM題庫目錄
回首頁

Problem 10008 What's Cryptanalysis?

此題就是將所有出現過的字母轉換成大寫紀錄它出現的次數以及將它排序(先比次數、再比字母大小)。

首先建一個結構(struct)並且創建陣列 w,內容有一 char 紀錄字母和一 int 紀錄字母出現次數。寫一個 check(char ch) 函式檢查字母是否出現在結構陣列 w 內。寫一 insert(char ch) 函式使用 check(char ch) 檢查後,如果有出現此字母,就累加並且將此字母的出現次數與前面的字母比較,若相等,則比字母大小;如果沒有出現,則加入,並且與前面的比較字母大小。C 語言程式碼如下:
struct Word
{
char ch;
int count;
};

struct Word w[26], c;
int index = 0, repeatIndex ;

int check(char ch)
{
for (repeatIndex = 0; repeatIndex < index; repeatIndex ++)
{
if (w[repeatIndex].ch == ch)
return 0;
}
return 1;
}

void insert(char ch)
{
int i;
if (check(ch))
{
w[index].count = 1, w[index].ch = ch;
index ++;
for (i = index - 1; i >= 1; i --)
if (w[i].ch < w[i - 1].ch && w[i].count >= w[i - 1].count)
c = w[i], w[i] = w[i - 1], w[i - 1] = c;
else break;
}
else
{
w[repeatIndex].count ++;
for (i = repeatIndex; i >= 1; i --)
if (w[i].count > w[i - 1].count ||
w[i].count == w[i - 1].count && w[i].ch < w[i - 1].ch)
c = w[i], w[i] = w[i - 1], w[i - 1] = c;
else break;
}
}

最後再將每個字母傳入 insert(char ch) 就可以了。主程式 C 語言程式碼如下:
int n, i, lineCount = 0;
char ch;
scanf("%d", &n);
getchar();
while (1)
{
ch = getchar();
if (isalpha(ch))
{
ch = toupper(ch);
insert(ch);
}
/* printf("%c", ch); */
if (ch == '\n')
{
lineCount ++;
if (lineCount == n)
{
print();
break;
}
}
}

最後別忘記要印出。

By David.K

p10008題目連結
回ACM題庫目錄
回首頁

2010年4月21日 星期三

Problem 10905 Children's Game,最大的數字排序

這題就是給你多個數值,將這些數值排序成最大的數。

這題最大的關鍵就是數值的比較,首先,舉兩個例子:9898989、 98 怎麼比較誰大誰小? 234、 2345 怎麼比較誰大誰小? 重點在於讓它化成類似循環小數,再去比較誰大誰小。做法如下:
98      →  98989898989898
9898989 → 98989899898989
---------------------------

此處可以看出 9898989 較大。

再來,是 234、 2345 的例子:
234 → 23423423
2341 → 23412341
---------------------------

此處可以看出 234 較大。

所以,寫一函式比較兩個字串的大小,順便找出兩字串長度的最小公倍數,這是兩字串比較的最大次數,若比到最小公倍數的次數還比較不出大小,這就代表兩字串相等。函式的 C 語言程式碼如下:
int gcd(int x, int y) {
int tmp;

while (x % y != 0) {
tmp = y;
y = x % y;
x = tmp;
}
return y;
}

int lcm(int x, int y) {
return x * y / gcd(x,y);
}


int numcmp(char c1[], char c2[])
{
int c1len = strlen(c1);
int c2len = strlen(c2);
int c1Index = 0, c2Index = 0;
int count = 0, maxCount = lcm(c1len, c2len);
while (count != maxCount)
{
if (c1Index == c1len) c1Index -= c1len;
if (c2Index == c2len) c2Index -= c2len;
if (c1[c1Index] - '0' < c2[c2Index] - '0') return 0;
if (c1[c1Index] - '0' > c2[c2Index] - '0') return 1;
c1Index ++, c2Index ++, count ++;
}
return 0;
}

最後,只需將每個字串加入一個結構陣列,並且排序,最後印出就可以了。C 語言程式碼如下:
struct num
{
char num[90];
};
struct num allNum[50];
int index;

主程式內...
index = 0;
for (i = 0; i < n; i ++)
{
scanf("%s", allNum[index ++].num);
for (j = index - 1; j >= 1; j --)
if (numcmp(allNum[j].num, allNum[j - 1].num))
{
strcpy(a.num, allNum[j].num);
strcpy(allNum[j].num, allNum[j - 1].num);
strcpy(allNum[j - 1].num, a.num);
}
else
break;
}
for (i = 0; i < index; i ++)
printf("%s", allNum[i].num);
printf("\n");
...

By David.K

p10905題目連結
回ACM題庫目錄
回首頁

Problem 10970 Big Chocolate,穆罕默德的懶惰

Mohammad 買了一個 M * N 長度的巧克力,問說他最少要「折」幾次巧克力才能將全部分開。

此題答案為:M * N - 1。

By David.K

p10970題目連結
回ACM題庫目錄
回首頁

2010年4月19日 星期一

Problem 11462 Age Sorts,累計排序

題目要求你記錄每一個人的年紀,最後要輸出它們的排序,而文中也順道規定它的數值範圍,「no individual in that country lives for 100 or more years.」,也就是說,年齡的範圍為:0 < y < 100。而排序的數量 n 的範圍為:0 < n <= 2000000。

如果還想用 bubleSort 排序那就是找吃 TLE,題目已經說明數值小、數量大,所以可以找到一種 Counting Sort (累計排序) 的方法來排序,老老實實用 Counting Sort 做它,約略會在 0.473 的時間上下。Counting Sort 就是假設我輸入 1 3 2 5 4,而我要有一個 100 索引的整數陣列 data,若每輸入一個整數 i,就將 data[i] ++;,最後陣列會變成 data[0] = 0、data[1] = 1、data[2] = 1、data[3] = 1、data[4] = 1、data[5] = 1、data[6] = 0、...、data[99] = 0。最後再用「類似」以下做法印出:
int isFirst = 0;
for (i = 1; i < 100; i ++)
for (; data[i]; data[i] --)
if (isFirst) printf(" %d", i);
else printf("%d", i), isFirst = 1;

當我第一次這樣做完這一題,0.460 AC 後,覺得要再縮短時間,所以到論壇上看看有沒有別的方法,想不到也有人也想縮短時間的方法,結果 neilor 網友有一些對這一題做法的時間排序:
原網址連結
Método Execution time
bubleSort TLE (> 5 seconds)
Qsort Stl with cin / cout 1.072
Quicksort with scanf / printf 0.786 secs (maybe not so good qsort!?)
Mergesort with scanf / printf 0.656 secs (with a best mergesort)
qsort Stl [ sort(age,age + tam); ] 0.596 secs
Counting Sort (with vector) 0.473 secs (18 º world time)
Counting Sort (without vector) 0.456 secs
Counting Sort with fast input 0.343 seconds (13 º )
Counting Sort with fread/fwrite 0.204 seconds (10 º )
Counting Sort fread/fwrite optimized 0.156 (8º)
Counting Sort fread optimized /fwrite optimized 0.052 (2º) same that 1º mundial place.

最棒的方法是用優化輸入,和優化輸出 ( 這部分就要請大家去找這些方法的資料了,在此就不提供程式碼,如果想知道就再問我吧! ),能使時間降到 0.1 秒以下,最後我改用了最後一個做法,結果我最好的時間是 0.056 秒,目前排名第 4,但想不到 pcy 同學才花 0.036 秒,真太拜服了。

By David.K

p11462題目連結
回ACM題庫目錄
回首頁

2010年4月18日 星期日

Problem 11455 Behold my quadrangle,判斷形狀

題目開宗明義說了:「任何正方形是一個矩形,任何長方形是一個四邊形,任何四邊形是由四個邊所構成的。但是不是所有矩形一定是正方形,不是所有四邊形一定是長方形,不是所有四個邊所構出來的一定是四邊形」。

題目給你四個邊長,請你判斷它可能會構成甚麼形狀,有"square"(正方形)、 "rectangle"(矩形), "quadrangle"(四邊形) or "banana"(啥都不是)。

首先,讀入四邊長之後,就要排序,因為判斷起來會方便許多。若四邊等長,則為 square;若四邊兩兩等長,則為 rectangle;若四邊形三邊加起來大於最大的邊,則為 quadrangle;剩下的,都是香蕉 (banana)。寫成 C 語言程式碼如下:
index = 0;  
for (i = 0; i < 4; i ++)
{
scanf("%d", &len[index ++]);
for (j = index - 1; j >= 1; j --)
if (len[j] < len[j - 1])
tmp = len[j], len[j] = len[j - 1], len[j - 1] = tmp;
else
break;
}
if (len[0] == len[3]) { printf("square\n"); continue; }
if (len[0] == len[1] && len[2] == len[3])
{ printf("rectangle\n"); continue; }
if (len[0] + len[1] + len[2] > len[3])
{ printf("quadrangle\n"); continue; }
printf("banana\n");

By David.K

p11455題目連結
回ACM題庫目錄
回首頁

Problem 11428 Cubes,立方相減

須求出兩立方相減小於 10000 的數,找出最大不過 583 - 573 = 9919,若 593 - 583 = 10267 就會超過,所以先找出 0 ~ 58 的立方,再用巢狀迴圈去找出每一個相減的結果,並且設置一個結構記錄這些結果,寫成 C 語言程式碼如下:
struct solution
{
int i;
int j;
int sol;
};
struct solution s[10001];
int pow3[59];

void create()
{
int i, j;
for (i = 0; i < 59; i ++)
pow3[i] = i * i * i;
for (i = 58; i >= 0; i --)
for (j = 0; j <= i; j ++)
{
int tmp = pow3[i] - pow3[j];
if (tmp <= 10000)
{
s[tmp].sol = 1;
s[tmp].i = i;
s[tmp].j = j;
}
}
}

最後一樣對應索引印出結果:
if (s[n].sol)
printf("%d %d\n", s[n].i, s[n].j);
else
printf("No solution\n");

By David.K

p11428題目連結
回ACM題庫目錄
回首頁

Problem 11401 Triangle Counting,木棍組合總和

給你 1、2、...、n 個長度的木棍,要你去組合它們成為不同的三角形,將這些組成三角形的總和起來,就是答案。

例如: n = 6,利用「任意兩邊之和等於或小於第三邊而不能構成三角形」的概念,所以有 234、245、256、345、346、356、456 共 7 種組合。

其實這也不需要傷腦筋去算出來,因為論壇上已有公式了。f(3) = 0,f(4) = 1,當i > 4 時,f(i) = f(i - 1) + j, j = i * (i-1) - (i+1) * (i-b) - b * (b-1),其中 b = i / 2 + 1。這裡還是提供 C 語言程式碼給大家參考:
unsigned long long int ans[1000001];

void create()
{
int i;
unsigned long long int s, b, now;
ans[3] = 0;
ans[4] = 1;
for (i = 5; i < 1000001; i ++)
{
s = i;
b = i / 2 + 1;
now = s*(s-1)-(s+1)*(s-b)-b*(b-1);
ans[i] = ans[i - 1] + now;
}
}

函式建構出來後,只需再主程式裡面針對索引印出答案就可以了。

By David.K

p11401題目連結
回ACM題庫目錄
回首頁

Problem 11498 Division of Nlogonia,方位

此題只要給你一個座標 N 與 M,有 K 筆問題,問題各有一個座標 X 與 Y,求出 X 與 Y 在 N 與 M 的哪一個方向。
首先我給座標定義成如上圖,在設計一個陣列儲存這些答案:
char ans[5][8] = {"NE", "SE", "NO", "SO", "divisa"};

最後,只需依照題目給的座標去判斷就可以了,C 語言程式碼如下:
scanf("%d %d", &N, &M);
while (K --)
{
site = 0;
scanf("%d %d", &X, &Y);
if (N == X || M == Y) { printf("%s\n", ans[4]); continue; }
if (X < N) site += 2;
if (Y < M) site += 1;
printf("%s\n", ans[site]);
}

By David.K

p11498題目連結
回ACM題庫目錄
回首頁

2010年4月17日 星期六

Problem 11520 Fill the Square

此題要用英文填滿正方形方塊,鄰近英文字不能相同。

輸入測試資料次數後,讀入一個整數 n,是正方形的邊長。再接下來有 n 行 n 個字元要讀入,包含 '.' 或 'A' ~ 'Z',如果為 '.',則是你要填入的地方;如果為 'A' ~ 'Z',則是固定字元,而輸出也必須一樣。最後你要輸出整個方塊在「鄰近字元不能相同」的情況下,輸出一 n * n 英文正方形。

例如:
A.B.
.C.D
E.F.
.G.H
要輸出:
ADBA
BCAD
EAFA
AGAH

首先,可以建立一個二維陣列,以及讀入字元的方法,C 語言程式碼如下:
scanf("%d", &n);
for (i = 0; i < n; i ++)
scanf("%s", square[i]);
printf("Case %d:\n", t);

一開始我本來用 scanf("%c", &square[i][j]); 讀入字元,但發現他連換行都吃,所以我改用字串的方式讀取。接下來可以寫一 isSame(int row, int col, char ch) 函式,測試 ch 字元在 row 和 col 位置是否會與鄰近位置字元相同,如果相同,回傳 0;反之,回傳 1。 C 語言程式碼如下:
int isSame(int row, int col, char ch)
{
if (row != 0)
{
if (ch == square[row - 1][col])
return 0;
}
if (row != n)
{
if (ch == square[row + 1][col])
return 0;
}
if (col != 0)
{
if (ch == square[row][col - 1])
return 0;
}
if (col != n)
{
if (ch == square[row][col + 1])
return 0;
}
return 1;
}

最後只需利用 isSame 函式將每一個位置都傳入測試字元 ch 判斷(ch 初設為 'A'),如果沒有與鄰近重複,就填入字元;如果有與鄰近重複,ch 累加 1( ch + 1 等於 'B'),轉移為一下個字元判斷。C 語言程式碼如下:
for (i = 0; i < n; i ++, printf("\n"))
for (j = 0; j < n; j ++)
{
if (square[i][j] != '.')
{
printf("%c", square[i][j]);
continue;
}
else
{
for (k = 0; k < 26; k ++)
if (isSame(i, j, ch + k))
{
printf("%c", ch + k);
square[i][j] = ch + k;
break;
}
}
}

By David.K

p11520題目連結
回ACM題庫目錄
回首頁

Problem 11586 Train Tracks,火車鐵軌

Andy 非常喜歡玩火車鐵軌積木的鋪設遊戲,他發現火車鐵軌有兩種接頭,一個是 male 接頭,一個是 female 接頭,如以下圖:

而當只有一個 male 接頭和一個 female 接頭是接不起來的,因為這兩個接頭在同一個鐵軌上,除非你把它折斷,才有可能。但有兩個 male 接頭和 female 接頭就接的起來。

看出重點了嗎 ? 只要是有兩個以上的 male 接頭和 female 接頭,而且數量相等,就會照成循環,但只要是一個就不行。所以寫成 C 語言程式碼如下:
gets(str);
M = 0, F = 0;
for (i = 0; str[i]; i ++)
{
if (str[i] == 'M') M ++;
if (str[i] == 'F') F ++;
}
if (M == F && M != 1 && F != 1) printf("LOOP\n");
else printf("NO LOOP\n");

By David.K

p11586題目連結
回ACM題庫目錄
回首頁

Problem 11526 H(n)

本來我以為這題會很難,因為老老實實的用暴力法做絕對超過時間,而且它也說它會拿 1000 個測試資料來嚇人,所以不能用暴力法。所以我上論壇看了一下,才知道解法,我引用一下:
原網址連結
「for n = 10; go along the similar way:

lets say n = 10;
k = 1; sum = 0;
so, 10/1 = 10

k = 2
and 10/2 = 5
so, for all the integer divisions, all i = 6 to 10
will produce n/i = 1; (last denominator)
so, you don't need to calculate for 6 to 10, you have
5x1 + 10/1 = 15; (for k = 1) sum = 15;

k = 3
again 10/3 = 3
so, for all the integer divisions, all i = 4 to 5
will produce n/i = 2; (last denominator)
so, you don't need to calculate for 4 to 5, you have
2x2 + 10/2 = 9; (for k = 2) sum = sum + 9 = 24;

as k is the largest within sqrt(10);
so last we count for k = 3; for 3, one thing here to
note that, 10/3 is also 3,
so, in such cases, we have to consider once, cause
otherwise it will be counted twice.
so, sum = sum + 3 = 27(ans)

for 10, we have the values (imagine RED is not yet
counted, and GREEN is already counted, and BLUE is
the current term)
k = 1; (10) + 5 + 3 + 2 + 2 + (1 + 1 + 1 + 1 + 1)
k = 2; 10 + (5) + 3 + (2 + 2) + 1 + 1 + 1 + 1 + 1
k = 3; 10 + 5 + (3) + 2 + 2 + 1 + 1 + 1 + 1 + 1;
so you see, 3 is to be counted once as it
has no separate counterpart.
if k==n/k then you need to count once;」

依據以上解說,相信非常的清楚,所以寫成 C 語言成式如下:
scanf("%ld", &n);
Hn = 0;
sqrtN = (int)sqrt(n);
for (i = 1; i <= sqrtN; i ++)
{
count = (n/i) - (n/(i + 1));
if (i == n / i) Hn += (n / i);
else Hn += i * count + (n / i);
}
printf("%ld\n", Hn);
By David.K

p11526題目連結
回ACM題庫目錄
回首頁

Problem 11538 Chess Queen,皇后互吃的擺法總和

給你 M * N 格棋盤大小,試問擺兩隻西洋棋的皇后,讓他們互相攻擊的擺法,總共有幾種。

這題在 ACM 解法提示 - 11538 有詳細解說以及公式。

公式為:m * (m - 1) * n + n * (n - 1) * m + (n * (n - 1) * (2 * n - 1) / 6 - (n - 1) * n / 2) * 4 + 2 * n * (n - 1) * (m - n + 1)。

注意: 要用 unsigned long long int 型態接收答案,不然會超出範圍。還有,若 M < N,要將兩值交換。

By David.K

p11538題目連結
回ACM題庫目錄
回首頁

Problem 11541 Decoding,解碼

此題要將一個字串解碼成原本的字串,這字串之中,是一個字元 ch 與一個整數 n 相間,而這個整數 n 代表這一個字元 ch 要印出 n 次,也就是說,例如 A5B6 就要印出 AAAAABBBBBB。

首先我的方法就是用 ctype 內判斷字元的 isalpha() 函式依字串順序判斷它是不是字元,如果是則記錄;如果不是字元,則為整數,但這整數有長有短,所以要用 count = count * 10 + str[i] - '0'; 來累加。字有了,整數也有了,就將這次的結果印出,依此類推,就可以印出正確答案。 C 語言程式碼如下:
printf("Case %d: ", i);
scanf("%s", str);
for (j = 0; str[j]; j ++)
{
if (isalpha(str[j])) ch = str[j], isPut = 1, count = 0;
else if (isPut && isdigit(str[j]))
count = count * 10 + str[j] - '0';
if (isPut && str[j + 1] == '\0' || !isdigit(str[j + 1]) && count > 0)
{
while (count --)
printf("%c", ch);
isPut = 0;
}
}
printf("\n");

By David.K

p11541題目連結
回ACM題庫目錄
回首頁

Problem 11547 Automatic Answer,簡單 AC 題

在 UVa Online Judge 上這種題目實在不多,因為他在 Output 上清清楚楚的把答案跟你說了,只差沒把程式碼打給你,算是營養題啦!
Multiply n by 567, then divide the result by 9, then add 7492, then multiply by 235, then divide by 47, then subtract 498. What is the digit in the tens column?

公式為: ( (n * 567) / 9 + 7492 ) * 235 ) / 47 - 498 => (n * 63 + 7492 ) * 5 - 498

注意小於 0 的數要乘以 -1。

這一題真是污辱智商 = =|||
By David.K

p11547題目連結
回ACM題庫目錄
回首頁

2010年4月16日 星期五

如何學好C語言─張毓庭

這篇文章是目前就讀實踐大學高雄校區資管系的同學的學習心得與建議,學C語言經過一些努力,必有所成,這位同學已成為程式能手,讀完這篇,預祝所有C語言初學者能有所體會。
liangk
----------------------------------------------
程式設計學到現在,哈哈~其實我也不知道我為什麼會寫程式,我只要覺得把那一些程式語言變成自己看得懂、會用的方式表達出來。
剛開始我沒有一下就懂,因為我不是天才,哈哈~我也是一點一滴慢慢地累積,而我個人比較不喜歡看文字啦!我比較喜歡看一些範例,然後慢慢地從範例中了解每一行所表達的意思,把每一種表達方式背起來,然後慢慢的運用,運用久了馬上就變成你自己的啦!

而寫程式其實就是用數學式子簡單計算表達出來,而剛開始其實我有一點不習慣為什麼要這樣用,而在反覆地練習下和課堂上老師的講解,我從中也慢慢地瞭解程式設計。
而剛開始一定都會很受挫,常常不知道要怎麼表達,這時候「問助教」就一個很好的方法啦(助教好辛苦唷)!可以快速的回答你要的問題,不用在那一些厚厚的書上尋找一個小小的問題,然後把自己搞的很煩燥。

假如你在書桌前花一個小時找一個小問題的話,我想你還是問助教最好了(哈哈~助教一定覺得你很認真),如果你花一個小時還沒找到你要找的答案,因為我想你也會很煩很想罵髒話,然後對程式就失去信心(學習程設當成一種興趣),所以你還是多多地問問題吧!

而當你自己成功的解決問題時,就會很有成就感,然後你就會把它當成一種挑戰,慢慢一題一題的解,我想你應該界會成為程式高手啦!
而到了你會寫程設的時候,你就要漸漸地去看一些書,因為老師在課堂上講的有限,在課堂上兩個小時,真的講的有限啦!

資一甲,張毓庭

Problem 11530 SMS Typing,按下的次數

現在有一手機的按鈕如下表:
---------------------
| | abc | def |
---------------------
| ghi | jkl | mno |
---------------------
| pqrs | tuv | wxyz |
---------------------
| | sp | |
---------------------

接著給你一段簡訊內容,問你需要按鍵需要按幾次。例如 akfz,需要按下 10 次按鍵方能打出這四個字,因為 a 排在第 1 個、k 排在第 2 個、f 排在第 3 個、z 排在第 4 個,所以 1 + 2 + 3 + 4 = 10,因此 10 次。
首先建立一個陣列 keyNum,是對應打入的字轉換整數以累加,再用一 Counter 函式來實作, C 語言程式碼如下:
int keyNum[26] = {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,
3,4,1,2,3,1,2,3,4};
int count;
char str[101];
void Counter(char ch)
{
if (ch == ' ') count ++;
count += keyNum[ch - 'a'];
}

最後主程式只需 gets() 字串,再一個一個傳入 Counter 函式,最後印出就好,C 語言程式碼如下:
for (j = 1; j <= n; j ++)
{
gets(str);
count = 0;
for (i = 0; str[i]; i ++)
Counter(str[i]);
printf("Case #%d: %d\n",j , count);
}

By David.K

p11530題目連結
回ACM題庫目錄
回首頁

2010年4月15日 星期四

Problem 11677 Alarm Clock,時間的差距

算出兩個以四個整數表示的時間,它們差距分鐘數為何。

假設開始時間大於結束時間,需將結束時間的時數加上 24 再去做相減就可以了。 C 語言程式碼如下:
if (H1 == 0 && H2 == 0 && M1 == 0 && M2 == 0) break;
if (H1 == H2 && M1 > M2 || H1 > H2) H2 += 24;
totalM = (M2 >= M1? (M2 - M1) + (H2 - H1) * 60:
(60-M1+M2) + (H2 - H1 - 1) * 60);
printf("%d\n", totalM);

By David.K

p11677題目連結
回ACM題庫目錄
回首頁

Problem 11636 Hello World!,複製貼上

此題是說目前有一行 printf("Hello World!") 的程式碼,但我們需要有 n 行,需複製貼上幾次。

因為行數是以 2 倍在成長的,所以這題是在問說 n 在 2m-1 < n <= 2m 之間,求 m 為多少,其實用 log() 做就可以了,再用 ceil (無條件進位)就可以了, C 語言程式碼如下:
if (n != 1) printf("Case %d: %d\n", ++ j, 
(int)ceil(log((double)n)/log(2)));
else printf("Case %d: 0\n", ++ j) ;

By David.K

p11636題目連結
回ACM題庫目錄
回首頁

B98012: 小考八:倉庫庫存(解答)

進入到程式,一開始先判斷他是in或不是in

假如是in就把 後面的木材數輸入進儲列


string[] value = line.Split(' ');
if (value[0] == "in")
{
int inbank = int.Parse(value[1]);
mybank.Push(inbank);
}

假如不是in則先把out所要取出的木材數先拿出

再使用forech加總儲列裡所有的木材數 最後印出答案 程式結束


else
{
cases++;
int outbank = int.Parse(value[0]);
int total = 0;
for (int i = 0; i < outbank; i++)
{
mybank.Pop();
}
foreach (int x in mybank)
{
total += x;
}
Console.WriteLine("#{0}: {1} left", cases, total);
}

By Alent



題目連結
回C#語言教學目錄
回首頁

B98012: 小考八:倉庫庫存

有一賣木板的商店,由於需求量過高,所以常常賣到缺貨,商店老闆非常的傷腦筋,所以想請你幫他寫一個程式讓他能知道他現在的庫存量還剩多少。因為木板進貨時都是一捆一捆的,所以進貨時或出貨時,皆以一捆數量來計算。值得注意的是,倉庫進貨出貨時是以先進後出的方式進行。

輸入以「in N」表示,N為一捆木板進貨的數量,0 < N < 100,而「M out」是將倉庫拿出 M 綑木板( 先前提到此倉庫是以後出方式進行出貨 )來販售,0 < M < 10。

輸出以「#i: t left」表示,i為此次出貨次數,t為庫存量。當倉庫出貨時,則需印出它的庫存量還剩多少塊木板,也就是說有幾個「M out」,就有幾個輸出。
Input:
in 3
in 5
in 4
in 8
2 out
in 3
in 10
1 out
Output:
#1: 8 left
#2: 11 left


By Alent



解答連結
回C#語言教學目錄
回首頁

Problem 11764 Jumping Mario,跳跳馬力歐

此題就是依序輸入牆的高度,看這馬力歐需要往上跳幾次,以及往下跳幾次。

只需紀錄上一次的高度以及這一次的高度,比較後看是往上跳或是往下跳,將次數累加,最後印出。C 語言程式碼如下:
for (i = 1; i <= T; i ++)
{
low = 0, high = 0;
scanf("%d%d", &N, &record), N --;
while (N --)
{
scanf("%d", &num);
if (record > num) low ++;
if (record < num) high ++;
record = num;
}
printf("Case %d: %d %d\n", i, high, low);
}

By David.K

p11764題目連結
回ACM題庫目錄
回首頁

Problem 11689 Soda Surpler,Tim 撿空瓶

Tim 是一個愛喝蘇打酒的人,但他身上沒有太多的錢讓他買他愛喝的蘇打酒,每天靠著撿空的蘇打酒瓶去換取新的蘇打酒,以解他愛喝蘇打酒的癢。

輸入 e、f、r 三整數,e 代表 Tim 目前手上有幾瓶空瓶,f 代表 Tim 一天能發現多少空酒瓶,r 則是能以 r 瓶空酒瓶換取 1 瓶新的滿滿的蘇打酒。

此題跟 Problem 11150 非常相似,只是此題稍稍難了一咪咪,甚至一咪咪的一咪咪。首先只需將 e 值與 f 值相加才能算是他一天拿到空瓶的總和,接著再用 11150 的觀念,讓 e 降到 c 以下。C 語言程式碼下:
while (n --)
{
int total = 0, record;
scanf("%d %d %d", &e, &f, &c);
e += f;
for (; e > c;)
{
total += e / c;
record = e / c;
e = (e % c + record);
}
if (e == c) total ++;
printf("%d\n", total);
}

By David.K

p11689題目連結
回ACM題庫目錄
回首頁

2010年4月14日 星期三

C98009: 作業九:捷運售票機(解答)

設一個變數算到達時間剪掉上一次的完成時間,假如是第一個客人當然不用等

第二個以後假如算出來是負的代表這個顧客需要等待,

所以設個wait變數將算出來的數轉為正數,再將運算的變數歸0

最後完成就是時間要加10秒運作時間

將算出來的等待時間與完成時間輸入進儲列


int come = int.Parse(line);
comeTotal += come;
int comewait = comeTotal - finish ;
int wait = 0;
if (i == 0)
{
wait = 0;
i++;
}
if (comewait < 0)
{
wait = -comewait;
comewait = 0;
}
finish = finish + comewait + 10;
waitTime.Enqueue(wait);
finishTime.Enqueue(finish);

程式的最後將儲列裡的等待時間與完成時間取出列印即完成作業

int cases = 1;
foreach (int w in waitTime)
{
Console.WriteLine("#{0}: waited {1}, finished {2}",cases,w,finishTime.Dequeue());
cases++;
}

作業九題目
回C#語言教學目錄
回首頁

C98009: 作業九:捷運售票機

作業內容

若有一個捷運自動售票機的售票處理時間為固定10秒,但是購票乘客抵達時間不固定,若自動售票機在有人使用的情形下,乘客必須先行排隊等待。(假設只有一部售票機) 乘客抵達時間為相隔時間,在輸入乘客抵達時間後,請輸出每個乘客的等待時間與完成時間。

程式基本要求:使用Queue類別。
輸出入格式

輸入的每一行為乘客抵達的間隔時間t,n<10000,第一個乘客抵達的時間,為t1-0;第二個乘客抵達的時間,為t2-t1,第三個乘客抵達的時間,為t3-t2;以此類推。輸入結束,則測試結束。

輸出格式為「#i: waited x, finished y」,i為第i個輸入的乘客。 x為等待時間,y為離開時間。
範例

Input:
5
12
16
8
6
10
13
Output:
#1: waited 0, finished 15
#2: waited 0, finished 27
#3: waited 0, finished 43
#4: waited 2, finished 53
#5: waited 6, finished 63
#6: waited 6, finished 73
#7: waited 3, finished 83

解答連結
回C#語言教學目錄
回首頁

Problem 11743 Credit Check,信用卡的 ID

此題是要用它給的方法去檢查信用卡的 ID 是否有效。

使用 gets() 讀入字串後,直接將字串索引 0、2、5、7、10、12、15、17 的每個字元轉換整數乘上 2,再將這些數的每個數字相加。接著將字串索引 1、3、6、8、11、13、16、18 的每個字元轉換整數相加。最後使上兩數相加,mod 10 後等於 0 為有效,其餘無效。寫成 C 語言程式碼如下:
while ( caseNum --)
{
gets(str);
total = ((str[0] - '0') * 2) % 10 + (str[0] - '0') * 2 / 10 +
((str[2] - '0') * 2) % 10 + (str[2] - '0') * 2 / 10 +
((str[5] - '0') * 2) % 10 + (str[5] - '0') * 2 / 10 +
((str[7] - '0') * 2) % 10 + (str[7] - '0') * 2 / 10 +
((str[10] - '0') * 2) % 10 + (str[10] - '0') * 2 / 10 +
((str[12] - '0') * 2) % 10 + (str[12] - '0') * 2 / 10 +
((str[15] - '0') * 2) % 10 + (str[15] - '0') * 2 / 10 +
((str[17] - '0') * 2) % 10 + (str[17] - '0') * 2 / 10 +
(str[1] - '0') + (str[3] - '0') + (str[6] - '0') +
(str[8] - '0') + (str[11] - '0') + (str[13] - '0') +
(str[16] - '0') + (str[18] - '0');
if (total % 10 == 0) printf("Valid\n");
else printf("Invalid\n");
}

By David.K

p11743題目連結
回ACM題庫目錄
回首頁

Problem 11727 Cost Cutting,中間的數

此題為簡單題,只需將輸入的 3 個數的中間那個數印出就可以了。在此就不提供程式碼。

By David.K

p11727題目連結
回ACM題庫目錄
回首頁

Problem 10921 Find the Telephone

輸入一串字串,再將這串字串用以下表格,轉換成對應後的電話號碼。
LettersNumber
ABC2
DEF3
GHI4
JKL5
MNO6
PQRS7
TUV8
WXYZ9

例如: ABC-DJKOOPLH 需輸出 222-35566754。

然而只需用 gets() 讀入字串,再用迴圈將字元一個一個傳入函式轉換 (或許你能有更好的方法) 印出即可, C 語言程式碼如下:
char charJudge(char ch)
{
if (ch == '0') return '0';
if (ch == '1') return '1';
if (ch >= 'A' && ch <= 'C') return '2';
if (ch >= 'D' && ch <= 'F') return '3';
if (ch >= 'G' && ch <= 'I') return '4';
if (ch >= 'J' && ch <= 'L') return '5';
if (ch >= 'M' && ch <= 'O') return '6';
if (ch >= 'P' && ch <= 'S') return '7';
if (ch >= 'T' && ch <= 'V') return '8';
if (ch >= 'W' && ch <= 'Z') return '9';
return ch;
}

By David.K

p10921題目連結
回ACM題庫目錄
回首頁

Problem 10931 Parity,2 進位的總和

此題是將一個十進位整數 n 轉換為二進位之後,將出現 1 的次數記錄下來,再以 「The parity of (n的二進位) is (n出現 1 的次數) (mod 2).」 印出即可。

首先把 21、22、...、231 找一個陣列來擺放, C 語言程式碼如下:
unsigned int binary[31], total;

void create()
{
int i, j = 1;
for (i = 0, j = 2; i < 31; i ++, j *= 2)
binary[i] = j;
}

再將所輸入的 n 值依序除下來,記錄 1 出現的次數後一起印出即可:
int isPut = 0;  
count = 0;
printf("The parity of ");
for (i = 30; i >= 0; i --)
{
if (isPut || n / binary[i] == 1)
printf("%d", n / binary[i]), isPut = 1;
if (n / binary[i] == 1) count ++ ;
n %= binary[i];
}
if (isPut) printf("%d", n);
if (n == 1) count ++;
printf(" is %d (mod 2).\n", count);

By David.K

p10931題目連結
回ACM題庫目錄
回首頁

2010年4月10日 星期六

Problem10392 Factoring Large Numbers,因數分解

Problem 10392 是一題將 long long int 長整數型態的數做因數分解的題目。

此題要將 30980 之內的質數找出來就夠用了,如果數大於 30980,再用這些質數的次方看找不找的到。以下是找質數 makeprime() 以及 isprime(long long int n) 判斷質數的函式,C 語言程式碼如下:
int makeprime(){
int i, j;

for(i = 3; i <= MAXSIZE; i += 2)
if(!prime[i]){
for(j = i + i; j <= MAXSIZE; j += i)
prime[j]=1;
prime_table[prime_table_len ++]=i;
}
}

int isprime(long long int n){
int i,temp;
if(n == 2) return 0;
if(n % 2 == 0) return 2;
if(n <= MAXSIZE){
if ((1-prime[n]))
return 0;
}

for(i = 0;i != prime_table_len && prime_table[i] * prime_table[i] <= n; ++ i)
if(n % prime_table[i] == 0)
return prime_table[i];
return 0;
}

再來用一遞迴函式將傳入的值印出因數,C 語言程式碼如下:
void printFactors(long long int n)
{
long long int i;
if (n != 1 && n != 0)
i = isprime(n);
else return;
if(i)
printf("%s%lld\n", " ", i), printFactors(n/i);
if (!i && n != 1) printf("%s%lld\n", " ",n);
return;
}

最後,主程式只須這樣呼叫:
makeprime();
long long int n, i;
while (1)
{
scanf("%lld", &n);
if (n < 0) break;
printFactors(n);
printf("\n");
}

By David.K

p10392題目連結
回ACM題庫目錄
回首頁

作業八:機器人駕駛(解答)

宣告一個迴圈,同時做讀取機器人走的方位與步數以及將字串拆解成陣列的動作,C#語言程式碼如下

for (i = 0; i < cases; i++)
{
int m = int.Parse(Console.ReadLine());
for (j = 0; j < m; j++)
{
string instruct = Console.ReadLine();
string[] value = instruct.Split(' ');
qus.Blue[i].MoveTo(value[0], value[1]);
qus.Red[i].MoveTo(value[2], value[3]);
}
}

計算方位與距離

double pointView = Math.Atan((qus.Blue[i].y - qus.Red[i].y) /
(qus.Blue[i].x - qus.Red[i].x)) * 180 / Math.PI;
double distance = Math.Sqrt((qus.Blue[i].x - qus.Red[i].x) * (qus.Blue[i].x - qus.Red[i].x) +
(qus.Blue[i].y - qus.Red[i].y) * (qus.Blue[i].y - qus.Red[i].y));

最後判斷以一點為中心另一點是在哪個象限再決定是要加90&270或者減90&270

if ((qus.Red[i].x - qus.Blue[i].x) >= 0 && (qus.Red[i].y - qus.Blue[i].y) >= 0)
{
Console.Write("Blue: {0:f3}, {1} Red: {2:f3}, {3}", distance, Math.Round(90 - pointView), distance, Math.Round(270 - pointView));
}
if ((qus.Red[i].x - qus.Blue[i].x) >= 0 && (qus.Red[i].y - qus.Blue[i].y) <= 0) { Console.Write("Blue: {0:f3}, {1} Red: {2:f3}, {3}", distance, Math.Round(90 - pointView), distance, Math.Round(270 - pointView)); } if ((qus.Red[i].x - qus.Blue[i].x) <= 0 && (qus.Red[i].y - qus.Blue[i].y) >= 0)
{
Console.Write("Blue: {0:f3}, {1} Red: {2:f3}, {3}", distance, Math.Round(270 - pointView), distance, Math.Round(90 - pointView));
}
if ((qus.Red[i].x - qus.Blue[i].x) <= 0 && (qus.Red[i].y - qus.Blue[i].y) <= 0) { Console.Write("Blue: {0:f3}, {1} Red: {2:f3}, {3}", distance, Math.Round(270 - pointView), distance, Math.Round(90 - pointView)); }
作業九題目
回C#語言教學目錄
回首頁

C98008: 作業八:機器人駕駛

作業內容

有紅、藍兩個機器人,在接獲一連串的移動指令後,必須能知道相互
之間的方位與距離。共有八種移動指令 E, W, S, N, NE, SE, SW,
NW,分別代表東、西、南、北、東北、東南、西南、西北八個方
向,指令中並包含行進的位移,前四個方位的位移為一個單位,後四
個方位位移的量為sqrt(2)的倍數。

程式基本內容要求如下:

1. 宣告一個Robot類別;
2. 宣告一個Point結構;
3. 建立一個非靜態方法MoveTo(),用來移動機器人;

輸出入格式

輸入的第一行為一個整數n,n<10,表示測試的題數,每個測試題的>

輸出格式為「 Blue: d, b1 Red: d b2」,d為紅藍機器人之間的距
離,精確度到小數點三位, b1為藍機器人看紅機器人的方位,b2為
紅機器人看藍機器人的方位,兩者皆用Math.Round()取整數。每兩個
測試題,中間有一個空行,最後一個測試題後面則無空行。連續兩個
測試題之間需空一行。下列範例結果如圖所顯示

範例

Input:
1
4
E 3 SW 2
N 2 NW 2
NW 1 N 5
NE 2 NW 2
Output:
Blue: 10.198, 281 Red: 10.198, 101

解答連結
回C#語言教學目錄
回首頁

C#語言教學目錄

Problem 10393 The One-Handed Typist,能打的單字

吉米手指受傷了,但他為了向老闆證明他可以打長單字( 因為老闆認為長的單字會使人看起來更聰明 ),現在有一列字串可以添加到老闆的文件,使老闆覺得他更聰明,你必需要幫他找出他「可以打」以及「最長」的字,如果「最長」的字有很多,依照字母大到小排列。

首先宣告幾個結構( struct )以及結構陣列還有函式來開啟或關閉吉米能打的字,C 語言程式碼如下:
struct finger
{
char word;
int fId;
int isUse;
};

struct string
{
char str[51];
};

struct string s, sArray[1000];
struct finger f[32];
int index, maxLen;

void creat()
{
f[0].word = 'a', f[0].fId = 1, f[1].word = 'b', f[1].fId = 4;
f[2].word = 'c', f[2].fId = 3, f[3].word = 'd', f[3].fId = 3;
f[4].word = 'e', f[4].fId = 3, f[5].word = 'f', f[5].fId = 4;
f[6].word = 'g', f[6].fId = 4, f[7].word = 'h', f[7].fId = 7;
f[8].word = 'i', f[8].fId = 8, f[9].word = 'j', f[9].fId = 7;
f[10].word = 'k', f[10].fId = 8, f[11].word = 'l', f[11].fId = 9;
f[12].word = 'm', f[12].fId = 7, f[13].word = 'n', f[13].fId = 7;
f[14].word = 'o', f[14].fId = 9, f[15].word = 'p', f[15].fId = 10;
f[16].word = 'q', f[16].fId = 1, f[17].word = 'r', f[17].fId = 4;
f[18].word = 's', f[18].fId = 2, f[19].word = 't', f[19].fId = 4;
f[20].word = 'u', f[20].fId = 7, f[21].word = 'v', f[21].fId = 4;
f[22].word = 'w', f[22].fId = 2, f[23].word = 'x', f[23].fId = 2;
f[24].word = 'y', f[24].fId = 7, f[25].word = 'z', f[25].fId = 1;
f[26].word = ' ', f[26].fId = 5, f[27].word = ' ', f[27].fId = 6;
f[28].word = ',', f[28].fId = 8, f[29].word = '.', f[29].fId = 9;
f[30].word = ';', f[30].fId = 10, f[31].word = '/', f[31].fId = 10;
}

void allUseFinger()
{
int i;
for (i = 0; i < 32; i ++)
f[i].isUse = 1;
}

void notUseFinger(int n)
{
if (n == 1) { f[0].isUse = 0, f[16].isUse = 0, f[25].isUse = 0; return; }
if (n == 2) { f[18].isUse = 0, f[22].isUse = 0, f[23].isUse = 0; return; }
if (n == 3) { f[2].isUse = 0, f[3].isUse = 0, f[4].isUse = 0; return; }
if (n == 4)
{ f[1].isUse = 0, f[5].isUse = 0, f[6].isUse = 0, f[17].isUse = 0, f[19].isUse = 0, f[21].isUse = 0; return; }
if (n == 5) { f[26].isUse = 0; return; }
if (n == 6) { f[27].isUse = 0; return; }
if (n == 7)
{ f[7].isUse = 0, f[9].isUse = 0, f[12].isUse = 0, f[13].isUse = 0, f[20].isUse = 0, f[24].isUse = 0; return; }
if (n == 8) { f[8].isUse = 0, f[10].isUse = 0, f[28].isUse = 0; return; }
if (n == 9) { f[11].isUse = 0, f[14].isUse = 0, f[29].isUse = 0; return; }
if (n == 10) { f[15].isUse = 0, f[30].isUse = 0, f[31].isUse = 0; return; }
}

int isUseWord(char ch)
{
if (ch == ' ') return (f[25].isUse || f[26].isUse);
if (ch == ',') return f[28].isUse;
if (ch == '.') return f[29].isUse;
if (ch == ';') return f[30].isUse;
if (ch == '/') return f[31].isUse;
int n = ch - 'a';
return f[n].isUse;
}

在主程式只須這樣呼叫:
creat();
index = 0, maxLen = 0;
allUseFinger();
while (F --)
scanf("%d", &nUF), notUseFinger(nUF);

再來就是讀入一列的添加字串,每讀入一個就判斷吉米是否能打出這個字,以及字串的長度。如果可以打,就判斷它的長度是否大於目前的最大長度?大於,則將索引歸 0,最大長度改為此字串長度,再將此字加入陣列;等於,則加入此字到陣列內,順便排序比較;小於,則剔除。加入到陣列的函式 C 語言程式碼如下:
void insert()
{
int repeatIndex = 0, i;
for (i = 0; i < index ; i ++)
{
if (strcmp(s.str, sArray[i].str) == 0)
return;
}
struct string repeatS;
strcpy(sArray[index ++].str, s.str);
for (i = index - 1; i >= 1; i ++)
{
if (strcmp(sArray[i].str, sArray[i - 1].str) == -1)
{
strcpy(repeatS.str, sArray[i].str);
strcpy(sArray[i].str, sArray[i - 1].str);
strcpy(sArray[i - 1].str, repeatS.str);
}
else return;
}

return;
}

最後,主程式只須這樣呼叫:
while (N --)
{
scanf("%s", s.str);
isKey = 1;
len = strlen(s.str);
for (i = 0; s.str[i]; i ++)
{
if (!isUseWord(s.str[i]))
{
isKey = 0;
break;
}
}
if (isKey && maxLen < len) maxLen = len, index = 0;
if (isKey && maxLen == len) insert();
}
printf("%d\n", index);
for (i = 0; i < index; i ++)
printf("%s\n", sArray[i].str);

By David.K

p10393題目連結
回ACM題庫目錄
回首頁

Problem 10394 Twin Primes,孿生質數

此題是要找出 p 和 p+2 都是質數的對數,找出前 100000 對就行了,我算過,前 100000 對的孿生質數不超過 18409300。

我用的方法很粗糙,2.252 秒才 AC,依照之前找質數的方法,這裡就不多說了,直接提供 C 語言程式碼如下:
int isPrime[18409300] = {0};
int prime[100001][2] = {0};
int index = 0;
void creat()
{
int i, j;
for (i = 3; i < 18409300; i += 2)
{
if(!isPrime[i])
{
for (j = i + i; j < 18409300; j += i)
isPrime[j] = 1;
if (!isPrime[i - 2])
prime[index][0] = i - 2, prime[index ++][1] = i;
}
}
}

接著只須在主程式內直接印出即可。

By David.K

p10394題目連結
回ACM題庫目錄
回首頁

2010年4月9日 星期五

Problem 10450 World Cup Noise,世界盃的氣笛聲

Problem 10450 要用到費氏(Fibonacci)級數的概念。

此題與 Problrm 11069 雷同,只是此題的公式稍稍不同。
F1 = 1,F2 = 2;而 n > 2後,則為Fn-1 + Fn-2,例如:F3 = F2 + F1 = 3。

(註: 陣列需要宣告為 long long int 型態)

By David.K

10450題目連結
回ACM題庫目錄
回首頁

2010年4月8日 星期四

Problem 10465 Homer Simpson,吃漢堡

說明一下我解題的步驟 - ( n: 吃 Krusty 漢堡時間,m: 吃新漢堡時間,t:時間 )
1. 將數值調整:
if (m < n)
{
tmp = n;
n = m;
m = tmp;
}
2. 先將時間 t 都分配到時間少的漢堡,順便紀錄剩餘時間:
eatNum = t / n;
t %= n;
recordT = t;
3. 若有剩餘時間,則把時間試著累加 n,看看是否能整除 m,或者縮短剩餘時間,如果兩種情況發生一種,就把時間退還,再把這些時間分配到時間多的漢堡:
if (t)
{
for (i = 1; i <= eatNum; i ++)
{
if ((t + i*n) % m == 0)
{
t += i*n;
eatNum -= i;
break;
}
if ((t + i*n) % m < recordT)
{
recordI = i;
recordT = (t + i*n) % m;
}
}
if (recordI && t % m ) t += recordI * n, eatNum -= recordI;
eatNum += t / m;
t %= m;
}
4. 最後,印出、上傳、等 AC:
printf("%d", eatNum);
if (t) printf(" %d", t);
printf("\n");

By David.K

p10465題目連結
回ACM題庫目錄
回首頁

Problem 10474 Where is the Marble?,彈珠遊戲

某天 Raju 和 Meena 這兩個傢伙玩個彈珠遊戲,居然需要用寫程式來偷吃步,那不就是在寫「外掛」了嗎?

這題是要紀錄每個編號的彈珠出現的次數以及彈珠如以小排到大,某顆彈珠第一個出現的位置是多少。首先可以宣告一個整數陣列以索引紀錄彈珠編號出現的次數,C 語言程式碼如下:
if (N == 0 && Q == 0) return 0;
int marble[MAXLEN] = {0};
count = 1;
while (N --)
scanf("%d", &marbleNum), marble[marbleNum] ++;

再從 1 ~ 10000 將大於 0 的索引轉變成位置,C 語言程式碼如下:
for (i = 0; i < MAXLEN; i ++)
if (marble[i]) record = marble[i], marble[i] = count,
count += record;

最後,只須要把結果印出即可,如遇索引的值為 0,輸出「XX not found」;反之,則將輸出所引的值:
printf("CASE# %d:\n", caseNum ++);    
while (Q --)
{
scanf("%d", &marbleNum);
if (marble[marbleNum]) printf("%d found at %d\n",
marbleNum, marble[marbleNum]);
else printf("%d not found\n", marbleNum);
}

By David.K

p10474題目連結
回ACM題庫目錄
回首頁

Problem 10515 Powers Et Al,mn的個位數

本以為這題頗難的,但看了解題提示才發現是自己笨,因為它的個位數是循環的變動的。

開始可以創一個陣列,如同以下表格:
n/m0123456789
10123456789
20149656941
30187456329
40161656161
5 (與 1 重複)0123456789
.................................

也就是說 2 * 2,只須對應到 m = 2、n = 2 的數值 4,恰好就是 2 * 2 的個位數。所以寫成 C 語言程式碼如下:
int cycle[4][10] = { {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{0, 1, 4, 9, 6, 5, 6, 9, 4, 1},
{0, 1, 8, 7, 4, 5, 6, 3, 2, 9},
{0, 1, 6, 1, 6, 5, 6, 1, 6, 1}};
char m[102], n[102];
int mLen, nLen, mJudge, nJudge;
while (scanf("%s %s", m, n) == 2)
{
if (m[0] == '0' && n[0] == '0') break;
if (m[0] == '0' && m[1] == '\0') { printf("0\n"); continue; }
if (n[0] == '0' && n[1] == '\0') { printf("1\n"); continue; }
mLen = strlen(m), nLen = strlen(n);
printf("%d\n", cycle[( (n[nLen - 1] - '0') + ( nLen - 2 == -1 ? 0: n[nLen - 2] - '0' ) * 10 + 3) % 4 ][m[mLen - 1] - '0']);
}

By David.K

p10515題目連結
回ACM題庫目錄
回首頁

2010年4月7日 星期三

Problem 10533 Digit Primes,質數中的質數

此題是需要找出質數中每位數字相加後,還能等於質數的傢伙。可以想見,在條件 0 < t1 <= t2 < 1000000 之下,最大的數也不過是 999999,判斷質數的數字為 54(9 + 9 + 9 + 9 + 9 + 9),所以先建立一個質數表,只要輸入索引,立即可知此數是否為質數,C 語言程式碼如下:
int prime[55] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 
0, 1, 0, 1, 0, 0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 0, 0, 0, 0, 1,
0, 1, 0, 0, 0, 0, 0, 1, 0, 0,
0, 1, 0, 1, 0, 0, 0, 1, 0, 0,
0, 0, 0, 1, 0};

定義一個整數 s 為 0,再來找出 1 ~ 1000000 之間的質數,並且將這些質數分解後並利用以上質數表判斷是否為質數,如是,則改為 ++ s;反之,改為 s。寫成 C 語言程式碼如下:
#define MAXLEN 1000000
int digitPrime[MAXLEN] = {0};

int makeprime(){
int i, j, sum, n, s = 0;
for(i = 2;i < MAXLEN; i ++)
{
if(!digitPrime[i])
{
for(j = i + i; j < MAXLEN; j += i)
digitPrime[j] = 1;
sum = 0;
n = i;
while (n)
sum += n % 10, n = n / 10;
if (prime[sum])
{ ++ s; digitPrime[i] = s; }
else digitPrime[i] = s;
}
else digitPrime[i] = s;
}
}

最後,主程式只須這樣寫:
int n, t1, t2, i, count;
scanf("%d", &n);
while (n --)
{
count = 0;
scanf("%d %d", &t1, &t2);
printf("%d\n", digitPrime[t2] - digitPrime[t1] + (digitPrime[t1] != digitPrime[t1 - 1]));
}

By David.K

p10533題目連結
回ACM題庫目錄
回首頁

Problem 10539 Almost Prime Numbers,只一質數整除的數

此題是要求出整數 low 和整數 high 之間的只一質數整除的數,首先得先求出 1 ~ sqrt(1000000000000) 之間只一質數整除的數,宣告一 prime[1000000] 陣列以存放每一個數能被幾個質數整除的數量:
#define MAXLEN 1000000

int prime[MAXLEN + 1] = {0};

再來將每一個 prime[i] = 0 的數,依 i * 2、i * 3、i * 4、....、i * n (i * n <= 1000000)的索引值累加 1,如遇 prime[i] > 0 則跳過不做,寫成 C 語言程式碼如下:
int i, j;
for (i = 2; i <= MAXLEN; i ++)
if(prime[i] > 0) continue;
else
for (j = 2; i * j <= MAXLEN; j ++)
prime[i * j] ++;

如此執行完,prime[i] = 1 的 i 值,即為 Almost Prime Number。而當 high <= 106 可以直接算出 prime[i] = 1 有幾個,但當 high > 106 則需創建另一個陣列來存放 prime[i] = 0 質數的次方,這些次方需小於 1012,寫成 C 語言程式碼如下:
unsigned long long int ten12 = (long long int)1e12;
unsigned long long int prime_tbl[80070] = {0};

unsigned long long int p;
int index = 0;
for (i = 2; i <= MAXLEN; i ++)
if (prime[i] == 0)
{
p = i;
while (p < ten12)
{
if (p != i) prime_tbl[index ++] = p;
p *= i;
}
}

創建好質數次方表後,再將質數次方表排序,而我使用前幾篇所用過的一種排序法,Mergesort(合併排序法),而這種排序請參考 Problem 10810 裡的文章的解說,相信很快就可以排序好。當 high > 106,就將 low 恰大於等於 prime[i] 的索引 lowIndex ,和 high 恰大於等於 prime[i] 的索引 highIndex 相減,答案就出來了,但 low 剛好等於 prime[i] 時,答案要多加 1。寫成 C 語言程式碼如下:
int i, n, count, lowIndex, highIndex;
unsigned long long int low, high;
scanf("%d", &n);
while (n --)
{
count = 0;
lowIndex = -1, highIndex = -1;
scanf("%lld %lld", &low, &high);
if (high <= MAXLEN)
{
for (i = low; i <= high; i ++)
if (prime[i] == 1) count ++;
}
else
{
for (i = 80069; i >= 0; i --)
{
if (prime_tbl[i] <= low && lowIndex == -1)
{
if (prime_tbl[i] == low) count ++;
lowIndex = i;
break;
}
if (prime_tbl[i] <= high && highIndex == -1)
highIndex = i;
}
count += highIndex - lowIndex;
}
printf("%d\n", count);
}

By David.K

p10539題目連結
回ACM題庫目錄
回首頁

2010年4月6日 星期二

Problem 10759 Dice Throwing,骰子點數的機率

此題是需要你輸入整數 n 和整數 x,問你擲 n 次骰子至少大於 x 點的機率是多少,以最簡分數表示。

除骰第一次骰子的點數機率是固定外,只要是骰一次以上的點數機率,都是由第一次骰子的點數機率衍生而來。你要創建一個類似以下的表格的陣列:
當陣列第一列定義好所有點數出現次數後,而當第二列的每一個數值會有這樣一個公式:當 i > 1,dice[i][j] = dice[i-1][j-6] + dice[i-1][j-5] + dice[i-1][j-4]+dice[i-1][j-3]+dice[i-1][j-2]+dice[i-1][j-1]。以上公式行的索引要在合理範圍,也就是說 j-6、j-5、....等不能是負值,不然會出錯。所以可以利用函式將此陣列創建出來,C 語言程式碼如下:
#define MAXN 24
#define MAXX 150

unsigned long long int dice[MAXN + 1][MAXX + 1];

void creat()
{
dice[1][1] = 1, dice[1][2] = 1, dice[1][3] = 1,
dice[1][4] = 1, dice[1][5] = 1, dice[1][6] = 1;
int i, j;
for (i = 2; i <= MAXN; i ++)
for (j = 2; j <= MAXX; j ++)
{
if (j - 6 >= i - 1) dice[i][j] += dice[i - 1][j - 6];
if (j - 5 >= i - 1) dice[i][j] += dice[i - 1][j - 5];
if (j - 4 >= i - 1) dice[i][j] += dice[i - 1][j - 4];
if (j - 3 >= i - 1) dice[i][j] += dice[i - 1][j - 3];
if (j - 2 >= i - 1) dice[i][j] += dice[i - 1][j - 2];
if (j - 1 >= i - 1) dice[i][j] += dice[i - 1][j - 1];
}
}

而主程式只須這樣寫, C語言程式碼如下:
creat();
int i, j, n, x;
unsigned long long int total, d;
while (scanf("%d %d", &n, &x) == 2)
{
if (n == 0 && x == 0) break;
total = 0, d = 0;
for (i = 0; i <= MAXX; i ++ )
{
total += dice[n][i];
if (i >= x) d += dice[n][i];
}
while (total % 2 == 0 && d % 2 == 0)
total /= 2, d /= 2;
while (total % 3 == 0 && d % 3 == 0)
total /= 3, d /= 3;
if (d == 0) printf("0\n");
else if(d == total) printf("1\n");
else printf("%lld/%lld\n", d, total);
}

By David.K

p10759題目連結
回ACM題庫目錄
回首頁

2010年4月5日 星期一

如何學好C語言─張巧玫

這篇文章是目前就讀實踐大學高雄校區資管系的同學的學習心得與建議,學C語言經過一些努力,必有所成,這位同學已成為程式能手,讀完這篇,預祝所有C語言初學者能有所體會。

liangk

----------------------------------------------

努力和堅持是我覺得學習程式設計很重要的一環,特別是“想”尤其為要,每個題目都要先仔細想過,該如何下手,想要怎麼寫都可以,無論是要從大範圍到小細節還是小細節到大範圍都行,完全依照個人的喜好,有想過才會變成自己的,否則一味的照著打沒有思考,這些並不會成為你的東西,要把不是你的變成你的才會有所進步,也比較有成就感。


了解題目的意思也很重要,誤會題目意思可能會造成下手時錯誤,有了個錯誤的開始就會變得很麻煩,所以要小心。


剛開始寫時,一定都會很有挫折感,不過碰壁碰久了仍會找到出路的,只不過花的時間久了點,有付出才有收穫可不是嗎?或許在寫程式的過程中,會發現它的樂趣,又或許越寫越高興,那麼恭喜你,你已經達到某種境界了。


多寫題目是最快學習到東西,我是這麼覺得的,每個題目要求與運用到的語法會不同,可想而知,每每解出個題目就代表又學到了新的東西,慢慢一步步累積自己的實力,會越來越覺得自己離成功越來越近了,儘管辛苦卻很值得,或許未來得你會很感謝現在的自己曾經這麼努力,只要肯努力,每個人都可以成功的。


資一甲,張巧玫

Problem 10359 Tiling,大數模型組合次數

這題需要用到 Problem 10254 的大數處理概念,再利用費氏級數概念,這題就不難解決了。

只需利用 F(0) = 1、F(1) = 1、F(2) = 3,當 n > 2,F(n) = F(n-1) + 2 * F(n-2)。我們可以宣告一個結構(struct),以及將它宣告陣列用以擺入答案,接著套用 Problem 10254 的大數處理概念,再寫成 C 語言程式碼如下:
#define MAXLEN 251
#define LEN 76
struct til
{
int num[100];
};
struct til t[MAXLEN];
struct til s;

void mult2s()
{
int i, j;
for (i = 0; i < LEN; i ++)
s.num[i] *= 2;
for (i = 0; i < LEN; i ++)
if (s.num[i] >= 10)
s.num[i + 1] ++, s.num[i] %= 10;
}

void add(int n)
{
int i;
for (i = 0; i < LEN; i ++)
{
t[n].num[i] += s.num[i];
if (t[n].num[i] >= 10)
t[n].num[i + 1] ++, t[n].num[i] %= 10;
}

for (i = 0; i < LEN; i ++)
{
t[n].num[i] += t[n - 1].num[i];
if (t[n].num[i] >= 10)
t[n].num[i + 1] ++, t[n].num[i] %= 10;
}
}

void creat()
{
int i, j;
t[0].num[0] = 1, t[1].num[0] = 1, t[2].num[0] = 3;
for (i = 3; i < MAXLEN; i ++)
{
for (j = 0; j < LEN; j ++)
s.num[j] = t[i - 2].num[j];
mult2s();
add(i);
}
}

這時只須將輸入的 n 值對應陣列索引,將它印出即可。C 語言程式碼如下:
creat();
while (scanf("%d", &n) == 1)
{
for (i = LEN - 1; i >= 0; i --)
if (t[n].num[i] > 0) break;
for (j = i; j >= 0; j --)
printf("%d", t[n].num[j]);
printf("\n");
}

By David.K

p10359題目連結
回ACM題庫目錄
回首頁

2010年4月4日 星期日

Problem 10763 Foreign Exchange,交換學生

一開始我想說用陣列紀錄它的國家是否有想交換的學生以及這學生想交換到哪一個國家,然而我怕國家的編號會大於陣列的索引,但實驗後證明國家編號不會大於 300,所以採用陣列紀錄的方法。

首先宣告一個 300 個索引的陣列, int data[300] = {0};,而這陣列只是方便紀錄,真正要判斷交換學生使否均衡,則須宣告兩變數來紀錄,int ConfirmCount, NotConfirmCount;, ConfirmCount 變數是紀錄交換學生的總數,NotConfirmCount 變數是紀錄國家欲收學生之缺額。當兩數計算後皆為 0,則交換學生才算均衡。C 語言程式碼如下:
ConfirmCount = 0, NotConfirmCount = 0;
while (n --)
{
scanf("%d %d", &i, &j);
if (data[i] >= 0)
data[i] ++, ConfirmCount ++;
else data[i] ++, NotConfirmCount --;
if (data[j] <= 0)
data[j] --, NotConfirmCount ++;
else data[j] --, ConfirmCount --;
}

if (ConfirmCount == 0 && NotConfirmCount == 0)
printf("YES\n");
else printf("NO\n");

By David.K

p10763題目連結
回ACM題庫目錄
回首頁

Problem 10810 Ultra-QuickSort,Mergesort

這題是要用 Mergesort(合併排序)來排序輸入的數值串,以小到大排序,求出最少移動次數。

大家可以先去讀一下 Mergesort 是什麼,再來解這一題,就會很快了,我還是推薦一篇 解說 Mergesort 的文章,裡面還有一虛擬碼和一 C 語言實際測試的程式,裡面寫的很詳盡,尤其是裡面 C 語言實際測試的程式已經完成了 90%,剩下就是算出移動次數了,讀完文章之後,大概就知道怎麼算出移動次數了,在此就不提供 C 語言程式碼。

By David.K

p10810題目連結
回ACM題庫目錄
回首頁

2010年4月1日 星期四

Problem 10254 The Priest Mathematician,四根柱子的河內塔

一開始,我以為四根柱子的河內塔在 64 片盤子移動的次數為 18433 次,當然 10000 片盤子的移動次數也應該或許不會超過 long long int 的範圍,但是我錯了,此移動次數的成長是以 2n 的次方成長。最後我算出 10000 片盤子的移動次數為 374931278650296101567069263458900577819295745 ,高達 44 位數,所以這一題應該是大數處理的題目。

我其實不太會算河內塔的次數,所以 google 了一下,發現這篇 文章 研究河內塔移動次數之深,其實不難懂,有興趣的人可以參考一下。而在這篇文章中說明了四根柱子移動次數的變化,如下表:

n1234567891011
F4(n)135913172533414965
F4(n)的差分122444888816

以上表說明了在四根柱子的情況下,F4(n)的差分中,20出現 1 次、21出現 2 次、22出現 3 次、23出現 4 次、....、2n出現 n + 1 次,所以,我們只需利用此表分差的概念,將 10000 以內盤子移動的次數累加並儲存起來,就可以輕鬆解決。

首先建立一個結構,C語言程式碼如下:
struct towerofHanoi
{
int num[MAXLEN];
};

struct towerofHanoi toH[10001];
struct towerofHanoi s;

s 為分差,所以需要一個累乘的 2 的函式,C語言程式碼如下:
void mult2s()
{
int i, j;
for (i = 0; i < MAXLEN; i ++)
s.num[i] *= 2;
for (i = 0; i < MAXLEN; i ++)
if (s.num[i] >= 10)
s.num[i + 1] ++, s.num[i] %= 10;
}

接著就要寫一個函式來建構這 10000 個陣列的值,依前面敘述的觀念,寫成C語言程式碼如下:
void creat()
{
s.num[0]= 1;
int i, count = 1, j, r = 0, v, k;
for (j = 0; j < MAXLEN; j ++)
toH[0].num[j] = 0;
for (i = 1; i <= 10000; )
{
for (j = 0; j < count; j ++, i ++)
if(i <= 10000)
{
copy(i, i - 1);
add(i);
}
else break;
mult2s(), count ++;
}
}

void add(int n)
{
int i;
for (i = 0; i < MAXLEN; i ++)
{
toH[n].num[i] += s.num[i];
if (toH[n].num[i] >= 10)
toH[n].num[i + 1] ++, toH[n].num[i] %= 10;
}
}

最後,再把所輸入的值,對應結構陣列印出即可:
int n, i, j;
creat();
while (scanf("%d", &n) == 1)
{
for (i = MAXLEN - 1; i >= 0; i --)
if (toH[n].num[i] > 0) break;
if (i == -1) printf("0");
for (j = i; j >= 0; j --)
printf("%d", toH[n].num[j]);
printf("\n");
}

By David.K

p10254題目連結
回ACM題庫目錄
回首頁