![]() ![]() ![]() |
![]() ![]() |
Deck
Solution Judge's input Judge's output Clarifications Comments
Two playing cards can be arranged, carefully, with short edges parallel to table edges, to extend 3/4 of a card length beyond the edge of the table. The top card hangs half a card length past the edge of the bottom card. The bottom card hangs with only 1/4 of its length past the table's edge. The center of gravity of the two cards combined lies just over the edge of the table.
Three playing cards can be arranged, with short edges parallel to table edges, and each card touching at most one other card, to extend 11/12 of a card length beyond the edge of the table. The top two cards extend 3/4 of a card length beyond the edge of the bottom card, and the bottom card extends only 1/6 over the table's edge; the center of gravity of the three cards lines over the edges of the table.
If you keep stacking cards so that the edges are aligned and every card has at most one card above it and one below it, how far out can 4 cards extend over the table's edge? Or 52 cards? Or 1000 cards? Or 99999?
# Cards Overhang
(that's two spaces between the words) and, following, a line for each input integer giving the length of the longest overhang achievable with the given number of cards, measured in cardlengths, and rounded to the nearest thousandth. The length must be expressed with at least one digit before the decimal point and exactly three digits after it. The number of cards is right-justified in column 5, and the decimal points for the lengths lie in column 12.
12345678901234567
# Cards Overhang
1
0.500
2
0.750
3
0.917
4
1.042
30
1.997
// a trick to deal with
the way some compilers handle loop index scoping
#define for if (0);
else for
// different ways to
sum numbers
class Sum
{
public:
virtual void
operator += (double a) = 0;
virtual operator
double() const = 0;
virtual ~Sum()
{}
};
// the obvious way to
sum numbers
class SimpleSum: public
Sum
{
public:
SimpleSum(double
a = 0.)
:s(a)
{}
void operator
+= (double a)
{ s += a; }
operator double()
const
{ return s; }
private:
double s;
};
// a more accurate way
to sum numbers
class CompensatedSum:
public Sum
{
public:
CompensatedSum(double
a = 0.)
:s(a),
err(0) {}
void operator
+= (double a)
{ double t =
s+(a+err); err=a-(t-s); s=t; }
operator double()
const
{ return s+err;
}
private:
double s, err;
};
// a each problem and
solution is represented by a triple
struct Triple
{
unsigned rank;
unsigned nBooks;
double overHang;
};
// for sorting triples
by their nBooks fields
int by_nBooks(const
void* a, const void* b)
{
Triple const*
ta = (Triple const*) a;
Triple const*
tb = (Triple const*) b;
return (ta->nBooks
< tb->nBooks)? -1: (ta->nBooks > tb->nBooks);
}
// for sorting triples
by their rank fields
int by_rank(const void*
a, const void* b)
{
Triple const*
ta = (Triple const*) a;
Triple const*
tb = (Triple const*) b;
return (ta->rank
< tb->rank)? -1: (ta->rank > tb->rank);
}
int main(int argc, char**
argv)
{
Sum* s;
unsigned nDigits;
// if you give
the secret hidden argument, you get the super-accurate
// computation,
which seems to be about 3 places more accurate that the
// simple compuation
if (argc > 1)
{
s = new CompensatedSum;
nDigits = 15;
}
else
{
s = new SimpleSum;
nDigits = 3;
}
// describe a
growable array of Triples
unsigned n =
0;
unsigned nalloc
= 16;
Triple* a = new
Triple[nalloc];
// read all problems
at once into Triples array
ifstream fin("deck.inp");
unsigned nBooks;
while (fin >>
nBooks)
{
// grow array if necessary
if (n == nalloc)
{
Triple* b = a;
nalloc *= 2;
a = new Triple[nalloc];
for (unsigned i = 0; i < n; ++i)
a[i] = b[i];
delete[] b;
}
a[n].nBooks = nBooks;
a[n].rank = n;
++n;
}
// reorder triples
by nBooks, so that we can calculate all the sums in one
// pass
qsort(a, n, sizeof(*a),
by_nBooks);
// start stacking
books; when the number stacked is among the queries, report it
nBooks = 0;
for (unsigned
i = 0; i < n; ++i)
{
while (nBooks < a[i].nBooks)
(*s) += 0.5/++nBooks;
a[i].overHang = *s;
}
// reorder triples
to their original orders
qsort(a, n, sizeof(*a),
by_rank);
// Tell them about
it
cout <<
"# Cards Overhang\n";
cout.precision(nDigits);
cout.setf(ios::fixed);
for (unsigned
i = 0; i < n; ++i)
cout
<< setw(5) << a[i].nBooks << " " << setw(8)
<< a[i].overHang << "\n";
// Be tidy
delete[] a;
delete s;
return 0;
}
The solution above has a couple of features that aren't really relevant to a good solution, given the precision we required and the number of samples in our test set. Still, we could have, if we'd been looking to nail people on this problem, constructed a very large test set with large numbers, so that people who missed the trick would run out of time. The trick is to calculate all the answers at once in a single pass over the numbers from 1 to 99999, rather than in many passes. It's fairly simple to do as I have done above and sort the inputs in order so that they can be evaluated optimally, then resort to the original order before printing.
The other feature regards precision. If we had asked for 12 digits or so of precsion, those of you who used double precision floating point would still have come out alright. But if we'd asked for 15 digits, you'd have to use special techniques like "compensated summation" to get extra accuracy. In the solution above, a command line argument triggers a higher precision calculation and display, should you care to investigate it.