TopCoder problem "IQTest" used in SRM 327 (Division II Level Two)



Problem Statement

    

You've taken a lot of 'IQ'-style tests, and noticed a common pattern appearing among them. They ask you to continue a given sequence of numbers. Say you're given the numbers 1,2,3,4,5, and are asked: what's the next number? Of course, the answer is 6. A slightly more complicated sequence would be 3,6,12,24,48, where 96 is the answer. Or, if the test is really tough, it might be even 1,4,13,40, where 121 is an answer (the latter follows the rule "multiply by 3 and add 1").

You've decided to write an automatic solver for these problems. It will be based on the following proposition: the rule for generating the sequence is always "multiply by a and add b", where a and b are integer (not necessarily positive) numbers.

You are given a int[] previous containing the first several numbers of the sequence. If this sequence could not be constructed using the above rule, return "BUG". If it could, and you can uniquely determine the next number, return a string containing that number without spaces or extra leading zeroes. If there are several possible next numbers, return "AMBIGUITY" (quotes for clarity only).

 

Definition

    
Class:IQTest
Method:nextNumber
Parameters:int[]
Returns:String
Method signature:String nextNumber(int[] previous)
(be sure your method is public)
    
 

Constraints

-previous will contain between 1 and 50 elements, inclusive.
-Each element of previous will be between -100 and 100, inclusive.
 

Examples

0)
    
{1, 2, 3, 4, 5}
Returns: "6"
1)
    
{3, 6, 12, 24, 48}
Returns: "96"
2)
    
{1, 4, 13, 40}
Returns: "121"
3)
    
{0}
Returns: "AMBIGUITY"
One cannot deduce anything from just one number.
4)
    
{-1, 2}
Returns: "AMBIGUITY"
There are many possibilities here: "multiply by -2 and add 0" with -4 as the next number, or "multiply by 1 and add 3" with 5, or "multiply by -1 and add 1" with -1, or "multiply by -5 and add -3" with -13, etc.
5)
    
{57, 57}
Returns: "57"
Sometimes just two numbers are enough to determine the next number. Although there are still many possibilities for a and b like "multiply by 1 and add 0" or "multiply by 2 and add -57", all of them yield 57 as the next number.
6)
    
{16, -8, 4, -2}
Returns: "BUG"
Here we're multiplying by -0.5, but non-integer multipliers are not allowed.
7)
    
{6, 5, 4, 3, 1}
Returns: "BUG"
There must have been some misprint.
8)
    
{-12, 12, -36, 60}
Returns: "-132"
It's "multiply by -2 and add -12".

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6600

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10007&pm=6600

Writer:

Petr

Testers:

PabloGilberto , brett1479 , Olexiy , ged

Problem categories:

Simple Math