Descomposición en 1, 2 y 3

Points: 100 (partial)

Time limit: 4.0s

Memory limit: 1G

Author:

Problem type

Allowed languages

C, C++, Go, Java, Python, VB

Dado un número entero positivo $N$ ~N~. Considere una secuencia de números enteros $A = (A_1, ..., A_K)$ ~A = (A_1, ..., A_K)~ que cumpla:

$\displaystyle \sum_{i=1}^{k} {A_i} = N$

y que cada $A_i$ ~A_i~ sea un número entero positivo tal que cada dígito en su notación decimal es $1$ ~1~, $2$ ~2~ o $3$ ~3~

Encuentre el valor mínimo posible de K, es decir, el número de elementos en dicha secuencia A.

Procese $T$ ~T~ casos de prueba por archivo de entrada.

Subtarea 1 $T \leq 1000, N \leq 10000$ ~T \leq 1000, N \leq 10000~. (30 puntos)

Subtarea 2 $T \leq 1000, N \leq 10^{18}$ ~T \leq 1000, N \leq 10^{18}~. (70 puntos)

T
N_1
N_2
.
.
.
N_T

answer1
answer2
.
.
.
answerT

Para cada $N$ ~N~, una secuencia $A$ ~A~ óptima se muestra a continuación:

$N = 456, A = (133, 323)$ ~N = 456, A = (133, 323)~
$N = 10000, A = (323,3132,3232,3313)$ ~N = 10000, A = (323,3132,3232,3313)~
$N = 123, A = (123)$ ~N = 123, A = (123)~
$N = 314, A = (312,2)$ ~N = 314, A = (312,2)~
$N = 91, A = (22,23,23,23)$ ~N = 91, A = (22,23,23,23)~

Comments

-2

Osvaldo23 commented on Sept. 23, 2022, 9:25 p.m.

Dato Curioso: Con 5 o menos números de esta forma es posible escribir cualquier N como suma de estos,es mi Hipótesis