Descomposición en 1, 2 y 3.

Submit solution
Points: 100 (partial)
Time limit: 4.0s
Memory limit: 1G
Author:
humbertoyusta
Problem type
Allowed languages
C, C++, Go, Java, Python, VB

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

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

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

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

Entrada

Procese T casos de prueba por archivo de entrada.

T
N_1
N_2
.
.
.
N_T

Salida

answer1
answer2
.
.
.
answerT

Subtareas

  • Subtarea 1 (30 puntos): T \leq 1000, N \leq 10000.
  • Subtarea 2 (70 puntos): T \leq 1000, N \leq 10^{18}.

Ejemplo de Entrada

5
456
10000
123
314
91

Ejemplo de Salida

2
4
1
2
4

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

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

Comments


  • 0
    Wizsuf  commented on Aug. 24, 2026, 9:30 p.m.

    Me voy a volver loco con este problema. Probé estos casos y todos me dan correctos pero cuando subo el problema me da WA.

    entrada:

    15

    1

    2

    3

    10

    13

    91

    123

    300

    333

    456

    2000

    10000

    99999

    1000001

    999999999999999999

    mi salida:

    1

    1

    1

    4

    1

    4

    1

    4

    1

    2

    4

    4

    3

    4

    3

    comprobación:

    1 ya válido

    1 ya válido

    1 ya válido

    4 10 → 3 → 7 → 3 → 4 → 3 → 1

    1 13 ya válido

    4 91 → 33 → 58 → 33 → 25 → 23 → 2 → válido

    1 123 ya válido

    4 300 → 233 → 67 → 33 → 34 → 33 → 1

    1 333 ya válido

    2 456 → 333 → 123 → válido

    4 2000 → 1333 → 334 → 333 → 1

    4 10000 → 3333 → 6667 → 3333 → 3334 → 3333 → 1

    3 99999 → 33333 → 66666 → 33333 → válido

    4 1000001 → 333333 → 666668 → 333333 → 333335 → 333333 → 1

    3 999999999999999999 → 333333333333333333 → 666666666666666666 → 333333333333333333 → válido

    Esta bien no? Todo comprobado a mano y ni siquiera paso el primer caso ¿pueden explicarme que está mal? (no se si permitan subir mi codigo así que no lo haré)


    • 0
      Wizsuf  commented on Aug. 24, 2026, 9:31 p.m.

      perdonen por hacerlo tan separado pero el prewiew lo unía todo y quedaba peor


      • 0
        samu_good1  commented on Aug. 25, 2026, 12:54 a.m.

        hola de nuevo XD, este problema creo que es un poco complicado podrias tratar de hacer algunos mas basicos :)


        • 0
          Wizsuf  commented on Aug. 25, 2026, 1:40 a.m.

          hola de nuevo. Bien intentaré resolverlo cuando esté en los primeros 100 puestos


          • 0
            samu_good1  commented on Aug. 25, 2026, 4:35 a.m.

            me acabo de acordar q se cayo el dmoj cusndo te explicaba tu error , bueno la cosa es esto tu codigo resta el mayor sehun vi tu simulacion entoces pars este caso 432 restas 333 dando 99 pero si restas 111 te da 321 y ya :)


          • 0
            samu_good1  commented on Aug. 25, 2026, 4:33 a.m.

            jsjs buena obsesion sigue asi :)