Autor
|
Tema: Retos C/C++ (Leído 55,371 veces)
|
[D4N93R]
Wiki
Desconectado
Mensajes: 1.646
My software never has bugs. Its just features!
|
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
Mensajes: 1.900
|
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
Mensajes: 822
Aprendiendo de la vida
|
@ghastlyX Correcto!! XD les dije que sera simple hehe Te toca poner reto
|
|
|
En línea
|
|-
|
|
|
ghastlyX
Ex-Staff
Desconectado
Mensajes: 1.900
|
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
|
|
|
En línea
|
|
|
|
[L]ord [R]NA
Desconectado
Mensajes: 1.513
El Dictador y Verdugo de H-Sec
|
No estoy muy seguro... espero confirmacion de GhastlyX. Los resultados coinciden con sus ejemplos.#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;} }
|
|
« Última modificación: 19 Agosto 2010, 19:38 pm por Lord R.N.A. »
|
En línea
|
|
|
|
ghastlyX
Ex-Staff
Desconectado
Mensajes: 1.900
|
¿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.
|
|
« Última modificación: 19 Agosto 2010, 19:50 pm por ghastlyX »
|
En línea
|
|
|
|
[L]ord [R]NA
Desconectado
Mensajes: 1.513
El Dictador y Verdugo de H-Sec
|
¿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 , 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
Mensajes: 1.900
|
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.
|
|
« Última modificación: 19 Agosto 2010, 20:31 pm por ghastlyX »
|
En línea
|
|
|
|
cgvwzq
Desconectado
Mensajes: 57
Agente P.
|
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... #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; 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) { if (!noFuck(corral,g1,g2,n)) addChicken(corral,g1,g2);// añadimos g1 a parejas de g2 y viceversa else gays = 1; } 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; }
^^
|
|
|
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
Mensajes: 1.900
|
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
|
|
|
|
|
Mensajes similares |
|
Asunto |
Iniciado por |
Respuestas |
Vistas |
Último mensaje |
|
|
Retos .Net
« 1 2 3 »
Ejercicios
|
[D4N93R]
|
20
|
20,015
|
6 Diciembre 2010, 03:26 am
por final_frontier
|
|
|
Concursos y retos
Programación General
|
lnvisible
|
0
|
2,298
|
12 Diciembre 2010, 19:44 pm
por lnvisible
|
|
|
cuando consigo nuevos retos?
« 1 2 »
WarZone
|
Tyrz
|
11
|
6,002
|
15 Junio 2011, 23:11 pm
por [-Franko-]
|
|
|
Desarrollo de Retos Informaticos
Desarrollo Web
|
Sinedra
|
0
|
3,236
|
23 Febrero 2011, 19:23 pm
por Sinedra
|
|
|
Retos C/C++
Programación C/C++
|
N0body
|
5
|
10,961
|
9 Mayo 2011, 09:54 am
por ghastlyX
|
|