// Scan a range of possible input values finding the largest expected output // within that range. // // Start and end range are given as command-line parameters. #include #include #include #include using namespace std; long lSqrt (long N) { if (N <= 1) return N; long maxSqrt = 1; while (maxSqrt * maxSqrt <= N) { maxSqrt *= 2L; } long minSqrt = maxSqrt / 2L; while (minSqrt < maxSqrt) { long mid = (minSqrt + maxSqrt) / 2L; long sqr = mid*mid; if (sqr == N) return mid; else if (sqr < N) { minSqrt = mid + 1; } else maxSqrt = mid; } return minSqrt-1L; } long pack(long N) { long bestSoFar = numeric_limits::max(); long stop = lSqrt(N)+1; long start = max(1L, 7 * (stop-1L) / 10); // slightly less than sqrt(2.0) * stop for (long h = start; h <= stop; ++h) { long w = N / h; if (2*h >= w) { if (h*w == N) { bestSoFar = 0; //cerr << N << " can be factored as " << h << " by " << w << endl; break; } else { ++w; if (2*h >= w) { long boxSize = h*w; bestSoFar = min(bestSoFar, boxSize - N); /* cerr << "Looked at " << h << " by " << w << " = " << boxSize << endl; cerr << "best so far: " << bestSoFar << endl; */ } } } } return bestSoFar; } void scan (long start, long stop) { cout << "Scanning from " << start << " to " << stop << endl; long best = -1; while (start <= stop) { long empty = pack(start); if (empty >= best) { cout << start << " " << empty << endl; best = empty; } ++start; } } int main (int argc, char** argv) { if (argc != 3) { cerr << "Usage: " << argv[0] << " minRange maxRange" << endl; return -1; } long start, stop; istringstream in1 (argv[1]); istringstream in2 (argv[2]); in1 >> start; in2 >> stop; scan(start, stop); }