2015
04-10

# Post Office

Other than postcards, the post office department of some country recognizes three classes of mailable items: letters, packets, and parcels. The three dimensions of a mailable item are called length, height and thickness, with length being the largest and thickness the smallest of the three dimensions.

A letter’s length must be at least 125mm but not more than 290mm, its height at least 90mm but not more than 155mm, and its thickness at least 0.25mm but not more than 7mm. (The unit millimeter is abbreviated by mm.)

All three of a packet’s dimensions must be greater than or equal to the corresponding minimum dimension for a letter, and at least one of its dimensions must exceed the corresponding maximum for a letter. Furthermore, a packet’s length must be no more than 380mm, its height no more than 300mm, and its thickness no more than 50mm.

All three of a parcel’s dimensions must be greater than or equal to the corresponding minimum dimension for a letter, and at least one of its dimensions must exceed the corresponding maximum for a packet. Furthermore, the parcel’s combined length and girth may not exceed 2100mm. (The girth is the full perimeter measured around the parcel, perpendicular to the length.)

The input will contain data for a number of problem instances. For each problem instance, the input will consist of the three dimensions (measured in mm) of an item, in any order. The length and width will be positive integers. The thickness will be either a positive integer or a positive floating point number. The input will be terminated by a line containing three zeros.

The input will contain data for a number of problem instances. For each problem instance, the input will consist of the three dimensions (measured in mm) of an item, in any order. The length and width will be positive integers. The thickness will be either a positive integer or a positive floating point number. The input will be terminated by a line containing three zeros.

100 120 100
0.5 100 200
100 10 200
200 75 100
0 0 0

not mailable
letter
packet
parcel

#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const double E = 1e-12;

inline
int dblcmp(double x)
{
if (x > - E && x < E)
return 0;
return x > 0 ? 1 : -1;
}

int main()
{
double num[5];

//freopen("input.txt", "r", stdin);

while (true) {
int cc = 0;
for (int i = 0; i < 3; i++) {
scanf("%lf", &num[i]);
if (dblcmp(num[i]) == 0)
cc++;
}
if (cc == 3) {
break;
}
sort(num, num + 3);
double t = num[0];
long long h = floor(num[1] + 0.5), l = floor(num[2] + 0.5);
bool ok = false;
if (dblcmp(t - 0.25) >= 0 && h >= 90 && l >= 125) {
if (dblcmp(7 - t) >= 0 && h <= 155 && l <= 290) {
printf("letter\n");
ok = true;
} else {
if (dblcmp(50 - t) >= 0 && h <= 300 && l <= 380) {
printf("packet\n");
ok = true;
} else {
double ans = t * 2 + (double)h * 2 + (double)l;
if (dblcmp(ans - 2100) <= 0) {
printf("parcel\n");
ok = true;
}
}
}
}
if (!ok) {
printf("not mailable\n");
}
}
return 0;
}

1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)