Autor
|
Tema: Retos C/C++ (Leído 55,216 veces)
|
leogtz
. . .. ... ..... ........ ............. .....................
Colaborador
Desconectado
Mensajes: 3.069
/^$/
|
Sí, así es.
La idea es poner problemas sencillitos e ir aumentando la dificultad.
Saludos.
|
|
|
En línea
|
|
|
|
Oblivi0n
Desconectado
Mensajes: 392
Odio las ranas.
|
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
Mensajes: 1.513
El Dictador y Verdugo de H-Sec
|
@guru6: las reglas... @Og.: Te falto dejar el proximo reto.
|
|
|
En línea
|
|
|
|
ghastlyX
Ex-Staff
Desconectado
Mensajes: 1.900
|
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. #include <iostream> #include <vector> using namespace std; const int INF = 1000000000; int dp(int p, vector<int>& M, vector<int>& v) { if (p < 0) return INF; if (p == 0) return 0; //Caso base if (M[p] == -1) { M[p] = INF; for (int i = 0; i < v.size(); ++i) M[p] = min(M[p], 1 + dp(p - v[i], M, v)); } return M[p]; } int main() { int n, p; cin >> n; vector<int> v(n); for (int i = 0; i < n; ++i) cin >> v[i]; //Lectura de las monedas cin >> p; vector<int> M(p + 1, -1); //Tabla para la dinamica cout << dp(p, M, v) << endl; }
|
|
|
En línea
|
|
|
|
Og.
Desconectado
Mensajes: 822
Aprendiendo de la vida
|
@ghastlyX Bien!!
Te toca dejarnos un reto.
|
|
|
En línea
|
|-
|
|
|
[L]ord [R]NA
Desconectado
Mensajes: 1.513
El Dictador y Verdugo de H-Sec
|
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
Mensajes: 822
Aprendiendo de la vida
|
Mejor lo pongo como nuevo Post, después podrían haber confusiones. Reto #7Este 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 Salida Por que 5! = 12 0 hay estan los N ceros Ejemplo2 Entrada Salida Por que 10! = 36288 00 hay estan los N ceros PD: N puede ser de hasta 10 9
|
|
|
En línea
|
|-
|
|
|
ghastlyX
Ex-Staff
Desconectado
Mensajes: 1.900
|
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. #include <iostream> using namespace std; long long ceros(long long x) { long long res = 0, pot = 5; while (x/pot > 0) { res += x/pot; pot *= 5; } return res; } int main() { long long n; cin >> n; long long ini = 1, fin = 5*n; while (ini <= fin) { long long m = (ini+fin)/2; if (ceros(m) >= n) fin = m - 1; else ini = m + 1; } cout << fin + 1 << endl; }
|
|
|
En línea
|
|
|
|
[D4N93R]
Wiki
Desconectado
Mensajes: 1.646
My software never has bugs. Its just features!
|
#include "stdafx.h" #include <iostream> using namespace std; int _tmain(int argc, _TCHAR* argv[]) { int n, fac; cin >> n; cout << "HUHU: " << n *5 << endl; return 0; }
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
Mensajes: 1.900
|
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
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Retos .Net
« 1 2 3 »
Ejercicios
|
[D4N93R]
|
20
|
19,959
|
6 Diciembre 2010, 03:26 am
por final_frontier
|
|
|
Concursos y retos
Programación General
|
lnvisible
|
0
|
2,293
|
12 Diciembre 2010, 19:44 pm
por lnvisible
|
|
|
cuando consigo nuevos retos?
« 1 2 »
WarZone
|
Tyrz
|
11
|
5,966
|
15 Junio 2011, 23:11 pm
por [-Franko-]
|
|
|
Desarrollo de Retos Informaticos
Desarrollo Web
|
Sinedra
|
0
|
3,231
|
23 Febrero 2011, 19:23 pm
por Sinedra
|
|
|
Retos C/C++
Programación C/C++
|
N0body
|
5
|
10,944
|
9 Mayo 2011, 09:54 am
por ghastlyX
|
|