//--------------------------------------------------------------------------- #include #include #include int a,p,n,m,*piedras,**botones,*puertas; //--------------------------------------------------------------------------- int* generaArregloAleatorio(int largo,int k) { int *resp,i,pos; resp = new int[largo]; for(i = 0; i < largo; i++) resp[i] = 0; for(i = 0; i < k; i++) { pos = rand()%largo; while( resp[pos] == 1 ) pos = (pos+1)%largo; resp[pos] = 1; } return resp; } //--------------------------------------------------------------------------- void generadorAleatorio(char archivo[],int p,int n,int m,int a) { int i,j,*temp; FILE *output; // Inicializamos los aleatorios. time_t t; srand((unsigned) time(&t)); output = fopen(archivo,"w+t"); fprintf(output,"%d\n%d\n%d\n",p,n,m); for(i = 0; i < n; i++) { temp = generaArregloAleatorio(p,m); for(j = 0; j < p; j++) { if( temp[j] == 1 ) fprintf(output,"%d ", j + 1); } delete[] temp; fprintf(output,"\n"); } fprintf(output,"%d\n",a); for(i = 0; i < a; i++) fprintf(output,"%d ",(rand()%n) + 1); fclose(output); } //--------------------------------------------------------------------------- void leeDatos(void) { int i,j,temp; FILE *input; //generadorAleatorio("Caso11.txt",1500,2,1500,20001); input = fopen("input.txt","r+t"); fscanf(input,"%d\n%d\n%d",&p,&n,&m); /// Inicializamos a todas las puertas como cerradas (cero) puertas = new int[p]; for(i = 0; i < p; i++) puertas[i] = 0; /// Inicializamos cuantos botonazos se han dado a cada piedra piedras = new int[n]; for(i = 0; i < n; i++) piedras[i] = 0; /// Guardamos que piedra mueve que puertas. botones = new int*[n]; for(i = 0; i < n; i++) { botones[i] = new int[m]; for(j = 0; j < m; j++) { fscanf(input,"%d",&botones[i][j]); botones[i][j]--; } } /// Leemos cuantos botonazos se dieron. fscanf(input,"%d",&a); /// Leemos los botonazos, contando cuantos botonazos se dieron a cada piedra. for(i = 0; i < a; i++) { fscanf(input,"%d",&temp); piedras[temp-1]++; } fclose(input); } //--------------------------------------------------------------------------- int muevePuertas(void) { int i,j,count; /// Determinamos que puertas son relevantes /// (sólo las congruentes con 1 modulo 2) for(i = 0; i < n; i++) { if( piedras[i]%2 == 1 ) { /// Aumentamos en uno al contador de las puertas que mueve la piedra i. for(j = 0; j < m; j++) puertas[botones[i][j]]++; } } /// Revisamos que puertas quedaron abiertas y lo guardamos en el contador. count = 0; for(i = 0; i < p; i++) { if( puertas[i]%2 == 1 ) count++; } /// Regresamos cuantas puertas estan abiertas return count; } //--------------------------------------------------------------------------- int main(void) { FILE *output; int i; leeDatos(); output = fopen("output.txt","w+t"); fprintf(output,"%d\n",muevePuertas()); for(i = 0; i < p; i++) { if( puertas[i]%2 == 1 ) fprintf(output,"%d ",i+1); } fclose(output); delete[] puertas; delete[] piedras; for(i = 0; i < n; i++) delete[] botones[i]; return 0; } //---------------------------------------------------------------------------