95 試題三

實踐大學高雄校區資管系95學年程式設計比賽的試題，這題不會太難，可是要仔細的測試，注意避免輸出負的或是超過180的角度。

題三：

一般的時鐘都有時針和分針兩隻腳，時針每720分鐘走一圈，分針每60分鐘走一圈，走一圈剛好繞360度。這個題目是要讀取一組時間，然後計算出時針與分針的夾角。時間的格式是0:00到12:00，小時數可能為1或2位數，分鐘數總是2位數，00到59之間。輸出角度為0到180之間的值，角度的精確度到千分之一。例如9:00是90.000度，不是-90，也不是270度。

例如，輸入12:00，輸出0.000；輸入9:00，輸出90.000；輸入8:10，輸出175.000。

回到首頁

Problem 256 Quirksome Squares，就是程式設計比賽第二題

程式設計比賽第二題出自於p256，這題也是很容易的題目，在讀取2, 4, 6, 或8之後，程式碼處理如下：

   maxint = 1;
   halfd  = 1;
   for (i=0;i > size;i++)
      maxint *= 10;
   for (i=0;i > size/2;i++)
      halfd *= 10;
   for (i=0; i > maxint; i++) {
      a = i/halfd;
      b = i%halfd;
      if ((a+b)*(a+b)==i)
         printf("%0*d\n",size,i);
   }

其實就用暴力法，一個個算出來，最後的printf可以使用"%0*d來印出適當長度的整數來。

p256 題目連結
回程式設計試題目錄
回ACM題庫目錄
回首頁

Problem 299 Train Swapping，火車對調

P299 是解到目前為止，最不費力的一題，難怪難易等級只有1.0。

只要使用bubble sort就行了，其他長長的故事內容根本就不用理會。

先讀取第一行，題目數量。其次兩行一組，一行先是元素數量，再一行是待排序的陣列。
在 C 語言中，解決動態的方法蠻容易的，程式碼如下：

   int *S;
   S = (int *)malloc(sizeof(int)*n);
   for (j=0; j < n; j++)
      scanf("%d", &S[j]);

這樣就不用煩惱要宣告S[?]陣列，又不知陣列大小。
最後別忘了用free(S);來釋放記憶體喔。

所有第一次試著解ACM程式題組的人，都應該先解這一題，這樣你就會信心大增。

p299 題目連結
ACM 題庫目錄
回到首頁

Problem 10106 Product，大數相乘

p10106就是要計算兩個整數的相乘，只是這兩個整數可以大到250位數。

題目的讀取適用字串來進行。

解題的邏輯是小學的乘法。可是我就是笨笨的做了好一會，才做完。
讀進來的數字從字元轉數字就直接減 48 就可以了。進位的部份只有兩個觀念。
1. 計算這個位數的值，亦即加上進位後去%10。
2.計算這個位數產生的進位值。

為了只用到一個進位變數addOne，所以要借用一下temp來暫存。程式大概如下：

            temp = (ansNum[i] + addOne)%10;
            addOne = (ansNum[i]+addOne)/10;
            ansNum[i] = temp;

p10106 問題連結
ACM 題庫目錄
回到首頁

95 試題二

實踐大學高雄校區資管系95學年程式設計比賽的試題，這題參賽的隊伍幾乎都答對了，可見是個容易的題目，有興趣的人可以試一下。

題二：
3025這個數字有個巧合，如果你將這數字看成字串，將其分為兩半，每一半也都是一個十位數，亦即30和25，則其和平方

(30+25)^2 = 3025

又變成原來的數字了。你的題目是找出這種類似的巧合數字出來，你的程式要讀取一個位數(2、4、6、或8)，然後找出該位數的所有類似巧合的數字。例如4位數，從0000到9999。請注意，0也要算在內，也就是說0001也等於(00+01)^2，也是4位數中的巧合數。例如輸入2時，輸出是
00
01
81

試題二解答
試題目錄
回到首頁

Problem 10105 Polynomial coefficients，多項式係數

這題解的很丟臉，因為根本就不是靠程式才解開。

原來這題根本就是考數學，如果沒有詳細的公式，光靠程式，太難了，本想以程式碼用力的算出來，後來發現資料結構就定不出來。

數學是很重要的，答案公式是

ans = n! / (n1! *n2!*n3!*...*nk!)

就這樣而已。

p10105 問題連結
ACM 題庫目錄
回到首頁

95 試題一：解題

試題一題目連結
試題一可以用暴力法來求解，只是到後來會用到許多的CPU時間。
另外，到了第七組解的時候，整數和將超過int的極限，造成錯誤的答案，所以可以用double來解決這個問題。

#include 
#include 
#define MAX 100000000
int main(void)
{
    double i, j, lsum, rsum;

    lsum = 0;
    rsum = 2;
    i = 2;
    j = 2;
    while (i<100000000) {
        lsum += i-1;
        rsum -= i;
        if (rsum > lsum)
            break;
        while (rsum < lsum) {
            j++;
            rsum += j;
        }
        if (rsum == lsum) {
            printf("%10.0lf%10.0lf\n", i,j);
        }
        i++;
    }
    system("pause");
    return 0;
}

程式設計比賽試題目錄
回到首頁

Problem 108 Maximum Sum，解子矩陣最大總和

題目說來短短的，在一個矩陣中，找一個包含於其中小矩陣，這個小矩陣中的和是最大的。

剛開始，我用了暴力法，從頭到尾，所有可能的小矩形都給他算一下，這樣就一定可以找出哪個矩形的和最小。可是上傳後，居然是超過時間(TLE)，所以這個題目是故意讓你想點辦法來解決的。

我也想不到，看看他網站的提示，原來要建立sum[i][j] 的矩陣，以減少未來計算總和的需求。在後面，如果要計算 R[i][j]到 R[x][y]的矩形的和，只要算

sum[x][y] - sum[i-1][y] - sum[x][j-1] + sum[i-1][j-1];

就行了。

最後完成上傳時，還出現小插曲，有runtime error，原來是宣告short所造成。真是的，幹麻省這一點點記憶體。

p108 問題連結
ACM 題庫目錄
回到首頁

Problem 102 Ecological Bin Packing，回收瓶包裝問題

p102題目剛看有點嚇人，感覺要解一個NP的問題，其實並不會太難。

每一行有9個數字，每三個一箱，分別是brown、green、clear三種顏色瓶子的數量，現在要決定每箱的瓶子顏色，顏色決定後，就必須將箱中非指定顏色的瓶子移走。

你的程式必須決定每箱要定什麼顏色，條件是移動瓶子的數量是最少。

所有只有六種狀況，BCG、BGC、CBG、CGB、GBC、GCB。

要注意最後一行所說的，如果有相同的移動次數，列印出依字母排序的第一組答案。

p102 問題連結
ACM 題庫目錄
回到首頁

95 試題一

實踐大學高雄校區資管系95學年程式設計比賽的試題對初學C者，是個小小的挑戰。

題一：

阿美是個程式設計師，每天早晨都要帶她家的狗出門遛一下，他住在一條長長的街上，每次出門，她隨意地選擇向左或向右走，每次走到街的盡頭，就折返回家。有一次，她發現她右邊住家的門牌號碼累加之後，居然等於她家左邊門牌號碼的累加。這種號碼的現象當然與她的住家門牌號碼與整條街的戶數有關。(整條街由1開始，不分單雙)

你的題目是找出有這種特性的數字組合，亦即門號與戶數，你必須列出十個這樣的數字組合，每個數字佔10個欄寬，向右靠齊。列出六個以內不算分。前三個的答案範例如下：

         6         8
       35        49
      204       288

試題一解答
試題目錄
回到首頁

C 程式設計作業一，選擇邏輯：解題

/* C Programming Project 1 */

#include <stdio.h>
#include <stdlib.h>

int main(void) {
   int adultNum, childNum, rate;
   int adultFee, childFee, totalFee;
   int over3Discount, discountFee;
   while (1) { 
      do {
         printf("輸入平日(1)、晚上(2)或離開(0)：");
         scanf("%d", &rate);
         fflush(stdin);
         if (rate==0)
            exit(0); 
      } while (rate!=1 && rate!=2);
    
      printf("輸入大人數：");
      scanf("%d", &adultNum);
      printf("輸入小孩數：");
      scanf("%d", &childNum);
    
      if (rate==1) {
         adultFee = 268;
         childFee = 120;
      } else {
         adultFee = 368;
         childFee = 150;
      }
      printf("大人 %d 人\n", adultNum);
      printf("小孩 %d 人\n", childNum);

      totalFee = (adultNum*adultFee + childNum*childFee)*1.1; 
      printf("原價 %d 元\n", totalFee); 

      over3Discount = (adultNum+childNum)/3;
      if (over3Discount>0) {
         if (childNum > over3Discount)
            discountFee = over3Discount*childFee*1.1;
         else
            discountFee = ((over3Discount-childNum)*adultFee + childNum*childFee)*1.1;
         totalFee -= discountFee; 
         printf("三人同行方案 折扣 %d 元\n", discountFee);
         printf("三人同行方案 小計 %d 元\n", totalFee); 
      }

      if (childNum+adultNum >= 10) { 
         discountFee = totalFee*0.05;
         totalFee -=  discountFee; 
         printf("十人以上方案 折扣 %d 元\n", discountFee); 
         printf("十人以上方案 小計 %d 元\n", totalFee); 
      } 
      printf("--------------------\n"); 
      printf("總計 %d 元\n\n", totalFee); 
   }
   return 0;
}

作業一題目
回到首頁

C 程式設計作業一，選擇邏輯

作業內容：
貴公司接受顧客委託，修改軟體，該顧客為家庭式日本料理餐廳，平日(星期一至五)中午收費大人 268元，小孩120元，晚上和例假日收費大人 368元，小孩150元，另加10%服務費。
現在該公司為舉辦週年促銷，特推出三人同行，一人免費活動，若第三人可為小孩，則算小孩免費。另外，如果10人以上同行，總價再打95折。
你的任務就是要完成一個發票列印程式的軟體，假設結帳時，平日午、晚間或例假日為已知，你必須提供適當的文字說明介面，以利使用者輸入，方便結帳。
測試方式：
狀況 A1：平日中午，一大一小用餐。
狀況 A2：平日中午，五大一小用餐。
狀況 A3：平日中午，四大用餐。
狀況 A4：平日中午，二大二小用餐。
狀況 A5：平日中午，六大五小用餐。
狀況 B1：平日晚間，一大一小用餐。
狀況 B2：平日晚間，五大一小用餐。
狀況 B3：平日晚間，四大用餐。
狀況 B4：平日晚間，二大二小用餐。
狀況 B5：平日晚間，六大五小用餐。

作業一解答
回到首頁

Problem 101 The Blocks Problem，磚塊問題

剛開始，不太了解題意，後來看到論壇的一段程式，才確定了題目的意思。

move a onto b：表示a和b的上面方塊都必須回到原來的位置，然後將a放在b上面。
move a over b：表示a上面的方塊都必須回到原來的位置，b上面的都不變，然後a放在有b的那一堆上面。
pile a onto b：表示b上面的方塊都必須回到原來的位置，a連著上面的一起都搬到b的上面。
pile a over b：a連著上面的一起都搬到有b的上面，b原來的那堆都不變。

剛開始我還以為要用到動態的陣列宣告，後來發現最多只要25個方塊，整個題目就簡單多了。

其實，我可以使用scanf("%s %d %s %d\n", str1, a, str2, b)的方式來讀取指令，可是我發現時，我已經用strtok的功能來完成指令讀取了。

這個題目對陣列的邏輯可以是個非常有效的訓練。

p101 問題連結
ACM 題庫目錄
回到首頁

Problem 100 The 3n + 1 problem，3n+1 問題

p100是個簡單的問題，他比較詐的地方是，他並沒有說 i 和 j 誰比較大，他給的範例都是前面小、後面大，可是她問題中有提到，要看 i 和 j 之間的每個數，這根本是在玩文字遊戲，所以 j 是有可能小於 i 的，程式碼只要考慮到這個部份就叮、叮、叮、叮，過關了。

p100 問題連結
ACM 題庫目錄
回到首頁