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