Skip to content

11608: 【原1608】Additive Number

题目

题目描述

author: Online Judge 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1608

Description

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.

Note:

  • 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

112358

Sample Output

1

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!