import java.util.Scanner; public class UnstableMountains { private static boolean satisfies(int x, int [] sequence) { /* Given that x and sequence[0] are the first two terms, does the sequence[] as * a whole satisfy the constraints ? */ int [] full_sequence = new int[sequence.length * 12 + 1]; /* Can't need more than that. */ full_sequence[0] = x; full_sequence[1] = sequence[0]; int current_full_sequence_index = 1; for(int i = 1; i < sequence.length; i++) { /* Check if sequence[i] is within the next 10. */ boolean found = false; // System.out.println("Locating " + sequence[i]); for(int j = 0; j < 10; j++) { current_full_sequence_index++; full_sequence[current_full_sequence_index] = full_sequence[current_full_sequence_index-1] + full_sequence[current_full_sequence_index-2]; // System.out.println("full_sequence[current_full_sequence_index] = " + full_sequence[current_full_sequence_index]); if((full_sequence[current_full_sequence_index] > 1073741824) || (full_sequence[current_full_sequence_index] < -1073741824)) { return false; } if(full_sequence[current_full_sequence_index] == sequence[i]) { found = true; break; } } if(found == false) { return false; } } return true; } private static boolean solveFibbonacciHard(int [] sequence, int [] first_five_terms_to_output) { /* ------------------- INSERT CODE HERE ---------------------*/ /* Let "x" denote the element just before sequence[0]. * Let "a" denote sequence[0]; * * Then the next element would be: a + x * Then the next element would be: a + 2x * Then the next element would be: 2a + 3x * Then the next element would be: 3a + 5x * Then the next element would be: 5a + 8x * Then the next element would be: 8a + 13x * Then the next element would be: 13a + 21x * Then the next element would be: 21a + 34x * Then the next element would be: 34a + 55x * Then the next element would be: 55a + 89x * * More generally: i^th element = original_fibbonacci[i] * x + original_fibbonacci[i+1] * sequence[0]. * * Here 0^th element refers to the one immediately after sequence[0]. * * Reversing that: x = (i^th element - original_fibbonacci[i+1] * sequence[0]) / original_fibbonacci[i]; * * sequence[1] must be one of these. */ /* We need the first 11 coefficients of the Fibbonacci series. */ int[] original_fibbonacci = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}; int x = -1; for(int i = 0; i < 10; i++) { /* We are going to check if it is possible that sequence[1] is the i^th element after x and sequence[0]. */ int numerator = sequence[1] - original_fibbonacci[i+1] * sequence[0]; if(numerator % original_fibbonacci[i] == 0) { x = numerator/original_fibbonacci[i]; // System.out.println("Possible value for x = " + x); if(satisfies(x, sequence)) { first_five_terms_to_output[0] = sequence[0]; first_five_terms_to_output[1] = x + sequence[0]; first_five_terms_to_output[2] = x + 2 * sequence[0]; first_five_terms_to_output[3] = 2 * x + 3 * sequence[0]; first_five_terms_to_output[4] = 3 * x + 5 * sequence[0]; return true; } } } /* -------------------- END OF INSERTION --------------------*/ return false; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int numCases = sc.nextInt(); int[] first_five_terms_to_output = new int[5]; for(int i = 0; i < numCases; i++) { int lengthOfSequence = sc.nextInt(); int [] sequence = new int[lengthOfSequence]; for(int j = 0; j < lengthOfSequence; j++) { sequence[j] = sc.nextInt(); } if(solveFibbonacciHard(sequence, first_five_terms_to_output)) { System.out.println("STABLE " + first_five_terms_to_output[0] + " " + first_five_terms_to_output[1] + " " + first_five_terms_to_output[2] + " " + first_five_terms_to_output[3] + " " + first_five_terms_to_output[4]); } else { System.out.println("UNSTABLE"); } } } }