Morris' Blog

2011-08-17 09:17:33Morris

c110. Packets

留言 3 收藏 0 推薦 0

內容：

有一間工廠生產的東西, 被包裝在相同高度 h 的正方形容器內, 但其面積大小分別有:1*1, 2*2, 3*3, 4*4, 5*5, 6*6等六種尺寸。這些產品總是用高度為h，面積為6*6的箱子打包後寄給客戶。因為成本關係，當然希望將客戶所訂購的產品放在最少的箱子裡寄出。請你寫一個程式找出寄送這些產品最少需要多少個箱子，這可以使工廠節省下不少錢。

輸入說明：

每組測試資料一列（就是一份訂單），含有6個整數。分別代表1*1到6*6產品的數目。若此6個整數均為0代表輸入結束。

輸出說明：

對每一組測試資料，輸出寄送這些產品最少需要多少個箱子。

範例輸入：

0 0 4 0 0 1
7 5 1 0 0 0
0 0 0 0 0 3
79 96 94 30 18 14
53 17 12 98 76 54
83 44 47 42 80 3
15 26 13 29 42 40
41 61 36 90 54 66
0 0 0 0 0 0

範例輸出：

提示：

* Luck 貓翻譯

出處：

ACM 311

作法 : Greedy
很明顯地,
5*5 剩餘的空間分配給 1*1
4*4 剩餘的空間分配給 2*2, 1*1
3*3 剩餘的空間分配給 2*2, 1*1
...
/**********************************************************************************/
/* Problem: c110 "Packets" from ACM 311                                          */
/* Language: C                                                                   */
/* Result: AC (4ms, 214KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-08-17 08:48:25                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
main() {
   int t1, t2, t3, t4, t5, t6;
   while(scanf("%d %d %d %d %d %d", &t1, &t2, &t3, &t4, &t5, &t6) == 6) {
       if(t1+t2+t3+t4+t5+t6 == 0) break;
       int Ans = t6, tmp, tmp2;
       Ans += t5;
       t1 -= t5*11;   if(t1 < 0) t1 = 0;
       Ans += t4;
       tmp = t4*20;
       if(t2 >= t4*5)   tmp = 0, t2 -= t4*5;
       else {
           tmp -= t2*4, t2 = 0;
           if(t1 >= tmp)   t1 -= tmp, tmp = 0;
           else   tmp -= t1, t1 = 0;
       }
       Ans += (t3/4), t3 %= 4;
       if(t3) {
           Ans++;
           tmp = 36-t3*9, tmp2 = (3-t3)*2+1;
           if(t2 >= tmp2)   t2 -= tmp2, tmp -= tmp2*4;
           else   tmp -= t2*4, t2 = 0;
           if(t1 >= tmp)   t1 -= tmp, tmp -= t1;
           else   tmp -= t1, t1 = 0;
       }
       Ans += (t2/9), t2 %= 9;
       if(t2) {
           Ans++;
           tmp = 36-t2*4;
           if(t1 >= tmp)   t1 -= tmp, tmp -= t1;
           else   tmp -= t1, t1 = 0;
       }
       Ans += t1/36 + (t1%36!=0);
       printf("%d\n", Ans);
   }
   return 0;
}

上一篇：d190. 11462 - Age Sort (優化重製)

下一篇：c102. Software CRC