Problem 573 The Snail，井底的蝸牛

給你井的高度 H、蝸牛白天上升高度 U、蝸牛晚上下降高度 D、蝸牛疲勞因子 F。
例如給你一隻蝸牛的數據 H = 6, U = 3, D = 1, F = 10。而這隻蝸牛會如以下表顯示，在第 3 天爬出井。

Day	Initial Height	Distance Climbed	Height After Climbing	Height After Sliding
1	0'	3'	3'	2'
2	2'	2.7'	4.7'	3.7'
3	3.7'	2.4'	6.1'	-

其中要注意的就是疲勞因子是以百分比去計算，還有如果因為疲勞而使得白天上升高度變成負值，就使白天上升高度為 0。

程式碼如下：

while (scanf("%f %f %f %f", &H, &U, &D, &F) == 4 && H != 0)
{
    int days = 1;
    float nowHigh = 0.0, sub = U * F / 100;
    while (1)
    {
        nowHigh += U;
        if (nowHigh > H) { printf("success on day %d\n", days); break;}
        nowHigh -= D;
        if (nowHigh < 0) { printf("failure on day %d\n", days); break;}
        U -= sub;
        if (U < 0) U = 0;
        days ++;
    }
}

By David.K

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

Problem 534 Frogger，蛙跳的最小距離

此題給你一些石頭的座標，而要從第一顆石頭跳到第二顆石頭所用最小距離是多少 ( 注意：是最小，不是最短 )。舉個例子，就拿第二個輸入範例來說，
3
17 4 <- 第一顆石頭 ( Freddy所在之石 )
19 4 <- 第二顆石頭 ( Fiona所在之石 )
18 5 <- 第三顆石頭

我們可以簡略算出 1 <--> 2 距離為 2，2 <--> 3 距離為 1.41421，3 <--> 1 距離為 1.41421。如果以最短路徑來說，從 1 直接跳到 2 最快。但以最小距離來說，從 1 跳到 3 再跳到 2，所用只要用 1.41421 的距離便可跳到 2，若直接從 1 跳到 2，便會花上 2.0 距離之長。這就不符合我們所說的最小距離。

一開始我們先將所有石頭之間的距離放入陣列，再用「最小路徑演算法」便可求出最小距離，C 語言程式碼如下：

for (i = 0; i < n; i ++)
    scanf("%f %f", &pt[i][0], &pt[i][1]);
for (i = 0; i < n; i ++)
{
    W[i][i] = 0;
    for (j = i + 1; j < n; j ++)
    {
        W[i][j] = sqrt( (pt[i][0] - pt[j][0]) * (pt[i][0] - pt[j][0]) + 
                        (pt[i][1] - pt[j][1]) * (pt[i][1] - pt[j][1]) );
        W[j][i] = W[i][j];               
    }
}
for (k = 0; k < n; k ++)
    for (i = 0; i < n; i ++)
        for (j = 0; j < n; j ++)
        {
            W[i][j] = min(W[i][j], max(W[i][k] , W[k][j]));
        }
printf("Scenario #%d\n", caseNum ++);        
printf("Frog Distance = %.3f\n\n", W[0][1]);

By David.K

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

Problem 729 The Hamming Distance Problem

此題題目我看的沒有很清楚，但是一看它的輸出入就知道它輸入兩個整數 N 和 H 後，N 為字串長度，H 為 1 的數量，例如：N = 3, H = 2，所以一開始就是 011 為初始字串。要請你求出這字串的所有不重複的排列組合。

一開始要先將初始字串設定好：

scanf("%d %d", &m, &h);
for (j = 0; j < m; j ++)
{
    if (j < m - h) str[j] = '0';
    else str[j] = '1';
}
str[m] = '\0';

再用與 Problem 146 的 next_permutation 函式或 C ++ 中的 next_permutation 的方法，持續找尋下一組的排列組合並且印出，直到找不到為止。C 語言程式碼如下：

void swap(int i, int j)
{
     char tmp;
     tmp = str[i];
     str[i] = str[j];
     str[j] = tmp;
} 

int next_permutation()
{
     int i, j, k;
     int length;
     length = strlen(str);
     for(i = length - 1;i > 0 ; --i)
      if(str[i - 1] < str[i]) break;
     j = i;
     if(j == 0) return 0;
     for(i = length - 1;i > 0; --i)
      if(str[j - 1] < str[i]) break;
     k = i;
     swap(j - 1, k);
     for(i = j, j = length - 1;i < j; ++ i, -- j)
      swap(i, j);
   return 1;
}

最後只需要在主程是內如此呼叫：

printf("%s\n", str);
while (next_permutation())
{
    printf("%s\n", str);
}

By David.K

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