AIO Sample Questions

The Australian Informatics Olympiad (AIO) has been held since 1998. Before 2005 it was known as the Australian Informatics Competition.

On this page we feature some past problems. Some are Senior (up to year 12) and others are labelled as Intermediate, for students up to Year 10.

Culture

SENIOR 1

Culture

Input File: cultin.txt
Output File: cultout.txt
Time Limit: 1 second

You are a biologist working in a large laboratory. For the last month you have been growing a culture of your favourite bacteria, Bacillus Fortranicus. You are particularly interested in the way in which it grows in hostile environments.

Today is the last day of your experimentation. With anticipation you pull your log book from the shelf, but in your excitement you knock a bottle of acid from the bench. You watch in despair as it spills across your log book and your precious notes dissolve before your eyes.

You try desperately to recall some statistics. How many individual bacteria did you begin with? You can’t even remember for how many days the experiment has been running. In desperation you call over your lab assistant.

“No, I don’t remember how many bacteria we began with either,” she says. “But I do remember that it was an odd number. Oh yes, and the number of bacteria doubled each day.” She looks down at the bench, sniffs the acid and walks back to her desk with a wrinkled nose.

Although you have lost your notes, you can still count the total number of bacteria that you have now. Combining this total with the assistant’s information, you must write a program to answer your two original questions. That is, you must calculate (i) how many bacteria you began with, and (ii) for how many days the experiment has been running.

Input

The input file will consist of one line only. This line will contain a single integer n representing the number of bacteria that you have now. You are guaranteed that 1 <= n <= 30,000.

Output

The output file must consist of the two integers b and d on a single line, where b represents the number of bacteria at the beginning of the experiment and d represents the number of days for which the experiment has been running. These two integers must be separated by a single space.

Sample Input

136

Sample Output

17 3

The sample data above can be explained as follows. We are given that the final bacteria count is 136. Observe that 136 = 17 x 2 x 2 x 2. Since 17 is odd, we see that the initial bacteria count was 17. Furthermore, the bacteria count has doubled three times and so the experiment must have been running for precisely three days.

Scoring

The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.

Copyright © 2003 Australian Mathematics Trust

AFL

INTERMEDIATE 1

AFL

Input File: aflin.txt
Output File: aflout.txt
Time Limit: 1 second

It’s football season, and the rush is on. You have the unfortunate job of trying to arrange seating in the stadium for the horde of fans phoning in to the ticket office.

Luckily you are only responsible for a single row of seats. For each football fan who phones in with a booking for k people, you have to find a continuous block of k empty seats in the row in which they can sit. To save yourself the hassle of having to decide each time which block of k empty seats to book, you decide upon the following strategy.

Each time a fan phones in with a booking for k people, you find the longest continuous sequence of empty seats in the row (if there is a tie then you choose the leftmost longest sequence). You then book the first k seats in this sequence (and hope that the sequence of empty seats is long enough). These seats are then marked as taken, and you move on to answer the next phone call.

As an example, consider a row of 10 seats numbered 1,2,…,10. Say that seats 3 and 8 have already been taken before you start making bookings. The initial state of the row is illustrated in the following diagram, where the shaded seats have already been taken.

Suppose that the first phone call is for a booking of size 1. The longest continuous sequence of empty seats is from seats 4 to 7, so you place the booking at the beginning of this sequence, claiming seat 4.

Suppose that the next request is for a booking of size 2. The longest continuous sequence of empty seats is now from seats 5 to 7, so the booking is made for seats 5 and 6.

Let the next request be another booking of size 1. There are now two longest continuous sequences of empty seats, each of length two. One is from seats 1 to 2 and the other is from seats 9 to 10. You choose the leftmost of these longest sequences and book seat 1.

And so on. After a few days of carrying out this procedure it is becoming rather tedious, so you decide to write a computer program that can carry it out for you. Grabbing your laptop and an AFL-branded meat pie, you set to work.

Input

The first line of input will contain the single integer n representing the total number of seats in the row (1 <= n <= 30,000). These seats are numbered 1,2,…,n from left to right.

The second line of input will contain the single integer t representing the total number of seats that have already been taken (0 <= t <= n). Following this will be t lines, each containing the number of a seat that has been taken (no two of these seat numbers will be identical).

The next line of input will contain the single integer b representing the total number of bookings that you must make (0 <= b <= n). Following this will be b lines, each describing a single booking. Each of these lines will contain a single integer k representing the number of seats to be booked (1 <= k <= n). The bookings will be presented in order from the first phone call to the last.

Output

For each booking, your program should write a single line of output. This line should contain a single integer describing the leftmost seat that was booked.

You may assume that it is possible to successfully make all of the requested bookings using the strategy described above.

Sample Input

The following sample data corresponds to the example discussed earlier.

10
2
3
8
3
1
2
1

Sample Output

4
5
1

Scoring

For each input file, let b be the total number of bookings. If your program correctly places r of these bookings, it shall be awarded r/b of the available marks for that input file.

Copyright © 2004 Australian Mathematics Trust

Stacking Numbers

SENIOR 2

Stacking Numbers

Input File: stackin.txt
Output File: stackout.txt
Time Limit: 2 seconds

It’s raining outside, you’re bored and you desperately need something to do. Staring at a pile of soft drink cans in the corner, you devise a game that could keep you entertained for hours.

This game is played on a pyramid of side length six. This pyramid contains 21 boxes as illustrated below. In each box you must place a single non-negative integer.

[numbers]
You may choose the six integers that are placed in the bottom row of the pyramid. Once this bottom row has been filled, you have rules that describe how to fill the remaining boxes from bottom to top. The integer that is placed in the very top box of the pyramid is your score. Your aim is to obtain the highest score possible.

Before you play the game you are given some positive integer b called the base. The rules for filling in the remaining boxes are as follows.

  • For each box below the top row, you add the integers in the two boxes directly beneath it. If this sum is greater than or equal to the base b, you subtract b from this total so that the sum becomes strictly less than b.
  • For the very top box, you simply multiply the integers in the two boxes directly beneath it.

A sample game is illustrated below, played with base b = 100. The left hand diagram shows six integers initially placed in the bottom row, and the right hand diagram shows the resulting pyramid with every box filled.

 

[numbers]

Examine the first box of the fourth row (61). This box simply contains the sum of the two integers beneath it: 33+28. On the other hand, consider the first box of the third row (49). The sum of the two integers beneath it is 61+88 = 149, which is larger than b. We thus subtract b = 100 from this total to obtain 49, which is placed within the box. The topmost box contains 9702, which is the product 99 x 98.

Note that every box aside from the topmost box contains an integer between 0 and b-1 inclusive. In particular, if the two integers beneath a box add to precisely b then that box is filled with the integer 0.

To make the game more interesting, you are given a small set of numbers from which the six integers in the bottom row must be chosen. No integer from this set may be used more than once in the bottom row. You must write a program that selects six integers from this set to place in the bottom row so that you obtain the highest score possible.

Input

The input file will consist of three lines. The first line will contain the base b with which the game is played. You are guaranteed that 1 <= b <= 32,768.

The second line will contain an integer s representing the number of integers in your set from which the bottom row must be chosen. You are guaranteed that 6 <= s <= 32.

The third line will contain the entire list of s integers from which the bottom row of the pyramid must be chosen. Each of these integers will be between 0 and b-1 inclusive. These integers will be separated by spaces, and no two of these integers will be equal.

Output

The output must consist of precisely two lines. The first line must contain a single integer representing the highest possible score.

The second line must contain six integers that can be placed in the bottom row of the pyramid to obtain this highest possible score. The six integers should be written from left to right as they appear in the bottom row, and should be separated by spaces.

If more than one solution exists then you should only output one of these solutions. Any of these solutions will suffice.

Sample Input 1

100
7
1 2 3 4 5 6 7

Sample Output 1

8100
2 5 6 7 4 3

Sample Input 2

100
8
7 12 15 21 35 49 53 67

Sample Output 2

9702
12 21 7 53 49 35

Scoring

The score for each input file will be 100% if a correct solution is written to the output file and 0% otherwise.

Copyright © 2003 Australian Mathematics Trust

 

You may also wish to take a look at the online training site, where you can view other problems from past papers and submit your own solutions for these and others for on-the-spot judging!

Please note that, although the training site only accepts C, C++ and Pascal solutions, the full list of allowable languages is C, C++, C#, Pascal, Java, PHP, Python.