Mensajes

Como bien ha dicho Kasswed, sobre Z (los enteros), dicha ecuación no tiene solución, puesto que aparecen números que no son de Z.

Tan facil como plantearlo asi:

Código [Seleccionar] Expandir


2y = 4x + 25


¿No?

¡Saludos!

Consideremos una ecuación ax + by = c. Es fácil ver que existe alguna solución entera si y sólo si mcd(a,b) | c, es decir, si el mcd de a y b divide c. Una posible demostración sería la siguiente:

Supongamos que el mcd divide a c. No es pérdida de generalidad suponer que mcd(a, b) = 1, ya que si no lo fuera, por hipótesis podríamos dividir a ambos lados de la igualdad, obteniendo una nueva ecuación diofántica con las mismas soluciones donde a, b son coprimos. Por lo tanto supongamos que a, b son coprimos. Por Bezout tenemos que existen infinitas soluciones (x,y) enteras de la forma ax + by = 1, de forma que multiplicando a ambos lados por c, tenemos infinitas soluciones de la ecuación diofántica.

La otra implicación es directa, dado que si tenemos una solución (x, y) tal que ax + by = c, sea d = mcd(a,b). Se tiene que d | a y d | b, de forma que d | (ax + by) => d | c.

Visto esto, tenemos que la ecuación con coeficientes sobre Z es -4x + 2y = 25. El mcd sería 2, que no divide 25, luego no existen soluciones enteras, por mucho que se quiten los decimales.

En este caso, suponiendo que hasta donde se ha posteado fuera correcto, el conjunto de soluciones es infinito sobre R, dando lugar a una recta de posibles valores.

Esto se suele resolver con la técnica de máximos-mínimos, generalizable a más dimensiones. Si se tienen dos segmentos en R, su intersección claramente será el máximo de los extremos izquierdos y el mínimo de los extremos derechos (siempre que esta exista, es decir, que el máximo sea menor o igual que el mínimo).

De esta forma, queda un código muy simple:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

int main() {
    int a1, b1, a2, b2;
    cin >> a1 >> b1 >> a2 >> b2;
    int a = max(a1, a2), b = min(b1, b2);
    if (a <= b) cout << a << " " << b << endl;
    else cout << "Interseccion vacia" << endl;
}

En efecto, la solución que esperaba era la recursiva, pongo aquí la solución que había hecho yo:

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

void rec() {
    char c;
    if (cin >> c) {
        rec();
        cout << c;
    }
}

int main() {
    rec();
    cout << endl;
}

Respecto a lo que se comentaba de la pila, aguanta perfectamente 100 llamadas recursivas (y bastantes más):

Código [Seleccionar] Expandir

alex@portatil:~/codigos$ cat entrada.in
10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
alex@portatil:~/codigos$ wc -c entrada.in
102 entrada.in
alex@portatil:~/codigos$ g++ prueba.cc
alex@portatil:~/codigos$ ./a.out < entrada.in
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001


El rango es totalmente intencionado, lo he puesto precisamente para que no coja en las variables numéricas primitivas. Ahí está la gracia del problema.

Para los que pedís más precisión en las restricciones o los que consideráis el ejercicio demasiado fácil, con permiso del autor lo podéis complicar un poco (bastante poco para cualquiera que sepa cuatro cosas de programación) siguiendo el siguiente enunciado, para el que la solución propuesta anteriormente no funcionará.

Problema:
Dado un número 0 <= n <= 10¹⁰⁰ por la entrada estándar (stdin), se debe mostrar por la salida estándar (stdout) su número girado, tal que si los dígitos de n son a₁, ..., a_n, los de su número girado serán a_n, ..., a₁ (es la misma definición, formalizada un poco). Tened en cuenta por ejemplo que el girado de 100 es 001 y no 1.

Restricciones:
No se pueden utilizar arrays, structs, strings, clases ni nada similar, tan sólo los tipos de variables básicos de C/C++, es decir int, char, long long, etc.

Algunos de los ejercicios del tema 2 te han quedado muy largos y poco simples, suponiendo que sean correctos, puesto que no los he mirado todos. Te pongo soluciones alternativas más cortas y simples, por lo menos a mi parecer.

Código (cpp) [Seleccionar] Expandir

//Problema 1
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cout << string(n - i, ' ');
        for (int j = 0; j + 1 < i; ++j) cout << "* ";
        cout << "*" << endl;
    }
}

//Problema 2
#include <iostream>
using namespace std;

void imprime(int n, int i) {
    if (i == 1) cout << n%10 << endl;
    else if (n/10 == 0) cout << -1 << endl;
    else imprime(n/10, i - 1);
}

int main() {
    int n, i;
    cin >> n >> i;
    imprime(n, i);
}

//Problema 3
#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    for (int i = 0; i < s.size() >> 1; ++i) {
        if (i > 0) cout << ", ";
        cout << s[i] << " + " << s[s.size() - 1 - i] << " = " << s[i] - '0' + s[s.size() - 1 - i] - '0';
    }
    if (s.size()&1) cout << ((s.size() > 1)?", ":"") << s[s.size()>>1];
    cout << endl;
}


//Problema 4
#include <iostream>
using namespace std;

int main() {
    int maxim = 0, act = 0;
    char c, ant = '0';
    while (cin >> c) {
        if (c >= ant) ++act;
        else {
            maxim = max(maxim, act);
            act = 1;
        }
        ant = c;
    }
    maxim = max(maxim, act);
    cout << maxim << endl;
}


//Problema 6
#include <iostream>
using namespace std;

int mcd(int a, int b) {
    if (a == b) return a;
    return (a > b) ? mcd(a - b, b) : mcd(b - a, a);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << mcd(a, b) << endl;
}


Siguiendo tu notación, efectivamente Dijkstra tiene complejidad cuadrática sobre los nodos en su implementación directa. Si lo implementas con colas de prioridad con coste logarítmico, bajas la complejidad a O((n + a)logn), que es la complejidad de BFS con un factor logarítmico extra (programándolo bien, obviamente).

Si el grafo es completo, i.e. a = n², uno quedará O(n²logn) y otro O(n²), que evidentemente es mejor.

Esto hablando de las versiones estándar de cada uno. Si se quiere rizar el rizo y hablar de la versión de Dijkstra con Fibonacci Heaps, que rara vez se usa a la práctica, entonces se acaba teniendo una complejidad teórica (no hablemos ya de las constantes debidas a implementación) de O(a + nlogn), que sigue siendo peor que un BFS.

Eso es falso, el orden de complejidad de Dijkstra es mayor que el de BFS y a la práctica también es más lento. Además, también hay pseudocódigos a patadas de BFS, que además es más fácil de programar que Dijkstra.

Edito:
Respecto a la pregunta anterior, sirve tanto si el grafo es dirigido como no dirigido.

Kruskal si lees y entiendes cómo funciona no es para nada complicado. Mira qué hace el algoritmo y una vez lo entiendas lo podrás programar. La única parte algo más complicada es si quieres hacer eficientemente el paso de comprobar si dos nodos están unidos directa o indirectamente, que lo puedes programar con un MFSet.

Respecto al segundo problema, como ya te han dicho se reduce a un problema de caminos mínimos. Ignora los costes originales de las aristas y ponles a todas coste 1. Es evidente que el camino mínimo entre dos nodos será con estos nuevos costes aquel que use un menor número de aristas. En lo que discrepo es con la recomendación de usar Dijkstra. Cuando todas las aristas tienen el mismo coste, puede calcularse la mínima distancia de un nodo al resto usando simplemente un BFS estándar, dado que este recorre el grafo por niveles. Y BFS es más eficiente que Dijkstra.

Si puedes usar la STL, es mucho más simple usando la función next_permutation. Si consideras el conjunto de las posibles permutaciones, dada una permutación, puedes considerar el agrupamiento que junta sigma(2i) con sigma(2i + 1), siendo sigma la permutación. Es decir, coges la permutación y vas juntando de dos en dos. Esto claramente no es biyectivo, pero si exhaustivo, de forma que aunque repetirás casos, no te dejarás ninguno. Por lo tanto será bastante más lento que si no repites y lo haces con un backtracking haciendo podas antes de calcular toda la permutación, pero salen cuatro líneas de código, haciendo algo así:

Código (cpp) [Seleccionar] Expandir

    vector<int> o(n);
    for (int i = 0; i < n; ++i) o[i] = i;
    int res = 0;
    do {
        int suma = 0;
        for (int i = 0; i + 1 < n; i += 2) suma += valor(o[i], o[i + 1]);
        res = max(res, suma);
    } while (next_permutation(o.begin(), o.end()));
    cout << res << endl;

Como comentario, se puede resolver este problema en tiempo polinómico (aunque el algoritmo es bastante complicado). Concretamente, tu problema se reduce a uno de los subproblemas (el más difícil) que aparecen al tratar de resolver el conocido Chinese Postman Problem.