AIOC Banner

Problem: Sleight of Hand

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

Sleight of Hand

Input File: handin.txt
Output File: handout.txt
Time Limit: 1 second

You do not like dinners with your extended family. This is unfortunate, as these happen all the time. Every few months you are forced to spend an entire evening away making small talk with distant relatives whose names you can never remember. You always end up on the end of the table where there's nothing but garden salad, listening to your second cousin droning on about her medieval history degree. And dessert is always prune pie - yeuch!

But then there's Uncle Max. With his beefy moustache and his hearty chortle, he always manages to turn an otherwise dry evening into a memorable one. Sometimes he tells mesmerising stories of his adventures grappling crocodiles in the Amazon, sometimes he shows off his incredible magic tricks. Tonight, he is demonstrating the ball-and-cups trick.

For the ball-and-cups trick, Uncle Max places N cups in a line on a table, all upside-down. Making sure everyone is watching, he puts a rubber ball underneath one. Then he begins to shuffle the cups around, sliding cups from one place to another at frightening speed. When he is done, he asks you to identify the cup with the ball underneath it.

Frustrated at your inability to choose the correct cup, you decide to turn to technology for assistance. You write down all the moves Uncle Max makes with the cups: for each move you note the original and new position for the cup that is moved. A position of 1 indicates the leftmost cup, a position of 2 indicates the second-leftmost cup, and so on. A position of N indicates the rightmost cup.

Now you just need to write a program that takes the initial position of the ball and the list of moves, and prints out the final position of the ball. You whip out your second cousin's trusty laptop - she's too busy gushing over the Magna Carta to notice - and begin to code.


To evaluate your solution, the judges will run your program against several different input files. All of these files will adhere to the following bounds:

As some of the test cases will be quite large, you may need to think about how well your solution scales for larger input values. However, not all the cases will be large - in particular:


Your program should read from the file . The first line of this file will consist of the integers N, S and K separated by spaces.

The following K lines will describe, in order, the moves Uncle Max makes with the cups. Each line will be of the form `ai bi', meaning that Uncle Max moves the cup in position ai so that it ends up in position bi.


Your program should write to the file . This file should contain a single integer: the final position of the ball.

Sample Input

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

Sample Output



In the sample case, there are eight cups. To begin with, the cup containing the ball is the fourth from the left.


Then, the cups are moved around as shown below:


At the end, the cup containing the ball is the sixth from the left, giving an answer of 6.


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


Privacy statement
© Australian Mathematics Trust 2001-2024

Page generated: 27 February 2024, 12:12am AEDT