15th Annual Computer Science Programming Contest Solutions -
Java
import java.io.*;
// Final Jeopardy Programming Problem
// Input: Our current winnings, followed by the winnings of each
// of our two competitors (contestants 2 & 3)
// Output: The amount we should wager, according the rules of the
// problem statement.
public class Jeopardy
{
public static void main( String[] args ) throws Exception
{
// get input from user
System.out.println( "Welcome to the Final Jeopardy round!" );
int[] dollars = new int[3]; // current winnings of the 3 contestants
for( int i = 0; i < 3; i++ )
dollars[i] = promptAmount( i+1 );
// which of the other contestants have more money?
int larger = dollars[1];
if( dollars[2] > larger ) larger = dollars[2];
// decide and output what our wager should be
if( larger >= dollars[0] )
System.out.println(
"You’re not in the lead, and should wager your entire $" +
dollars[0] + ".");
else if( dollars[0] > 2*larger )
System.out.println( "You can comfortably wager $" +
(dollars[0] - 2*larger - 1) + "." );
else
System.out.println( "You should wager $" +
(2*larger - dollars[0] + 1) + "." );
}
private static int promptAmount(int contestant) throws Exception
{
BufferedReader br = new BufferedReader(
new InputStreamReader( System.in ) );
int amount = 0;
while( true )
{
if( contestant == 1 )
System.out.print( "Enter your current winnings: " );
else
System.out.print( "Enter the current winnings of contestant #" +
contestant + ": " );
amount = Integer.parseInt( br.readLine() );
if( amount >= 0 ) break;
System.out.println( "Please enter a nonnegative integer..." );
}
return amount;
}
}
1
import java.io.*;
// Array Rank Programming Problem
// Input: An array size, followed by the specified number of integers
// Output: The corresponding rank array.
// The rank of an element is the number of smaller elements in the
// array plus the number of equal elements that appear to its left.
// The rank array is an array of element ranks. For example, if the
// input array is [4, 3, 9, 3, 7], the corresponding rank array is
// [2, 0, 4, 1, 3].
public class Rank
{
public static void main( String[] args ) throws Exception
{
// get input from user:
BufferedReader br = new BufferedReader(
new InputStreamReader( System.in ) );
final int ARRAY_SIZE = promptSize( br );
int[] theInts = new int[ARRAY_SIZE];
int[] ranks = new int[ARRAY_SIZE];
System.out.println( "Enter the ints, each on a separate line:" );
for( int i = 0; i < ARRAY_SIZE; i++ )
{
theInts[i] = Integer.parseInt( br.readLine() );
ranks[i] = 0; // simultaneously set all ranks to 0 as we get input
} // (saves having another for loop)
// compare all pairs of elements, increment the proper ranks
for( int i = 1; i < ARRAY_SIZE; i++ )
for( int j = 0; j < i; j++ )
if( theInts[j] <= theInts[i] )
ranks[i]++;
else
ranks[j]++;
// output the rank array
System.out.println( "The input array was: " );
for( int i = 0; i < ARRAY_SIZE; i++ )
System.out.print( theInts[i] + " " );
System.out.println();
System.out.println( "The corresponding rank array is: " );
for( int i = 0; i < ARRAY_SIZE; i++ )
System.out.print( ranks[i] + " " );
System.out.println();
}
private static int promptSize( BufferedReader br ) throws Exception
{
int s = 0;
System.out.print( "Enter desired size of array : " );
s = Integer.parseInt( br.readLine() );
while( s < 1 )
{
2
System.out.print( "Please enter a size of at least 1: " );
s = Integer.parseInt( br.readLine() );
}
return s;
}
}
3
import java.io.*;
// Perfect Numbers Programming Problem
// Input: A positive integer
// Output: A message stating whether the number is perfect, abundant,
// or deficient.
// The program continues to prompt for input until a nonpositive integer
// is provided as input.
public class PerfNum
{
public static void main( String[] args ) throws Exception
{
BufferedReader br = new BufferedReader(
new InputStreamReader( System.in ) );
int n, s;
while( true )
{
System.out.print( "Enter an integer (0 to quit): " );
n = Integer.parseInt( br.readLine() );
if( n < 1 ) break;
s = sumDiv(n);
if( s < n )
System.out.println( n + " is deficient." );
else if( s > n )
System.out.println( n + " is abundant." );
else
System.out.println( n + " is perfect." );
}
System.out.println( "Goodbye!" );
}
// computes and returns the sum of the proper divisors of n
// (assumes n is positive)
// for example, if n=12, the return value is 1+2+3+4+6=16
private static int sumDiv( int n )
{
int sum = 0;
for( int i = 1; i < n; i++ )
if( n%i == 0 )
sum += i;
return sum;
}
}
4
import java.io.*;
// Permutations Programming Problem
// Input: An array size, followed by the specified number of integers
// Output: Each possible permutation of the input array of ints
// Assumpution:
// The input array contains no duplicate ints
// Implementation note:
// This solution generates permutations recursively.
// A nonrecursive solution is available at the contest website:
// http://cs.wcu.edu/cscontest
public class Perm
{
public static void main( String[] args ) throws Exception
{
BufferedReader br = new BufferedReader(
new InputStreamReader( System.in ) );
// get input from user:
final int PERM_LEN = promptSize( br );
int[] theInts = new int[PERM_LEN];
System.out.println( "Enter the ints, each on a separate line:" );
for(int i = 0 ; i < PERM_LEN; i++)
theInts[i] = Integer.parseInt( br.readLine() );
// find & display the permutations
System.out.println( "The permutations: " );
perm( theInts, 0, PERM_LEN - 1 );
}
// recursively find and display permutations
private static void perm( int[] list, int k, int m )
{
if ( k==m )
{
// list has one permutation, output it
for( int i = 0; i <= m; i++ )
System.out.print( list[i] + " " );
System.out.println();
}
else
{
// list[k:m] has more than one permutation
// generate these recursively
for( int i = k; i <= m; i++ )
{
swap( list, i, k );
perm( list, k+1, m );
swap( list, i, k );
}
}
}
// prompt user for permutation size; ensure it’s at least 1
private static int promptSize( BufferedReader br ) throws Exception
{
5
int p = 0;
System.out.print( "Enter number of integers in original array : " );
p = Integer.parseInt( br.readLine() );
while( p < 1 )
{
System.out.print( "Please enter an array size of at least 1: " );
p = Integer.parseInt( br.readLine() );
}
return p;
}
// swap a[i] and a[j]
private static void swap( int[] a, int i, int j )
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
6
import java.io.*;
import java.util.*;
// Permutations Programming Problem
// Input: An array size, followed by the specified number of integers
// Output: Each possible permutation of the input array of ints
// Assumpution:
// Unlike the previous version of this problem, this version assumes
// that the input array may contain duplicates.
// Solution overview:
// This solution generates permutations recursively, just as the previous
// version (that assumes no duplicates) does. As we find permutations,
// we add each to a TreeSet, which ensures that we never have a duplicate.
// We wait to output all the permutations until this process is complete.
// An added bonus of our PermComparator implemenation, along with the
// behavior of TreeSet, is that the permutations will be listed in
// lexicographic order!
// A nonrecursive solution is available at the contest website:
// http://cs.wcu.edu/cscontest
public class Perm2
{
private static TreeSet permList; // set to hold our permutations
public static void main( String[] args ) throws Exception
{
// get input from user:
BufferedReader br = new BufferedReader(
new InputStreamReader( System.in ) );
final int PERM_LEN = promptSize( br );
int[] theInts = new int[PERM_LEN];
System.out.println( "Enter the ints, each on a separate line:" );
for(int i = 0 ; i < PERM_LEN; i++)
theInts[i] = Integer.parseInt( br.readLine() );
// find the permutations
permList = new TreeSet( new PermComparator() );
perm( theInts, 0, PERM_LEN - 1 );
// display the permutations
System.out.println( "The permutations: " );
Iterator iter = permList.iterator();
while( iter.hasNext() )
System.out.println( iter.next().toString() );
}
// recursively generate permutations, and add each to permList.
// The Set behavior of permList ensures that no duplicates actually get
// added (depends on the proper functioning of our PermComparator
// below...)
private static void perm( int[] list, int k, int m )
{
if ( k==m )
{
// list has one permutation, add it to the Set of permutations
int[] tempPerm = new int[list.length];
7
for( int i = 0; i <= m; i++ )
tempPerm[i] = list[i];
permList.add( new Permutation( tempPerm ) );
}
else
{
// list[k:m] has more than one permutation
// generate these recursively
for( int i = k; i <= m; i++ )
{
swap( list, i, k );
perm( list, k+1, m );
swap( list, i, k );
}
}
}
// prompt user for permutation size; ensure it’s at least 1
private static int promptSize( BufferedReader br ) throws Exception
{
int p = 0;
System.out.println( "Enter number of integers in original array : " );
while( p < 1 )
{
System.out.print( "Please enter an array size of at least 1: " );
p = Integer.parseInt( br.readLine() );
}
return p;
}
// swap a[i] and a[j]
private static void swap( int[] a, int i, int j )
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// we have to add Objects to our Set (arrays don’t qualify), so we use
// this "wrapper" class to store our permutations
private static class Permutation
{
public Permutation( int[] p )
{
this.p = p;
}
public String toString()
{
StringBuffer sb = new StringBuffer();
for( int i = 0; i < this.p.length; i++ )
sb.append( this.p[i] + " " );
return new String( sb );
}
private int[] p;
}
// TreeSet calls this class’s compare method to determine if two
// objects are equal, as well as to determine in what order they fall
8
private static class PermComparator implements Comparator
{
public int compare( Object o1, Object o2 )
{
Permutation p1 = (Permutation) o1;
Permutation p2 = (Permutation) o2;
// we’ll just assume for this program that we don’t need to
// ensure that the permutations are equal length
for( int i = 0; i < p1.p.length; i++ )
if( p1.p[i] < p2.p[i] ) return -1;
else if( p1.p[i] > p2.p[i] ) return 1;
return 0;
}
}
}
9