elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado:


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Retos C/C++
0 Usuarios y 3 Visitantes están viendo este tema.
Páginas: 1 2 3 [4] 5 6 7 8 9 Ir Abajo Respuesta Imprimir
Autor Tema: Retos C/C++  (Leído 40,821 veces)
Og.


Desconectado Desconectado

Mensajes: 822


Aprendiendo de la vida


Ver Perfil
Re: Retos C/C++
« Respuesta #30 en: 20 Agosto 2010, 02:00 am »

Buen problema. Así si son divertidos.
Código
  1. #include <iostream>
  2.  
  3. using std::cin;
  4. using std::cout;
  5. using std::endl;
  6.  
  7. struct pareja
  8. {
  9.    int h;
  10.    int m;
  11. };
  12.  
  13. pareja *relaciones;
  14. int N, M;
  15. short *pollos, *relacionesChk;
  16. bool correcto;
  17.  
  18. bool Relaciona(int);
  19. void entid(int num, int tp);
  20.  
  21. int main(void)
  22. {
  23.    cin >> N >> M;
  24.    pollos = new short[N];
  25.    relacionesChk = new short[M];
  26.    relaciones = new pareja[M];
  27.    for(int i=0; i<M; i++)
  28.        relacionesChk[i] = 0;
  29.    for(int i=0; i<M; i++)
  30.    {
  31.        cin >> relaciones[i].h >> relaciones[i].m;
  32.    }
  33.    correcto = true;
  34.    Relaciona(0);
  35.    if(correcto)
  36.        cout << "SI";
  37.    else
  38.        cout << "NO";
  39.    delete pollos;
  40.    delete relacionesChk;
  41.    delete relaciones;
  42. }
  43.  
  44. bool Relaciona(int num)
  45. {
  46.    if(!correcto)
  47.        return 0;
  48.    if(num>=M)
  49.        return true;
  50.    for(int i=0; i<N; i++)
  51.        pollos[i] = -1;
  52.    relacionesChk[num] = 1;
  53.    pollos[relaciones[num].h] = 0;
  54.    pollos[relaciones[num].m] = 1;
  55.    entid(relaciones[num].h, 1);
  56.    entid(relaciones[num].m, 0);
  57.    while(relacionesChk[++num] && num<=M);
  58.    Relaciona(num);
  59. }
  60.  
  61. void entid(int num, int tp)
  62. {
  63.    if(!correcto)
  64.        return;
  65.    for(int i=0; i<M; i++)
  66.        if(!relacionesChk[i])
  67.        {
  68.            if(relaciones[i].h==num)
  69.            {
  70.                relacionesChk[i] = 1;
  71.                if(pollos[relaciones[i].m] == -1)
  72.                {
  73.                    pollos[relaciones[i].m] = tp;
  74.                    entid(relaciones[i].m, !tp);
  75.                }
  76.                else if(pollos[relaciones[i].m] == !tp)
  77.                    correcto = false;
  78.            } else if(relaciones[i].m==num) {
  79.                relacionesChk[i] = 1;
  80.                if(pollos[relaciones[i].h] == -1)
  81.                {
  82.                    pollos[relaciones[i].h] = tp;
  83.                    entid(relaciones[i].h, !tp);
  84.                }
  85.                else if(pollos[relaciones[i].h] == !tp)
  86.                    correcto = false;
  87.            }
  88.        }
  89.    return;
  90. }


En línea

|-
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #31 en: 20 Agosto 2010, 02:19 am »

Parece correcto mirando el código por encima y probando algunos casos. La idea era ver que el problema se puede convertir en un grafo donde los animales son los nodos y las relaciones entre ellos las aristas. Una vez hecho esto, la cuestión era ver si este grafo era bipartido o no (si se pueden partir los nodos en dos grupos tal que cada grupo no tenga aristas entre ellos, que serán los machos y las hembras).

Es fácil de demostrar y ver que si G = (V,E) es un grafo no dirigido, los siguientes enunciados son equivalentes:

1) G es bipartido.
2) G es bicoloreable (2-coloreable).
3) G no contiene ningún ciclo simple de longitud impar.

Como las tres son equivalentes, se puede mirar cualquiera de ellas y la más eficiente de comprobar es la segunda, que mirando tú código supongo que es lo que haces.

Os dejo también la solución que había preparado:
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef vector<int> VI;
  6. typedef vector<VI> VVI;
  7.  
  8. bool bicolor(int u, int c, VVI& G, VI& color) {
  9.    bool res = true;
  10.    for (int i = 0; i < G[u].size(); ++i) {
  11.        int v = G[u][i];
  12.        if (color[v] < 0) {
  13.            color[v] = c;
  14.            res &= bicolor(v, 1 - c, G, color);
  15.        }
  16.        else if (color[v] != c) res = false;
  17.    }
  18.    return res;
  19. }
  20.  
  21. int main() {
  22.    int n, m;
  23.    cin >> n >> m;
  24.    VVI G(n);
  25.    for (int i = 0; i < m; ++i) {
  26.        int a, b;
  27.        cin >> a >> b;
  28.        G[a].push_back(b);
  29.        G[b].push_back(a);
  30.    }
  31.    VI color(n, -1);
  32.    bool res = true;
  33.    for (int i = 0; i < n; ++i) { //Por si hay mas de un componente
  34.        if (color[i] < 0) {
  35.            color[i] = 0;
  36.            res &= bicolor(i, 1, G, color);
  37.        }
  38.    }
  39.    if (res) cout << "Si" << endl;
  40.    else cout << "No" << endl;    
  41. }

PD: Cuidado con las salidas, tu código imprime SI y NO en vez de Si y No. A mí me da igual, pero si eres olímpico como supongo por tu firma, ves con cuidado con estas cosas en los concursos, puesto que el juez automático te daría un WA y estos errores tontos en pleno concurso pueden costar de encontrar, pensando que es problema en el código o el razonamiento.

Edito: Se me olvidaba, dos cosas:
- Para saber si un grafo es bicoloreable basta con ir asignando a cada nodo libre un color cualquiera y a sus vecinos el contrario. Si se encuentra algún vecino con el mismo color es que no es bicoloreable.

- Pon el siguiente reto xDD


« Última modificación: 20 Agosto 2010, 02:22 am por ghastlyX » En línea

Og.


Desconectado Desconectado

Mensajes: 822


Aprendiendo de la vida


Ver Perfil
Re: Retos C/C++
« Respuesta #32 en: 20 Agosto 2010, 03:30 am »

jeje, a un amigo le paso que no le contaron los casos por un \n de mas al final del programa xD

Reto #9

Recibes don enteros (X, Y) los cuales representan una caja

y tu quieres partir esa caja en cuadrados exactos. hacer un programa que te diga el mínimo numero de cuadrados exactos dentro de una caja.

Ejemplo1

Entrada
Código:
3 5

Salida
Código:
4
Explicacion
1 caja de 3*3
1 caja de 2*2
2 cajas de 1*1

Ejemplo2

Entrada
Código:
5 6

Salida
Código:
5
Explicacion
2 cajas de 3*3
3 cajas de 2*2
« Última modificación: 20 Agosto 2010, 03:46 am por Og. » En línea

|-
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #33 en: 20 Agosto 2010, 15:35 pm »

Supongo que sería así:
Código
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef vector<int> VI;
  6. typedef vector<VI> VVI;
  7.  
  8. const int INF = 1000000000;
  9.  
  10. int dp(int n, int m, VVI& M) {
  11.    if (n < m) return dp(m, n, M);
  12.    if (m == 0) return 0;
  13.    if (M[n][m] == -1) {
  14.        M[n][m] = INF;
  15.        for (int x = 0; x <= m; ++x) {
  16.            M[n][m] = min(M[n][m], 1 + dp(x, m - x, M) + dp(n - x, m, M));
  17.            M[n][m] = min(M[n][m], 1 + dp(n, m - x, M) + dp(n - x, x, M));
  18.        }
  19.    }
  20.    return M[n][m];
  21. }
  22.  
  23. int main() {
  24.    int n, m;
  25.    cin >> n >> m;
  26.    if (n < m) swap(n, m);
  27.    VVI M(n + 1, VI(m + 1, -1));
  28.    cout << dp(n, m, M) << endl;
  29. }
  30.  

A ver si la gente le pierde un poco el miedo a las dinámicas!
En línea

[L]ord [R]NA


Desconectado Desconectado

Mensajes: 1.513

El Dictador y Verdugo de H-Sec


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #34 en: 20 Agosto 2010, 21:08 pm »

GhastlyX deja el proximo reto... :xD sin mucho chackra
En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #35 en: 21 Agosto 2010, 06:15 am »

Reto #10
Una compañía de autobuses sospecha que en una de sus rutas el autobús va demasiado lleno y están estudiando poner otro más para mejorar el servicio. Para ello, han colocado un contador en las puertas que registra en cada parada cuánto varía la cantidad de personas en el bus (este número podrá ser obviamente negativo).

En un cierto momento de la ruta, el conductor activa el contador y se generan los registros y más tarde lo apaga (nótese que esto implica que la suma de las diferencias podrá ser negativa, puesto que podía haber gente dentro del bus). La compañía estudiará después las sumas de subsecuencias consecutivas de la secuencia de registros. Por ejemplo, si la secuencia es -20 -15 30 -15 30, subsecuencias consecutivas son entre otras -15 30, 30 o incluso la propia secuencia completa.

Entrada:
Un número N <= 1000 en una línea. En la siguiente línea, N números indicando registros. Se cumple que los números de los registros serán menores en valor absoluto que 100.

Salida:
Escribe la mayor suma que pueda obtenerse de una subsecuencia consecutiva.

Ejemplos:

Entrada 1:
Código:
4
1 2 3 4

Salida 1:
Código:
10

Entrada 2:
Código:
5
-20 -15 30 -15 30

Salida 2:
Código:
45

Notas:
- El hecho de que la N pueda ser hasta 1000 implica que una solución trivial de complejidad O(N3) no sirve (es decir, para cada posible inicio y posible final [dos fors anidados], hacer un for más anidado para calcular la suma y quedarse con la mayor). Si alguien no tiene claro si su solución es suficiente rápida (teniendo claro al menos que es correcta), se puede generar 1000 números enteros y ver cómo de rápido es su código. Debería tardar menos de un segundo, si tarda más que eso, el algoritmo no es suficiente bueno (no consiste en optimizar el código).

- Espero una solución de complejidad O(N2) intencionadamente para intentar que el problema sea más sencillo. Este problema se puede solucionar de forma más eficiente, usando una estrategia Divide&Conquer que deja una complejidad de O(NlogN) o incluso una forma ingeniosa para obtener un algoritmo O(N). Si alguien hace algún algoritmo mejor que cuadrático, como los que comento, obviamente el código será correcto.
En línea

cgvwzq

Desconectado Desconectado

Mensajes: 57


Agente P.


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #36 en: 21 Agosto 2010, 15:05 pm »

Solución trivial O(N³):

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main(int argc, char **argv) {
  5.  
  6.   int n,*sec,i,j,k;
  7.  
  8.   if (argc != 2) return 1;
  9.  
  10.   n = atoi(argv[1]);
  11.   sec = (int*)calloc(n,sizeof(int));
  12.   for (i=0;i<n;i++) scanf("%d",&sec[i]);
  13.  
  14.   for (i=0;i<n;i++) {
  15.      for (j=i;j<n;j++) {
  16.         sum = 0; for (k=i;k<=j;k++) sum+=sec[k];
  17.         if (sum > max) max = sum;
  18.      }
  19.   }
  20.  
  21.   printf("%d\n",max);
  22.  
  23.   free(sec);
  24.   return 0;
  25.  
  26. }

Solución mejorada, en lugar de sumar cada vez todos los intervalos usamos los datos ya calculados para obtener el nuevo resultado. ¿Es O(N²)?

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main(int argc, char **argv) {
  5.  
  6.   int n, i, j, **sec, max=0;
  7.  
  8.   if (argc != 2) return 1;
  9.  
  10.   n = atoi(argv[1]);
  11.   if (!(sec = (int**)calloc(n,sizeof(int*)))) return 1;
  12.   for (i=0;i<n;i++) if(!(sec[i] = (int*)calloc(n,sizeof(int)))) return 1;
  13.  
  14.   for (i=0;i<n;i++) scanf("%d",&sec[0][i]);
  15.  
  16.   for (i=1;i<n;i++)
  17.      for (j=i;j<n;j++) {
  18.         sec[i][j] = sec[i-1][j]+sec[0][j-i];
  19.         if (sec[i][j] > max) max = sec[i][j];
  20.      }
  21.  
  22.   printf("%d\n",max);
  23.  
  24.   for (i=0;i<n;i++) free(sec[i]); free(sec);
  25.  
  26.   return 0;
  27.  
  28. }

Una mejora clara sería reservar menos espacio, ya que estoy usando tan solo media matriz...


En línea

Some stuff:

  • www.a] parsed as ]www.a]
  • Bypass elhacker's img filter with ALT attribute!
  • ¿Para cuándo SQLi I y II? WZ


ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #37 en: 21 Agosto 2010, 15:35 pm »

No es la solución cuadrática estándar pero también es cuadrática y correcta, por lo tanto perfecta. En tu solución usas programación dinámica por lo que veo para calcular sec(i,j), que representa la suma de i + 1 elementos acabando en j si lo he entendido bien.

La solución cuadrática estándar usa un solo vector que guarda las sumas acumuladas, dejo el código:
Código
  1. #include <vector>
  2. #include <iostream>
  3. using namespace std;
  4. int main() {
  5.    int n;
  6.    cin >> n;
  7.    vector<int> suma(n);
  8.    for (int i = 0; i < n; ++i) {
  9.        cin >> suma[i];
  10.        if (i > 0) suma[i] += suma[i - 1];
  11.    }
  12.    //suma[i] contiene la suma de los i + 1 primeros numeros
  13.    int res = 0;
  14.    for (int i = 0; i < n; ++i) {
  15.        for (int j = 0; j < n; ++j) {
  16.            //Calculamos la suma de cada intervalo aprovechando el vector de sumas calculadas
  17.            //La suma de [i,j] sera suma[j] - suma[i - 1]
  18.            int temp = suma[j];
  19.            if (i > 0) temp -= suma[i - 1];
  20.            res = max(res, temp);
  21.        }
  22.    }
  23.    cout << res << endl;
  24. }
  25.  

La solución lineal que comenté, es decir, O(N), además no requiere espacio en memoria extra. Aunque el código es muy simple, la idea puede costar un poco más de ver, pero si alguien se lo mira con invariantes puede ver que es correcto.
Código
  1. #include <vector>
  2. #include <iostream>
  3. using namespace std;
  4. int main() {
  5.    int n;
  6.    cin >> n;
  7.    int a, res = 0, suma = 0;
  8.    for (int i = 0; i < n; ++i) {
  9.        cin >> a;
  10.        suma += a;
  11.        if (suma < 0) suma = 0;
  12.        res = max(res, suma);
  13.    }
  14.    cout << res << endl;
  15. }

Pon el siguiente reto cuando quieras.
En línea

cgvwzq

Desconectado Desconectado

Mensajes: 57


Agente P.


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #38 en: 21 Agosto 2010, 21:38 pm »

@ghastlyX, la solución lineal es mu chulaa...XD

El programa generará una matriz "sopa de letras" de N x M, usando una función random. A la vez se le pasará una palabra que buscará en la sopa.

- Las letras de la palabra deberán aparecer en orden consecutivo. Podrán estar en horizontal, vertical, diagonal y en orden inverso.
- La sopa de letras contendrá solo minusculas.
- Una vez se encuentra la palabra la búsqueda termina aunque pueda estar repetida (simplifica el problema)

Al finalizar la búsqueda, se imprimirá la sopa de letras con la palabra en mayúsculas (si es que ha sido encontrada), y un mensaje ("Si" o "No") en función de si ha habido éxito.

Entrada:
Código:
5 5 pi

Salida:
Código:
r v x i l
q l g w f
q c w m n
w q I j j
l q t P q

Si

Entrada:
Código:
5 5 zas

Salida:
Código:
i v t x u
i l f n y
i e f t l
x j w a k
w e d j o

No

Es bastante sencillo, pero nunca me he planteado un problema de estos, y esto es lo primero que se me ha ocurrido...
En línea

Some stuff:

  • www.a] parsed as ]www.a]
  • Bypass elhacker's img filter with ALT attribute!
  • ¿Para cuándo SQLi I y II? WZ


ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #39 en: 22 Agosto 2010, 16:01 pm »

Código
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. int arrf[8] = {-1,-1,-1,0,1,1,1,0};
  7. int arrc[8] = {-1,0,1,1,1,0,-1,-1};
  8.  
  9. int main() {
  10.    int n, m;
  11.    cin >> n >> m;
  12.    vector<vector<char> > S(n, vector<char>(m));
  13.    srand(time(NULL));
  14.    for (int i = 0; i < n; ++i)
  15.        for (int j = 0; j < m; ++j)
  16.            S[i][j] = 'a' + rand()%26;
  17.    string s;
  18.    cin >> s;
  19.    bool busca = true;
  20.    for (int i = 0; i < n and busca; ++i)
  21.        for (int j = 0; j < m and busca; ++j)
  22.            for (int d = 0; d < 8 and busca; ++d) {
  23.                bool ok = true;
  24.                for (int k = 0; k < s.size() and ok; ++k) {
  25.                    int f = i + arrf[d]*k, c = j + arrc[d]*k;
  26.                    if (f < 0 or f >= n or c < 0 or c >= m or S[f][c] != s[k]) ok = false;
  27.                }
  28.                if (ok) {
  29.                    busca = false;
  30.                    for (int k = 0; k < s.size(); ++k) {
  31.                        int f = i + arrf[d]*k, c = j + arrc[d]*k;
  32.                        S[f][c] ^= 32;
  33.                    }
  34.                }
  35.            }
  36.    for (int i = 0; i < n; ++i) {
  37.        for (int j = 0; j < m; ++j) {
  38.            if (j > 0) cout << " ";
  39.            cout << S[i][j];
  40.        }
  41.        cout << endl;
  42.    }
  43.    cout << endl << (busca?"No":"Si") << endl;
  44. }
  45.  

Para el próximo, ¿queréis algo simple o para pensar un poco?
En línea

Páginas: 1 2 3 [4] 5 6 7 8 9 Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Retos .Net « 1 2 3 »
Ejercicios
[D4N93R] 20 14,546 Último mensaje 6 Diciembre 2010, 03:26 am
por final_frontier
Concursos y retos
Programación General
lnvisible 0 1,428 Último mensaje 12 Diciembre 2010, 19:44 pm
por lnvisible
cuando consigo nuevos retos? « 1 2 »
WarZone
Tyrz 11 3,970 Último mensaje 15 Junio 2011, 23:11 pm
por [-Franko-]
Desarrollo de Retos Informaticos
Desarrollo Web
Sinedra 0 2,405 Último mensaje 23 Febrero 2011, 19:23 pm
por Sinedra
Retos C/C++
Programación C/C++
N0body 5 9,200 Último mensaje 9 Mayo 2011, 09:54 am
por ghastlyX
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines