## [URI Online Judge] – 1290 – Very Special Boxes

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1290

Special Box Company (SBC) is a small family-owned and family-run business which produces decorated carton boxes for wrapping gifts. The boxes are hand-made, produced individually from ﬁne materials. When accepting an order from a client, they always produce a few more boxes than needed, to keep a stock of boxes to be sold in the future, if needed. Over the years their stock has been growing, with boxes all over the place, and they decided they needed to organize it a bit more. They have therefore made a list registering the dimensions of every box in their stock.

SBC has just received an order from a client that must be delivered tomorrow, so there is no time to produce new boxes. The client wants a certain number N of boxes *all of the same size*; each box will be used to pack one item of dimensions X, Y and Z. As the carton used in the boxes is very thin, you may assume that a box of size (X, Y, Z) would ﬁt perfectly the item the client wants to wrap. If there are not at least N boxes that ﬁt perfectly, the client wants N boxes that ﬁt the items as tightly as possible. The box size that ﬁts the items as tightly as possible is the one which minimizes the empty space when the item is put inside the box. An item can be rotated in any direction to be accomodated inside a box; therefore, a box of size (X, Y, Z) is as good as a box of size (Y, Z, X), for example.

Can you help SBC ﬁnding whether they can fulﬁll the customer order?

## Input

The input consists of several test cases. The ﬁrst line of a test case contains two integers **N** and **M**, indicating respectively the number of boxes the client needs to buy (1 ≤ **N** ≤ 1500) and the number of boxes in the stock list (1 ≤ **M** ≤ 1500). The second line contains three integers **X**, **Y** and **Z**, representing the dimensions of the item the client wants to wrap (0 < **X**, **Y**, **Z** ≤ 50). Each of the next **M** lines contains three integers **A**, **B** and **C** representing the dimensions of a box in the stock list (0 < **A**, **B**, **C** ≤ 50). A test case with **N** = 0 indicates the end of the input.

## Output

For each test case in the input your program must produce one line, containing either:

- the single word ‘impossible’, in case it is not possible to fulﬁll the client’s order (because there are not at least N boxes of the same size in stock that can contain the item); or
- one integer V , which speciﬁes the volume of empty space left when one of the N items is packed in one of the boxes chosen.

Sample Input | Sample Output |

1 1 2 4 3 2 3 4 2 6 3 1 3 7 4 7 10 8 2 2 8 10 6 2 9 7 7 4 6 2 9 1 1 3 3 3 1 1 1 0 0 | 0 99 impossible |

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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; int main () { ios_base :: sync_with_stdio(0); cin.tie(0); vector< pair<int, vector<int> > > v; vector<int> caixa; int n, m; int x,y,z, i, j, k, v1, flag, cont; while (1) { cin>>n>>m; if (!n && !m) return 0; cin>>x>>y>>z; caixa.push_back(x); caixa.push_back(y); caixa.push_back(z); sort(caixa.begin(), caixa.end()); v1 = x*y*z; while (m--) { cin>>i>>j>>k; if ((i*j*k) - v1 >=0) { v.push_back(make_pair(i*j*k, vector<int> ())); v[v.size()-1].second.push_back(i); v[v.size()-1].second.push_back(j); v[v.size()-1].second.push_back(k); sort(v[v.size()-1].second.begin(), v[v.size()-1].second.end()); } } flag=0; sort(v.begin(),v.end()); int ans = 141241; cont=0; for (i=0; i<v.size(); i++) { cont=1; if (v[i].second[0] >= caixa[0] && v[i].second[1] >= caixa[1] && v[i].second[2] >= caixa[2] && v[i].first >= v1) { for (j=i+1; j<v.size(); j++) { if(v[i].second[0] == v[j].second[0]) if(v[i].second[1] == v[j].second[1]) if(v[i].second[2] == v[j].second[2]) cont++; if(cont==n) break; } if (cont==n) { ans = v[i].first - v1; flag=1; break; } } } if (!flag) cout<<"impossible"<<'\n'; else cout << ans << '\n'; v.clear(); caixa.clear(); } } |