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

 

 


Tema destacado: Recopilación Tutoriales y Manuales Hacking, Seguridad, Privacidad, Hardware, etc


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Ejercicios
| | | |-+  Retos C/C++
0 Usuarios y 2 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 55,371 veces)
[D4N93R]
Wiki

Desconectado Desconectado

Mensajes: 1.646


My software never has bugs. Its just features!


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #20 en: 19 Agosto 2010, 17:13 pm »

Seee lo sé xD era joda, ghastlyX te toca poner reto, no te hagas el loco,  no leiste las reglas? xD


En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



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

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.


En línea

Og.


Desconectado Desconectado

Mensajes: 822


Aprendiendo de la vida


Ver Perfil
Re: Retos C/C++
« Respuesta #22 en: 19 Agosto 2010, 17:18 pm »

@ghastlyX Correcto!! XD

les dije que sera simple hehe

Te toca poner reto :D
En línea

|-
ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #23 en: 19 Agosto 2010, 17:22 pm »

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:
Citar
3 2
0 1
1 2

Salida 1:
Citar
Si

Entrada 2:
Citar
3 3
0 1
1 2
2 0

Salida 2:
Citar
No
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 #24 en: 19 Agosto 2010, 18:57 pm »

No estoy muy seguro... espero confirmacion de GhastlyX.
Los resultados coinciden con sus ejemplos.

Código
  1. #include <iostream>
  2.  
  3. using std::cout;
  4. using std::cin;
  5. using std::endl;
  6.  
  7. int consistencia(int v1[],int v2[],int lenght)
  8. {
  9. int temp;
  10. for(int i=0;i<lenght;i++)
  11. { int k=0;
  12. do{
  13. if(v2[k]==v1[i])
  14. {
  15. temp=v1[k];
  16. v1[k]=v2[k];
  17. v2[k]=temp;
  18. }
  19. k++;
  20. }while(k<temp);
  21. }
  22.  
  23. for(int i=0;i<lenght;i++)
  24. { int k=0;
  25. do{
  26. if(v2[k]==v1[i])return 1;
  27. k++;
  28. }while(k<lenght);
  29. }
  30. return 0;
  31. }
  32.  
  33. int main()
  34. {
  35. int Regs, *gen1, *gen2, i;
  36.  
  37. cout<<"Cantidad de Registros: ";
  38. cin>>Regs;
  39. gen1 = new int[Regs];
  40. gen2 = new int[Regs];
  41.  
  42. for(i;i<Regs;i++)
  43. {
  44. gen1[i]=-1;
  45. gen2[i]=-1;
  46. }
  47.  
  48. for(i=0;i<Regs;i++)
  49. {
  50. cout<<"1er Valor del registro "<<i+1<<" :";
  51. cin>>gen1[i];
  52. cout<<"2do Valor del registro "<<i+1<<" :";
  53. cin>>gen2[i];
  54. }
  55.  
  56. if(consistencia(gen1,gen2,Regs))cout<<"No son consistentes"<<endl;
  57. else{cout<<"Son Consistentes"<<endl;}
  58.  
  59. }
  60.  
« Última modificación: 19 Agosto 2010, 19:38 pm por Lord R.N.A. » En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #25 en: 19 Agosto 2010, 19:41 pm »

¿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:
Citar
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.
« Última modificación: 19 Agosto 2010, 19:50 pm por ghastlyX » 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 #26 en: 19 Agosto 2010, 20:12 pm »

¿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:
Citar
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.



Dice que es inconsistente por el
Código:
4 4
, entiende que ambos son el mismo animal.

Edito: Estas en lo cierto... tiene un error incluso excluyendo el error aparente del [4 4].
« Última modificación: 19 Agosto 2010, 20:28 pm por Lord R.N.A. » En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Retos C/C++
« Respuesta #27 en: 19 Agosto 2010, 20:30 pm »

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í:
Citar
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.
« Última modificación: 19 Agosto 2010, 20:31 pm por ghastlyX » En línea

cgvwzq

Desconectado Desconectado

Mensajes: 57


Agente P.


Ver Perfil WWW
Re: Retos C/C++
« Respuesta #28 en: 20 Agosto 2010, 00:14 am »

Bueno, aunque no es eficiente creo que la idea no es mala del todo. Solo he hecho las dos pruebas del enunciado y funciona bien, pero ya me dirás si he hecho algún disparate.

El caso es que los valores de 'N' y 'M' se pasan por argumento, y se van pidiendo las 'M' 2-tuplas de parejas, en el momento en que una viole el "tratado de nogays" se muestra el 'No'. Si el final es consistente mostrará el 'Si'. De cualquier forma podría mostrar el 'No' al final, eso es facilmente modificable...

Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int noFuck (int **corral, int g1, int g2, int n);
  5. int addChicken (int **corral, int g1, int g2);
  6.  
  7. int main(int argc, char **argv) {
  8.  
  9.   int **corral, n, m, i, gays = 0;
  10.   int g1,g2;
  11.  
  12.   if (argc != 3) return 1;
  13.  
  14.   n = atoi(argv[1]);
  15.   m = atoi(argv[2]);
  16.  
  17.   if (!(corral = (int**)calloc(n,sizeof(int)))) return 1;
  18.   for (i=0;i<n;i++) if (!(corral[i] = (int*)calloc(n/sizeof(int),sizeof(int)))) return 1;
  19.  
  20.   while (m-- > 0 & !gays) {
  21.  
  22.      scanf("%d %d",&g1,&g2);
  23.      if (!noFuck(corral,g1,g2,n)) addChicken(corral,g1,g2);// añadimos g1 a parejas de g2 y viceversa
  24.      else gays = 1;
  25.  
  26.   }
  27.  
  28.   if (!gays) printf("Si\n"); else printf("No\n");
  29.  
  30.   for (i=0;i<n;i++) free(corral[i]); free(corral);
  31.  
  32.   return 0;
  33.  
  34. }
  35.  
  36. int noFuck (int **corral, int g1, int g2, int n) {
  37.  
  38.   int i;
  39.  
  40.   if (g1 == g2) return 1;
  41.   for (i=0;i<=n/sizeof(int);i++) if (corral[g1][i] & corral[g2][i]) return 1;
  42.   return 0;
  43.  
  44. }
  45.  
  46. int addChicken (int **corral, int g1, int g2) {
  47.  
  48.   corral[g1][g2/sizeof(int)] |= (g2%sizeof(int));
  49.   corral[g2][g1/sizeof(int)] |= (g1%sizeof(int));
  50.   return 0;
  51.  
  52. }

^^
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 #29 en: 20 Agosto 2010, 01:51 am »

He mirado tu código y si lo he entendido bien, creas una matriz de adyacencia con máscaras de bits y cada vez que se añade una arista miras si hay un nodo intermedio que forme un camino alternativo entre ambos nodos, lo que conforma un ciclo de longitud 3 y por lo tanto una situación inconsistente.

Suponiendo que sea eso lo que estás haciendo (en caso contrario dímelo), la solución no es correcta puesto que aunque ese es un caso no consistente claramente, hay más casos "malos" que no detectas, por ejemplo, si tenemos cinco animales que formen con las relaciones un pentágono (un ciclo de longitud cinco).

El problema como bien has enfocado, se reduce a transformar la información en un grafo y decidir si el grafo es de un cierto tipo o no (sabiendo cómo, claro). Si veo que sigue sin salir, daré más pistas.
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 20,015 Último mensaje 6 Diciembre 2010, 03:26 am
por final_frontier
Concursos y retos
Programación General
lnvisible 0 2,298 Último mensaje 12 Diciembre 2010, 19:44 pm
por lnvisible
cuando consigo nuevos retos? « 1 2 »
WarZone
Tyrz 11 6,002 Último mensaje 15 Junio 2011, 23:11 pm
por [-Franko-]
Desarrollo de Retos Informaticos
Desarrollo Web
Sinedra 0 3,236 Último mensaje 23 Febrero 2011, 19:23 pm
por Sinedra
Retos C/C++
Programación C/C++
N0body 5 10,961 Último mensaje 9 Mayo 2011, 09:54 am
por ghastlyX
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines