Skip to content

11608: 【原1608】Additive Number



author: Online Judge 原OJ链接:


Additive number is a string whose digits can form additive sequence. A valid additive sequence should contain at least three number. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two numbers.

Your task: given a string containing only digits '0^'-'9', write a function to determine if it’s an additive number.


  • Numbers in the additive sequence cannot have leading zeros, so for example, sequence 1,2,03 or 1,02,3 is invalid. That is to say, '02'and '023' are invalid. However, '0' is valid.
  • You need to figure out how to handle overflow for very large input integers.
  • You should consider the first two additive numbers might not be only a single number. (Eg: ‘199100199’ is also an additive number.)
  • If the input sequence has less than three numbers, the ouput should be 0.

Input Format

Your input needs to be a string consisting of only digits '0^'-'9', and the string which starts with ‘0’ is invalid.

Output Format

Output if the input is an additive number.

Sample Input


Sample Output


Oops! 本题目还没有解答!