Retos C/C++

[leogtz]

Sí, así es.

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

Saludos.

[Oblivi0n]

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

[[L]ord [R]NA]

@guru6: las reglas...
@Og.: Te falto dejar el proximo reto.

[ghastlyX]

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 (cpp) [Seleccionar] Expandir

#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;
}

[Og.]

@ghastlyX Bien!!

Te toca dejarnos un reto.

[[L]ord [R]NA]

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

[Og.]

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 [Seleccionar] Expandir

1

Salida

Código [Seleccionar] Expandir

5
Por que 5! = 120 hay estan los N ceros

Ejemplo2

Entrada

Código [Seleccionar] Expandir

2

Salida

Código [Seleccionar] Expandir

10
Por que 10! = 3628800 hay estan los N ceros

PD: N puede ser de hasta 10⁹

[ghastlyX]

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 (cpp) [Seleccionar] Expandir

#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;
}


[[D4N93R]]

Código (cpp) [Seleccionar] Expandir


#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

[ghastlyX]

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.