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題庫目錄
回首頁

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題庫目錄
回首頁

Problem 10491 Cows and Cars，牛與車

此題為機率題，找出其中公式就可解此題。舉幾個例子：

牛數量	車數量	開門數	門總數
2	1	1	3

以上資料來看，
先選牛的機率 2 / 3，換選車機率 1 / 1 (因為會開一個門是牛的門，規定又說一定要換門)，所以機率 2 / 3 * 1 = 2 / 3。
先選車機率 1 / 3，換選車機率 0 / 1 (一開始選車，再開一個是牛的門，規定一定要換門)，所以機率 1 / 3 * 0 = 0。
一定要換門的機率為 2 / 3 + 0 = 2 / 3。

牛數量	車數量	開門數	門總數
5	3	2	8

先選牛的機率 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。
最後推導公式：

牛數量	車數量	開門數	門總數
NCOWS	NCARS	NSHOW	DOORS (= 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題庫目錄
回首頁

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題庫目錄
回首頁

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題庫目錄
回首頁

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題庫目錄
回首頁