The British
Informatics Olympiad is the computing competition for
schools.
We are proud to present BIO'96, sponsored by Data Connection.
The following sample questions have been adapted from last year's problems. The usual format will be for a programming task followed by a written task.
This paper is longer than should be expected for the 3-hour British Informatics Olympiad, but is of a similar standard. You may use any programming language on any computer, and have access to manuals and on-line help. But note that the only languages available at the final will be C/C++ and Pascal.
A prime number is an whole number greater than one, which can only be divided by one and itself to leave no remainder.
a) Write a program which asks for a number, M, and then prints all the prime numbers between 1 and M. Your program should also display the number of prime numbers found. M will not be greater than 2000.
b) How many prime numbers are between 150 and 450 ?
An example solution is part of the 1995 BIO sample problems, samples.pas
A code key contains all the characters A to Z, comma, full stop and space exactly once. Given a key we can encrypt a message as follows :
Each character has a value: A=1, ..., Z=26, comma=27, full stop=28 and space=29. Start with a marker pointing to the first character in the key. For each character in the message the marker is moved right (from its current position) by the value of the character in the message, wrapping around to the start of the key if the pointer moves beyond the end. The symbol pointed to in the key is the encrypted character.
a) Write a program to encode and decode text using the coding method described above. Your program should have a simple menu-based structure as follows :
----------------------------------------------------------
1) Enter an encoding "key" string.
2) Encode a section of text using the current key.
3) Decode a section of text using the current key.
4) Exit the program.
Choice?
----------------------------------------------------------
When Option 1 is selected a one-line string should be read from the keyboard. This should be converted to upper case, and all characters other than A to Z, comma, full stop and space should be deleted. This can then be converted into a valid key by removing any multiple occurrences of a character (leaving the first occurrence), and adding any characters that do not occur to the end, in increasing order of value.
For example, the string "I wandered lonely as a cloud" produces the key
"I WANDERLOYSCUBFGHJKMPQTVXZ,."
When Option 2 is chosen the program should read in a text message from the keyboard; this will not be more than 250 characters long, and your program should check for this limit. Characters other than A to Z, command, full stop and space should be removed, and the input should finish when a # character is read. Line breaks, except when immediately preceded by a \ character, should be converted into spaces. No text or spaces before the # should be deleted, but all text after it on the same line must be, and the input buffer must be cleared to the end of the line.
The message should then be encoded. For example with the above code key, the message "I WANDER" should be encoded as "OOANJQ,G". Output lines should be limited to 50 characters, and if a line needs to be split after the 50th character a \ should be printed after it. The text should terminate with a #.
Option 3 requires you to reverse this process, using the same input and output methods, but also printing the encoded text again. The same coding key should be used.
When Option 4 is selected your program should terminate.
b) There is one character which always detectable in encrypted text (without the code key). What is the character, and how may it be detected ?
This question formed part of the first round to the 1995 BIO. Solution.
Consider a 5x5 board of squares, where the bottom left square has co-ordinate (1,1) and the top right square is (5,5). Valid moves from square (x,y) are to any unoccupied square on the board with co-ordinates :
(x +/- 3, y), (x, y +/- 3), (x +/- 2, y +/- 2)
For example on an empty board from position (1,2) a valid move is to either (1,5), (4,2) or (3,4). To solve the game we need to place the numbers 1 to 25 in order onto an empty grid, always making a valid move between numbers.
a) Write a program which given a starting square for 1 prints the possible positions of 2.
b) Write a program which given a starting square for 1 prints the number of ways to solve the game from here, and outputs an example solution.
c) Suppose you colour each square black if it contains an even number, and white if it contains an odd number. Is there a solution which gives a chess-board pattern? How about if we fit 1 to 36 on a 6x6 grid??
This question was first set at the Third International Olympiad in Informatics, Athens, 1991. Solution.
END OF BIO'96 SAMPLE QUESTIONS
The British Informatics Olympiad
Christ's College
Cambridge CB2 3BU
The BIO is sponsored by Data Connection, specialists in complex software development.