AIOC Banner

Problem: Psychological Jujitsu

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


Psychological Jujitsu

Input File: psychin.txt
Output File: psychout.txt
Time Limit: 1 second

Psychological jujitsu: a two player card game of infinite wit and cunning. The rules are simple. Each player has thirteen different cards numbered from 1 to 13. A third pile of cards numbered from 1 to 13 known as the "prize deck" is placed face down in the middle of the table.

The game consists of 13 rounds. For each round, the top card on the prize deck is turned face up on the table; this becomes the "prize card". Each player then secretly chooses one of the cards in their hand to use as a bid. The player who has the higher bid wins the number of points on the prize card. If both players bid the same amount, no points are allocated for the round at all. After each round the prize card and the two cards used to bid are thrown away. The player with the highest score at the end of the game wins.

Unbeknown to friends and family, you are actually a psychological jujitsu grandmaster. By years of practice of carefully analysing your opponent, you have learnt how to accurately determine in advance what value they will bid for each particular prize card.

Unsatisfied with merely winning tournaments, you wish to flaunt your brilliance by beating your opponent by the greatest possible margin. That is, the difference between your score and your opponent's score should be as large as possible.

Your task is, given a list of what bid your opponent will make for each prize card, to determine the greatest margin by which you can beat your opponent.

Input

The input file will consist of exactly thirteen lines. The ith line of input will contain a single integer bi, the value your opponent will bid for the prize card of value i (1 <= bi <= 13). Each of the bids from 1 to 13 will appear precisely once in the input file.

Output

The output file should contain a single line containing a single integer, giving the maximum possible margin by which you can beat your opponent. If it is not possible to win against your opponent, your program should output the single line "Not possible".

Sample Input

2
1
4
5
12
3
8
9
7
6
11
10
13

Sample Output

68

Explanation

For each of the following prize cards, your opponent makes the following bids:

Prize 1 2 3 4 5 6 7 8 9 10 11 12 13
Bid 2 1 4 5 12 3 8 9 7 6 11 10 13

Your best possible play is to make the following bids for each prize card:

Prize 1 2 3 4 5 6 7 8 9 10 11 12 13
Bid 3 2 5 6 1 4 9 10 8 7 12 11 13

By bidding this way, you win prize cards 1-4 and 6-12. Your opponent wins prize card 5, and you both draw for prize card 13 (causing it to be awarded to neither player). Your total score is 73, while your opponent remains on 5 points. The difference between your scores is 73-5 = 68, the maximum margin possible.

Scoring

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

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 24 May 2019, 11:18pm AEST