---
tags: Zerojudge
---
# c110: 00311 - Packets

## Problem Statement

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

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

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

### 範例輸入 #1

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

### 範例輸出 #1

2
1
3
86
231
137
115
219

## 解題思路

**原則：從最大的箱子開始統計**

### 變數說明
> box[n] : n*n的箱子數量
> num_box : 箱子的總數量

### 解題步驟
1. 處理6*6的箱子，因為每一個都是塞滿，num_box直接加上box[6]

    if(i == 5) //zero-indexed
    {
        box_num += box[i];
    }

2. 處理 5 * 5 的箱子，每一個大箱子可放一個 5 * 5的箱子，剩餘36-25 = 11格可放1*1的小箱子

    else if(i == 4) //zero-indexed
    {
        box_num += box[i];
        remains = box[i]*11;
        box[0]-=remains;                 
    }

3. 處理 4 * 4 的箱子，每一個大箱子可放一個 4 * 4的箱子，剩餘36-16 = 20 格可放 1 *1 或 2 * 2的小箱子

> 技巧：可以先全部塞2*2的進去，多扣的最後再用 1 * 1 的補回來（ 4個1 * 1換 1 個2 * 2 )
> 所以box[2]容許是負的！


    else if(i == 3)
    {
        box_num += box[i];
        remains = box[i]*5;
        box[1]-=remains;
    }

4. 處理 3 * 3 的箱子，需分情形討論
> 一個大箱子可以塞四個小箱子

將box[4]除以4：可以裝滿的箱子數 -> 存入num_box

再討論**box[4]取4的餘數**

| 情形 | 圖示 | 操作 |
| ---- |:---------------------------------------------:|:-----------------------------:|
| 餘 3 |  | 可放 5 * (2*2) 及 7 * (1 * 1) |
| 餘 2 |  | 可放 3 * (2*2) 及 6 * (1 * 1) |
| 餘 1 |  | 可放 1 * (2*2) 及 5 * (1 * 1) |
| 餘 0 | 皆已裝滿，不需要再操作 | |

    else if(i == 2)
    {
        int tmp = box[i]/4;
        int tmp2 = box[i]%4;
        box_num += tmp;
        if(tmp2 != 0)
        {
            box_num += 1;
            if(tmp2 == 1)
            {
                box[1] -=5;
                box[0] -=7;
            }
            else if(tmp2 == 2)
            {
                box[1] -=3;
                box[0] -=6;       
            }
            else if(tmp2 == 3)
            {
                box[1] -=1;
                box[0] -=5;
            }           
        }
      
    }