Ok, so I just participated in my first ever coding competition. I did it just for fun because I've never done it before and I thought it would be fun to see what I know and what I need to work on. Turns out my algorithms/problem solving suck more than I thought they did. Good to know. Anyway, I'm going to repost the problems here for ya'll to enjoy. The problems are language agnostic, and points were awarded by running the submitted code with various inputs and checking its output (1 point awarded means it successfully passed 1 particular run with some specific input). Problems with 6 or more points included stress test that would require the program to execute in under a certain amount of time/memory, so it was easy to get just a couple but difficult to get all of them. Have fun!


Fibs (3 points)

Recall that the Fibonacci numbers are defined as follows:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n > 1

The first eleven Fibonacci numbers are written out on the second line:

n 0 1 2 3 4 5 6 7 8 9 10 ...
F(n) 0 1 1 2 3 5 8 13 21 34 55 ...

Given two endpoints A and B, how many unique Fibonacci numbers are there, such
that for a given Fibonnaci number F(n), A <= F(n) <= B?

You will first be given the number of problems to solve, N, and then you will be
given N rows, each consisting of two endpoints A and B. For each row, you must
output the number of unique Fibonacci numbers in that range, inclusive.

Example:

STDIN:

3
2 21
2 4
4 10

STDOUT:

6
2
2

Chromakey (3 points)
Chromakey is a technique to replace all pixels in an image that fall in a
certain color range with the pixels from another image. In other words, a green
screen.

Input:

The first two lines consist of one integer each, the width W and height H of the
images to follow, each between 1 and 256. After that, each line will consist of
three numbers R G and B, each between 0 and 255. There will be W x H lines for
the first (base) image, and then another W x H lines for the second (overlay)
image.

Output:

Output the chromakey'd image. For every pixel in the first image where the Green
value is greater than the combined Red and Blue value, replace that pixel with
the corresponding pixel from the second image. Every other pixel remains
unchanged in the output.

Example:

STDIN:

2
2
75 35 5
15 255 35
12 46 35
16 48 5
0 0 0
15 75 30
5 25 3
0 4 0

STDOUT:

75 35 5
15 75 30
12 46 35
0 4 0

Minesweeper (3 points)
You may remember the classic Windows game of Minesweeper. In this game, an N by
M grid of cells was covered by opaque buttons, and K mines were hidden under
the buttons.

During the initial setup for the game, the Minesweeper program would randomly
place all K mines on the grid and then number the remaining grid cells with how
many adjacent mines each cell had, leaving 0-cells blank. In this way, every
cell is in one of three states:

1) It has a mine.
2) It is adjacent, either horizontally, vertically, or diagonally, to a cell
with a mine, and keeps count of how many mines it is adjacent to.
3) It is not adjacent to any mines.

Your job will be to calculate the counts that cells in state (2) have.

You will first be given a line that contains N, M, and K. You will then receive
K additional lines describing where the mines are. Each mine description line
will consist of X and Y, where 0 <= X < N, and 0 <= Y < M.

Your job is to write out all of the counts for cells in state (2) in sorted
order. Your output will be a row for each cell consisting of X, Y, and the
adjacent mine count. You should skip cells in state (3) completely (i.e., cells
with a 0 adjacent mine count). The sort order for your output should be ordered
by X primarily, lowest to highest, with Y lowest to highest breaking ties on X.

Example:

STDIN:

3 3 2
0 0
0 1

STDOUT:

0 2 1
1 0 2
1 1 2
1 2 1

The Claw (7 points)
Cade is out with some friends and sees a particularly exciting claw-style game.
The game consists of a number of stuffed chickens and goats laid out in a grid
where Cade has the opportunity to control a hovering claw to try and grab one of
the stuffed farm animals.

A friend bets Cade that he can't get both a chicken and a goat in the same
attempt. Cade accepts the challenge, but needs your help. Cade needs to know
which chicken and goat pair is the closest together to best improve his chances.

You will receive C, C >= 1, the number of chickens, and G, G >= 1, the number of
goats, on the first line. You will then receive C lines consisting of a chicken
ID followed by integral X and Y coordinates, and then you will receive G lines
consisting of a goat ID followed by integral X and Y coordinates. Goat IDs and
chicken IDs will not overlap and will be globally unique.

Your output will be one line consisting of a chicken ID followed by a goat ID
that constitutes the closest pair of stuffed farm animals for Cade to try and
grab.

Example:

STDIN:

2 3
1 0 0
2 -1 3
3 2 2
4 2 -4
5 -3 -1

STDOUT:

1 3

Wormholes (6 points)
Suppose there are U universes.

Suppose each universe is filled with N galaxies, where N varies from universe to
universe, and connecting the galaxies are M wormholes, where M varies from
universe to universe. Wormholes are unidirectional and always connect two
different galaxies in the same universe.

Suppose further that traveling through a wormhole is instantaneous and travel
through a galaxy is negligible. Additionally, wormholes each have a specific
time differential associated, such that when you enter some wormholes, you exit
some amount of years in the future, but through others, you exit some amount of
years in the past.

Lastly, suppose that you can reach, from a starting galaxy, through some series
of wormhole jumps, every other galaxy in that universe, though it's not
necessarily the case that you can get back.

Given a universe description, is it possible to go an arbitrary amount of time
back into the past?

You will be given U universe descriptions. Each universe description consists
of one line containing N and M for that universe. Then M lines will follow,
each of the format A B T, where A is the source galaxy, B is the target galaxy,
and T is the time differential in years (positive means into the future,
negative means into the past). You can assume the starting galaxy is labeled
galaxy 1.

For each universe, you will need to output "Y" or "N".

Example:

STDIN:

1
5 6
1 2 15
2 5 12
3 2 20
5 3 -40
3 4 40
4 5 10

STDOUT:

Y

Spelunking (6 points)
A team of spelunkers is spelunking through a series of caves. The caves they
spelunk in are organized in the following way:

Each cave is connected to other caves through at least partially vertical
corridors. Caves can hold all of the available spelunkers, whereas corridors
each have their own limit of the maximum number of spelunkers that can travel
through them at a time. Since the corridors are in some places vertical, the
spelunkers can only travel down. The caves are arranged on a series of levels,
such that every corridor connects a cave from one level to a cave on the very
next level below it. The topmost level has exactly one cave, as does the
bottommost level.

The spelunkers play a simultaneous spelunking game with these caves. All of the
spelunkers start in the topmost cave and all travel to the bottommost cave. The
spelunkers time their descents through the corridors such that every spelunker
moves down exactly one level at the same time.

Since the corridors have a maximum capicity of simultaneous spelunkers, given
a cave description, what is the maximum number of spelunkers the cave system can
support?

The caves are numbered 1..N, where 1 is the topmost cave, and N is the
bottommost cave. There are M corridors.

The first line of STDIN given to you is N. The second line is M.

The next M lines are formatted as A B C, where A is the source cave, B is
the destination cave, and C is the corridor capacity.

Your output should be the maximum number of spelunkers that can participate in
the game of simultaneous spelunking at the same time.

Example:

STDIN:

4
4
1 2 1
1 3 2
2 4 1
3 4 3

STDOUT:

3

Roads (6 points)
There are M countries.

In some country, N cities (numbered 1..N) are connected with one-way roads. Each
road has two properties: a length, and the toll required to travel the road. You
want to travel from city 1 to city N, covering the shortest distance possible.
However, you have limited funds. For each country description, find the shortest
path from city 1 to city N that you can afford.

Input:

The first line is M, the number of countries there are. For each country:

* You are given a line consisting of C, the number of bitcoins you can spend in
that country, 0 <= C <= 10000
* You are given a line consisting of N, the number of cities, 2 <= N <= 1000
* You are given a line consisting of R, the number of roads, 1 <= R <= 10000
* You are given R lines, each containing 4 numbers S, D, L, and T, describing
each road. S is the source city, D is the destination city, L is the road
length, and T is the toll to use the road (in bitcoins).

Output:

For each country, give the total distance traveled, or -1 if no acceptable route
exists.

Example:

STDIN:

2
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
0
2
1
1 2 1 1

STDOUT:

11
-1

Hexcode (6 points)
Benji and Heidi work at George Films. The founder of George Films, Lucas George,
has recently started making questionable editorial decisions regarding
rereleases of his work, and Benji and Heidi want to discuss it privately.

Heidi tells Benji to send him coded messages using a hexadecimal encoding. Heidi
assumes Benji will use the standard ASCII encoding for the alphabet, but Benji
opts to use the following mapping instead.

a = 1 h = 8 o = F v = 16
b = 2 i = 9 p = 10 w = 17
c = 3 j = A q = 11 x = 18
d = 4 k = B r = 12 y = 19
e = 5 l = C s = 13 z = 1A
f = 6 m = D t = 14
g = 7 n = E u = 15

Benji's test message is "hanshotfirst," which he encodes as "81E138F1469121314."
Heidi meets with him later to discuss the problem she sees.

"Benji," Heidi says, "letters before 'p' all use a single digit in your scheme,
but letters 'p' and up use two digits. It's ambiguous. I could decode your
message as 'hanachotfiract,' or as 'hanshoadfirsad,' or even as
'hanachoadfiabacad,' for example."

Benji replies, "no no, it's fine," sort of waving his hands above his head.
"It's ambiguous, but that's what makes it a better code. Those other decodings
of my message don't make sense. You should be able to just pick the decoding
that actually makes sense and isn't crazy. This is more secretive and harder to
crack."

Heidi isn't convinced. "I bet if you gave me a string of any paragraph-sized
length, there would be too many decodings to make sorting through which ones
make sense intractable."

Who's right? Given a string of characters [0-9A-F], how many possible messages
could have generated the string given Benji's encoding? Your job is to write
a program that answers this question.

Your input will be an arbitrary number of strings, one per line. Each line will
be a valid encryption (so, no line will start with a "0", for example). The
input will end when you receive the string "0". For each string prior to "0"
that you receive, you should output the number of possible decodings that string
has, one per line.

Example:

STDIN:

85CCF
11211
191191012F7121DD9E7
0

STDOUT:

1
6
24


Practice Problems: (not part of the final score, they were released before the competition as warm up)

21 (4 points)
Given a variable number of playing cards, form the best hand that does not
exceed 21. The cards are in the set [23456789JQKA], where 2-9 are worth their
face value, J Q and K are worth 10, and A can be selected to be worth either 1
and 11. In this scenario, you are only playing with one suit, so there is never
more than one of each card.

Input:

The first line is a single number, which is the number of lines to follow. Each
line after that is a sequence of characters in the above set.

Output:

For each input line of cards, output the highest possible score that does not
exceed 21.

Example:

STDIN:

4
296J
85
A37
475A

STDOUT:

21
13
2120


Permute (3 points)
My friend Mike just sent me a text message, asking if I can think of a way to
make the numbers 10, 10, 9, 9, and 1 equal 8. He says I am only allowed to use
addition, subtraction, and/or multiplication (+, -, *), and numbers must be used
the number of times they are listed (i.e., I should use 1 once, but I should use
10 and 9 both twice).

I solved this problem myself, and I kind of lucked out, because there was a
solution. It turns out that (((10 - 10) * 9) + (9 - 1)) = 8, but I'd like to be
able to know in the future whether or not a solution even exists first, for if
Mike texts me again. Can you help?

You need to write a program that takes a list of numbers and a target result
and outputs whether or not it's possible to combine those numbers using only
addition, subtraction, and/or multiplication to get the target result.

You will first receive a line that says how many problems your program can
expect, N, followed by N lines of an arbitrary amount of integers. The last
integer on each line is the target. If a combination can be made, output "Y",
otherwise output "N".

Example:

STDIN:

1
10 10 9 9 1 8

STDOUT:
Y

I wish I could make the questions not format like code, but I'm too lazy to do much about it.