Five random integers are placed at the corners of a pentagon. Typically, some of these numbers will be negative, but their sum is guaranteed to be positive. The goal is to get rid of all the negative numbers through a balanced process of subtraction and negation.
Starting with the lowest of the negative numbers, we negate the number (thus making it positive), and then subtract that value from each of its two neighbors.The sum of the new numbers will remain the same as the original pentagon,so the pentagon is still "balanced." This process(finding the lowest of the negative numbers,negating it, and dubtracting it from its neighbors) is then repeated until all of the numbers are non-negative.
During any step, if the lowest negative number appears at more than one corner, use the one that would be found first, if you started at the top corner and traversed in clockwise direction. The Problem:
Given the original five numbers at the corners of a pentagon, output the Positive Pentagon that can be created by following this process. You may assume this process will always make a pentagon "pentastic" in at most 1000 steps.
The first input line will contain only a single positive integer N, which is the number of pentagons to process. The next N lines will contain pentagon descriptions, one per line. Each pentagon description will consist of exactly 5 integers, which are in the range -999 to 999 (inclusive), and which sum up to a positive number less than 1000.
There will be exactly one space between numbers, and no leading or trailing spaces on the input lines. Positive numbers in the input will not have a leading '+' sign. The numbers are given in a clockwise order around the pentagon, starting from the top. This means that the 1st and 3rd numbers are neighbors of the 2nd number, the 5th and 2nd numbers are neighbors of the 1st number, and so on.
For each pentagon in the input, output the message "pentagon #p:",where p is the pentagon number (starting from 1). Then, for each pentagon, output the Positive Pentagon that results from applying the process described above. Output the numbers for each corner using the same ordering and method used in the input, with number for the top corner first, and the others following a clockwise order. Output one space between output numbers.
Leave a blank line after the output for each test case. Follow the format illustrated in the Sample Output.
2 -1 5 7 -4
99 -1 -1 4 0
1 2 2 3 1
97 1 1 2 0