Mensajes

No me había fijado que había puesto C, sin STL lo que he dicho como que no xDD.

Por si te sirve de ayuda, te dejo un código del algoritmo de Dinic que tenía hecho, sigue el formato de entrada y salida de este problema:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=761

Código (cpp) [Seleccionar] Expandir

/****************************************************************************************/
/* Algoritmo Dinic (usa blocking flows en lugar de caminos aumentativos) Coste: O(V^2E) */
/****************************************************************************************/

#include <iostream>
#include <string.h>
using namespace std;

//Cambiar constantes si es necesario
#define NODOS 100
const int INF = 1000000000;

int adj[NODOS][NODOS], deg[NODOS], cap[NODOS][NODOS], padre[NODOS], f[NODOS][NODOS], MC[NODOS], visto[NODOS];
int n, m; // n = |V|, m = |E|

int Q[NODOS]; //cola
int ebp, esp;

bool bfs(int s, int t) {
    esp = ebp = 0;
    memset(padre, -1, sizeof(padre));
    memset(visto, 0, sizeof(visto));
    visto[s] = 1;
    padre[s] = -2;
    Q[esp++] = s;
    while (ebp != esp) {
        int u = Q[ebp++];
        for (int i = 0; i < deg[u]; ++i) {
            int v = adj[u][i];
            if (cap[u][v] - f[u][v] > 0 and not visto[v]) {
                visto[v] = 1;
                padre[v] = u;
                Q[esp++] = v;
            }
        }
    }
    return visto[t];
}

void mincut(int s) {
    ebp = esp = 0;
    Q[esp++] = s;
    MC[s] = 1;
    while (ebp != esp) {
        int u = Q[ebp++];
        for (int i = 0; i < deg[u]; ++i) {
            int v = adj[u][i];
            if (cap[u][v] - f[u][v] > 0 and not MC[v]) {
                MC[v] = 1;
                Q[esp++] = v;
            }
        }
    }
}

int maxflow(int s, int t) {
    int flow = 0;
    memset(MC, 0, sizeof(MC));
    memset(f, 0, sizeof(f));
    while (bfs(s, t)) {
        for (int i = 0; i < n; ++i) {
            if (cap[i][t] - f[i][t] > 0 and padre[i] != -1) {
                int bot = cap[i][t] - f[i][t];
                for (int v = i, u = padre[i]; u >= 0; v = u, u = padre[u])
                    bot = min(bot, cap[u][v] - f[u][v]);
                if (bot == 0) continue;
                f[i][t] += bot;
                f[t][i] -= bot;
                for (int v = i, u = padre[i]; u >= 0; v = u, u = padre[u]) {
                    f[u][v] += bot;
                    f[v][u] -= bot;
                }
                flow += bot;
            }
        }
    }
    mincut(s); //MC[u] == 1 <=> u esta en la particion de s
    return flow;
}

int main() {
    int net = 1;
    while (cin >> n and n > 0) {
        memset(deg, 0, sizeof(deg));
        memset(cap, 0, sizeof(cap));
        int s, t;
        cin >> s >> t >> m;
        s--; t--;
        for (int i = 0; i < m; ++i) {
            int a, b, c;
            cin >> a >> b >> c;
            --a; --b;
            if (cap[a][b] == 0) {
                adj[a][deg[a]++] = b;
                adj[b][deg[b]++] = a;
            }
            cap[a][b] += c;
            cap[b][a] += c;
        }
        cout << "Network " << net++ << endl;
        cout << "The bandwidth is " << maxflow(s,t) << "." << endl << endl;
    }
}

Puedes leer una línea entera usando

Código (cpp) [Seleccionar] Expandir

getline(cin,s);
Donde s es una string.

Luego para parsear la entrada, si sabes que siempre serán números, puedes usar stringstream e ir leyendo desde s y añadiendo en un vector los números. Si no, deberías picar alguna función que compruebe que si es número o no.

En referencia al algoritmo, ¿cuál usas para calcular el Maxflow?

Bueno, ante todo no conozco Fortran ni lo he usado nunca, pero en tu código, no tendrías que poner a 0 las variables s y t para cada nuevo valor de n?

Otra cosa, por lo que veo, tú quieres encontrar los números amigos en un intervalo [n,m] y en tu código lo que haces es iterar sobre el valor de n y lo comparas con m, que la dejas fija. Así, suponiendo que lo que te he dicho arriba esté bien, sólo miras si m es amigo de algún número dentro del intervalo, pero si el intervalo es [30,50], no miras nunca si 34 es amigo de 42, por poner un ejemplo.

Una forma de corregir el algoritmo sería hacer lo siguiente (te lo pongo en pseudocódigo):

Código [Seleccionar] Expandir

i := n;
mientras i <= m
    s := suma_divisores(i);
    si s > i y s <= m
        t := suma_divisores(s);
        si t = i
            imprime i " y " s " son amigos";
        fsi
    fsi
    i := i + 1;
fsi
Con este algoritmo, la complejidad es del orden de O(n²) puesto que tal y como tú calculas los divisores necesitas otro bucle lineal para cada número. En C++, el código quedaría así más o menos (no lo he probado):

Código (cpp) [Seleccionar] Expandir

#include <iostream>
using namespace std;

int suma_div(int n) {
    int s = 0;
    for (int i = 1; i <= n/2; ++i) if (n%i == 0) s += i;
    return s;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = n; i <= m; ++i) {
        int s = suma_div(i);
        if (s > i and s <= m and suma_div(s) == i) cout << i << " y " << s << " son amigos" << endl;
    }
}
Para mejorar la eficiencia, podrías hacer una Criba de Eratóstenes al inicio del código para calcular todos los primos hasta la raíz cuadrada de m y luego para calcular los divisores, factorizar con dichos primos el número y generar con un pequeño bactracking todos los divisores, pero aunque supongo que iría más rápido, el código sería un poco más largo.

Bueno, pues uno muy típico. Dadas dos strings, decir la longitud de la máxima subsecuencia que tengan en común (subsecuencia != substring). Hacedlo con una complejidad temporal polinómica, nada de probar a saco todas las posibilidades.

Un saludo de ghastlyX

Si te he entendido, es un simple backtracking muy sencillo de hacer.

Código (cpp) [Seleccionar] Expandir

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

void rec(int p, string& s, string r) {
    if (p == s.size()) {
        do {
            cout << r << endl;
        } while (next_permutation(r.begin(), r.end()));
        return;
    }
    rec(p + 1, s, r);
    r.push_back(s[p]);
    rec(p + 1, s, r);
}

int main() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    rec(0, s, "");
}

Un saludo de ghastlyX

Supongo que os referís a mostrar los subconjuntos de k elementos dada una lista de n elementos. He hecho un código en C++ que hace eso:

Código (cpp) [Seleccionar] Expandir

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

typedef vector<int> VI;
typedef vector<bool> VB;

void rec(VI& v, VB& usado, int cnt, int primero, int n) {
    if (cnt == n) {
        cout << "{";
        bool first = true;
        for (int i = 0; i < usado.size(); ++i) {
            if (usado[i]) {
                if (first) first = false;
                else cout << ",";
                cout << v[i];
            }
        }
        cout << "}" << endl;
        return;
    }
    for (int i = primero; i < v.size(); ++i) {
        usado[i] = true;
        rec(v, usado, cnt + 1, i + 1, n);
        usado[i] = false;
    }
}

int main() {
    int n;
    cin >> n; //numero de elementos;
    VI v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    for (int i = 0; i <= n; ++i) {
        cout << "Subconjuntos de " << i << " elementos:" << endl;
        VB usado(n, false);
        rec(v, usado, 0, 0, i); //genera los subconjuntos de v de i elementos (habra n sobre i)
        cout << endl;
    }
}


Un saludo de ghastlyX

Para el 3, pongo varios algoritmos de ordenación en C++ que permiten ordenar un vector de reales:

Ordenación por inserción (O(n²)):

Código (cpp) [Seleccionar] Expandir

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

void ordena_por_insercion(vector<double>& v) {
    for (int i = 1; i < v.size(); ++i) {
        double x = v[i];
        int j = i;
        while (j > 0 and v[j-1]>x) {
            v[j] = v[j-1];
            --j;
        }
        v[j] = x;
    }
}


Ordenación por selección (O(n²)):

Código (cpp) [Seleccionar] Expandir

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

int posicion_maximo(const vector<double>& v, int n) {
    int pos = 0;
    for (int i = 1; i <= n; ++i)
        if (v[i] > v[pos]) pos = i;
    return pos;
}

void ordena_por_seleccion(vector<double>& v, int n) {
    if (n > 0) {
        swap(v[posicion_maximo(v,n)],v[n]);
        ordena_por_seleccion(v,n-1);
    }
}

Ordenación por burbuja (O(n²)):

Código (cpp) [Seleccionar] Expandir

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

void ordena_por_burbuja(vector<double>& v) {
    for (int i = 0; i < v.size(); ++i) {
        for (int j = v.size()-1; j >= i + 1; --j) {
            if (v[j] < v[j - 1] ) swap(v[j], v[j - 1]);
        }
    }
}

Y un par de algoritmos Divide&Conquer, primero Merge Sort (Ordenación por fusión, O(n log n)):

Código (cpp) [Seleccionar] Expandir

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

void fusiona(vector<double>& v, int e, int m, int d) {
    int n = d-e+1;
    vector<double> aux (n);
   
    int i = e;
    int j = m + 1;
    int k = 0;
    while (i <= m and j <= d) {
        if (v[i] <= v[j]) {
            aux[k] = v[i];
            ++i;
            ++k;
        }
        else {
            aux[k] = v[j];
            ++j;
            ++k;
        }
    }
    while (i <= m) {
        aux[k] = v[i];
        ++k;
        ++i;
    }
   
    while (j <= d) {
        aux[k] = v[j];
        ++j;
        ++k;
    }
    for (k = 0; k < n; ++k) v[k+e] = aux[k];
}

void ordena_rec(vector<double>& v, int e, int d) {
    if (e < d) {
        int m = (e+d)/2;
       
        ordena_rec(v,e,m);
        ordena_rec(v,m+1,d);
        fusiona(v,e,m,d);
    }
}

void ordena_por_fusion(vector<double>& v) {
    ordena_rec(v, 0, v.size()-1);
}

Otro Divide&Conquer, Quicksort (O(n log n) en caso promedio, O(n²) en el peor caso, aunque en general es más rápido que el Merge Sort):

Código (cpp) [Seleccionar] Expandir

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

int pivota(vector<double>& v, int ini, int fin) {
    double valor_pivote = v[ini];
    int p1 = ini + 1, p2 = fin - 1;
    while (p1 <= p2) {
        if (v[p1] < valor_pivote) ++p1;
else if (v[p2] >= valor_pivote) --p2;
else {
    swap(v[p1], v[p2]);
    ++p1;
    --p2;
}
    }
    swap(v[ini], v[p1 - 1]);
    return p1 - 1;
}

void quicksort_rec(vector<double>& v, int ini, int fin) {
    if (ini >= fin - 1) return;
    int pivote = pivota(v, ini, fin);
    quicksort_rec(v, ini, pivote);
    quicksort_rec(v, pivote + 1, fin);
}

void quicksort(vector<double>& v, int r) {
    quicksort_rec(v, 0, r);
}

Un saludo de ghastlyX

Si he entendido bien el enunciado, así es bastante más sencillo:

Código (cpp) [Seleccionar] Expandir

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

int main() {
    queue<int> Q;
    vector<int> cantidad(12, 0);
    int a;
    bool acabado;
    while (not acabado) {
        cout << "Ingresa una carta" << endl;
        cin >> a;
        acabado = (++cantidad[a - 1] == 3);
        Q.push(a);
    }
    cout << "Secuencia" << endl;
    while (not Q.empty()) {
        cout << Q.front() << " ";
        Q.pop();
    }
    cout << endl;
}

Un saludo de ghastlyX

Sí, así te ahorras tener que pasar por cada uno de los cuadrados. Habría que decidir si el cero es o no es cuadrado perfecto. Si lo consideras cuadrado perfecto, sería el bucle hasta K - 1 incluído, si no empezaría en 1 y sería hasta K.

Un saludo de ghastlyX

Este código no es muy eficiente...

Sabemos que un número tiene un número impar de divisores si y sólo si es un cuadrado perfecto.

En vez de ir número a número y ver si es un cuadrado, es más fácil directamente coger los k primeros números y mostrar sus cuadrados. Como yo digo haces k iteraciones, como tú haces estás mirando hasta el último de los cuadrados perfectos, es decir, k² iteraciones.

Un saludo de ghastlyX