博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
TOJ 2541: Paper Cutting
阅读量:5794 次
发布时间:2019-06-18

本文共 2767 字,大约阅读时间需要 9 分钟。

2541: Paper Cutting 分享至QQ空间

Time Limit(Common/Java):1000MS/10000MS     Memory Limit:65536KByte
Total Submit: 1            Accepted:1

Description

ACM managers need business cards to present themselves to their customers and partners. After the cards are printed on a large sheet of paper, they are cut with a special cutting machine. Since the machine operation is very expensive, it is necessary to minimize the number of cuts made. Your task is to find the optimal solution to produce the business cards. 

There are several limitations you have to comply with. The cards are always printed in a grid structure of exactly a * b cards. The structure size (number of business cards in a single row and column) is fixed and cannot be changed due to a printing software restrictions. The sheet is always rectangular and its size is fixed. The grid must be perpendicular to the sheet edges, i.e., it can be rotated by 90 degrees only. However, you can exchange the meaning of rows and columns and place the cards into any position on the sheet, they can even touch the paper edges. 
For instance, assume the card size is 3 * 4 cm, and the grid size 1 * 2 cards. The four possible orientations of the grid are depicted in the following figure. The minimum paper size needed for each of them is stated. 

The cutting machine used to cut the cards is able to make an arbitrary long continuous cut. The cut must run through the whole piece of the paper, it cannot stop in the middle. Only one free piece of paper can be cut at once -- you cannot stack pieces of paper onto each other, nor place them beside each other to save cuts.

 

Input

The input consists of several test cases. Each of them is specified by six positive integer numbers, A,B,C,D,E,F, on one line separated by a space. The numbers are: 

A and B are the size of a rectangular grid, 1 <= A,B <= 1 000, 
C and D are the dimensions of a card in cms, 1 <= C,D <= 1 000, and 
E and F are the dimensions of a paper sheet in cms, 1 <= E,F <= 1 000 000. 
The input is terminated by a line containing six zeros.

Output

For each of the test cases, output a single line. The line should contain the text: "The minimum number of cuts is X.", where X is the minimal number of cuts required. If it is not possible to fit the card grid onto the sheet, output the sentence "The paper is too small." instead.

Sample Input

 

Sample Output

 

Source

Tag

要切一种卡片 纸张大小事px,py格子大小gx,gy 卡片要cx,xy;于是每次就要切出gx*gy个大小为cx*cy的卡片 问最少切几次关键是:1:一次只能切连续,不能在中间中断 故只能一横或一竖切下来2:每次只能切连在一起的纸 若你之前被切开的则不能一起切 当然纸张更不能折叠来切(观察sample就可以知道了,然后对于大小为n*m的格子只要切n*m-1次就行了当然还要再检验一下边角需不需要切) 枚举所有情况啊
#include
int a,b,c,d,e,f;const int INF=1<<30;int la(int w,int x,int y,int z){ if(w*y>e||x*z>f)return INF; return w*x-1+(w*y

 

转载于:https://www.cnblogs.com/BobHuang/p/7663512.html

你可能感兴趣的文章
大学课程能给我们带来什么?——“我们能从大学得到什么”系列之三
查看>>
webdis实现Redis的http接口及多数据格式共享 [含json,restful]
查看>>
网站另类推广玩法心得
查看>>
直播答题APP撒币背后,这些行业可能被革命!
查看>>
objective-c Foundation kit
查看>>
小企鹅输入法 安装 设置 支持中文 for ubuntu 10.04
查看>>
PDB文件概说
查看>>
将 ASP.NET MVC3 Razor 项目部署到虚拟主机中
查看>>
Js~实现public和private对象,即static修饰符
查看>>
C/C++的static成员
查看>>
Microsoft Excel 不能访问文件“ 文件名称或路径不存在。 • 文件正被其他程序使用。 • 您正要保存的工作簿与当前打开的工作簿同名。...
查看>>
<cf>Walking in the Rain
查看>>
A Byte of Python (for Python 3.0) 下载
查看>>
Linux下父子进程的全局变量
查看>>
HDU-Pattern and Text 枚举
查看>>
WebService的事务处理
查看>>
2.10 寻找数组中的最大值和最小值
查看>>
VC 2005 解决方案的目录结构设置和管理
查看>>
[Tip] U盘空间遗失的解决方法
查看>>
介绍"Napa"-Office 365 开发工具
查看>>