ACM Programming Contest

April 22, 2015, 6:00 - 9:00 PM


Problem 0 : Names

Write a program that prints your name and email address n times on n lines, where n is a command line parameter. For example, if your program is written in Java, your name is “Grace Hopper”, and your email address is “fortran@mansion.hvn” a run of the program might go like the following:

Example Input:
    java Names 4

Example Output:
    Grace Hopper, fortran@mansion.hvn
    Grace Hopper, fortran@mansion.hvn
    Grace Hopper, fortran@mansion.hvn
    Grace Hopper, fortran@mansion.hvn

To hand in your program, use the command

handin acmjudge program0 [YourSourceFiles]


Problem 1 : Repeated Letters

Write a program that takes a word as input on the command line, and prints out the same word, except that each letter is repeated however many times it is repeated in original word. Words with no repeated characters will be unchanged, but a word like mommy would print out 3 copies of m for each m in the original, or in other words:

Example Input:
    java RepeatLetters mommy

Example Output
    mmmommmmmmy

handin acmjudge program1 [YourSourceFiles]


Problem 2 : Double primes

An integer n is prime if it has only 2 factors, 1 and itself. We will say that an integer n is a “double” prime if n is prime, and if the sum of the digits of n (in base 10) is also prime.

Given a number k between 1 and a million, specified on the command line, calculate the number of double primes between 1 and k. For example, if
the user inputs the number 13, the program would print 5, since the primes 2, 3, 5, 7, and 11 are all double primes.

Example Input:
    Java DoublePrimes 13

Example output
    5

handin acmjudge program2 [YourSourceFiles]


Problem 3 : Degree 2 polynomials

Let $f(x) = ax^2 + bx + c$ be a polynomial of degree 2. Given $f(0)$, $f(1)$, and $f(2)$, we can find the value of $f$ for any point. For this problem, your program will take 4 real numbers on the command line. They correspond to $f(0)$, $f(1)$, $f(2)$, and a number $x$. Your goal is to print out $f(x)$.

Example Input:
    java Poly 1.0 2.0 5.0 3.0

This is the polynomial f(x) = 1x^2 + 0x + 1. The output should be:
    10.0

handin acmjudge program3 [YourSourceFiles]


Problem 4 : Inside out

Given a string s, write a program that will print a 2D grid using the characters from s as follows: the first letter is printed in the center, the next character is printed in a square around it, the next letter is printed in a square around that one, etc.

Example Input:
    java InsideOut a.b

Example Output:
    bbbbb
    b...b
    b.a.b
    b...b
    bbbbb

handin acmjudge program4 [YourSourceFiles]


Problem 5 : Alphabetic Permutations

Write a program that will take a string as input and print out all of the unique permutations of the letters of the string in alphabetical order, one per line.

Example Input:
    java AlphabeticPermutations abbc

Example Output:
    abbc
    abcb
    acbb
    babc
    bacb
    bbac
    bbca
    bcab
    bcba
    cabb
    cbab
    cbba

handin acmjudge program5 [YourSourceFiles]


Problem 6 : Math Dice

Given 3 integers and a target integer, create a postfix expression with value closest to the target using the operators +, -, *, /, while using some or all of the numbers. For the purposes of this program, / will be integer divide.

As an example, suppose that the input numbers are 2, 3 and 4, and the target is 10. One answer would be the postfix expression:

2 3 * 4 +

This has value 10 (equal to the target) For this problem, your program must take 4 integers as command line arguments: the 3 arguments, and the target value. The program must then print out a postfix expression and corresponding value that is closest to the target.

Example Input:
    java MathDice 2 3 4 15

Example Output:
    14 = 3 4 * 2 +

handin acmjudge program6 [YourSourceFiles]


Problem 7 : Lindenmeyer Systems

A Lindenmeyer System (or L-System) is a string rewriting system that successively rewrites a string by replacing different symbols with strings. It has been frequently used to simulate plants, constructing plant geometry by interpreting the final string geometrically.

The starting string is called the “axiom”, and the rules are used to successively rewrite it.

For this program, you will write a program that takes 3 command line arguments. The first argument is the name of a file that has a set of rewriting rules. The next argument gives the axiom, and the third argument gives the number of iterations that should be performed.

Rules are specified in a file as follows: Each line of the file gives one rule, which consists of a letter, followed by an arrow, followed by a resulting string. For example, let a file called “input.txt” have the contents:

A -> AA
B -> A[B]B

Given this file, we can run the following:

Example Input:
    java LSystem input.txt B 2

Example Output
    AA[A[B]B]A[B]B 

handin acmjudge program7 [YourSourceFiles]


Problem 8 : Ffun

Let us define the function $f$ as follows

$f(0) = 1$
$f(1) = 1$
$f(2) = 1$

For larger numbers,

$f(n) = f(n-1) + f(n-2) + f(n-3)$

Thus, $f(3)=3$, $f(4)=5$, $f(5)=9$, etc.

Write a program that will take an integer n on the command line between 3 and 10 million. The program must write out $f(n)$ in scientific notation and be accurate to within 8 decimal places. (Hint: $f(n)$ will be too big to fit into a long or a double.)

Example input:
    java Ffun 5

Example output:
    9.00000000 * 10^0

handin acmjudge program8 [YourSourceFiles]


Problem 9 : LCM problem

For a given integer $n$, we define a “partition of n” as being a set of positive integers that add up to n. The function $LCM(n)$ defines the largest least common multiple of all the partitions of $n$. For example, $LCM(5) = 2*3 = 6$, and {2,3} is the best partition. Note that the partition can have duplicates, so {1,1,2} is a partition of 4.

Given a number $n$ between 2 and 50 specified on the command line, compute and print out $LCM(n)$.

Example input:
    java Lcm 7

Example output:
    12 (3*4)

handin acmjudge program9 [YourSourceFiles]