2010年7月11日 星期日

Problem 11805 Bafana Bafana,傳球

輸入 N K P 三整數,代表有球員 1 - N,而球員圍成一圈,球員 2 在球員 1 的右邊,球員 3 在球員 2 的右邊,...以此類推。從球員 K 發球,每次傳球只往右邊一個球員傳,傳 P 次。問你最後球會在哪一個球員腳上。

此題讀入三整數後,利用以下 C 語言程式碼即可解:
j = (K + P) % N;
if (j == 0) j = N;
By David.K

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

Problem 10405 Longest Common Subsequence,最長共同子字串

建議大家可以上網去找「最長共同子字串」的演算法,此演算法是由「最長連續共同子字串」推演而來。「最長共同子字串」的方法就是依序比對字串,將最佳比對結果逐一往陣列右下方推,推到最後,答案就出來了。
C 語言程式碼如下:
#define LEN 1000

char seq1[LEN + 1], seq2[LEN + 1];

int lcs_length(int s1Len, int s2Len)
{
int i, j;
int table[s1Len + 1][s2Len + 1];
memset(table, 0, sizeof(table));

for(i = 1; i <= s1Len; ++i) {
for(j = 1; j <= s2Len; ++j) {
if(seq1[i - 1] == seq2[j - 1])
table[i][j] = table[i - 1][j - 1] + 1;
else if(table[i - 1][j] > table[i][j - 1])
table[i][j] = table[i - 1][j];
else
table[i][j] = table[i][j - 1];
}
}
return table[s1Len][s2Len];
}

int main()
{

while (gets(seq1))
{
gets(seq2);
int s1Len = strlen(seq1), s2Len = strlen(seq2);
printf("%d\n", lcs_length(s1Len, s2Len));
}

return 0;
}

By David.K

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

Problem 10409 Die Game,骰子遊戲

首先宣告一結構,紀錄骰子上下東西南北所屬數字為何:
struct Dice
{
int up, down, north, east, south, west;
};
struct Dice d;
主程式內,讀入翻動次數 n 次後,先初始化骰子數字各在哪些方位:
d.up = 1, d.down = 6, d.north = 2,
d.east = 4, d.south = 5, d.west = 3;
最後只要依照相對面的骰子總和為 7 以及空間概念,就可寫出來:
while (n --)
{
scanf("%s", str);
if (str[0] == 's') /* 南 */
d.south = d.up, d.up = d.north,
d.down = 7 - d.up, d.north = 7 - d.south;
if (str[0] == 'n') /* 北 */
d.down = d.north, d.north = d.up,
d.up = 7 - d.down, d.south = 7 - d.north;
if (str[0] == 'w')
d.down = d.west, d.west = d.up,
d.up = 7 - d.down, d.east = 7 - d.west;
if (str[0] == 'e')
d.east = d.up, d.up = d.west,
d.down = 7 - d.up, d.west = 7 - d.east;
}
printf("%d\n", d.up);

By David.K

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

Problem 10452 Marcus

給你一陣列,要你求出從字元 '@'( 一定在最後一排 )到字元 '#'( 一定在第一排 ),按照字串 "IEHOVA" 走法,列出怎麼走才會走的到字元 '#' 的走法。

所以先寫好一字串,讓它走一步可以比對索引字元,若不對,則不走;若走到,則印出。用一遞迴函式實現,i, j 為目前位置,index 為目前字串索引:
#define SIZE 8
#define LEN 7
int n, row, col, sI, sJ, eI, eJ;

char letters[LEN + 1] = {'@', 'I', 'E', 'H', 'O', 'V', 'A', '#'};
char path[LEN];
char stone[SIZE][SIZE + 1];
void visit(int i, int j, int index)
{
if (letters[index] != stone[i][j]) return;
if (i == eI && j == eJ)
{
int k;

if (path[0] == 'r') printf("right");
else if (path[0] == 'l') printf("left");
else if (path[0] == 'f') printf("forth");

for (k = 1; k < LEN; k ++)
{
if (path[k] == 'r') printf(" right");
else if (path[k] == 'l') printf(" left");
else if (path[k] == 'f') printf(" forth");
}
printf("\n");
}
/* 左 */
if (j - 1 >= 0) path[index] = 'l', visit(i, j - 1, index + 1);
/* 右 */
if (j + 1 < col) path[index] = 'r', visit(i, j + 1, index + 1);
/* 前 */
if (i - 1 >= 0) path[index] = 'f', visit(i - 1, j, index + 1);
}
最後,在主程式如此呼叫:
scanf("%d %d", &row, &col);  
for (i = 0; i < row; i ++)
{
scanf("%s", stone[i]);
if (i == 0)
{
for (j = 0; j < col; j ++)
if (stone[i][j] == '#') eI = i, eJ = j;
}
if (i == row - 1)
{
for (j = 0; j < col; j ++)
if (stone[i][j] == '@') sI = i, sJ = j;
}
}
visit(sI, sJ, 0);

By David.K

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

Problem 10494 If We Were a Child Again,小學數學

此題要算出他給你的運算式。用 scanf("%s %s %lld", m, ch, &n) 讀入,第一個數可能會很大,所以利用字串讀入,讀入之後,利用我們平常小學算數的方法,將被除數一個一個從大位數到小位數的讀入,再用 n 去除或取餘數,除法就每次除每次印;餘數就最後在印就好了:
first = 1;  
if (ch[0] == '/')
{
tmp = 0;
for (i = 0; (c = m[i]); i ++)
{
tmp *= b;
tmp += c - '0';
j = tmp / n;
if (j != 0) first = 0;
if (!first) printf("%lld", j);
tmp %= n;
}
if (first) printf("0");
printf("\n");
}
if (ch[0] == '%')
{
for (i = 0, tmp = 0; (c = m[i]); i ++)
{
tmp *= b;
tmp += c - '0';
tmp %= n;
}
printf("%lld\n", tmp);
}

By David.K

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

Problem 10497 Sweet Child Makes Trouble,麻煩的小孩

通常可愛的小孩會製造一些麻煩,例如說拿別人的東西總是不會歸回原位放好,如果拿了 3 個人的東西,而不歸回原位放好的擺法有 2 個,2 3 1 和 3 1 2。所以給你一個 n 值就是小孩拿了 n 樣東西,要你求出不歸回原位的擺法有幾種。

此處要用到大數概念,最長位數有 1976 位這麼長,所以處理起來頗為耗時,不過也只需處理一次並且記錄在字元陣列內,最後用 puts() 印出即可:
#define SIZE 800
#define LEN 2000
int p[SIZE + 1][LEN + 1] = {0};
char output[SIZE + 1][LEN + 1];
void create()
{
int i;
p[0][0] = 1;
p[1][0] = 0;
output[0][0] = '1';
output[0][1] = '\0';
output[1][0] = '0';
output[1][1] = '\0';
int j, k, s, count = 0;
for (i = 2; i <= SIZE; i ++)
{
for (j = 0; j <= LEN; j ++)
{
p[i][j] += (p[i - 1][j] + p[i - 2][j]) * (i - 1);
p[i][j + 1] += p[i][j] / 10, p[i][j] %= 10;
}

for (j = LEN; j >= 0; j --)
if (p[i][j] > 0) break;
for (k = j, s = 0; k >= 0; k --, s ++)
output[i][s] = p[i][k] + '0';
output[i][s] = '\0';
}
}

int main()
{
int n;
create();
while (scanf("%d", &n) == 1 && n != -1)
puts(output[n]);
return 0;
}

By David.K

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

2010年7月5日 星期一

Problem 10432 Polygon Inside A Circle

給你圓的半徑 r 與內接 n 邊形的邊數量,要你求出 n 邊形面積多少。以上為 n = 8 的表示方式。
推導公式,要求橘色邊和綠色邊方能求出 n 邊形之一塊三角形面積,所以 θ 角要先求出,2 * PI 為一個圓周率,所以 θ = 2 * PI / n。
所以,取 θ 角的一半,橘色邊為 r * cos(PI / n),
綠色邊為 2 * r * sin(PI / n),
面積為 r * cos(PI / n) * 2 * r * sin(PI / n) / 2,
約分後為 r * r * cos(PI / n) * sin(PI / n) = r * r * sin(2 * PI / n) / 2。
(依照公式 sin2θ = 2sinθcosθ)
而有 n 塊三角形所以 n 邊形總面積為 n * r * r * sin(2 * PI / n) / 2。

By David.K

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

2010年7月4日 星期日

Problem 10491 Cows and Cars,牛與車

此題為機率題,找出其中公式就可解此題。舉幾個例子:
牛數量車數量開門數門總數
2113
以上資料來看,
先選牛的機率 2 / 3,換選車機率 1 / 1 (因為會開一個門是牛的門,規定又說一定要換門),所以機率 2 / 3 * 1 = 2 / 3。
先選車機率 1 / 3,換選車機率 0 / 1 (一開始選車,再開一個是牛的門,規定一定要換門),所以機率 1 / 3 * 0 = 0。
一定要換門的機率為 2 / 3 + 0 = 2 / 3。
牛數量車數量開門數門總數
5328
先選牛的機率 5 / 8,換選車機率 3 / 5,所以機率 5 / 8 * 3 / 5 = 15 / 40。
先選車機率 3 / 8,換選車機率 2 / 5 ,所以機率 3 / 8 * 2 / 5 = 6 / 40。
一定要換門的機率為 15 / 40 + 6 / 40 = 21 / 40。
最後推導公式:
牛數量車數量開門數門總數
NCOWSNCARSNSHOWDOORS (= NCOWS + NCARS)
先選牛的機率 NCOWS / DOORS,換選車機率 NCARS / (DOORS - NSHOW - 1),所以機率 NCOWS * NCARS / (DOORS * (DOORS - NSHOW - 1))。
先選車機率 NCARS / DOORS,換選車機率 (NCARS - 1) / (DOORS - NSHOW - 1),所以機率 NCARS * (NCARS - 1) / (DOORS * (DOORS - NSHOW - 1))。
一定要換門的機率為 (NCOWS + NCARS - 1) * NCARS / (DOORS * (DOORS - NSHOW - 1))。

By David.K

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

2010年7月3日 星期六

Problem 10551 Basic Remains,進位餘數

此題給你三個數,一是進位制,二是被除數,三是除數。要你求出在此進位制的餘數為何。

首先將於除轉為 10 進制,讀入數值後,用一函式轉換:
#define SIZE 1000
char p[SIZE + 1], m[10], print[SIZE + 1];
int b, r;

int get10Basic()
{
int n = 0, i;
int len = strlen(m);
for (i = 0; i < len; i ++)
n = n * b + (m[i] - '0');
return n;
}

主程式內 ....
scanf("%s %s", p, m);
int len = strlen(p);
int i;
r = get10Basic();
最後只需將被除數從大到小一個一個讀入,每次讀入都要乘上進位制,再去和 r 取餘數,最後要轉回進位制印出。
int n = 0;
for (i = 0; i < len; i ++)
{
n *= b;
n += p[i] - '0';
n %= r;
}
printbBasic(n);
printbBasic 函式程式碼:
void printbBasic(int n)
{
int i = 0, j;
for ( ; n; n /= b)
print[i ++] = n % b;
if (i == 0) printf("0");
for (j = i - 1; j >= 0; j --)
printf("%c", print[j] + '0');
printf("\n");
}

By David.K

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

Problem 10573 Geometry Paradox,面積

這題要求出下圖灰色部分的面積。

這題如果給你 r1, r2 半徑,那就很好算出灰色部分面積。
依照公式: ((r1 + r2) * (r1 + r2) - r1 * r1 - r2 * r2) * PI。
如果只給你 t,要假設 r1 = r2,則 t 就為直徑,則 t / 4 則為兩圓半徑,
則白色部分面積為: 2 * (t / 4 * t / 4 * PI) = t * t / 8 * PI。
而灰色部分則是 (t / 2 * t / 2 * PI) - t * t / 8 * PI = t * t / 8 * PI。

By David.K

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

Problem 10583 Ubiquitous Religions,最大宗教群

此題與 Problem 10608 Friends 是一樣的,不過數量更大,建議可以使用輸入優化來縮短時間,但還是跑了一秒多,說明可點上面連結去看。

以下還是提供 C 語言程式碼:
int n, m;

int getInt()
{
char ch;
int n = 0;
while( ch = getchar())
if(ch != ' ' && ch != '\n') break;
n = ch - 48;
while( ch = getchar())
{
if(ch == ' ' || ch == '\n') break;
n = n * 10 + ch - 48;
}
return n;
}

主程式內 ....
while ((n = getInt()) && (m = getInt()))
{
int student[n + 1];
religionID = 1, count = 0;
memset(student, 0, sizeof(student));
while (m --)
{
i = getInt(), j = getInt();
if (student[i] == 0 && student[j] == 0)
{
student[i] = religionID, student[j] = religionID;
religionID ++;
count ++;
}
else if((student[i] != 0 && student[j] == 0) ||
(student[i] == 0 && student[j] != 0))
{
tmp = student[i] < student[j] ? student[j] : student[i];
student[i] = tmp, student[j] = tmp;
}
else if (student[i] != student[j])
{
tmp = student[j];
replace = student[i];
for (s = 1; s <= n; s ++)
if (student[s] == tmp) student[s] = replace;
count --;
}
}
/* for (i = 1; i <= n; i ++)
printf("%d ", student[i]);
printf("\n"); */
for (i = 1; i <= n; i ++)
if (student[i] == 0) count ++;
printf("Case %d: %d\n", caseNum ++, count);
}

By David.K

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

Problem 10608 Friends,最大朋友群

鎮上有 N 個人,照一句諺語說:「我朋友們的朋友也是我的朋友」。A 和 B 為朋友,B 和 C 為朋友,所以 C 和 A 也為朋友。

讀入 N 和 M 兩整數,N 為鎮上有公民 1 - N,而接下來會有 M 列資料,M 列資料都有兩整數 a, b,代表公民 a 和公民 b 為朋友。最後請你算出這鎮上最大朋友群的數量為多少。

其實只要給朋友群定義一個朋友群編號,如果雙方都沒有朋友群編號,就將兩人都定義一個新的朋友群編號,並將此朋友編號數量變成 2;若兩人其中一人沒有朋友群編號,則將他加入有編號的朋友群之中;如果兩人都有朋友群編號,就將其中一方的所有朋友的編號改為另一方的編號,順便將另一方朋友編號數量累加對方的數量。

一開始宣告陣列以及初始化朋友群編號以及朋友群數量:
scanf("%d %d", &n, &m);
int friends[n + 1], record[n + 1], max = 0;
count = 0, groupID = 1;
memset(friends, 0, sizeof(friends));
memset(record, 0, sizeof(record));
接下來用以上敘述的概念寫成分群並且計算數量的方法,順便記錄最大值,寫成 C 語言程式碼如下:
while (m --)
{
scanf("%d %d", &a, &b);
if (friends[a] == 0 && friends[b] == 0)
{
friends[a] = groupID, friends[b] = groupID;
record[groupID] = 2;
if (max < record[groupID]) max = record[groupID];

groupID ++;
count ++;
}
else if((friends[a] != 0 && friends[b] == 0) ||
(friends[a] == 0 && friends[b] != 0))
{
tmp = friends[a] < friends[b] ? friends[b] : friends[a];
friends[a] = tmp, friends[b] = tmp;
record[tmp] ++;
if (max < record[tmp]) max = record[tmp];
}
else if (friends[a] != friends[b])
{
tmp = friends[b];
replace = friends[a];
record[tmp] = 0;
for (s = 1; s <= n; s ++)
if (friends[s] == tmp) friends[s] = replace, record[replace] ++;
if (max < record[replace]) max = record[replace];
count --;
}
/* for (s = 1; s <= n; s ++)
printf("%d ", record[s]);
printf("\n"); */
}
printf("%d\n", max);

By David.K

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

2010年7月2日 星期五

Problem 10637 Coprimes,互質

此題用回溯演算法就可解決。這一開始我怎麼寫都寫不出來,答案的順序錯誤,結果我上網找了一下,原來找尋這些互質的數要由小到大,而且找的下一個數要比前一個相等或來的大。

還有一點,要建構互質表,不然很容易就超過時間了,網友 藍ㄚ有兩種解題方法 ,我從這裡參考的。

所以一開始建立互質表,C 語言程式碼如下:
#define SIZE 101

int print[SIZE];
int GCD[SIZE][SIZE];
int S, t;

int gcd(int a,int b)
{
if (a % b == 0){ return b;}
return gcd(b, a % b);
}

主程式內 ....
int a, b, n;
for(a = 1; a < SIZE; a ++)
for(b = 1; b < SIZE; b ++)
GCD[a][b] = gcd(a,b);
最後寫一函式,利用回溯演算法將每一種可能的方法全部試過,如果超過我們所定義數值,只有剛好等於我們定義數值,才會被列出。
void find (int index, int n, int sum)
{
int i, j;
if (index == t && sum == S)
{
printf("%d", print[0]);
for (i = 1; i < index; i ++)
printf(" %d", print[i]);
printf("\n");
return;

}
if (sum >= S) return;
for (; n <= S - sum; n ++)
{
for (j = 0; j < index; j ++)
if (GCD[print[j]][n] != 1) break;

if (j == index && S - sum >= n)
{
print[index] = n;
find(index + 1, n, sum + n);
}
}

}
最後在主程是如此呼叫:
scanf("%d", &n);
for (i = 1; i <= n; i ++)
{
scanf("%d %d", &S ,&t);
printf("Case %d:\n", i);
find(0, 1, 0);
}

By David.K

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

Problem 10696 f91

此題為簡單題一枚。依照題目給的公式:
    *  If N ≤ 100, then f91(N) = f91(f91(N+11));
* If N ≥ 101, then f91(N) = N-10.
我們可以拿 92 來做例子:
f91(92) = f91(f91(92 + 11)) = f91(f91(103)) = f91(93) = f91(f91(93 + 11)) = f91(94) = ...... = f91(101) = 91。
以上例子證明小於 101 之數,此遞迴函式必定將他調整為 91。
所以只要小於 101 之數為 91,大於等於 101 之數為此數減 10。
By David.K

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

Problem 10684 The jackpot,賭博

此題需要用到動態規畫。告知一連串的賭局輸贏金額,要你求出在任一段連續賭局中,能獲得的最多金幣,只需輸出金幣數值即可。

只需利用動態規劃將較佳數值往後推,推到陣列結束,在找出陣列內最大值即可。這裡也用到了輸入優化的方法。C 語言程式碼如下:
#define SIZE 10001

int money[SIZE], record[SIZE];

int getInt()
{
char ch;
int n = 0, isNegative = 0;
while(ch = getchar())
if(ch != ' ' && ch != '\n') break;
if (ch == '-') isNegative = 1;
else n = ch - 48;
while( ch = getchar())
{
if(ch == ' ' || ch == '\n') break;
n = n * 10 + ch - 48;
}
if(isNegative) return -n;
return n;
}

主程式內 ....
while (n = getInt())
{
for (i = 0; i < n; i ++)
money[i] = 0, record[i] = 0;
int max = 0;
money[0] = getInt();
if (money[0] <= 0)
record[0] = 0;
else
record[0] = money[0], max = money[0];
for (i = 1; i < n; i ++)
{
money[i] = getInt();
record[i] = money[i] < money[i] + record[i - 1] ?
money[i] + record[i - 1] : money[i];
if (record[i] > max) max = record[i];
}
if (max == 0) puts("Losing streak.");
else printf ("The maximum winning streak is %d.\n", max);
}

By David.K

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

Problem 10664 Luggage,行李

此題讀入各行李重量後,以大到小排序,最後再平均分配在兩台車子上,如兩台車同重量,輸出 "YES",否則,輸出 "NO"。

此處我也用到了輸入優化的方式。
關鍵程式碼如下:
#define SIZE 21

int luggage[SIZE], changeLine, index;

int getInt()
{
char ch;
int n = 0;
changeLine = 0;
while( ch = getchar())
if(ch != ' ' && ch != '\n') break;
n = ch - 48;
while( ch = getchar())
{
if(ch == ' ' || ch == '\n') break;
n = n * 10 + ch - 48;
}
if (ch == '\n') changeLine = 1;
return n;
}

主程式內 ....
index = 0, changeLine = 0, a = 0, b = 0;
while (!changeLine)
{
luggage[index] = getInt();
for (i = index; i >= 1; i --)
if (luggage[i] > luggage[i - 1])
tmp = luggage[i], luggage[i] = luggage[i - 1], luggage[i - 1] = tmp;
else break;
index ++;
}

for (i = 0; i < index; i ++)
{
if (a == b) a += luggage[i];
else if (a > b) b += luggage[i];
else a += luggage[i];
}

if (a == b) puts("YES");
else puts("NO");

By David.K

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

Problem 10919 Prerequisities?,畢業

讀入此學生修課通過的課程編號,用陣列接收,並且排序,再讀入課程類別課程數量以及必須通過課程的數量,接著一筆一筆讀入此課程類別的所有課程編號,比對修課通過的課程編號,累計數量後,大於等於此課程類別就代表此課程類別通過。如此將所有課程類別判斷過一次,如果沒有不通過的,就代表他會畢業。

此處如果輸入數量多的話,可以利用輸入優化來讀入整數或小數,而大家可以參網友「藍丫」提供的輸入優化 這函式讀入整數,如果數量一大,幾乎可以縮短一半以上的時間。感謝網友提供的輸入優化函式。而此函式程式碼如下:
#define SIZE 101

int classID[SIZE];
int index, n, m, c, r;

int getInt()
{
char ch;
int n = 0;
while( ch = getchar())
if(ch != ' ' && ch != '\n') break;
n = ch - 48;
while( ch = getchar())
{
if(ch == ' ' || ch == '\n') break;
n = n * 10 + ch - 48;
}
return n;
}


所以可利用函式讀取修課通過的數量,排序好後,課程可用二分搜尋法來找尋是否有此課程。最後判斷他是否會畢業。
int isFind(int low, int high, int n)
{
int mid;
if (low > high) return -1;
else
{
mid = (low + high) / 2;
if (n == classID[mid])
return mid;
else if (n < classID[mid])
return isFind(low, mid - 1, n);
else
return isFind(mid + 1, high, n);
}
}

主程式內 ....
while ((n = getInt()))
{
index = 0;
m = getInt();
while (n --)
{
id = getInt();
classID[index] = id;
for (i = index; i >= 1; i --)
if (classID[i] < classID[i - 1])
tmp = classID[i], classID[i] = classID[i - 1], classID[i - 1] = tmp;
else break;
index ++;
}
int error = 0, f;
while (m --)
{
c = getInt(), r = getInt();
int count = 0, find;
while (c --)
{
f = getInt();
find = isFind(0, index, f);
if (find != -1) count ++;
}
if (count < r) error = 1;
}
if (error) puts("no");
else puts("yes");
}

By David.K

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

Problem 10903 Rock-Paper-Scissors,剪刀石頭布

讀入兩整數 n 和 k,說明有 n 的人進行 k * n * (n-1) / 2 場剪刀石頭布的遊戲,要你算出最後每個人的勝率,而勝率為 w / (l + w) (註:w 為勝場數,l 為敗場數)。

創建一個結構陣列,紀錄每個人勝敗場次數,如以下程式碼:
#define SIZE 101

struct player
{
int win;
int lose;
};
struct player p[SIZE];

其實只要比較每場勝敗為誰,再將這些結果累加到每個人的陣列索引,最後印出勝率。C 語言程式碼如下:
scanf("%d", &k);
for (i = 1; i <= n; i ++)
p[i].win = 0, p[i].lose = 0;
game = k * n * (n - 1) / 2;
while (game --)
{
scanf("%d %s %d %s", &p1, f1, &p2, f2);
int kind1, kind2;
if (f1[0] == 'r') kind1 = 1;
else if (f1[0] == 'p') kind1 = 2;
else kind1 = 3;
if (f2[0] == 'r') kind2 = 1;
else if (f2[0] == 'p') kind2 = 2;
else kind2 = 3;
if (kind1 > kind2)
{
j = kind1 - kind2;
if (j == 1) p[p1].win ++, p[p2].lose ++;
else p[p2].win ++, p[p1].lose ++;
}
else if (kind1 < kind2)
{
j = kind2 - kind1;
if (j == 1) p[p2].win ++, p[p1].lose ++;
else p[p1].win ++, p[p2].lose ++;
}
}
int total, win;
for (i = 1; i <= n; i ++)
{
win = p[i].win;
total = win + p[i].lose;
if (total == 0) printf("-\n");
else printf("%.3f\n",(float)win / (float)total);
}

By David.K

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

Problem 10963 The Swallowing Ground,拼組地面

就是給你地面每個格子的間隙,要你判斷它組不組的起來。

只要記錄第一格子的間隙,再判斷接下來的間隙是否相同,不相同,輸出 no;相同,輸出 yes。
scanf("%d", &n);
while (n --)
{
error = 0;
scanf("%d", &m);
scanf("%d %d", &y1, &y2);
sub = y1 - y2;
m --;
while (m --)
{
scanf("%d %d", &y1, &y2);
if (sub != y1 - y2) error = 1;
}
if (error) printf("no\n");
else printf("yes\n");
if (n) printf("\n");
}

By David.K

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

2010年7月1日 星期四

Problem 11005 Cheapest Base,省錢

讀入 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" 每個字印出的錢,可用一整數陣列來接收:
for (i = 0; i < 36; i ++)
scanf("%d", &money[i]);
接著我寫一函式,傳入兩整數,一為轉換為錢之整數,一為此整數的進位制。函式程式碼如下:
int getMoney(int n, int base)
{
int nMoney = 0;
for (; n; n /= base)
nMoney += money[n % base];
return nMoney;
}
最後將 2 - 36 進位與欲印出的數字丟到上述函式轉換錢,並且進行比較,比較後記錄最小值,最後印出即可。C 語言程式碼如下:
index = 0;
scanf("%d", &m);
for (i = 0; i < m; i ++)
{
scanf("%d", &k);
index = 0;
min = getMoney(k, 2);
best[index ++] = 2;
for (j = 3; j <= 36; j ++)
{
count = getMoney(k, j);
if (min == count) best[index ++] = j;
if (min > count) min = count, index = 0, best[index ++] = j;
}
printf("Cheapest base(s) for number %d:", k);
for (j = 0; j < index; j ++)
printf(" %d", best[j]);
printf("\n");
}

By David.K

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

Problem 11015 05-2 Rendezvous,小組集合

此題給你兩整數,N 和 M,接下來會有 N 列姓名,代表組員 1 ~ N 的姓名。再接下來會有 M 列資料,M 列每列會有三整數 i, j 和 k,代表組員 i 到組員 j 的距離為 k。最後要你求出哪一組員的家,與其他所有組員家的距離是最短的。

使用「佛洛依德最短路徑演算法」就可以解決此題。首先,創建一個 N * N 陣列 W 並且將陣列內所有值歸 0,順便紀錄 N 個組員的姓名;而接下來 M 列資料,讀取每行 i, j , k 後將 W[i][j] = W[j][i] = k。

因為可能有些組員到其他組員家是沒有路勁的,所以演算法稍做修改,C 語言程式碼如下:
#define SIZE 23
struct Crew
{
char name[12];
};
struct Crew c[SIZE];
int W[SIZE][SIZE];

主程式內 ....
for (k = 1; k <= n; k ++)
for (i = 1; i <= n; i ++)
for (j = 1; j <= n; j ++)
{
if (i != j && W[i][k] != 0 && W[k][j] != 0)
{
int m = W[i][k] + W[k][j];
if (W[i][j] == 0) W[i][j] = m;
else if (m < W[i][j]) W[i][j] = m;
}
}

最後,加總以某組員家為集合地點的路徑,再去比較誰的路徑最短,最後再印出組員名字。C 語言程式碼如下:
for (i = 1, min = 0; i <= 1; i ++)
for (j = 1; j <= n; j ++)
if (i != j)
min += W[i][j];
minID = 1;
int count;
for (i = 2; i <= n; i ++)
{
for (j = 1, count = 0; j <= n; j ++)
{
if (i != j)
count += W[i][j];
}
if (min > count)
min = count, minID = i;
}
printf("Case #%d : %s\n", caseNum ++, c[minID].name);

By David.K

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