Retos C/C++

[[D4N93R]]

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

[ghastlyX]

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.

[Og.]

@ghastlyX Correcto!! XD

les dije que sera simple hehe

Te toca poner reto

[ghastlyX]

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

[[L]ord [R]NA]

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

Código (cpp) [Seleccionar] Expandir

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

int consistencia(int v1[],int v2[],int lenght)
{
int temp;
for(int i=0;i<lenght;i++)
{ int k=0;
do{
if(v2[k]==v1[i])
{
temp=v1[k];
v1[k]=v2[k];
v2[k]=temp;
}
k++;
}while(k<temp);
}

for(int i=0;i<lenght;i++)
{ int k=0;
do{
if(v2[k]==v1[i])return 1;
k++;
}while(k<lenght);
}
return 0;
}

int main()
{
int Regs, *gen1, *gen2, i;

cout<<"Cantidad de Registros: ";
cin>>Regs;
gen1 = new int[Regs];
gen2 = new int[Regs];

for(i;i<Regs;i++)
{
gen1[i]=-1;
gen2[i]=-1;
}

for(i=0;i<Regs;i++)
{
cout<<"1er Valor del registro "<<i+1<<" :";
cin>>gen1[i];
cout<<"2do Valor del registro "<<i+1<<" :";
cin>>gen2[i];
}

if(consistencia(gen1,gen2,Regs))cout<<"No son consistentes"<<endl;
else{cout<<"Son Consistentes"<<endl;}

}


[ghastlyX]

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

[[L]ord [R]NA]

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

Dice que es inconsistente por el

Código [Seleccionar] Expandir

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].

[ghastlyX]

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.

[cgvwzq]

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 (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>

int noFuck (int **corral, int g1, int g2, int n);
int addChicken (int **corral, int g1, int g2);

int main(int argc, char **argv) {

   int **corral, n, m, i, gays = 0;
   int g1,g2;

   if (argc != 3) return 1;

   n = atoi(argv[1]);
   m = atoi(argv[2]);

   if (!(corral = (int**)calloc(n,sizeof(int)))) return 1;
   for (i=0;i<n;i++) if (!(corral[i] = (int*)calloc(n/sizeof(int),sizeof(int)))) return 1;

   while (m-- > 0 & !gays) {

      scanf("%d %d",&g1,&g2);
      if (!noFuck(corral,g1,g2,n)) addChicken(corral,g1,g2);// añadimos g1 a parejas de g2 y viceversa
      else gays = 1;

   }

   if (!gays) printf("Si\n"); else printf("No\n");

   for (i=0;i<n;i++) free(corral[i]); free(corral);

   return 0;

}

int noFuck (int **corral, int g1, int g2, int n) {

   int i;

   if (g1 == g2) return 1;
   for (i=0;i<=n/sizeof(int);i++) if (corral[g1][i] & corral[g2][i]) return 1;
   return 0;

}

int addChicken (int **corral, int g1, int g2) {

   corral[g1][g2/sizeof(int)] |= (g2%sizeof(int));
   corral[g2][g1/sizeof(int)] |= (g1%sizeof(int));
   return 0;

}

^^

[ghastlyX]

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.