Ctrl K

Цепочка сумм из цифр

Средняя
Дана строка digits из цифр. Разрежьте её на куски так, чтобы получилась **цепочка сумм** — список неотрицательных целых чисел, в котором: - не меньше трёх чисел; - каждое число, начиная с третьего, равно сумме двух предыдущих; - каждое число не больше 2³¹ − 1. Кусок не может начинаться с нуля, если только он сам не равен 0. Первые два числа однозначно задают всю цепочку, поэтому разбиения различаются только ими. Если подходящих разбиений несколько, верните то, у которого в первом числе меньше всего цифр, а при равенстве — то, у которого меньше всего цифр во втором числе. Если разбить нельзя, верните пустой список.
Пример 1
digits="358132134" → [3, 5, 8, 13, 21, 34]

3, 5, 8, 13, 21, 34: каждое число — сумма двух предыдущих.

Пример 2
digits="22325" → [2, 23, 25]

Подходят два разбиения: [2, 23, 25] и [22, 3, 25]. У первого первое число короче — его и возвращаем.

Пример 3
digits="1023" → []

После 1, 0 должна идти 1, а после 10, 2 — 12; кусок 02 запрещён из-за ведущего нуля. Разбить нельзя, ответ — пустой список.

Ограничения
  • 1 ≤ len(digits) ≤ 200
  • digits состоит только из цифр
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСлова с кнопочного телефона СредняяВсе правильные скобочные строки СредняяСлово на сетке букв СредняяIP-адреса из цепочки цифр СредняяНарезка слова на палиндромы Средняя
загружаем Python…
Вход
digits="358132134"
Ожидается
[3, 5, 8, 13, 21, 34]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 79 тестов на сервере, включая скрытые.