All Ireland Schools Programming Competition

Day 1 Problems

Introduction
Problem A
Problem B
Problem C

Introduction

There are three problems contained in this document. Attempt as many as you can.

With each problem there will be a number of examples. The first two of these examples will be used (in addition to other unseen tests) to test your program. The example files and solutions will be on the D: drive. The names of these files will be as given in the problem. There is also a batch file test.bat that will mark your program. (This program is also on the D: drive.) If you type ‘test 1 a 1’, then it will run day1a.exe or day1a.bas (if it exists) using the file test1a1 as input, and check that you produced the correct output file, day1a.sol. So when you have written day1a, you can test it using the two example files that you are given using the commands

test 1 a 1

and

test 1 a 2

You can similarly test your programs, day1b and day1c.

When you are finished, ensure that you have saved your files onto the root directory of the D: drive. (That is, a BASIC program for problem A should be saved as D:\day1a.bas.) You will also be given a floppy disk at the end, and you must also save your files to this disk and give it to a supervisor.

Best of luck

Problem A String Compression

Description

Consider the string ‘AAAABCCCCCDDDD’ consisting of alphabetic characters only. This string is of length 14. Since the string consists of alphabetic characters only, duplicate characters can be removed and replaced with a duplication factor n. With this technique the string can be compressed and represented by ‘4AB5C4D’. The compressed string is of length 7. Write a program which takes a string in compressed form and recreates the original uncompressed string.

Input

The string will be of the format ‘nA...’ where n, the duplication factor, is an integer between 2 and 99 and A is an uppercase alphabetic character. A string may contain single characters not prefixed with a duplication factor. If this were not the case, for instance, the string ‘AABCDE’ would be compressed to ‘2A1B1C1D1E’. To avoid this, single characters will not be prefixed with a duplication factor. The string ‘AABCDE’ would be compressed to ‘2ABCDE’.

The maximum length of an input string is 80 characters.

Output

The uncompressed string, 40 characters per line (it may be necessary to break an uncompressed string over multiple lines).

Example 1

Input

3A4B7D

Output

AAABBBBDDDDDDD

Example 2

Input

22D7AC18FGD

Output

DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF
FFFFFFFFGD

Instructions

Your program should be called day1a.bas if it is a BASIC program, day1a.pas if it is a Pascal program, day1a.c if it is a C program, day1a.cpp if it is a C++ program and day1a.lg if it is a logo program.

It should read its input from a file called day1a.dat, and write its output to a file called day1a.sol. The two example input files and the solutions are on the D: drive. The names of the input files are test1a1 and test1a2. The solution files are called test1a1.sol and test1a2.sol.

Note that if your program generates correct results for these files, it does not mean that your program is correct.

N.B. If you are writing a BASIC program ensure that it terminates with a system command, so that it exits to DOS. This is essential if it is to be processed automatically. You will get zero marks for the program if you neglect to do this.

Problem B Factorials

Description

The factorial of an integer n, written n!, is the product of all the integers from 1 to n inclusive. The factorial quickly becomes very large; 13! is too large to store as an integer on most computers, and 35! is too large for a floating-point variable. Your task is to find the rightmost non-zero digit of n!. For example, 5! = 1 * 2 * 3 * 4 * 5 = 120, so the rightmost non-zero digit of 5! is 2. Also, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, so the rightmost non-zero digit of 7! is 4.

Mike Scott provided some more information about factorials

Input

An integer n, between 1 and 100 inclusive.

Output

The rightmost non-zero digit of n!.

Example 1

Input

Output

Example 2

Input

Output

Instructions

Your program should be called day1b.bas if it is a BASIC program, day1b.pas if it is a Pascal program, day1b.c if it is a C program, day1b.cpp if it is a C++ program and day1b.lg if it is a logo program.

It should read its input from a file called day1b.dat, and write its output to a file called day1b.sol. The two example input files and the solutions are on the D: drive. The names of the input files are test1b1 and test1b2. The solution files are called test1b1.sol and test1b2.sol.

Note that if your program generates correct results for these files, it does not mean that your program is correct.

Problem C Transformations

Description

A square pattern of black and white tiles is transformed into another square. Write a program that will recognise the minimum transformation that has been applied to the original pattern given the following list of possible transformations:

90 Degree Rotation: The pattern was rotated to the right 90 degrees.
180 Degree Rotation: The pattern was rotated to the right 180 degrees.
270 Degree Rotation: The pattern was rotated to the right 270 degrees.
Vertical Reflection: The pattern was reflected vertically. (See example 4.)
Combination: The pattern was reflected vertically and then subjected to one of the rotations.
No Change: The original pattern was not changed.
Invalid Transformation: The new pattern was not obtained by any of the above methods.

Input

The input file will consist of a number n (between 1 and 10 inclusive), the size of the square, followed by n lines of the original pattern, and then after a blank line, the n lines of the transformed pattern. Black squares will be indicated by a ‘.’, and white squares by an ‘X’.

Output

The output from your program will be a phrase describing the transformation that changed the original pattern to the new pattern. If more than one transformation is possible, then your program should show the transformation corresponding to the minimal amount of work necessary to convert the original pattern to the new pattern. For the purposes of evaluating the amount of work needed, rotations are considered less work than reflections, and smaller rotations are less work than larger ones.

Note that only the above possibilities should be considered - there is no such thing as a 360 Rotation, nor is there a horizontal reflection. Also remember that if a single rotation is not sufficient, your program should consider a reflection followed by a rotation.

Example 1

Input

5
X...X
.X...
...X.
..X.X
....X
 
....X
...X.
.X...
..X..
XX..X

Output

ROTATED 90 DEGREES.

Example 2

Input

6
....XX
...X..
XX..X.
..X...
...X..
..X..X
 
X....X
X.X...
.X..X.
...X.X
..X...
..X...

Output

ROTATED 270 DEGREES.

Example 3

Input

2
X.
.X
 
X.
.X

Output

NOT TRANSFORMED.

Example 4

Input

4
..X.
XX..
....
...X
 
...X
....
XX..
..X.

Output

REFLECTED.

Example 5

Input

5
X....
.X...
.X...
...X.
....X
 
.X...
..X..
..X..
....X
X....

Output

IMPROPER TRANSFORMATION.

Example 6

Input

4
.X..
.X.X
....
..X.
 
..X.
X...
..XX
....

Output

REFLECTED AND ROTATED 270 DEGREES

Instructions

Your program should be called day1c.bas if it is a BASIC program, day1c.pas if it is a Pascal program, day1c.c if it is a C program, day1c.cpp if it is a C++ program and day1c.lg if it is a logo program.

It should read its input from a file called day1c.dat, and write its output to a file called day1c.sol. The two example input files and the solutions are on the D: drive. The names of the input files are test1c1 and test1c2. The solution files are called test1c1.sol and test1c2.sol.

Note that if your program generates correct results for these files, it does not mean that your program is correct.