Problem D
Moderate Pace

An ultra-marathon is a race that takes place over an uncomfortably long distance and time, typically lasting for five hours or more. You are part of a group of three ultra-marathon runners looking to place in this year’s Great South-to-North run from Plymouth to Aberdeen.

You have a set number of days until the next race to train. You will all train together, as training alone can be dangerous. As everyone has their own schedule in mind for how many kilometres to run per day, this will not be easy, you will have to compromise.

The fairest option is to look at each day individually, examine the three options for how far to run, and to take the median one. That is to say, the option taken for each day should be one that is not be greater or lesser than both of the other possibilities at the same time.


  • A line with the integer $n$ ($1\leq n\leq 1000$), the number of days of training.

  • A line with $n$ integers $k_{1,\ldots ,n}$ ($0\leq k \leq 10^6$), your ideal daily distances.

  • A line with $n$ integers $a_{1,\ldots ,n}$ ($0\leq a \leq 10^6$), your first colleague’s ideal daily distances.

  • A line with $n$ integers $b_{1,\ldots ,n}$ ($0\leq b \leq 10^6$), your second colleague’s ideal daily distances.


Output a plan for the $n$ days as $n$ integers, where the distance for every day corresponds to the median of choices for that day.

Sample Input 1 Sample Output 1
1 2 3 4
4 3 2 1
2 2 2 2
2 2 2 2
Sample Input 2 Sample Output 2
3 1 4 1 5 9
2 7 1 8 2 8
1 6 1 8 0 3
2 6 1 8 2 8

Please log in to submit a solution to this problem

Log in