Packets Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 38381 Accepted: 12817 Description A factory produces products packed in square packets of the same height h and of the sizes 1*1, 2*2, 3*3, 4*4, 5*5, 6*6. These products are always delivered to customers in the square parcels of the same height h as the products have and of the size 6*6. Because of the expenses it is the interest of the factory as well as of the customer to minimize the number of parcels necessary to deliver the ordered products from the factory to the customer. A good program solving the problem of finding the minimal number of parcels necessary to deliver the given products according to an order would save a lot of money. You are asked to make such a program. Input The input file consists of several lines specifying orders. Each line specifies one order. Orders are described by six integers separated by one space representing successively the number of packets of individual size from the smallest size 1*1 to the biggest size 6*6. The end of the input file is indicated by the line containing six zeros. Output The output file contains one line for each line in the input file. This line contains the minimal number of parcels into which the order from the corresponding line of the input file can be packed. There is no line in the output 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 Source Central Europe 1996 大致題意： 一個工廠制造的產品形狀都是長方體盒子，它們的高度都是 h，長和寬都相等，一共有六個型號，分別為1*1, 2*2, 3*3, 4*4, 5*5, 6*6。 這些產品通常使用一個 6*6*h 的長方體箱子包裝然後郵寄給客戶。因為郵費很貴，所以工廠要想方設法的減小每個訂單運送時的箱子數量BoxNum。 解題思路： 由於盒子和箱子的高均為h，因此只需考慮底面積的空間。 6*6的盒子，每個盒子獨占一個箱子。 5*5的盒子，每個盒子放入一個箱子，該箱子的剩余空間允許放入的最大尺寸為1*1，且最多放11個。 4*4的盒子，每個盒子放入一個箱子，該箱子的剩余空間允許放入的最大尺寸為2*2。 3*3的盒子，每4個剛好獨占一個箱子，不足4個3*3的，剩下空間由2*2和1*2填充。 2*2的盒子和1*1的盒子主要用於填充其他箱子的剩余空間，填充後的多余部分才開辟新箱子裝填。 [cpp] #include<iostream> #include<cstdio> using namespace std; int main() { int p[4]={0,5,3,1},a[10]; //3×3的放完後，余下的放入新箱子後，還可以放幾個2×2的包裹（下標對應余數） while(1) { int sum=0; for(int i=1;i<=6;i++) { scanf("%d",&a[i]); sum+=a[i]; } if(sum==0) break; sum=0; sum=a[4]+a[5]+a[6]+a[3]/4; if(a[3]%4!=0) sum++; int need2=a[4]*5+p[a[3]%4]; if(need2<a[2]) { sum+=(a[2]-need2)/9; if((a[2]-need2)%9!=0) sum++; } int need1=sum*36-a[2]*4-a[3]*9-a[4]*16-a[5]*25-a[6]*36; //需要的1×1的個數，即所有箱子的總面積減去後5種盒子的總面積 if(need1<a[1]) { sum+=(a[1]-need1)/36; if((a[1]-need1)%36!=0) sum++; } printf("%d\n",sum); } return 0; }
