Packets问题

Afactory produces products packed in square packets of the same height h and ofthe sizes 1*1, 2*2, 3*3, 4*4, 5*5, 6*6. These products are always delivered tocustomers in the square parcels of the same height h as the products have andof the size 6*6. Because of the expenses it is the interest of the factory aswell as of the customer to minimize the number of parcels necessary to deliverthe ordered products from the factory to the customer. A good program solvingthe problem of finding the minimal number of parcels necessary to deliver thegiven products according to an order would save a lot of money. You are askedto make such a program.

Input

Theinput file consists of several lines specifying orders. Each line specifies oneorder. Orders are described by six integers separated by one space representingsuccessively the number of packets of individual size from the smallest size1*1 to the biggest size 6*6. The end of the input file is indicated by the linecontaining six zeros.

Output

Theoutput file contains one line for each line in the input file. This linecontains the minimal number of parcels into which the order from thecorresponding line of the input file can be packed. There is no line in theoutput file corresponding to the last “null” line of the input file.

Sample Input

0 0 4 0 0 1

7 5 1 0 0 0

0 0 0 0 0 0

Sample Output

2

1

程序代码：

#include<stdio.h>

#include<stdlib.h>

int main()

{

    int i,flag=1,p[6],n,filltwo,fillone;   /*i表示数组p[]的下标，flag是一个标志，赋初值为1，当输入的都为0时，结束循环，数组p[]用来记录输入的各种规格的产品的个数，n表示需要最少产品的数量，filltwo表示用于填充的2*2的产品的个数，fillone表示用于填充的1*1的产品的个数*/

    int two[4]={0,5,3,1};              //数组two[]表示用于填充3*3的产品所需要2*2的产品的可能的个数

    while(flag)

    {

       for(i=0;i<6;i++)         //for循环，输入的各种规格的产品的个数并记录在数组p[]中

       {

           scanf("%d",&p[i]);       //输入

       }

       if(!p[0]&&!p[1]&&!p[2]&&!p[3]&&!p[4]&&!p[5])  //判断，如果输入的都为0，则flag=0，返回空，结束输入

       {

           flag=0;   

           return NULL;

       }

       n=p[5]+p[4]+p[3]+(p[2]+3)/4;    /*因为6*6、5*5、4*4的产品每一个包装中只能放入一个，3*3的产品每四个可以装满一个并且3*3的产品不用于填充，(p[2]+3)/4就表示所有3*3的产品所需的包装数，所以，所有的6*6、5*5、4*4、3*3的产品所需的包装数为n=p[5]+p[4]+p[3]+(p[2]+3)/4*/

       filltwo=5*p[3]+two[p[2]%4];     /*再将2*2的产品填充到4*4和3*3的产品包装中，每填充一个4*4的产品包装需要5个2*2的产品，填充3*3的产品所需要2*2的产品的个数为数组two[]中相应的值，所以用掉的2*2的产品

的数为filltwo=5*p[3]+two[p[2]%4]*/   

       if(p[1]>filltwo)  //判断，如果2*2的产品的个数大于用于填充的个数，则将剩余的2*2的产品的个数每9个放入一个产品包装中

       {

           n=n+(p[1]-filltwo+8)/9;     //用完所有2*2的产品后需要的包装数n=n+(p[1]-filltwo+8)/9

       }

       fillone=36*n-36*p[5]-25*p[4]-16*p[3]-9*p[2]-4*p[1];     /*填充1*1的产品，需要的个数为用完所有6*6、5*5、4*4、3*3、2*2后的包装总数n的面积减去所有6*6、5*5、4*4、3*3、2*2的产品所占用的面积*/

       if(p[0]>fillone)  //判断，如果1*1的产品的个数大于用于填充的个数，则将剩余的1*1的产品的个数每36个放入一个产品包装中

       {

           n=n+(p[0]-fillone+35)/36;   //用完所有1*1的产品后需要的包装数n=n+(p[0]-fillone+35)/36

       }

       printf("%d\n",n);    //输出结果

    }

    return 0;

}