No divisibles

Submit solution
Points: 100 (partial)
Time limit: 0.03s
Java 8 0.3s
Memory limit: 64M
Author:
oanillar
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

¿Cuántos números hasta N no se dividen por 2, 3 o 5?

Entrada

La entrada consiste en un número entero 1 \leq N \leq 10\,000\,000.

Salida

Imprimir en una línea la cantidad de números que cumplen lo antes descrito.

Ejemplo de entrada

10

Ejemplo de salida

2

Comments


  • 2
    JoJo_Cubano_13  commented on Oct. 15, 2023, 9:33 p.m.

    Banda, este problema lo resolví el 26 de mayo de 2022 cuando estaba empezando a programar, hoy lo leí de nuevo por curiosidad, pero me encuentro que mi solución es lo menos óptima posible, de hecho, literalmente itero desde 1 hasta N, y le voy sumando a un contador por cada numero que no sea divisible uno a uno. Que alguien me explique por qué me da bien ya que el tiempo límite es 0.03 seg y no debería dar en tiempo para mi solución


    • 6
      linkyless  commented on Oct. 16, 2023, 7:46 a.m.

      Comentaré mi opinión con respecto al tema.

      Este problema está creado para hacerse utilizando las combinatorias. Luego de que los autores del problema comprobaran que se podía obtener todos los AC utilizando la fuerza bruta e iterando hasta el valor máximo de N para los casos (complejidad O(N)), los creadores decidieron "comprimir" y rebajar el tiempo hasta 0.03s para el límite de tiempo máximo en cada caso. Resulta que aun así no se pudo "solucionar" lo de los envíos en O(N), ya que utilizando el enfoque de fuerza bruta se llegaba como máximo a 0.029s, siendo un límite de tiempo un poco más bajo con respecto a 0.030s por 0.001s. Eso explicaría los casos de gente que ha realizado este problema utilizando la fuerza bruta.

      La solución debería ser disminuir el tiempo aún más a, quizás, 0.02s o aún más bajo; ya que las soluciones para los casos utilizando la combinatoria rondan ese tiempo.


  • 0
    CarlosJavier  commented on Aug. 30, 2021, 12:40 a.m. ← edited

    Los ultimos dos casos me dan TLE, alguien pudiera revisar mi sol y decirme como pudiera mejorar eso, se agradecería mucho.


    • 0
      eblabrada  commented on Aug. 30, 2021, 9:29 p.m. ← edit 2

      El tiempo límite en este problema (0.03s) no permite que soluciones O(n) entren en tiempo

      Nota del admin: El resto del comentario fue movido al editorial, ya que no se debe publicar código aquí.


  • 0
    PedroPabloAB  commented on March 4, 2021, 12:00 p.m.

    Isidrito, cout y cin pertenecientes a la biblioteca iostream son muy pesados a la hora de compilar el programa. Recomiendo que uses las funciones scanf (para entrada) y printf (para la salida), ambas están declaradas en la biblioteca stdio.h


  • -4
    isidrito  commented on March 1, 2021, 4:29 p.m.

    Sitio lento, da un TLE espeso aunque le pongas cout << "Cualquier cosa";


    • 4
      aniervs  commented on March 8, 2021, 3:15 a.m.

      Prueba añadir ios_base::sync_with_stdio(0); cin.tie(0); al inicio de la función main(). Y no uses endl para imprimir saltos de línea, en su lugar usa el caracter \n.


  • 0
    PedroPabloAB  commented on Oct. 14, 2020, 2:44 p.m.

    Gracias


  • 0
    PedroPabloAB  commented on Oct. 13, 2020, 4:37 p.m.

    Que significa RTE en los casos de prueba


    • 2
      josed  commented on Oct. 14, 2020, 1:45 p.m.

      RunTime Error


  • 0
    Alejandro777  commented on Oct. 10, 2020, 1:34 p.m.

    Pero mi teoria yo la veo bastante acertada, yo sumo los q son divisibles por 2, mas los divisibles por 3 menos los q son divisibles por 6, mas los q son divisibles por 5 menos los q son divisibles por 10 y 15.


    • 1
      ToOma_KFP  commented on Oct. 10, 2020, 2:49 p.m.

      Te faltaría tener en cuenta sumar los que son divisibles por 30


  • 0
    Alejandro777  commented on Oct. 9, 2020, 11:55 p.m.

    Puede alguien revisar mi sol y decirme q tan mal lo estoy haciendo...?


    • 1
      ToOma_KFP  commented on Oct. 10, 2020, 4:01 a.m. ← edit 5

      Hola. Este problema se puede resolver aplicando el principio de inclusión y exclusión. F(x, n) cantidad de números divisibles por x en el rango 1..n La cantidad de números que son divisibles por 2, 3 y 5 en el rango 1..n se calcula: x = F(2,n)+F(3,n)+F(5,n) - F(23,n)-F(2 5,n)-F(35,n) + F(235,n) Luego la respuesta del problema es: n - x


    • 0
      aniervs  commented on Oct. 10, 2020, 2:43 a.m.

      Explica tu idea


  • -1
    jnisac  commented on May 25, 2018, 7:29 p.m.

    porque me da TLE si lo único que hago es un cálculo aplicando principio de inclusión exclusión


  • 0
    cdamianlv  commented on March 1, 2018, 5:45 p.m.

    aplica el principio de inclusion y exclusion