elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: Guía actualizada para evitar que un ransomware ataque tu empresa


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Retos C/C++
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: 1 [2] 3 4 5 6 7 8 9 Ir Abajo Respuesta Imprimir
Autor Tema: Retos C/C++  (Leído 38,392 veces)
leogtz
. . .. ... ..... ........ ............. .....................
Colaborador
***
Desconectado Desconectado

Mensajes: 3.069


/^$/


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #10 en: 19 Agosto 2010, 08:52 »

Sí, así es.

La idea es poner problemas sencillitos e ir aumentando la dificultad.

Saludos.


En línea

Código
  1. (( 1 / 0 )) &> /dev/null || {
  2. echo -e "stderrrrrrrrrrrrrrrrrrr";
  3. }
  4.  
http://leonardogtzr.wordpress.com/
leogutierrezramirez@gmail.com
Oblivi0n


Desconectado Desconectado

Mensajes: 392

Odio las ranas.


Ver Perfil
Re: Retos C/C++
« Respuesta #11 en: 19 Agosto 2010, 10:43 »

Buenas, yo me apunto a los retos, alguien puede decirme cuales estan resueltos y cuales no? (aunque los acabaré haciendo todos xD)


En línea

[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.513

El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #12 en: 19 Agosto 2010, 14:38 »

@guru6: las reglas...
@Og.: Te falto dejar el proximo reto.
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #13 en: 19 Agosto 2010, 15:15 »

Para el de las monedas, el problema surge en que el algoritmo greedy de ir cogiendo siempre las monedas más grandes no minimiza la cantidad de monedas, como se puede ver en el primer ejemplo que se ha puesto.

Una posible solución correcta pero muy ineficiente sería un backtracking probando todas las posibles maneras. Una forma mejor, que dejo a continuación, sería usando programación dinámica, quedando entonces una complejidad polinómica, en concreto O(np), donde n es el número de monedas y p la cantidad. Quizá me haya equivocado en algo, pero creo que es correcto.
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. const int INF = 1000000000;
  6.  
  7. int dp(int p, vector<int>& M, vector<int>& v) {
  8.    if (p < 0) return INF;
  9.    if (p == 0) return 0; //Caso base
  10.    if (M[p] == -1) {
  11.        M[p] = INF;
  12.        for (int i = 0; i < v.size(); ++i)
  13.            M[p] = min(M[p], 1 + dp(p - v[i], M, v));
  14.    }
  15.    return M[p];
  16. }
  17.  
  18. int main() {
  19.    int n, p;
  20.    cin >> n;
  21.    vector<int> v(n);
  22.    for (int i = 0; i < n; ++i) cin >> v[i]; //Lectura de las monedas
  23.    cin >> p;
  24.    vector<int> M(p + 1, -1); //Tabla para la dinamica
  25.    cout << dp(p, M, v) << endl;
  26. }
En línea

Og.


Desconectado Desconectado

Mensajes: 822


Aprendiendo de la vida


Ver Perfil
Re: Retos C/C++
« Respuesta #14 en: 19 Agosto 2010, 15:18 »

@ghastlyX Bien!!

Te toca dejarnos un reto.
En línea

|-
[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.513

El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #15 en: 19 Agosto 2010, 15:23 »

Og. coloca el reto#6, al parecer esta de acuerdo con la respuesta... numeralo y plantealo debajo de tu respuesta al de LeoGutierrez.
En línea

Og.


Desconectado Desconectado

Mensajes: 822


Aprendiendo de la vida


Ver Perfil
Re: Retos C/C++
« Respuesta #16 en: 19 Agosto 2010, 15:36 »

Mejor lo pongo como nuevo Post, después podrían haber confusiones.

Reto #7

Este estara simple.

Dado un numero N devuelve un numero K tal que K! tenga N 0's al final y K sea el menor posible.

Ejemplo1

Entrada
Código:
1

Salida
Código:
5
Por que 5! = 120 hay estan los N ceros

Ejemplo2

Entrada
Código:
2

Salida
Código:
10
Por que 10! = 3628800 hay estan los N ceros

PD: N puede ser de hasta 109
En línea

|-
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #17 en: 19 Agosto 2010, 16:24 »

A ver, está claro que hay que contar el número de parejas de factores 5 y 2 y como hay más doses que cincos, basta con contar los cincos si no me equivoco. De esta forma, dado un cierto K, para saber cuántos ceros tendrá K!, habrá que contar cuántas veces aparece cada una de las potencias de 5 si no me equivoco. Así, haciendo binaria sobre el resultado, me queda esto, aunque puede que haya algún error en el razonamiento.
Código
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. long long ceros(long long x) {
  5.    long long res = 0, pot = 5;
  6.    while (x/pot > 0) {
  7.        res += x/pot;
  8.        pot *= 5;
  9.    }
  10.    return res;
  11. }
  12.  
  13. int main() {
  14.    long long n;
  15.    cin >> n;
  16.    long long ini = 1, fin = 5*n;
  17.    while (ini <= fin) {
  18.        long long m = (ini+fin)/2;
  19.        if (ceros(m) >= n) fin = m - 1;
  20.        else ini = m + 1;
  21.    }
  22.    cout << fin + 1 << endl;
  23. }
  24.  
En línea

[D4N93R]
Wiki

Desconectado Desconectado

Mensajes: 1.647


My software never has bugs. Its just features!


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #18 en: 19 Agosto 2010, 16:52 »

Código
  1. #include "stdafx.h"
  2. #include <iostream>
  3. using namespace std;
  4.  
  5.  
  6. int _tmain(int argc, _TCHAR* argv[])
  7. {
  8. int n, fac;
  9. cin >> n;
  10. cout << "HUHU: " << n *5 << endl;
  11. return 0;
  12. }
  13.  

Sin comprobar ni nada xD para qué? todo factorial de K va atener mínimo N ceros al final xD
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #19 en: 19 Agosto 2010, 17:06 »

Pero te pide el menor K que cumpla eso y tu programa no devuelve el menor. Si la entrada es N = 6, tu programa devuelve 30 cuando el menor es 25.
En línea

Páginas: 1 [2] 3 4 5 6 7 8 9 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Retos .Net « 1 2 3 »
Ejercicios
[D4N93R] 20 13,377 Último mensaje 6 Diciembre 2010, 03:26
por final_frontier
Concursos y retos
Programación General
lnvisible 0 1,248 Último mensaje 12 Diciembre 2010, 19:44
por lnvisible
cuando consigo nuevos retos? « 1 2 »
WarZone
Tyrz 11 3,735 Último mensaje 15 Junio 2011, 23:11
por [-Franko-]
Desarrollo de Retos Informaticos
Desarrollo Web
Sinedra 0 2,233 Último mensaje 23 Febrero 2011, 19:23
por Sinedra
Retos C/C++
Programación C/C++
N0body 5 8,814 Último mensaje 9 Mayo 2011, 09:54
por ghastlyX
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines