Problem 10346 Peter's Smokes，愛抽菸的彼得

此題與 Problem 11150 非常相似，所以可以點過去看它的解說。在此就不贅述。

不過還是提供程式碼給大家參考：

while (scanf("%d%d", &n, &k) == 2)
{
    int total = n, record;  
    for (; n > k - 1;)
    {
        total += n / k;
        record = n / k;
        n = (n % k + record);
    }
    printf("%d\n", total);
}

By David.K

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

Problem 10295 Hay Points，薪資字典

Problem 10295 此題是要算出員工針對工作描述，而算出他的薪資。在描述之前會有一本所謂「薪資字典」的本子，裡面記錄著一些關鍵字，只要提及字典上任何一個關鍵字，就可以取得這個關鍵字的 Hay Points，當然，Hay Points 越高，員工的薪資也越高。

所以在一開始要先記錄它的字典裡的字，再去讀取員工描述。將每個字與字典的字比對後，若有出現，則加上它的 Hay Points；反之，則否。程式如下：

int m, n, i, j, k;
scanf("%d%d", &m, &n);
for (i = 0; i < m ; i ++)
    scanf("%s %d", w[i].str, &w[i].point);
for (i = 0; i < n; i ++)
{
    int point = 0;
    while (gets(str))
    {
        if (str[0] == '.') break;
        int index = 0;
        for (j = 0; str[j]; j ++)
        {
            if (isalpha(str[j]))
                word[index ++] = str[j];
            if (!isalpha(str[j]) || str[j + 1] == '\0')
            {
                word[index] = '\0';
                for (k = 0; k < m; k ++)
                    if (strcmp(word, w[k].str) == 0)
                    { point += w[k].point; break; }
                index = 0;   
            }      
        }    
    }
    printf("%d\n", point);
    
}

而結構宣告如下：

struct word
{
    char str[20];
    int point;     
};

struct word w[1000];
char str[200];
char word[20];

By David.K

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

Problem 11121 Base -2，-2 進位

你沒有看錯，就是 -2 進位，這題是要我們輸入一個 n 值，算出他的 -2 進位為何。例如 n = 7，則輸出 11011。

這題須把握幾個原則，用迴圈以 n 持續 mod -2，而 mod 的值就是要印出的數，再用 -2 除它。當遇 n 為奇數且為負數時，除 -2 後須將值加上 1；當持續除到 n = -1 時，則印出 1，將 n 變為 1；當 n = 1，印出 1，則跳出迴圈。例如 n = -25，
n = -25 為奇數且為負數，mod -2 為 1，印出 1，除 -2 後為 12，需加 1，則 n = 13。
n = 13 mod -2 後為 1，印出 1，除 -2 後為 -6， n = -6。
n = -6 mod -2 為 0，印出 0，除 -2 後為 3， n = 3。
n = 3 mod -2 後為 1，印出 1，除 -2 後為 -1， n = -1。
n = -1 則需先印出 1，再將 n 變為 1。
n = 1 ，印出 1， 跳出迴圈。

所以答案 111011。記住：順序是反的，所以可能需要將這些數字記錄下來。
寫成程式如下：

scanf("%d", &n);
a = n;
while (n --)
{  
    scanf("%d", &m);
    index = 0;
    for (;m != 1 && m != 0;)
    {
        int add = 0;
        if (m < 0 && m % 2) add = 1;
        ans[index ++] = abs(m % -2);
        m /= -2;
        if (add) m ++; 
        if(m == -1) ans[index ++] = 1, m = 1;
          
    }
    if (m == 1) ans[index ++] = 1;
    printf("Case #%d: ", a - n);
    for (i = index - 1; i >= 0; i --)
        printf("%d", ans[i]);
    if (m == 0) printf("%d", 0);    
    printf("\n");
}

By David.K

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

Problem 11150 Cola，愛喝可樂的你

此題為簡單題目一枚，由於商店有著三瓶空瓶可樂換一瓶的活動，所以愛喝可樂的人有福了，正好，你就是那位愛喝可樂的人，而你可以跟你的朋友多借幾瓶空瓶子，再多換幾瓶可樂，但前提是，要有借有還。所以你必須寫一個程式，輸入整數 n，n 為所要買的可樂數，而要輸出你最多能喝到幾瓶可樂。

其實想一想就知道，你能跟朋友借的可樂數最多只一瓶，借兩瓶你絕對還不起，所以我用一個迴圈讓它自己把瓶子數算到 3 瓶以下，再判斷它瓶子數是否剩 2 瓶，若剩 2 瓶，可跟朋友借 1 瓶空瓶，再多換 1 瓶可樂，把這杯可樂喝完，再還這個空瓶給他。寫成如以下程式碼：

int i ,total = n, recode;
for (; n > 2;)
{
    total += n / 3;
    recode = n / 3;
    n = n % 3 + recode;
}  
if (n == 2) total ++;
printf("%d\n", total);

By David.K

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

Problem 974 Kaprekar Numbers，卡布列克數

此題要求出範圍內的卡布列克數。若正整數 X 在 n 進位下的平方可以分割為二個數字，而這二個數字相加後恰等於 X，那麼 X 就是 n 進位下的卡布列克數，但這兩個數字其中一個數字不得為 0。

依據以上卡布列克數解說，加上這範圍不超過 40000，所以要有一些特殊條件控制分割的方法，以下為關鍵程式碼：

isPut = 0;
for (j = s; j <= e; j ++)
{
    recode = j * j;
    mul = 10;
    for (k = 0; k < 4; k++)
    {
        g = 0;
        while (recode / mul != 0 && recode % mul != 0)
        {
            if (recode / mul + recode % mul == j)
            {
                printf("%d\n",j);
                isPut = 1;
                g = 1;
                break;       
            }
            mul *= 10;
        }
        if (g) break;
        mul *= 10;
    }
}
if (!isPut)
   printf("no kaprekar numbers\n");

(註：s 為開始範圍，e 為結束範圍)

By David.K

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

Problem 344 Roman Digititis，羅馬數字

此題是輸入一個數字 n，要你算出以羅馬數字表示從 1 ~ n 內，共出現幾次 i、v、x、l、c。

首先還是設計一個結構(struct)，順便將這結構宣告 101 個的陣列：

struct RomanNum
{
   int i;
   int v;
   int x;
   int l;
   int c;       
};

struct RomanNum RN[101];

接著我們可以用函式來建立陣列在整個羅馬數字出現的次數，因為羅馬數字最大範圍只到100，但整數40、90排列比較特殊，所以要優先處理，寫成如以下程式碼：

void adder(int index, int n)
{
     if (n == 0) return;
     if (n >= 40 && n <= 49)
         RN[index].l ++, RN[index].x ++, n -= 40;     
     if (n >= 90 && n <= 99)
         RN[index].c ++, RN[index].x ++, n -= 90;
     if (n % 10 == 4)
         RN[index].v ++, RN[index].i ++, n -= 4;     
     if (n % 10 == 9)
         RN[index].x ++, RN[index].i ++, n -= 9;
     if (n / 100 > 0)
         RN[index].c += (n/100), n %= 100;
     if (n / 50 > 0)
         RN[index].l += (n/50), n %= 50;
     if (n / 10 > 0)
         RN[index].x += (n/10), n %= 10;
     if (n / 5 > 0)
         RN[index].v += (n/5), n %= 5;
     if (n / 1 > 0)
         RN[index].i += (n/1), n %= 1;                    
}

以上函式的 index 代表陣列索引值，而 n 則為欲分解的羅馬數字(以10進位傳入)。我們可以在主程式內寫一迴圈，將上一陣列索引羅馬數字的總和傳遞給下一陣列索引羅馬數字，再進行累加：

for (i = 0; i < 100; i ++)
{
    adder(i, i + 1);
    RN[i + 1].i = RN[i].i, RN[i + 1].v = RN[i].v, 
    RN[i + 1].x = RN[i].x;
    RN[i + 1].l = RN[i].l, RN[i + 1].c = RN[i].c;  
}

如此一來，只須對應所輸入的值，將陣列索引印出即可：

while (1)
{
    scanf("%d", &n);
    if (n == 0) break;
    n -= 1;
    printf("%d: %d i, %d v, %d x, %d l, %d c\n", n+1, 
            RN[n].i, RN[n].v, RN[n].x, RN[n].l, RN[n].c);  
}

By David.K

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

Problem 253 Cube painting，立方體旋轉

這題是給你兩塊立方體，而這兩塊立方體各面塗上顏色，問說第一塊的立方體旋轉後會不會與第二塊的各個面顏色相同。以下是顏色對照圖：

從上圖得知，輸入的六種顏色以這種方式排序。以輸入例子 rbgggrrggbgr 來說，第一塊立方體各面顏色為 rbgggr，而第二塊立方體各面顏色為 rggbgr。當比對這兩個立方體要有一點概念，就是當它相對的面與另一塊立方體相對的面比較後(所謂相對的面就是指上圖的 1 與 6、2 與 5、3 與 4)，若相同，則相同；若不同，則不同。以下為關鍵程式碼：

while (gets(str))
{
    int isTurn = 0, i, j;
    c[0].ch1 = str[0], c[0].ch2 = str[5], c[0].isComp = 0;
    c[1].ch1 = str[1], c[1].ch2 = str[4], c[1].isComp = 0;
    c[2].ch1 = str[2], c[2].ch2 = str[3], c[2].isComp = 0;
    c[3].ch1 = str[6], c[3].ch2 = str[11], c[3].isComp = 0;
    c[4].ch1 = str[7], c[4].ch2 = str[10], c[4].isComp = 0;
    c[5].ch1 = str[8], c[5].ch2 = str[9], c[5].isComp = 0;
    for (i = 0; i < 3; i ++)
        for (j = 3; j < 6; j ++)
        {
            if (c[i].isComp == 0 && c[j].isComp == 0)
            {
                if (c[i].ch1 == c[j].ch1 && c[i].ch2 == c[j].ch2 ||
                    c[i].ch1 == c[j].ch2 && c[i].ch2 == c[j].ch1)
                {
                    c[i].isComp = 1, c[j].isComp = 1;
                    break;
                }
            }
        }
    for (i = 0; i < 6; i ++)
        if (c[i].isComp == 0)
           isTurn = 1;
    if (isTurn)
        printf("FALSE\n");
    else printf("TRUE\n");                     
}

以下是結構程式碼：

struct Cube
{
    char ch1;
    char ch2;
    int isComp;
};

struct Cube c[6]; 

By David.K

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

Problem 575 Skew Binary，2n - 1 進位

此題為要求輸入一個2ⁿ - 1的進位轉 10 進位的題目。

一開始我先創造一個 1 ~ 2³¹ - 1 的位數陣列 binary，依次擺入各位數所需乘的數值：

unsigned int binary[31], total;

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

則在程式一開始須先呼叫 create() 函式，讓它建構出來，再讀入字串，倒著擺入 rev 陣列：

scanf("%s", str);
if (str[0] == '0') break;  
total = 0;
for (i = 0; i < strlen(str); i ++)
    rev[i] = str[strlen(str) - i - 1] - '0';

最後再將 rev 陣列與 binary 陣列互相相乘累加即可：

for (i = 0; i < strlen(str); i ++)
    total += rev[i] * binary[i];
    printf("%ld\n", total);

By David.K

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

Problem 568 Just the Facts，階乘的尾數

此題是要求出 n! 從右邊算來最後一個不是 0 的數字。

我們要建立一個 10000 格的整數陣列，以放每一個階乘的結果。但是如果只存個位數，可能在數字上會有誤差，所以每次的結果，都以 10000 以下的數字來存放，以下為關鍵程式碼：

int Factorial[10001] = {0};
Factorial[0] = 1;
for (i = 1; i <= 10000; i ++)
{
    Factorial[i] = Factorial[i - 1] * i;
    while (Factorial[i] % 10 == 0)
        Factorial[i] /= 10;
    Factorial[i] %= 100000;    
}

建立表後，只須將內容值 mod 10 後印出即可：

while (scanf("%d", &n) == 1)
          printf("%5d -> %d\n", n, Factorial[n]%10);

By David.K

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

Problem 340 Master-Mind Hints，猜數字

此題就是我們平常在玩的猜數字遊戲，讀入一個 n 值後，n 為數字的數量，如果 n = 0，則程式結束；而再接下來第一行會讀到 n 個整數，那是此測試例子的答案，再接下來所輸入的 n 個整數，只要全部都是 0，則此測試例子結束；反之，需輸出它與答案比對的結果。

首先，宣告一個結構，而結構內容有一個數字，與一個使否有比對過的值：

struct Ans
{
    int ansInt;
    int isComp;   
};

所以只須讀入 n 值，即可宣告一個結構陣列 a[n]，存放答案：

struct Ans a[n];
for (i = 0; i < n; i ++)
{
    scanf("%d", &m);
    a[i].ansInt = m;
    a[i].isComp = 0;
}

則也要宣告一個結構陣列 b[n]，以接受測試資料，而在比對過程之中，需先將相同位置的數值比對一遍，如有比對成功，則將雙方的 isComp 改成 1，而比對成功的總數值為 A 的值。接著再將 b 內沒比對過的值再與 a 比對，如果有比對成功，也是將雙方的 isComp 改成 1，而比對成功的總數值則為 B 的值：

isZero = 1, A = 0, B = 0;
for (i = 0; i < n; i ++)
{
    scanf("%d", &m);
    if (m != 0) isZero = 0;
    b[i].ansInt = m;
    b[i].isComp = 0;
    a[i].isComp = 0;
}
for (i = 0; i < n; i ++)
    if (a[i].ansInt == b[i].ansInt)
       A ++, a[i].isComp = 1, b[i].isComp = 1;
for (i = 0; i < n; i ++)
    for (j = 0; j < n; j ++)
    {
        if (i != j && a[i].isComp == 0 && b[j].isComp == 0 && a[i].ansInt == b[j].ansInt)
           B ++, a[i].isComp = 1, b[j].isComp = 1;
    }          
if (isZero) break;
else printf("    (%d,%d)\n", A, B);

By David.K

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

350 Pseudo-Random Numbers，循環長度

這題有點類似循環小數的做法，也是要紀錄它的餘數是否出現過，並且紀錄餘數的長度，有出現過，就將它在上一次出現長度相減後，便能算出它的循環長度。

首先可以先宣告兩個長度為10000的整數陣列(因為每個數最大不超過9999)：

int isTrue[10000] = {0}, len[10000];

而 isTrue 陣列是對應餘數使否有出現過，len 陣列是紀錄每個餘數的出現長度，則只須持續使用 (Z * L + I) % M 即可，一旦判斷出有出現過的餘數，即跳出迴圈，輸出長度：

int count = 0;
while (!isTrue[L])
{
    isTrue[L] = 1, len[L] = count ++;  
    L = PseRand(Z, I, M, L);  
}
printf("%d\n", count - len[L]);

(註：PseRand() 函式將四個數丟入後，運算 (Z * L + I) % M 後回傳 L 值)
By David.K

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

Problem 944 Happy Numbers

此題輸入兩個數字後，判斷這兩數之間有哪些數是Happy Number以及這些Happy Number的長度為多少即可。

以下為關鍵程式碼：

int isHappyNumber(int n)
{
    int i, len = 1, sum = 0, recode[50];
    
    if (n == 1) return len;
    while (sum != 1)
    {
        recode[len ++] = n;
        sum = 0;
        for (i = 10; (n / i) != 0 || (n % i) != 0; )
        {
            sum += (n % i) * (n % i);
            n /= i;
        } 
        n = sum;
        for (i = 0; i < len; i ++)
            if (recode[i] == sum)
               return 0;       
    }
    return len;
}

則主程式內只須這樣寫：

for (k = i; k <= j; k++)
if (isHappyNumber(k))
   printf("%d %d\n", k, isHappyNumber(k));

By David.K

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

Problem 375 Inscribed Circles and Isosceles Triangles，連續內切圓

以下為此題參考圖片。

此題只需求到內切圓半徑小於 0.000001 即可停止，但首先必須先將第一個半徑求出來，用B/2、H 求斜邊 SL，而內切圓半徑公式為 2 * S / (a+b+c)(S 為面積)，則半徑求法寫成程式：

cycleLen = 1e-12;
scanf("%lf %lf", &B, &H);
B += 1e-15; H += 1e-15; 
SL = (double)sqrt( (H*H) + (B*B/4) );
area = B * H / 2;
r = 2 * area / (SL+SL+B);

而下一個內切圓的半徑 r₁，只需用比例法即可寫出，H : H-2r = r : r₁，則 r₁ = (H-2r)/H*r。用以上觀念寫成程式碼：

while (r >= 0.000001)
{
    cycleLen += 2 * r * PI;  
    HSub2R = H - 2 * r;
    r *= HSub2R / H;
    H = HSub2R;
}

最後把 cycleLen 使用 %13.6lf 印出即可。
By David.K

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

Problem 382 Perfection，完美數

此題輸入一 n 值，求出此 n 值是否為完美數，而完美數則是將數值所有的因數(不包含本身)相加後，看與原本數值比較大小，若相等即為完美數；若因數總和比較大，則為 ABUNDANT 數；若因數總和比較小，則為 DEFICIENT 數。

舉個例子算出因數總和。數值為 12，12 = 2²*3¹，因數 2 有0、1、2次方項，而 3 有0、1次方項。則(2⁰+2¹+2²) * (3⁰+3¹) = 28，但因為 28 是所有因數總和，所以須減去本身數值，則結果為 16，與 12 相較之下，數值 12 為 ABUNDANT 數。

以下為此題關鍵程式碼：

while (1)
{
    scanf("%d", &input[len]);
    len ++;
    if (input[len - 1] == 0) break;
}
printf("PERFECTION OUTPUT\n");
for (j = 0; j < len - 1; j ++)
{
    n = input[j];
    int total = 1, n1 = n;
    for( i = 2 ; i < n1; i++ )
    {
        int isFactor = 0, add = 1, count = 1;
        while ( n % i == 0 && n != 0)
        {
            n /= i;  
            add += pow(i, count);
            count ++;
            isFactor = 1;
        }
        if (isFactor)
           total *= add;
    }
    if (total - n1 < n1)
       printf("%5d  DEFICIENT\n", n1);
    else if (total - n1 == n1)
       printf("%5d  PERFECT\n", n1);
    else
       printf("%5d  ABUNDANT\n", n1);    
}
printf("END OF OUTPUT\n");

By David.K

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

Problem 389 Basically Speaking，位元轉換

此題需使用 %s %d %d 以str、sc、ec接收資料，字串為初始的 sc 進位，要將它轉成 ec 進位。

當讀入字串後，將它轉成 10 進位：

int i, j, length, num = 0;
length = strlen(str);
for (i = length - 1; i >= 0; i --)
    intArray[length - 1 - i] = charToInt(str[i]);
for (i = 0, j = 1; i < length; i ++, j *= sc)    
    num += intArray[i] * j;

其中有一個 int charToInt(char) 函式，可以將 char 轉為 int，也要寫一個char intToChar(int)的函式，等等會用到：

int charToInt(char hex)
{
    if (hex == 'A') return 10;
    else if (hex == 'B') return 11;
    else if (hex == 'C') return 12;
    else if (hex == 'D') return 13;
    else if (hex == 'E') return 14;
    else if (hex == 'F') return 15;
    else return (hex - '0');
}

char intToChar(int i)
{
    if (i == 10) return 'A';
    else if (i == 11) return 'B';
    else if (i == 12) return 'C';
    else if (i == 13) return 'D';
    else if (i == 14) return 'E';
    else if (i == 15) return 'F';
    else return (i + '0');
}

再來需構寫一個印出的函式，首先需判斷此數除以 ec⁷ 是否大於 0，若大於 0，則會超出顯示器顯示，若不大於 0，則以 ec⁶、ec⁵、....等累除，但記得需要靠右 7 隔，所以某些地方需要印出空白：

void print(int num)
{
    int i, j, isPut = 0;
    if (num == 0) printf("0");
    else if (num / pow(ec, 7) > 0) printf("ERROR");
    else
    {
        for (i = pow(ec, 6); i >= 1; i /= ec)
        {
            if (isPut)  printf("%c", intToChar(num / i)), num %= i;
            else if (num / i > 0 && !isPut) 
                printf("%c", intToChar(num / i)), num %= i, isPut = 1;
            else printf(" ");    
        }
    }
    printf("\n");
}

最後只需再主程式呼叫 print(int) 即可。
By David.K

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

Problem 392 Polynomial Showdown，多項式

此題輸入九個數，須降冪印出它的多項式。

這題只需判斷它是否為第一次印出，或者是否為一次方項、常數項。

以下為關鍵程式碼：

int isPut = 0, i;
for (i = 0; i < 9; i ++)
{
    if (isPut && pow[i] != 0)
    {
         if (pow[i] < 0) printf(" - ");
         else printf(" + ");
         pow[i] = pow[i] < 0 ? -1 * pow[i]: pow[i];
         if (pow[i] != 1) printf("%d", pow[i]);
         else if (i == 8) printf("%d", pow[i]);
         if (i == 7) printf("x");
         else if (i != 8) printf("x^%d", 9 - i - 1);                 
    }
    else if (!isPut && pow[i] != 0)
    {
         if (pow[i] < 0) printf("-");
         pow[i] = pow[i] < 0 ? -1 * pow[i]: pow[i];
         if (pow[i] != 1) printf("%d", pow[i]);
         else if (i == 8) printf("%d", pow[i]);
         if (i == 7) printf("x");
         else if (i != 8) printf("x^%d", 9 - i - 1); 
         isPut = 1;    
    }
}
if (!isPut) printf("0");
printf("\n");      

By David.K

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

Problem 311 Packets，最少包裝箱

這題是考你的邏輯以及空間概念，其實不難，以下會有分析。

我是先宣告兩個整數陣列，residual[6], packets[6];，分別存放各產品的多餘空間數以及使用空間數。再來讀入所有產品的使用空間數，並且判斷所有產品是否為 0：

int i, isZero = 1, total = 0;
for (i = 0; i < 6; i ++)
{
    scanf("%d", &packets[i]);
    residual[i] = 0;
    if (packets[i] != 0)
       isZero = 0;
}
if (isZero) break;

接下來就是重點了，我們必須將 6*6 的箱子妥善分配空間，方能使所耗箱子量減到最低。

在讀入所有產品數量後，可以想見，規格 6*6 的產品必須以一個箱子來包裝，所以箱子總數就必須先加上這個數量：

total += packets[5];

規格 5*5 的產品也必須以一個箱子來包裝，但是會產生 11 個規格 1*1 產品的空間，如以下表格顯示：

X	X	X	X	X	O
X	X	X	X	X	O
X	X	X	X	X	O
X	X	X	X	X	O
X	X	X	X	X	O
O	O	O	O	O	O

所以程式可以這樣寫：

total += packets[4];
residual[0] += packets[4] * 11;

規格 4*4 的產品必須以一個箱子來包裝，但是會產生 5 個規格 2*2 產品的空間。(以下就不提供表格，自行畫圖想像)，所以：

total += packets[3];
residual[1] += packets[3] * 5;

規格 3*3 的產品以 4 個為一箱來包裝。若有剩餘 1 個規格為 3*3 的產品，則會產生 5 個規格 2*2 產品的空間和 7 個規格 1*1 產品的空間；若有剩餘 2 個規格為 3*3 的產品，則會產生 3 個規格 2*2 產品的空間和 6 個規格 1*1 產品的空間；若有剩餘 3 個規格為 3*3 的產品，則會產生 1 個規格 2*2 產品的空間和 5 個規格 1*1 產品的空間，以此觀念寫成以下程式：

total += packets[2] / 4;
packets[2] %= 4, residual[2] = packets[2];
if (residual[2] == 1)
   residual[2] = 0, residual[0] += 7, residual[1] += 5, total ++;
else if (residual[2] == 2)
   residual[2] = 0, residual[0] += 6, residual[1] += 3, total ++;
else if (residual[2] == 3)
   residual[2] = 0, residual[0] += 5, residual[1] += 1, total ++;

接下來只需將 2*2 多餘空間去和使用空間數比較大小，若多餘空間數比較大，則將多餘空間數轉移給規格 1*1 產品使用；若使用空間比較大，則視它能裝幾箱大小，再把多餘的位置轉移給規格 1*1 的產品使用：

if (residual[1] >= packets[1])
   residual[1] -= packets[1], packets[1] = 0;
else
   packets[1] -= residual[1], residual[1] = 0;
total += packets[1] / 9;
packets[1] %= 9;
if (packets[1] > 0)
   residual[0] += 36 - packets[1] * 4, packets[1] = 0, total ++; 
else residual[0] += residual[1] * 4, residual[1] = 0;

而規格 1*1 產品就不需再轉移給空間更小的產品了，只需老老實實的算出它還能裝幾箱大小，如有剩餘，就多一箱：

if (residual[0] >= packets[0])
   residual[0] -= packets[0], packets[0] = 0;
else
   packets[0] -= residual[0], residual[0] = 0;
total += packets[0] / 36;
packets[0] %= 36;
if (packets[0] > 0)
   total ++;

最後只需將total印出即可。
By David.K

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

Problem 455 Periodic Strings，字串的最小週期

此題是要找出字串的最小週期。例如 abcabc 有兩種週期，一由子字串 abc 重複 2 次(週期為 3)，二由子字串 abcabc 重複 1 次(週期為 6)。在這例子中，要輸出 3，因為它為字串的最小週期。

稍微想一下，可以知道只要是字串長度的因數，都有可能是字串的週期。所以可以寫一個函式，傳入字串與字串的因數，去找尋與它相對位置互相比較是否相等，若不相等，則不為此字串週期；若皆相等，則為子字串週期。

以下為此題關鍵函式：

int strPeriod(char str[], int j)
{
    int i;
    for (i = j; i < strlen(str); i ++)
        if (str[i] != str[i % j]) break;
    if (i == strlen(str)) return 1;
    else return 0;    
}

而主程式只需如此呼叫函式：

gets(str);
length = strlen(str);
for (j = 1; j < length; j ++)
{
    if (length % j == 0)
        if (strPeriod(str, j) == 1)
            break;
}
printf("%d\n", j);

此題最需注意的地方就是輸出的格式，因為格式是 Online Judge 最 GY 的地方，多一個空白或換行都不行，所以要多試幾次。

By David.K

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

Problem 195 Anagram，排列組合

此題只須將字串所有可能的排序，由小到大排列出來。

首先，宣告一個陣列，並建構一函式比較字元大小：

#define MAXLEN 35

char str[MAXLEN];
char compStr[] = {'A','a','B','b','C','c','D','d','E','e','F','f','G','g','H','h','I','i','J','j'
,'K','k','L','l','M','m','N','n','O','o','P','p','Q','q','R','r','S','s','T','t'
                 ,'U','u','V','v','W','w','X','x','Y','y','Z','z'};

int comp(char ch1, char ch2)
{
    int i, ch1i, ch2i;
    for (i = 0; i < strlen(compStr); i ++)
        if (ch1 == compStr[i]) ch1i = i;
    for (i = 0; i < strlen(compStr); i ++)
        if (ch2 == compStr[i]) ch2i = i;
    if (ch1i < ch2i) return 1;
    else return 0;    
}

再使用Problem 146上函式判斷是否有下一次的字串排序，一直判斷到底即可。但重點是你須將輸入字串做排序：

void sort()
{
    int i, j;
    char ch;
    for (i = strlen(str) - 1; i >= 0; i--)
        for (j = 0; j < strlen(str); j++)
            if (comp(str[strlen(str) - j - 1], str[i]) )
               ch = str[strlen(str) - j - 1], 
               str[strlen(str) - j - 1] = str[i], str[i] = ch; 
}

再將排序函式稍做修改：

int next_permutation()
{
    int i, j, k;
    int length;
    length = strlen(str);
    for(i = length - 1;i > 0 ; --i)
        if(comp(str[i-1], str[i])) break;
    j = i;
    if(j == 0) return 0;
    for(i = length - 1;i > 0; --i)
        if(comp(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;
}

而主程式只須用一無窮迴圈印出即可：

int n, i;
scanf("%d", &n);
getchar();
for (i = 0; i < n; i ++)
{
    gets(str);
    sort();
    printf("%s\n", str);
    while (next_permutation())
        printf("%s\n", str);
             
}

By David.K

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

Problem 146 ID Codes，識別碼

此題需要將輸入字串依照字串排序，印出它下一次會出現的字串排序。

舉個例子，對於abc字串的排序一共有六種，分別是：
abc
acb
bac
bca
cab
cba
當我輸入 cab 時，需要輸出 cba，也就是它下一次會出現的字串排序，可當我輸入 cba 時，因為它已是排序結尾，所以要輸出 No Successor。

對於這一題 C++ 可以使用 Algorithm 的 next_permutation() 方能輕易解出，可我們網站標榜「C的解題」，總不能掛羊頭賣狗肉吧！所以我又上網找了一些關於這題的演算法，因此寫出以下函式：

#define MAXLEN 60

char str[MAXLEN];

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;
}

以上程式碼參考來源

以上函式可以方便找到下一次出現的字串排序，再接著只需判斷它是否有下一次的字串，將它印出即可。
By David.K

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

Problem 424 Integer Inquiry，大數加法

這題就是簡單的大數加法，只要會大數加法，很輕易就寫出來了。

先創建一個結構(struct)，AN1 和 AN2，AN1為累加結果，AN2讀入每次輸入的大數並與AN1相加：

#define NUMLEN 200

struct AddNum
{
    int num[NUMLEN];
    int length;
};

struct AddNum AN1, AN2;
char numStr[101];

再讀入字串並反轉為整數陣列(integer array)：

gets(numStr);
if (numStr[0] == '0') break;
AN2.length = strlen(numStr) - 1;
for (i = AN2.length, j = 0; i >= 0; i --, j ++)
    AN2.num[j] = numStr[i] - '0'; 
for (i = 0; i < NUMLEN; i ++)
{
    AN1.num[i] += AN2.num[i];
    if (AN1.num[i] >= 10)
       AN1.num[i + 1] ++, AN1.num[i] %= 10;
}

最後AN1和AN2相加：

for (i = 0; i < NUMLEN; i ++)
{
    AN1.num[i] += AN2.num[i];
    if (AN1.num[i] >= 10)
       AN1.num[i + 1] ++, AN1.num[i] %= 10;
}

再將結果印出就可以了。
By David.K

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

Problem 495 Fibonacci Freeze，大數費氏級數

此題為大數題，只需用到大數中的加法就可以了。

還是不例外，創建一個結構(struct)來使用：

#define LEN 5001
#define NUMLEN 1050

struct FibNum
{
    int num[NUMLEN];
    int length;
};

struct FibNum FN[LEN];

將第0個索引的num設定為0，第1個索引的num設定為1：

FN[0].num[0] = 0, FN[0].length = 0, 
FN[1].num[0] = 1, FN[1].length = 0;

接著利用Fib(0) = 0、Fib(1) = 1，當n > 2，Fib(n) = Fib(n-1) + Fib(n-2)的觀念，用大數加法算出到5000之內的Fib值，順便紀錄長度：

int i, j, k, n;

for (i = 2; i < LEN; i ++)
{
     for (j = 0; j < NUMLEN; j ++)
     {
         FN[i].num[j] += FN[i - 1].num[j] + FN[i - 2].num[j];
         if (FN[i].num[j] >= 10)
            FN[i].num[j + 1] ++, FN[i].num[j] %= 10;
     }
     for (j = NUMLEN - 1; ; j--)
         if (FN[i].num[j] > 0)
            break;
     FN[i].length = j ;       
}

最後，只須對應輸入值將大數取出就行了：

while (1)
{
     if (scanf("%d", &n) < 1) break;
     printf("The Fibonacci number for %d is ", n);
     for (i = FN[n].length ;i >= 0 ; i--)
          printf("%d", FN[n].num[i]);
     printf("\n");
}

不過成效不太好，用了0.368秒，我相信會有更好的方法。
By David.K

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