1998 ACM South Central USA Collegiate Programming Contest
Rice University

Deck

Solution  Judge's input     Judge's output   Clarifications   Comments

Scenario

A single playing card can be placed on a table, carefully, so that the short edges of the card are parallel to the table's edge, and half the length of the card hangs over the edge of the table.  If the card hung any further out, with its center of gravity off the table, it would fall off the table and flutter to the floor.  The same reasoning applies if the card were placed on another card, rather than on a table.

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?

Input

The file ``deck.inp'' contains several nonnegative integers, one to a line.  No integer exceeds 99999.

Output

The standard output will contain, on successful completion of the program, a heading:

# 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.

Sample Input

1
2
3
4
30

Sample Output

The line of digits is intended to guide you in proper output alignment, and is not part of the output that your solution should produce.

12345678901234567
# Cards  Overhang
    1     0.500
    2     0.750
    3     0.917
    4     1.042
   30     1.997



 

Solution

#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>
#include <stdlib.h>

// 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;
}
 

Judge's Input

1
2
3
4
5
6
7
8
16
32
64
128
256
512
99999
99998
99988
99888
98888
88888
88887
88877
88777
87777
77777
77776
77766
77666
76666
66666
66665
66655
66555
65555
55555
 

Judge's Output

 Cards  Overhang
    1     0.500
    2     0.750
    3     0.917
    4     1.042
    5     1.142
    6     1.225
    7     1.296
    8     1.359
   16     1.690
   32     2.029
   64     2.372
  128     2.717
  256     3.062
  512     3.408
99999     6.045
99998     6.045
99988     6.045
99888     6.045
98888     6.039
88888     5.986
88887     5.986
88877     5.986
88777     5.986
87777     5.980
77777     5.919
77776     5.919
77766     5.919
77666     5.919
76666     5.912
66666     5.842
66665     5.842
66655     5.842
66555     5.842
65555     5.834
55555     5.751
 

Clarifications

No major clarifications were issued for this problem.

Comments

This was, not surprisingly, a popular problem.  I had figured it to be, along with "Ratio", one of the quickies.  The problem people had was that they failed to use double precision numbers and so, on one of the test cases, missed the right answer in the third digit.

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.