Boys' High School & College
Mentem Hominis Spectato Non Frontem

An open programming contest for classes 11 and 12 is being held on 08-09-2008. The rules and problem set is as follows:

Note

1. Last Date for submitting the solutions is Wed, September 10, 2008.
2. The soft copy of the solution is to be given to Mr. Vinay Singh or mailed to This e-mail address is being protected from spambots. You need JavaScript enabled to view it latest by 8:00 am on the above mentioned date.
3. Only students of class 11 and 12 are eligible.
4. Programming language can either C++ (gcc) or Java.
5. The name and class of the student must be included as a comment at the top of the program.

1. CD TITLES

A keen photographer, I found my hard disk quickly filling up with snapshots and videos. I decided to offload a lot of the files to CD. Each CD is in its own plastic case, and the contents are clearly described on the front of the case. As the number of CDs increased, I built myself a shelf on which the CDs stand vertically.

I need your help! I have written a title for each CD into a text file, but I need the titles to appear vertically so that I can put them in the spine of the CD cases and be able to read them easily from the shelf. I want you to write a program that will output my titles vertically. I need lines between each title so that, when I print them, I can easily cut along the lines.

I have worked out that I can fit 36 characters into the available space, so all output titles must be 36 characters long, padded with spaces at the end where necessary. If I accidentally make a title too long, only output the first 36 characters.

INPUT FORMAT

Input will be at most 50 titles, one to a line. Each title consists of 1 to 100 arbitrary characters. A single ‘#’ on a line by itself indicates the end of input.

SAMPLE INPUT:

012345678901234567890123456789012345

Alfresco Quiz 2005

Founders’ Day 2006

#

OUTPUT FORMAT

Output will be the same titles presented vertically, where the left to right order will

be the same as the order of the input. There will be a column of bar (‘|’)

characters at each end, and separating each title, and a row of minus (‘-’)

characters (1 per column) at the beginning and end.

SAMPLE OUTPUT:

-------

|0|A|F|

|1|l|o|

|2|f|u|

|3|r|n|

|4|e|d|

|5|s|e|

|6|c|r|

|7|o|s|

|8| |’|

|9|Q| |

|0|u|D|

|1|i|a|

|2|z|y|

|3| | |

|4|2|2|

|5|0|0|

|6|0|0|

|7|5|6|

|8| | |

|9| | |

|0| | |

|1| | |

|2| | |

|3| | |

|4| | |

|5| | |

|6| | |

|7| | |

|8| | |

|9| | |

|0| | |

|1| | |

|2| | |

|3| | |

|4| | |

|5| | |

-------

2. Tharian NUMBERS

In the supposedly uninhabited part of Thar Desert, a tribe of unusual people has

been discovered. The Tharians have only 2 fingers and a thumb on each hand,

and have invented their own numbering system. The digits they use and the

symbols they use for digits are quite unusual, but anthropologists have been able

to represent them as follows:

% represents 0

) represents 1

~ represents 2

@ represents 3

? represents 4

\ represents 5

Rs.  represents -1 (yes, they even have a negative digit)

As you may expect, their system is base 6 where each place value is 6 times the

value to its right, as in the following examples:

)@% is 1*62+3*6+0 = 36+18+0 = 54

?Rs. ~~ is 4*63+(–1)*62+2*6+2 = 864–36+12+2 = 842

Rs. ~~ is (–1)*62+2*6+2 = –36+12+2 = -22

Your task is to take Tharian numbers and represent them as standard base 10

numbers.

INPUT FORMAT

Input consists of Tharian numbers, one per line. Each number consists of a

sequence of 1 to 10 Tharian digits. A single ‘#’ on a line by itself indicates the

end of input.

SAMPLE INPUT:

)@%

?Rs. ~~

Rs. ~~

%

#

OUTPUT FORMAT

Output will be the corresponding decimal numbers, one per line.

SAMPLE OUTPUT:

54

842

-22

0

3. CHANGE

A small local shop is having a problem because the assistants find it hard to work

out how much change to give to customers. You have been asked to help them

by writing a program that does all the work!

Notes and coins available are as follows:

Notes: Rs. 20, Rs. 10, Rs. 5, Rs. 2, Rs. 1.

Coins: 50p, 20p, 10p, 5p.

As the smallest coin available is 5p, the cost of the purchase may need to be

rounded to the nearest 5p, using the so-called Swedish rounding method. The

rules for rounding are as follows:

1 or 2 paise – rounded down to 0.

3 or 4 paise – rounded up to 5.

6 or 7 paise – rounded down to 5.

8 or 9 paise – rounded up to 10.

The program must work out the change required and specify the notes and coins

to use. In each case, the smallest possible number of notes and coins must be

used.

INPUT FORMAT

Each line of input will represent a single transaction, and will contain 2 decimal

numbers in the range 0.05 to 1000.00, each with two digits after the decimal

point, and separated by a single space. The first number is the cost of a

purchase, the second the amount the customer offers at the till. As mentioned,

the cost of the purchase may need to be rounded, and, of course, the amount

offered by the customer is a multiple of 5 paise. A line consisting of two 0.00

numbers marks the end of the input.

SAMPLE INPUT

20.03 20.00

20.07 20.05

20.08 25.00

0.09 0.10

0.00 0.00

OUTPUT FORMAT

Your program must output one line for each transaction. Where the amount of

money offered by the customer is not enough to cover the rounded purchase

price, your program must output

Not enough money offered.

Where the amount of money offered by the customer is exactly the rounded

purchase price, your program must output

Exact amount.

In all other cases output the sequence describing the change. Each sequence

item starts with a note or coin value in the format described earlier (e.g., Rs. 2 or

10p), followed by a multiplication sign (i.e., an asterisk, ‘*’) and ends with a

repetition count (a number ³ 1). Items are listed in order of decreasing values and are separated by single spaces.

SAMPLE OUTPUT

Not enough money offered.

Exact amount.

Rs. 2*2 50p*1 20p*2

Exact amount.

4. MAZE MADNESS

You have been placed somewhere in a maze and you wish to escape by the shortest

possible route. Fortunately you have been given a map of the maze. Before setting

off, you wish to calculate the distance you need to travel. Your task is to write a

program that will calculate the shortest distance to leave the maze. Note that there

may be more than one exit and the specified start position could be at any location

within the maze.

The maze is set on a grid that has M columns and N rows, with 1 £ M, N £ 100.

Some squares of this grid have impenetrable walls of negligible thickness between

them (or on their outside border). You may move from any square to a horizontally

or vertically adjacent square (possibly outside the maze, thus escaping) provided that

there is no wall between them. Each single move between squares adds 1 meter to

the distance travelled.

INPUT FORMAT

The input involves a series of scenarios. Within each of the scenarios the first line

has the size of the maze. This is given as two numbers M and N. Then the maze is

drawn on 2*N+1 lines and 2*M+1 columns using the printable characters “-”, “|”, “+”,

“.”, “ ” (space), and “s”:

· “|” is used for “vertical” walls,

· “-” is used for “horizontal” walls,

· “+” is used to indicate boundaries between rows and columns (there are

always (N+1)*(M+1) of these),

· “.” is used for wall openings,

· “ ” (space) is used for empty squares,

· “s” is used to show your start location (there is exactly one “s”).

A line with "0 0" indicates the end of the scenarios.

SAMPLE INPUT:

1 1

+-+

|s.

+-+

3 2

+-+-+.+

| .s| |

+-+.+-+

| . . .

+-+-+-+

5 6

+-+-+-+-+-+

| . . . . |

+-+-+.+-+-+

| |s. . . |

+.+-+-+-+.+

| | . . . |

+.+-+-+-+.+

| | . . . |

+.+-+.+-+.+

| . . | | |

+-+-+.+.+.+

. . . | . |

+-+-+-+-+-+

3 2

+-+-+.+

| .s| |

+-+-+-+

| . . .

+-+-+-+

0 0

OUTPUT FORMAT

Output a single line for each of the scenarios. This line should contain either "Maze

i: d" or "Maze i: No escape!", where i is the scenario number (counting from

1) and d is the minimum distance (in meters) needed to escape (use single spaces

for spacing).

SAMPLE OUTPUT:

Maze 1: 1

Maze 2: 3

Maze 3: 12

Maze 4: No escape!

5. BOOK PAGES

For the purposes of this problem, we will assume that every page in book is numbered sequentially, and that the first page is numbered 1.

How many digits would you need to use to number the pages of a 10 page book? Pages 1 to 9 would require 1 digit each (total 9), and page 10 would require 2 digits. This makes 11 digits. Similarly, a book of 34 pages would require 59 digits.

Can we work backwards? If you are told that a book requires 13 digits to number its pages, can you work out how many pages the book has? I hope so, because that is all you have to do for this problem. Each line in the input file represents the number of digits used in numbering a book. Your answer will be the number of pages the book has. If the number supplied cannot possibly be valid, your answer should be “Impossible!” Beware that books can be quite large, and the number of digits required for a given book can reach 2,000,000,000.

INPUT FORMAT

Each line in the input file contains a single integer, between 1 and 2,000,000,000, representing a number of digits used in numbering the pages of a book. A single # on a line indicates the end of input.

SAMPLE INPUT:

OUTPUT FORMAT

Output for each input number must be on a single line. If the input value is valid, output the number of pages in the book. Otherwise, output “Impossible!”

SAMPLE OUTPUT: