ACM Programming Contest
April 14, 2016, 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++, and must compile and run from a command prompt to be counted.
Problem 0 : FavoriteColor
Write a program that prints your name, email address, and favorite color, on 3 separate lines. The program should not take any input. For example, if your program is written in Java, your name is “Grace Hopper”, and your email address is “email@example.com”, and your favorite color is turquoise, a run of the program might go like the following:
Example Input: java FavoriteColor Example Output: Grace Hopper firstname.lastname@example.org turquoise
Problem 1 : Collatz sequence
The Collatz conjecture (https://en.wikipedia.org/wiki/Collatz_conjecture) suggests that iterating on following operations will eventually terminate at 1 for all starting integers, n:
f(n) = n/2 if n is even f(n) = 3n+1 if n is odd
For example, starting with the number 3 yields the sequence:
3 10 5 16 8 4 2 1
Write a program that prints out the Collatz sequence for a number entered by the user, up to 1000000.
Example Input: Java Collatz 5 Example output: 5 16 8 4 2 1
Problem 2 : Table
Write a program that takes a CSV (comma separated value) file as input, and then prints the rows of the file lined up in columns with precisely 3 spaces between the columns. Each line of the input will contain the same number of values (however, this number may vary between different input files).
Example file: input.txt Hello,T,Everyone H,There,E Example run of the program: java Table input.txt Example Output: Hello T Everyone H There E
Problem 3 : OSU
Write a program that will print OSU in large block letters with a variable-width border around it spelling “OSU Cowboys!” over and over, where the border width is input by the user.
Example Input: Java OSU 1 Example output: s! OSU Cowboys! OSU Cowboys! OSU Cowboys! OSU Cow y b o . . X X X . . . . . X X X X . . X X . . X X o b . X X X X X . . . X X . . . . . X X . . X X y w X X . . . X X . . X X . . . . . X X . . X X s o X X . . . X X . . . X X X . . . X X . . X X ! C X X . . . X X . . . . . X X . . X X . . X X . X X X X X . . . . . . X X . . X X . . X X O U . . X X X . . . . X X X X . . . . X X X X . S S U O syobwoC USO !syobwoC USO !syobwoC USO !syobwoC
Problem 4 : Outer Planetary Delivery Service
Malcolm Reynolds has a very successful space delivery business. He delivers cargo from planet to planet in the verse using his Firefly class space ship. Ideally, Malcolm would like to fly to all known planets, but unfortunately the Inner Alliance has a warrant out for his arrest.
As it turns out, the Inner Alliance does not control planets that are on the border of empty space, so Malcolm can make deliveries there. These planets lie on the “Convex hull” of all the inhabited planets. Given a set of points in 2D, the “convex hull” is the smallest convex polygon that encloses all of the points. (https://en.wikipedia.org/wiki/Convex_hull#Convex_hull_of_a_finite_point_set)
For this problem, write a program that will take a set of 2D planet coordinates from an input file, one per line, and will determine which of the planets lie on the convex hull of the set of planets.
Example input file: planets.txt 0 0 1 0 0.25 0.25 0.8 0.02 0 1 Example run of the program: java ConvexDelivery planets.txt Example output (0,0), (1,0), (0,1)
Problem 5 : Rectangle Circle
Write a program to determine the intersection points between a Rectangle and a Circle. The rectangle will be specified by its lower left corner (x,y) and width and height (w,h). The circle will be specified by its center (xc,yc) and radius (r). Keep in mind that there may be up to 8 distinct intersection points.
Example Input: java CircleRectangle x y w h xc yc r java CircleRectangle -1 -1 2 2 1 -1 1 Example Output: (0.0, -1.0) (1.0, 0.0)
Problem 6 : One Number Math
Given a number and a target value, create an infix expression with value closest to the target using the operators +, -, *, /, @, using up to 5 copies of the number. Let the symbol @ mean concatenation. For example 3 @ 45 = 345. You may consider that / performs an integer division, so 7 / 3 = 2. use parentheses to indicate the order of oprations.
As an example, suppose that the input number is 3, and the target is 52. One answer would be the expression:
((3 @ 3) + (3 * 3))
This has value 52 (equal to the target). For this problem, your program must take 2 integers as input (base number and target value). The program must then print out an infix expression and corresponding value that is closest to the target.
Example Input: java OneMath 3 999 Example Output: 999 = (((3 @ 3) @ 3) * 3)
Problem 7 : One Bit
Given two numbers $m$ and $n$ input by the user, where $m \leq 16$, list the bit strings of length $m$ that have at least $n$ ones in a row in them. for example, if $m=3$, and $n=2$, your program should print out the strings $011$, $110$, and $111$, and then state that 3 matching bit strings were found.
Example Input: Java OneBit 3 2 Example Output: 011 110 111 3 matching bit strings found.
Problem 8 : Substring Match
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 0 or 1 single letter deletions in A or B, or both. For example, if A=”Jabberwocky” and B=”Jaberwoocky”, then a longest mutated match from A would be “Jaberwocky”.
Example Input: java SubstringMatch Jaberwoocky Jabberwocky Example output: Jaberwocky
Problem 9: Center To Edge
Given a grid of positive numbers of odd width and height, find the shortest cost path going from the middle of the grid to any square on the outside going left, right, up, and down. For example, suppose that the following grid is stored in the file “grid.txt”:
4 1 2 3 4 2 3 4 2 5 5 6 0 2 5 6 2 1 1 3 9 3 4 2 8
In this case, the optimal path starts on the middle position, and goes (down, right, down). In your program, print out the sequence of up, down, left, right moves to get to the outside of the grid, and the cost to get there.
Example input: java CenterToEdge grid.txt Example output: 4 (down, right, down)