Free for All 7

Sam Loyds Puzzle Carnival II

Problem A: The Archery Puzzle

Here is an odd little puzzle which occurred the other day at an
archery meeting. The young lady who carried off the first prize
scored exactly one hundred points. Can you figure out how
many arrows she used, as well as the points awarded to each
arrow?

You will receive a list of N positive integers, P1 , P2 , . . . , PN ,

The young archer scored 100 points
which represent the scores in the archery target; that is, the
different scores that can be achieved with a single hit. You will also receive an integer S, which is the total
score that is to be obtained.
Determine the minimum number of arrows necessary to score S points, and print the points awarded to each
of those arrows, sorted in descending order. If there is more than one group of arrows that provide a valid
solution, choose the solution for which the first arrow scores the highest amount of points; if the solution
is still not unique, then choose one in which the second arrow scores the highest score possible, and keep
applying this reasoning for the rest of the arrows.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case starts with two integers in a single line: N and S. The second line for each test case contains N
integers in ascending order: P1 , P2 , . . . , PN .
T 6 500 ; 1 6 N 6 50 ; 1 6 P1 < P2 < P3 < . . . < PN 6 S 6 300

Output
For each test case, print the case number, followed by the minimum number of arrows required to score S
points between square brackets, and then the sequence of points for each arrow, in descending order. These
scores must be separated by single spaces.
If the test case does not have a solution, simply print the case number, followed by the string impossible.

Sample Input

Output for Sample Input

Case 1: [6] 17 17 17 17 16 16

6 100

Case 2: [3] 20 20 10

16 17 23 24 39 40

Case 3: impossible

3 50
10 15 20
2 25
7 13

Problem B: In Puzzleland (III)

Whittington is showing his trained cat in its surprising feat of going from A to Z, grabbing all the mice
in his way while stepping on each circle just once.

You receive an arbitrary, undirected graph, where

each node is identified by a single uppercase letter.
One vertex is the source, or starting point, and the
other is the target, or end point.
Your job is to imitate the cats ability, and identify a
path that goes from the source to the target, visiting
each node in the graph exactly once. If there is more
than one valid path, choose the lexicographically lowest one.

Whittingtons cat is very well trained

Input
Input starts with a positive integer T , that denotes the number of test cases.
Theres a blank line at the beginning of each case. Then two integers are given in a single line: N and M,
representing the number of nodes and the number of bi-directional edges in the graph, respectively. You can
assume that there is at most one edge between any pair of nodes, and that each edge will be reported only
once.
The next line will contain N distinct letters, separated by spaces, which are the identifiers for all the nodes
in the graph. The first letter in this list will be the source, the last letter will be the target. All letters will be
uppercase letters from the English alphabet.
Then M lines will be presented, describing the edges of the graph. Each of these lines contain two distinct
letters, which describe two nodes that are connected by an edge.
T 6 60 ; 2 6 N 6 15

Output
For each test case, print the case number, followed by the sequence of letters that describe the path from the
source to the target, visiting all nodes exactly once.
If a valid solution doesnt exist, print the word impossible.

Sample Input

Output for Sample Input

Case 1: AVCDYFUBWXEZ
Case 2: impossible

12 14

Case 3: LINK

A B C D E F U V W X Y Z
A F
A V
B U
B W
C D
C V
D Y
D W
E X
E Z
F U
F Y
U Z
W X
3 2
A B C
A B
A C
4 5
L N I K
L N
I L
I N
K N
K I

Problem C: The Courier Problem

Here is a pretty problem which has been the source of much confusion in the past due to unfortunate
misunderstandings while defining its terms.
The ancient version which appears in old mathematical works
goes something like this: A courier starting from the rear of
a moving army, fifty miles long, dashes forward and delivers
a dispatch to the front and returns to his position in the rear,
during the exact time it required the entire army to advance just
fifty miles. How far did the courier have to travel in delivering
the dispatch, and returning to the rear of the army?

Now, for the general problem: Consider an army L miles long,

The courier galloping around the army
marching forward at constant speed. A courier starts from the
rear of the army, travels all the way to the front, and immediately
goes back to the rear of the army, reaching his final destination at the precise moment when the army has
covered a distance of exactly L miles. Assume that the courier also moves with constant speed, and that the
time he spends on the front delivering the dispatch is negligible.
Write a program that, given the value L, calculates the total distance traveled by the courier, in miles.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case is described by a single integer L, in its own line.
T 6 3000 ; 1 6 L 6 105

Output
For each test case, print the case number, followed by the total distance covered by the courier. Print this
result as a real number, with exactly two digits after the decimal point.

Sample Input

Output for Sample Input

Case 1: 120.71

50

Problem D: Disputed Claims

Our puzzle shows an animated dispute between some miners over their
respective claims. It seems that they have obtained patents on some
mining claims of the same size. Each claim was in the form of a right
angled triangle, and all of exactly the same area, but of different dimensions, as would be the case with a triangle with a base of 35 feet, an
elevation of 12 and the hypotenuse of 37, as compared with another
with dimensions of 20, 21 and 29, as both contain areas of 210 feet.
The puzzle calls for the complete list of different triangles with an area
of 210 square feet, taking into account that all triangles must have a
square angle, and the lengths of their sides must be integers.

The miners and their claims

Your task now is to identify all possible triangles (right-angled and with sides of integer lengths, as in the
puzzle) with a certain area A. Print the lengths of each triangle in ascending order, and the whole list of
triangles in ascending order as wellsort the triangles first by their first (shortest) side, then the second side
and finally by their longest side.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test is described by a single integer A, in a line of its own.
T 6 104 ; 1 6 A 6 107

Output
For each test case, print the case number, followed by the number of valid triangles with area A. Then print
the sorted list of these triangles, one per line, using the format (a,b,c), where a, b, c are the lengths of the
sides of the triangle, in ascending order.

Sample Input

Output for Sample Input

Case 1: 2

210

(12,35,37)

1000

(20,21,29)

2400

Case 2: 0

3360

Case 3: 1
(60,80,100)
Case 4: 3
(30,224,226)
(48,140,148)
(80,84,116)

Problem E: Outwitting the Weighing Machine

Some school children discovered that by getting on a weighing machine in couples, and then exchanging placesone at a
timethey could get the correct weight of a whole party on
the payment of but one cent. They found that in couples they
weighed (in pounds): 129, 125, 124, 123, 122, 121, 120, 118, 116
and 114. What was the weight of each one of the five little girls
if taken separately?
It proves that they must have been clever scholars or they never
would have been able to work out the correct answer to such
an interesting puzzle question, which is liable to confuse older
heads than theirs.

Guess the weights of the girls

Given a list of 10 integers, representing the weighs of each couple formed from a group of 5 people, determine
the weights of each person.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case is described by 10 integers W1 , W2 , . . . , W10 in a single line.
T 6 3000 ; 100 6 W1 6 W2 6 . . . 6 W10 6 400

Output
For each test case, print the case number, followed by the 5 weights asked, separated by spaces. Print these
numbers in ascending order.

Sample Input

Output for Sample Input

Case 1: 56 58 60 64 65

114 116 118 120 121 122 123 124 125 129

Case 2: 53 57 58 61 65

110 111 114 115 118 118 119 122 123 126

Case 3: 90 90 100 106 126

180 190 190 196 196 206 216 216 226 232

Problem F: The Jolly Friars Puzzle

A group Jolly Friars are captivated by a puzzle presented to them.
Ten coins are placed upon the sixteen squares, so that you can
readily discern ten even lines. An even line is a line (horizontal,
vertical or diagonal) inside the grid with a positive, even number
of coins in it.
The Friars have learned that the maximum number of even lines
that can be formed on a grid with ten coins is 16. A grid with that
amount of even lines is known as an optimal grid. The puzzle they
are trying to solve now is, what is the minimum number of moves
required to turn their current grid into an optimal grid?
Picking up one coin and placing it on any other cell (as long as its
empty) counts as one move.

The Jolly Friars moving coins

You receive the description of several grids, each one with ten coins placed on it arbitrarily. Solve the Jolly
Friars puzzle for each grid.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case begins with a blank line, followed by four lines with four characters each, describing a grid.
Each character of the grid is either a dot (.) or an asterisk (*) which denote an empty cell or a coin, respectively.
Every grid will have exactly ten coins.
T 6 1000

Output
For each test case, print the case number, followed by the minimum number of moves required to make the
grid optimal.

Sample Input

Output for Sample Input

Case 1: 4
Case 2: 1

****
*.*.
.**.
*..*
*.*.
.***
*.**
.**.

Explanation of Sample Cases

For the first case, moving two coins from the top row into the second row, one in the third row and one in the
fourth row can turn the grid into the following:
.**.
****
..**
*.*.

Which has 16 even lines. For the second case, just one move is necessary to turn it into an optimal grid (the
question of which move is left as an exercise).

Problem G: A Daisy Puzzle Game

Gretchen, a little peasant girl from the Swiss Alps, is an expert at the
Daisy game, a simple game that is very well-known around the country.
Two players pluck off the petals of a Daisy flower, and each player is
always at liberty to pluck a single petal or any two contiguous ones, so
that the game would continue by singles or doubles until the victorious
one takes the last leaf and leaves the stumpcalled the old maidto
the opponent.
The pretty mdchen has mastered the Daisy game to such an extent
that she always plays optimally. In other words, she always plays by
performing the best possible moves on each turn, a feat which never
fails to astonish tourists who dare to challenge her to a game.

Little Gretchen playing the Daisy game

Analyzing the game, it is not very complicated to figure out a winning strategy for the second player, as
long as the game starts with a complete flower (having all of its petals intact). However, what will happen
when Gretchen plays against an opponent that also plays optimally, and some of the flowers petals have been
plucked off at random?

A flower is described by a number N which represents the original number of petals of the flower, and a list of
the petals that have been plucked off. All petals are numbered from 1 to N, and given the circular nature of
the flower, that means petals 1 and N are originally adjacent.
Given the description of a flower, and assuming its Gretchens turn, will she win the game? Remember that
both players always play optimally.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case begins with two integers in a single line, N and M, representing the number of petals originally
in the flower, and the number of petals that have been plucked off, respectively.
The next line contains M distinct integers, representing the petals that have been plucked off. These numbers
will always be in ascending order.
T 6 5000 ; 3 6 N 6 20 ; 1 6 M < N

Output
For each test case, print the case number, followed by the string yes if Gretchen wins the game, or no otherwise.

Sample Input

Output for Sample Input

Case 1: yes

13 1

Case 2: no

7
5 3
1 3 4

10

Problem H: Who Will Get the Nomination?

Occasionally during presidential elections puzzles get created for
campaign purposes, some of them becoming fervidly popular, like
this little game called The Political Puzzle Game.
It consists of a 5 5 board, and nine pieces, each one representing
a different candidate. The object of the game is to capture eight of
the pieces, and leave the last one (the winner) on the square located
at the centre of the board. We are not particularly interested in
which candidate wins the game, but in doing this in the minimum
number of moves possible.
A move means sliding any piece to an adjacent square, or jumping
over another piece, removing the piece that was jumped over. All
moves, whether they capture a piece or not, can be performed
horizontally, vertically or diagonally. You can capture only one
piece in one move, and only if there is a free square directly on
the opposite side of the captured piece (the landing square).

The political puzzle game

You receive a description of a board, where a number of pieces (between 1 and 9) are arbitrarily scattered
throughout the board. Your task is to determine the minimum number of moves required to win the game
with any of its pieces.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each case starts with a blank line. The next five lines contain five characters each, and they describe the
board. Each character of the board will be either a dot (.) or an asterisk (*). Dots represent empty squares,
and asterisks represent game pieces. The number of pieces will be always between 1 and 9 (inclusive).
T 6 100

Output
For each test case, print the case number, followed by the minimum number of moves required to capture all
pieces on the board except for one, leaving the winner on the center of the board.

11

Sample Input

Output for Sample Input

Case 1: 8
Case 2: 2

.....

Case 3: 5

.***.
.***.
.***.
.....
.....
.*...
..*..
.....
.....
.....
..*..
.***.
..*..
.....

Explanation of Sample Cases

For the first case, consider enumerating the pieces as follows:
.....
.123.
.456.
.789.
.....

Then one way to solve it in eight moves can be as follows:

2 jumps 6.
5 jumps 8.
2 jumps 9.
7 jumps 2.
5 jumps 7.
5 jumps 3.
5 jumps 1.
5 jumps 4.

For the second case, the topmost piece jumps over the other, and then moves back into the center, for a total
of 2 moves.
For the third case, there is an interesting way to solve it in 5 moves, which is left as an exercise.

12

Problem I: In Puzzleland (IV)

While Whittington is busy with his cat, the small boy asks the princess:
if it takes six seconds for the clock to strike six, how long would it
take to strike twelve?

Every hour the tower clock sounds a large bell as many times as the
number of hours it is marking. So, for example, at 6 oclock it sounds
the bell six times. The time it takes to complete this task is counted
from the moment it hits the bell the first time until the moment it
hits it the last time. The time between consecutive strikes is always
constant.

To the right: London towers clock

You know that at hour H1 it takes the clock exactly S seconds to strike H1 . How long would it take to strike a
different hour H2 ?

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case is described by three integer numbers in a single line, in order: H1 , S, H2 .
T 6 5000 ; 2 6 H1 , H2 6 12 ; 0 < S < 60 ; H1 6= H2

Output
For each test case, print the case number, followed by the exact number of seconds that the clock takes to
mark H2 .
If this number is not an integer, and is less than 1, then print it as a simplified fraction p/q (that is, p and q
have to be coprimes).
If the answer is not an integer, and is greater than 1, then print it as a mixed number, with its fraction part
simplified. See the samples below for the formatting details.

Sample Input

Output for Sample Input

Case 1: 13 1/5

6 6 12

Case 2: 12

6 6 11

Case 3: 1/2

3 1 2

13

Problem J: Mothers Jam Puzzle

Mrs. Hubbard has invented a clever system for keeping tabs on her
blackberry jam. She filled twenty-five jars and arranged the three sizes
so as to have twenty quarts on each shelf. Can you guess her secret so
as to tell how much jam is on each type of jar?

As you can see, there are three types of jars, which we will call small,
medium and large. Mrs. Hubbard puts a certain number of jars on each
of her three shelves. If all jars are completely filled with jam, and you
know the total amount of jam in each shelf, determine the capacity of
each type of jar.
Mrs. Hubbards kids inspect the jam

Input

Input starts with a positive integer T , that denotes the number of test cases.
Each test case begins with a blank line; after that, there will be three lines describing each shelf.
A shelf is described by four numbers, in order: three integers S, M, L which represent the number of small,
medium and large jars in the shelf, and a real number J that represents the total amount of jam for that shelf.
The value of J will always be presented with two digits after the decimal point. You may assume that all test
cases have a valid answer.
T 6 5000 ; 0 6 S, M, L 6 15 ; 0 < J 6 100

Output
For each test case, print the case number, followed by the capacity of the small, medium and large jars, in that
order. Print the answers as real numbers rounded to exactly two digits after the decimal point.

Sample Input

Output for Sample Input

Case 1: 1.11 3.33 6.67

Case 2: 1.00 2.00 3.00

3 3 1 20.00
6 0 2 20.00
6 4 0 20.00
3 0 1 6.00
0 2 2 10.00
1 3 1 10.00

14

Problem K: Skating Puzzle

Two graceful skaters, Jennie and Maude, race each other along a
track one mile long. However, they start from opposite ends of the
track, and skate towards the others starting point. Because of a
strong wind, Jennie receives an important advantage that helps
her finish the race two and a half times as quick as Maude. Maude
finished the race six minutes later. What was the time of each of
them skating the mile?
Jennie and Maude skating

Assume that the race always happens in a track one mile long, and that the skaters always maintain constant
speeds. Let vJ be Jennies speed, and vM Maudes speed. We will call r the ratio between the two speedsthat
is, r = vJ vM . Let t be the time in minutes between the moment when Jennie finished the race and the
moment when Maude did the same. Given the values r and t, determine the time that each skater took to
complete the race.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case contains two real numbers: r and t, as described above. Each number will be presented with
two digits after the decimal point.
T 6 5000 ; 1 < r 6 10 ; 0 < t 6 30

Output
For each test case, print the case number, followed by two real numbers: the time in minutes of Jennie and
Maude to complete the race, in that order. Print these numbers with exactly three digits after the decimal
point.

Sample Input

Output for Sample Input

Case 1: 4.000 10.000

2.50 6.00

Case 2: 3.784 7.114

1.88 3.33

15

Problem L: The Tinkers Puzzle

There is an old nursery rhyme that says:
I agreed with a tinker whose name was Doo-little
to make for my aunt a flat-bottomed kettle.
Twelve inches exactly the depth of the same,
and twenty-five gallons of beer to contain.
The inches across at the top would show
just twice the width, as measured below.
So tell me that width, across at the top
for auntie now wants a lid from the shop.
Tell the size of the kettle

Can you indicate the diameter of the required lid to fit on the
kettle, which is twelve inches deep, and will hold just twenty-five
gallons?

Given the depth of the kettle, and the volume it can hold, calculate its diameter at the topwhich is twice the
diameter at the bottom. The depth is given in inches, while the volume is given in beer gallons, which you
should assume to be equivalent to 282 cubic inches.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case contains two integers: D and V which denote the depth and the volume of the kettle, respectively.
T 6 1000 ; 1 6 D 6 50 ; 1 6 V 6 100

Output
For each test case, print the case number, followed by the diameter at the top of the kettle, in inches. Print this
as a real number rounded to exactly three digits after the decimal point.

Sample Input

Output for Sample Input

Case 1: 35.810

12 25

Case 2: 45.069

10 33

16

Problem M: The Misers Puzzle

There once was an old miser who had hoarded up a quantity of five, ten
and twenty-dollar gold pieces. Before starving to death, the miser used
to count his gold using a peculiar method. He used to take his coins and
form 4 piles with them, such that each pile had the same amount of 5, 10
and 20-dollar pieces. Not only that, but he could also divide his gold into
5 groups, also alike (with the same number of coins of each type). Finally
he repeated the process, this time splitting the gold into 6 alike groups.
Assuming that each of the piles he made had a positive number of gold
pieces of each type, what is the minimum amount of gold that the miser
could have had?

Lets say that the miser was able to divide his gold in N different ways, and
for each method of partitioning he was able to form Mi similar groups (for
1 6 i 6 N). You are asked now to determine the minimum amount of gold
he had.

Tell how much the miser has

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each case starts with an integer N in a single line. The next line contains N integers, representing the set
M1 , M2 , . . . , MN .
T 6 2000 ; 1 6 N 6 8 ; 2 6 M1 < M2 < M3 < . . . < MN 6 100

Output
For each test case, print the case number, followed by the the minimum amount of gold that the miser could
have.

Sample Input

Output for Sample Input

Case 1: 2100

Case 2: 7350

4 5 6
4
10 14 15 35

17

Problem N: The Pony Cart Problem

While driving a speedy pony, a young boy went around a sharp
turn at a gait which threatened an upset to the pony cart, as
well as to his fathers nerves. Fortunately no accidents occurred,
and after some experimentation, the following information was
gathered:
In turning the pony cart around within a ring of a certain diameter, which might be said to be reasonably safe, it was found that
the outer wheels made two turns to the inner wheels one; the
wheels were fixed at the statutory distance of five feet apart on
the axletree. The problem is to guess the circumference of the
track described by the outer wheels in making the turn.

What is the circumference of the outer track?

Assume that the tracks marked on the floor are perfectly circular, that the distance between a wheel on one
side and its opposite on the other side is D feet, and that for one turn of the inner wheels, the outer wheels
make N turns. Determine the circumference of the circle formed by the outer wheels.

Input
Input starts with a positive integer T , that denotes the number of test cases.
Each test case is described by the two real numbers D and N in the same line. These numbers are always
given with two digits after the decimal point.
T 6 1000 ; 3 6 D 6 10 ; 1 < N 6 10

Output
For each test case, print the case number, followed by the circumference of the outer tracks (in feet), with
exactly three digits after the decimal point.

Sample Input

Output for Sample Input

Case 1: 62.832

5.00 2.00

Case 2: 86.365

4.20 1.44

Case 3: 100.408

8.03 2.01

18