El cumpleaños de Ponyo


Submit solution


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

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

El cumpleaños de Ponyo es uno de los más esperado por la comunidad de hámster, en esta fiesta el alpiste y las semillas de girasol están por todos lados, además se realizan bailes y juegos, estos últimos en ocasiones con artículos comprados en la Feria Tecnológica para Hámster. Este año a diferencia de los otros, Ponyo cuenta con muy poco presupuesto y el derroche habitual no será posible.

En la FTH Ponyo compró una máquina que genera papeles con números en el rango 1...1000000, por lo que a cada uno de los N hámster invitados (1 \leq N \leq 100000) según iban llegando se les iba dando un número generado por la máquina (no necesariamente distinto) y se le sentaba en un círculo gigante al lado del que había llegado anteriormente. Al finalizar la entrada de los invitados, el invitado i tenía como vecinos al i-1 y al i+1, en el caso del invitado 1 tenía como vecinos al 2 y al N. Luego de sentado los invitados Ponyo le propuso el siguiente juego: Cada uno de ustedes en el orden que llegaron, deben dar una vuelta al círculo y por cada invitado que tenga un papel con un número que divida al número del papel de ustedes recibirán una deliciosa semilla de girasol. Ponyo que es muy organizado quiere tener paquetes con la cantidad de semillas que le corresponde a cada invitado, por lo que le pide a usted que realice un programa que dado el número en el papel de cada invitado en orden que llega, determine la cantidad de semilla que le corresponderá a cada invitado en orden luego de realizado el juego.

Entrada

  • Línea 1: Un solo entero: N
  • Líneas 2..N+1: La línea i+1 contiene un solo entero: A_i que representa el número en el papel del invitado i

Salida

Líneas 1..N: En la línea i, imprima un solo número entero que es la cantidad de semilla que le corresponde al invitado i.

Ejemplo de entrada

5
2
1
2
3
4

Ejemplo de salida

2
0
2
1
3

Explicación

Entrada

A los 5 invitados se les dan los números 2, 1, 2, 3, y 4, respectivamente.

Salida

El primer invitado recibe 2 semillas, por tener el segundo y tercer invitado un número que divide al del primer invitado; el segundo no encuentra papel con número divisible; etc.


Comments


  • 1
    Osnielfc_07  commented on June 25, 2022, 4:56 a.m.

    Hermano , lee el editorial , ahí te explican la solución súper bien.


  • 0
    gleam_eyes  commented on June 25, 2022, 2:50 a.m.

    Alguien pudiera ayudarme a optimizar mi código por favor?, me sigue dando muchos casos TLE


  • 0
    angelmh  commented on March 16, 2018, 11:36 p.m. edit 10

    Buen dia a quien pueda leer esto, estuve intentando de varias formas resolver este problema y siempre me da WA (caso que lo que hago no sirve), pero me da la duda de que me da en varias pruebas siempre TLE, cosa que yo compruebo con un envio incorrecto para ver si se me va de tiempo por la idea que estoy desarrollando, mi envio esta vez fue el siguiente, yo tomo la cantidad de casos de prueba, itero esa cantidad y muestro las entradas, eso solamente me da 6 pruebas TLE de 13 y creo que eso no esta bien de alguna parte, solo sin procesar, con entrada y salida rapida me da eso, pudiera seguir siendo error mio??? mi lenguaje es JAVA, saludos.


  • -1
    dmesadiaz  commented on Feb. 20, 2018, 2:55 a.m. edited

    De que forma pudiera ayudarme eso si puedo utilizar solamente la memoria que necesito ya que me dicen la cantidad de numeros que me entran y como reduciria el tiempo.


  • 0
    dmesadiaz  commented on Feb. 17, 2018, 2:56 p.m.

    me da con muchos casos de prueba pero no tengo ni idea de como reducir el tiempo


    • 4
      josed  commented on Feb. 19, 2018, 1:15 p.m.

      Prueba utilizando memoria estática, o sea resérvala de antemano para el máximo tamaño del arreglo.