A Programming Problem

``Programmers get a great deal of experience programming by solving problems. Some problems are difficult because the appropriate representation within a machine is unexpected or complex. Such problems are interesting because they're not immediately obvious and, as one's understanding of computer science matures, one's view on how to solve these problems effectively will undoubtedly change.

``In Java Elements we present a number of problems that are typical of those found in a programming contest. Each may be solved using the Java you have learned within this text, but we are also certain that returning to these problems after some time will yield different solutions-especially as you learn more about the art and science of programming.''

Here's one of the problems we present in the text:

``Problem 4. (Due to Knuth.) Suppose you are given 100 gold coins labeled with numbers 1 through n. Coin n has weight (and worth) that is sqrt(n).
Given one minute of computation, how close can you come to dividing the 100 coins into two piles of 50 coins each of equal weight? The output should be a difference in the weights of the piles, followed by a list of the 50 labels of coins on one side of the scale.''