Mensajes

Pongo la mía, en C++. El formato de entrada es la longitud del lado del cubo y a continuación las coordenadas del vértice con coordenadas más pequeñas. Por ejemplo, si se quiere la intersección del cubo de lado 4 con vértice de menores coordenadas en (0,0,0) con el cubo de lado 3 con vértice de menores coordenadas en (-1,-1,-1), la entrada sería así:

4
0 0 0
3
-1 -1 -1

Y la salida devuelve el volumen de la intersección (devuelve 0 si la intersección es vacía).

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <vector>
using namespace std;

void lee(vector<int>& v) {
   int len;
   cin >> len;
   for (int i = 0; i < 3; ++i) {
       cin >> v[i];
       v[i + 3] = v[i] + len;
   }
}

int main() {
   vector<int> A(6), B(6);
   int res = 1;
   lee(A); lee(B);
   for (int i = 0; i < 3; ++i) A[i] = max(A[i], B[i]);
   for (int i = 3; i < 6; ++i) A[i] = min(A[i], B[i]);
   for (int i = 0; i < 3; ++i) res *= max(0, A[3 + i] - A[i]);
   cout << res << endl;
}

He puesto el caso siguiendo el formato de entrada como había dicho antes, lo que tu programa no lo sigue y cuando lo he evaluado en él ya lo he cambiado consecuentemente. A tu programa se lo he pasado así:

4
0 1
2 3
0 2
1 3

Es decir, le he dicho que hay cuatro registros y se los he puesto y dice que no son consistentes mientras que sí lo son. El 4 4 que tú decías si te fijas en el formato de la entrada en el enunciado, quiere decir que hay 4 animales y 4 registros, que se dan a continuación.

Edito: No había visto tu modificación. Y como te decía, lo del 4 4 no es un error, es la primera línea de la entrada. Fíjate en el enunciado del problema en el apartado de entrada.

¿Dónde lees en tu código la cantidad de animales (N)? Por lo que veo estás suponiendo que N = 3 como en los dos ejemplos que he puesto, pero como dice el enunciado, 3 <= N <= 10000. Es decir, la cantidad de animales también es un parámetro de la entrada, no sólo los registros.

Edito: Veo que tal y como lo haces no depende de la N, voy a ver si es correcto y te digo algo.

Revisado, no es correcto, te dejo un contraejemplo:

4 4
0 1
2 3
0 2
1 3

Tu programa dice que no son consistentes pero sí lo son. Por ejemplo, si 0 y 3 son gallos y 1 y 2 gallinas, todo cuadra.

[Reto 8:]

Pues os dejo el que he preparado mientras por si estaba bien.

Reto 8: Se tiene un corral con gallos y gallinas, de tal forma que entre todos suman N animales (no necesariamente hay N/2 de cada, de hecho no tiene porque ser N par) y los animales están numerados de 0 a N - 1, pero no se sabe qué número pertenece a cada animal.

Buscando entre los papeles del anterior dueño, se encuentran unos registros de apareamiento entre los animales, en forma A B, donde A y B son números entre 0 y N - 1 que indican que los animales A y B se aparearon (no se especifica cuál es el macho y cuál la hembra). Ahora el problema es ver si los registros encontrados son consistentes o no, es decir, si existe alguna manera de numerar los animales para que se puedan cumplir. Nótese que los gallos no se aparean entre ellos y lo mismo se aplica a las gallinas.

Entrada: Dos números N y M, donde M será el número de registros existentes. A continuación, M líneas con dos números cada una indicando un registro de apareamiento.

Salida: Si los datos son consistentes, se deberá escribir "Si", en caso contrario, "No".

Restricciones (para que no se hagan backtrackings más que nada): 3 <= N <= 10000, 0 <= M <= 100000.

Ejemplos:

Entrada 1:

3 2
0 1
1 2

Salida 1:

Si

Entrada 2:

3 3
0 1
1 2
2 0

Salida 2:

No

Si es correcta mi solución pongo el siguiente, pero la he pensado rápido y quizá haya algún error. A ver que dice Og.

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.

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


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

No tienes que guardar el recorrido, te da igual si sólo quieres saber cuántas ordenaciones hay (no cuáles son), simplemente deberías saber cuántos nodos tiene el subárbol, que lo puedes precalcular linealmente para todos los nodos haciendo un único recorrido inicial del árbol.

Dada una secuencia de números, puedes construir el BST (Binary Search Tree) asociado. Entonces, fijado un nodo del árbol que no sea una hoja, si consideras los subárboles izquierdo y derecho, mientras mantengas el orden relativo con los nodos de su subárbol, cualquier orden mantendrá el mismo BST.

En el caso que has puesto, el único nodo que tiene un subárbol a cada lado es el 4. El subárbol izquierdo es un 3 y el derecho un 5 y a continuación un 4. Por lo tanto, el 3, 5, 4 de la entrada lo puedes ordenar como quieras siempre que el 5 vaya antes que el 4, por estar en el mismo subárbol, y así salen las tres posibles opciones (moviendo de sitio el 3).

El cálculo de fijado un nodo cuántas ordenaciones válidas hay lo puedes calcular fácilmente con programación dinámica y seguramente por combinatoria también salga. Lo único que tienes que tener cuidado de no repetir casos.

Lo he pensado rápido así que quizá me haya equivocado en algún punto, pero si es correcto el algoritmo resultante tiene complejidad polinómica y por lo tanto es mucho más eficiente que lo que comentabas.