ACM Programming Contest

November 19, 2015, 6:00 - 9:00 PM

Instructions for handing in a program

When you have finished a program, demonstrate it directly to a judge. Raise your hand, and a judge will come to you. The judge will compile and run your program from the command line on your machine. If a judge is not available, work on the next program until one is available. Programs may be written in Java, C/C++, or C#, and must compile and run from a command prompt to be counted.


Problem 0 : Name

Write a program that prints your name and email address side-by-side vertically. 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

Example Output:
    G  f 
    r  o
    a  r
    c  t
    e  r
       a
    H  n
    o  @
    p  m
    p  a
    e  n
    r  s
       i
       o
       n
       .
       h 
       v 
       n

Problem 1 : Diagonal

Write a program that takes a word and a number n as input on the command line, and prints out the same word n times diagonally on the screen as shown in the example.

Example Input:
    java Diagonal mummy 3

Example Output:
    mmm
     uuu
      mmm
       mmm
        yyy

Problem 2 : Circle

Have the user input a number n between 1 and 100. Print an nxn grid of ‘X’ and ‘.’ characters, with one space between successive characters, such that X’s are placed in positions that are closer than n*0.5 units away from the center of the grid, and dots are placed in other positions.

Example Input:
    Java Circle 7

Example output:
    . . X X X . .
    . X X X X X .
    X X X X X X X
    X X X X X X X
    X X X X X X X
    . X X X X X .
    . . X X X . .

Problem 3 : Goldbach

Goldbach’s conjecture posits that any even number larger than 2 can be written as the sum of two primes. For example $8=5+3$. Although not proven, the conjecture is known to be true for all even numbers up to $4 * 10^{17}$. Given an even number between four and a billion input by the user, find and print two primes that sum to that number.

Example Input:
    Java Goldbach 20

Example output:
    13
    7

Problem 4 : Longest Mutated Substring

Given two strings input by the user A and B, write a a program that will print the longest common substring between A and B, allowing for a single point mutation (i.e. one of the letters does not have to match). For example, if A=”yellow” and B=”smelly”, then a longest mutated match from A would be “yell”, which matches with “mell” from string B.

Example Input:
    java LongestMutatedSubstring carpetbagger beggersbanquet

Example output:
    match from A: bagger
    match from B: begger

Problem 5 : Alphabetic Combinations

Write a program that will take a string of letters with no repeats as input and print out all of the unique combinations of the letters of the string. List each combination in alphabetical order (abc instead of bac), and the also print the list of combinations in alphabetic order.

Example Input:
    java AlphabeticCombinations cab

Example Output:
    a
    ab
    abc
    ac
    b
    bc
    c

Problem 6 : Math Dice 2.0

Given 4 integers and a target integer, create an expression with value closest to the target using the operators +, -, *, while using all of the numbers.

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

((2 + 3) * (4 + 5)) 

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

Example Input:
    java MathDice 1 2 10 11 3

Example Output:
    3 = ((1 + 2) * (11 - 10)) 

Problem 7 : Jiggle Sort

We will define a Jiggle Sort of length 3 to be a routine that rearranges the numbers of a list such that the first 3 form an ascending sequence, The last of these begins a descending sequence of length 3, followed by an ascening sequence of 3, and so forth. For example, given the numbers 0-9:

0 1 2 3 4 5 6 7 8 9

A possible Jiggle sort of length 3 would be

0 2 4 3 1 5 8 7 6 9

Other lengths are defined similarly. Write a program that will take two numbers (n and k) as input from the command line, and then print out the numbers 0 to n in Jiggle Sorted order of length k.

Example input:
    java JiggleSort 10 3

Example output
     0 2 4 3 1 5 8 7 6 9 10

Problem 8 : Planetary Delivery Service

Malcolm Reynolds has a very successful space delivery business. He delivers cargo from planet A to other planets in the verse using his Firefly class space ship. Ideally, Malcolm would like to fly to all known planets, but he doesn’t have enough fuel to do that, and the only place he can refuel his spaceship is on planet A.

Malcolm’s goal is to maximize his profit while making a delivery circuit from planet A through some of the planets in the verse, and then travel back to planet A without running out of fuel.

Write a program that will build an optimal itinerary for Malcolm given an input file that specifies how far he can travel, the names and (x,y) positions of the other planets relative to planet A, and the profit he can receive by visiting each of the planets. Planet A is considered to be at position (0,0). In your itinerary, specify (1) which planets Malcolm will visit and in which order, (2) how far he will travel, and (3) how much profit he will make.

Example input file: 
    3.5             # Maximum distance that Malcolm may travel
    B 1 0 10        # Planet name, (x,y) location, profit for visiting
    C 1 1 20
    D 0 1 30

Example output
    Itinerary: C D
    Distance traveled: 3.414
    Profit: 50

Problem 9: XML Pretty Printer

Write a program that takes a string of XML text from from a file and prints out the correctly indented form of that string. For this problem, we will use a limited form of XML, where tags have no attributes, and there is no data between tags. You may also assume that tags have no spaces in them, but there may be unlimited whitespace (or none) between tags. Each tag must be placed on its own line, indented by 4 spaces for each level of nesting surrounding it, as shown in the example below:

Example input: 
    <contest>  <acm>
    <fun></fun></acm>   <food></food></contest>

Example output:
    <contest>
        <acm>
            <fun>
            </fun>
        </acm>
        <food>
        </food>
    </contest>