AIOC Banner

Problem: World Bus Driving Championships

Want to try solving this problem? You can submit your code online if you log in or register.

World Bus Driving Championships

Input File: busin.txt
Output File: busout.txt
Time Limit: 1 second
Memory Limit: 32 MB

The most exciting moment of your entire life is almost here. The 2011 World Bus Driving Championships (WBDC) are coming to Australia, giving you a once-in-a-lifetime opportunity to watch the incredible skills of bus driving greats such as Stan Butler, Otto Mann, Ernie Prang and of course the one and only eight-time world bus driving champion Jim Thomas.

The WBDC runs the enormous competition in a knock-out tournament format. The organisers select the top N bus drivers from a series of national competitions around the world, then bring them to the finals to compete in a series of one-on-one matches involving a display of bus racing, bus demolition derby and buses flying over lines of motorcycles.

Each bus driver has a competitor number and a unique skill level, which you have carefully calculated from exhaustive analysis of every bus driving competition since 1953. In any match, you are certain that the driver with the higher skill level will win.

The competition is split into a number of rounds. In each round of the competition,

This continues until only one bus driver is remaining: the 2011 World Bus Driving Champion. There will always be an even number of drivers in any round of the competition, as N is always chosen to be a power of two.

Due to the phenomenal demand for seats at WBDC matches, tickets are extremely expensive. You have made a list of the bus drivers that you wish to see compete, and now need to determine the minimum number of matches you need to attend in order to see each of these bus drivers at least once.


The input file will consist of three lines.


Your output should contain one line with a single integer: the minimum number of matches you must attend in order to see all your favourite bus drivers compete at least once.

Sample Input

8 4
2 5 3 6 4 7 8 1
2 4 5 8

Sample Output



The matches in the first round will be:

The matches in the second round will be:

The final match in the third round will be:

By attending the three marked matches, all your favourite bus drivers can be seen at least once. This is the fewest number of matches needed to see all your favourite bus drivers.


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

For 30% of the available marks, N ≤ 20.


Privacy statement
© Australian Mathematics Trust 2001-2020

Page generated: 14 August 2020, 12:23am AEST