Game Of Sticks
All submissions for this problem are available.
Bob was walking down the street all alone one day thinking of what to do. While walking he found a couple of sticks of different lengths lying on the road. He picked them up and devised a game that could be played with them.
He glued magnets on to both ends of all the sticks so that he could easily join any two sticks. In this way he could form many triangles. Now the game he made was to use all or some of these magnetic sticks to form triangles. The winner of the game was the one who could form triangles such that the sum of the area of all triangles formed was larger.
So now he called up Alice and asked her to play this game with him. They both select some sticks and a make triangles out of them and then the one to make triangles such that total area of those triangles is larger wins.
As usual Alice goes first. In her turn she doesn't actually show all the triangles to Bob, rather she just tells him the total area of the triangles formed. Bob is aware of the fact that Alice might cheat or not play properly so if he sees that it is not possible to make triangles such that the sum of the area amounts to what Alice said then he openly declares that it's not possible , otherwise Bob plays his turn.
Alice plays optimally, in the sense that if she declares her total area then for at least one possible subset of the given set of stick lengths , the maximum area possible using the sticks in that subset is the area declared by Alice. If the area declared by Alice is not exactly equal to the maximum area of any subset of the set of stick lengths then Bob considers it to be not possible.
Bob plays optimally, in the sense that the area he declares will be the maximum possible area for the given set of stick lengths ( because he had a lot of time for testing all possible set selections while Alice was coming to his house ).
Therefore the game can end only in a DRAW,BOB WINS or AREA NOT POSSIBLE verdict (poor Alice :( ).
So given the stick lengths and the area declared by Alice, you have to predict the verdict of the game.
The input will start with a single line containing the number of sticks in the set ( 1<=N<=16 ).
The next N lines contain a single integer. The ith of these lines contains Li (1<=Li <=100) the length of the ith.
The last line contains a single real number A (1<=A<=10000000).
The first line of the output should consist of the verdict of the game. If the game ends in a draw print "DRAW" , if bob wins print "BOB WINS", if Alice's area is not proper as per Bob then print "AREA NOT POSSIBLE" (all of which will be without quotes).
Additionally, if Bob wins print in the next line the area declared by Bob. Errors in the answer less than 10-6 are neglected.
Input 1: 7 3 4 5 6 7 8 9 6 Output 1: BOB WINS 36.754383 Input 2: 7 3 4 5 6 7 8 9 21.630119 Output 2: AREA NOT POSSIBLE
Example case 1
Alice's area is valid as it is the maximum sum of area of triangles formed by picking sticks of length 3,4 and 5.But Bob wins as overall maximum is more than Alice's area.
Example case 2
Alice's area can be made using stick lengths 4,5 and 7 as one triangle and 3,8 and 9 as another triangle but using the set 4,5,7,3,8,and 9 the maximum area that can be made is 32.832816 which means Alice did not play optimally hence This area is not possible.
|Time Limit:||0.155446 - 0.310891 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions