Problem Solving►UVa

UVa 311 - Packets

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址
無需考慮高度。

Solution

可以分成以下情形:

  • 6x6 : 1 個箱子
  • 5x5 : 1 個箱子 會剩餘 11 個 1x1
  • 4x4 : 1 個箱子 會剩餘 5 個 2x2
  • 3x3 : 1一個箱子最多可放 4 個， 依照放入的不同，會剩餘不同數量的 2x2 和 1x1
  • 2x2 : 1 個箱子最多可放 9 個
  • 1x1 : 1 個箱子最多可放 36 個

從大的開始放。
記得處理當 2x2 放完還有剩空間時，可以將 2x2 的換成 4 個 1x1 的。

Code

UVa 311
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<cstdio>

int main()
{
    int size[7];
    while (scanf("%d", &size[1]))
    {
        int i, temp = size[1];
        for (i = 2; i <= 6; i++)
        {
            scanf("%d", &size[i]);
            temp += size[i];
        }

        if (!temp)
            break;

        int box = size[6]+size[5]+size[4];//6x6+5x5+4x4
        size[1] -= 11 * size[5];//5x5+11*(1x1)
        if (size[1] < 0)
            size[1] = 0;

        temp = size[2] - size[4] * 5;//4x4+5*(2x2)
        if (temp < 0)
        {
            temp *= -1;
            if (size[1])//4x4+n*(2x2)+n*(1x1)
                size[1] -= temp * 4;

            size[2] = 0;
        }
        else
            size[2] = temp;

        int temp2 = size[3] / 4;
        box += temp2;//4*(3x3)
        size[3] %= 4;
        if (size[3])
            box++;

        temp = size[2];
        if (size[3])//放完 3x3 剩下的空間
        {
            if (size[2])
            {
                if (size[3] == 1)
                    temp -= 5;
                else if (size[3] == 2)
                    temp -= 3;
                else if (size[3] == 3)
                    temp -= 1;

                if (temp > 0)
                {
                    size[2] = temp;
                    temp = 0;
                }
                else
                {
                    temp *= -1;
                    size[2] = 0;
                }
            }

            if (size[1] > 0)
            {
                if (size[3] == 1)
                    size[1] -= 7;
                else if (size[3] == 2)
                    size[1] -= 6;
                else if (size[3] == 3)
                    size[1] -= 5;
                
                size[1] -= temp * 4;
            }

        }

        if (size[2])//9*(2x2)
        {
            box += size[2] / 9;
            size[2] %= 9;
            if (size[2])
                box++;
        }

        if (size[1] > 0)//剩下的 1x1
        {
            if (size[2])
            {
                size[1] -= 36 - size[2] * 4;
                if (size[1] < 0)
                    size[1] = 0;
            }

            box += size[1] / 36;
            if (size[1] % 36)
                box++;
        }

        printf("%d\n", box);
    }

    return 0;
}