Números Crecientes.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++

En IslaGrande, Bitman se dedicó a vender problemas a sitios de programación competitiva para ganar dinero. Tras el fracaso en ventas de su último problema, se dió cuenta que esto no era lo suyo y decidió retirarse del negocio de la venta de problemas, pero lo haría luego de crear un problema más que pondría en las pruebas de la Olimpiada Cubana de Informática (OCI).

El problema consiste en dado un número N usted debe encontrar la menor cantidad de sumandos, no necesariamente diferentes, en que se puede descomponer a N, de forma tal que todos los sumandos sean números crecientes. Un número es creciente si para cada dígito, no hay ninguno mayor que este a la izquierda, por ejemplo, los números 1, 25,  122344 y 1234 son crecientes, pero los números 10, 1231, 561 y 21 no lo son.

Entrada

La única línea de entrada contiene un solo entero N, el número que se quiere descomponer.

Salida

La única línea de salida contiene un entero k, la menor cantidad de números crecientes en la que se puede descomponer a N.

Subtareas

  • Subtarea 1 (40 puntos): 1 \leq N \leq 10^5.
  • Subtarea 2 (60 puntos): 1 \leq N \leq 10^{100000} .

Ejemplo #1 de Entrada

1234

Ejemplo #1 de Salida

1

Ejemplo #2 de Entrada

121

Ejemplo #2 de Salida

2

Una posible solución al segundo ejemplo son los sumandos 119 y 2.


Comments

There are no comments at the moment.