Цепочки переносов
В сумматоре с последовательным переносом каждый разряд ждёт перенос от соседа справа, и время сложения определяет самая длинная цепочка переносов — об этом глава «Машина считает» базового курса. Длинная арифметика складывает так же, только разрядов не 64, а миллионы.
Даны два натуральных числа в десятичной записи. Сложите их столбиком и сосчитайте, сколько раз возник перенос в следующий разряд и какой длины самая длинная цепочка переносов — сколько разрядов подряд передали единицу следующему. Например, при сложении 999 999 и 1 переносов шесть, и все они идут подряд. Один из тестов — первый миллион цифр числа π и первый миллион цифр числа e.
Вход
Две строки, в каждой — натуральное число без ведущих нулей, не длиннее 10⁶ цифр. Длины чисел могут различаться.
Выход
Два числа через пробел: количество переносов и длина самой длинной цепочки переносов.
Примеры
Пример 1
758 467
3 3
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перенос возникает, когда сумма двух цифр разряда и пришедшего переноса не меньше 10. Что будет в разряде, где цифры дают в сумме ровно 9?
2Подсказка 2
Превращать строки в числа и складывать их встроенной арифметикой бесполезно: сумма не говорит, где были переносы. Нужно пройти разряды справа налево, как в столбике, и держать перенос в переменной.
3Идея
Это сложение длинных чисел по основанию 10, только вместо цифр суммы нас интересует перенос. Идём от младшего разряда к старшему: s = ai + bi + перенос, новый перенос — 1, если s ≥ 10. Считаем переносы и длину текущей серии: перенос продлевает её, его отсутствие обнуляет.
4Разбор
Разворачиваем строки, чтобы индекс 0 был младшим разрядом. Если одно число короче, недостающие цифры — нули. Перенос из старшего разряда тоже считается: у 999 999 + 1 их шесть, и последний создаёт седьмую цифру ответа. Проход один, память — только для входа.
Любопытно, что получается на π и e. Переносов 500 105 на миллион разрядов — почти ровно половина, как у случайных цифр: перенос возникает при сумме от 10 до 18 (45 пар из 100) и при сумме 9 с переносом снизу (ещё 10 пар), и в среднем это одна вторая. Самая длинная цепочка — 21. Для случайных цифр цепочка продолжается с вероятностью 0,55 (сумма 9 или больше), и самая длинная из миллиона ожидается около log1/0,55(450 000) ≈ 22.
4+Решение
5Сложность
O(n) по времени, где n — длина длинного числа, и O(n) памяти на сами строки.
6Типичные ошибки
- Только пара цифр. Условие «ai + bi ≥ 10» пропускает разряды, где сумма цифр равна 9, а снизу пришла единица. На 999 + 1 оно даст один перенос вместо трёх.
- Разные длины. Цепочка может уйти за конец короткого числа: 999 999 + 1.
- Медленный ввод. Миллион цифр нужно читать целиком, а не по символу; в Go — через буферизованный ввод.