Unos y ceros

Submit solution
Points: 100 (partial)
Time limit: 14.0s
Java 8 20.0s
Python 20.0s
Memory limit: 1G
Author:
reinier
Problem types
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

La representación decimal de ciertos enteros positivos consite solo de unos y ceros, y teniendo al menos un dígito uno, por ejemplo 101. Si un entero positivo no cumple esta propiedad, uno puede tratar de multiplicarlo por algún entero positivo para comprobar si el producto cumple esta propiedad.

Entrada

Número K de casos de prueba (K es aproximadamente 500); en cada una de las siguientes K líneas hay un entero n \; (1 \leq n \leq 20000)

Salida

Para cada caso de prueba, su programa debe calcular el menor múltiplo del número n, que consiste solo de dígitos 1 y 0 (comenzando con 1).

Ejemplo de entrada

3
17
11011
17

Ejemplo de salida

11101
11011
11101

Comments


  • -3
    Osvaldo23  commented on Nov. 6, 2022, 6:36 p.m.

    Ño estoy pasao,lo tiré así mismo y dio quién lo diría


  • 1
    Osvaldo23  commented on Nov. 6, 2022, 6:25 p.m.

    Tiene mucho sentido,la solución,es el menor número binario que con los mismos digitos en la forma decimal es divisible por n,podemos iterar de 1 en adelante convertir a binario y dividir por n,ahora hay soluciones que tienen muchos dígitos por ejemplo los múltiplos de 9,el problema estaría desplazado a ver que combinación de potencias de 10 distintas al sumarlas de diviaible por n,pero priorizando la optimización.


  • 0
    Pimienta  commented on Aug. 2, 2021, 5:42 a.m.

    Se necesita algún truco para superar los 20 puntos en este problmea, o solo canalizar bien la fuerza bruta??


    • 0
      teruel  commented on Aug. 2, 2021, 3:38 p.m.

      bfs pasa en el límite de tiempo


      • 3
        Pimienta  commented on Aug. 2, 2021, 4:03 p.m.

        M intriga mucho como un algoritmo d grafos resuelve esto. Supongo q la solución es estudiar más


        • 3
          teruel  commented on Aug. 2, 2021, 10:29 p.m. ← edited

          Como los números de la forma 001 no son una solución válida, sabes que debe empezar con un 1, de ahí que puedes ir generando todos los números en orden creciente, empezando por 1, vas de X a 10X y a 10X + 1. Ahora solo necesitas saber si el número es divisible por K, y ahí te puedes apoyar en la aritmética modular.


          • 1
            Pimienta  commented on Sept. 20, 2021, 1:50 a.m.

            Gracias man


  • 0
    PedroPabloAB  commented on March 7, 2021, 12:16 a.m.

    Cómo es esto?


  • -8
    yrg  commented on Feb. 19, 2018, 12:09 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -5
    dcq  commented on Feb. 16, 2018, 3:04 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.