После введения на сервере языков Java и C# ограничения по памяти у задач выросли минимум до 16 Мб, однако сами задачи остались прежними. Весь смысл этой задачи состоит в том, чтобы обойтись без массива (раньше ограничением по памяти был 1 Мб).
Что мешает сразу выводить суммы цифр в каждом разряде? То, что где-то на младших разрядах может произойти переполнение, в результате которого до текущего разряда может «подняться» дополнительная единица. Однако это возможно лишь, если все разряды между текущим и тем, в котором произошло переполнение, заполнены девятками. Т.е. как только в каком-то разряде получается сумма, меньшая 9, то можно с уверенностью сказать, что в старше разряды никакая 1 не уйдёт, и поэтому вывести их.
Таким образом, понадобится переменная для хранения текущего старшего разряда, в котором ещё возможно прибавление единицы из младших разрядов. Тогда между этим разрядом и просто текущим располагается k девяток (в противном случае единица просто бы не достигла старшего разряда). Соотвественно, необходима переменная, хранящая это число k. Наконец, необходимо рассмотреть три варианта при чтении текущего разряда:
- если там число, меньшее девяти, то выводим значение текущего старшего разряда, затем k девяток, обнуляем счётчик девяток, полагаем текущий разряд текущим старшим;
- если там 9, то просто увеличиваем счётчик;
- в противном случае выводим инкремент текущего старшего разряда, затем k нулей, обнуляем счётчик девяток, полагаем текущим старшим значение текущего разряда минус 10.
Важно отметить необходимость выводить результат с текущими нулями. Например, на тест [4 0001 0002] следует выводить [0003], а не [3].
Комментариев нет:
Отправить комментарий