Tutto e di + - Risolto il problema "Camelot"

Mhuahua

Ho risolto il problema difficolt? "Guru" che hanno messo alle olimpiadi d'informatica di qualche anno fa in circa 40-50 minuti.

Il testo lo trovate qui:

143.225.229.60/ioi-site/problemi/…/camelot.html

Ed ecco la mia soluzione in C (non ho curato per niente i commenti e lo "stile", dal momento che valutano solamente il risultato finale).

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

struct knight{
  int id;
  int *friends;
};

int *disposition;
int n;
int firstdispose;
struct knight *knightarr;


int GetUnhappyKnightId(){
int c;
 for (c = 0; c<n; c++){
  if (!ThisKnightIsFriendOf(knightarr[c],GetKnightOnTheLeftOf(knightarr[c].id))) return knightarr[c].id;
  if (!ThisKnightIsFriendOf(knightarr[c],GetKnightOnTheRightOf(knightarr[c].id))) return knightarr[c].id;
 }
}

int GetDispositionIndexFromKnightId(int kid){
  int c;
  for (c=0; c<n; c++) if (disposition[c] == kid) return c;
  return -1;
}


void SwitchPosition(int kid, int kid2){
  int t;
  int i1, i2;
  
  i1 = GetDispositionIndexFromKnightId(kid);
  i2 = GetDispositionIndexFromKnightId(kid2);
  
  t = disposition[i1];
  disposition[i1] = disposition[i2];
  disposition[i2] = t;
}

void TryAssignment(){
 int c;
 int kid;
 
 if (firstdispose) {
  firstdispose = 0;
  for (c=0; c<n; c++) disposition[c] = knightarr[c].id;
 }else{
  
  kid = GetUnhappyKnightId();
  SwitchPosition(kid,GetKnightOnTheLeftOf(kid));
 
 }
}




int ThisKnightIsFriendOf(struct knight k, int fid){
    if (k.friends[fid-1]) return 1;
    else return 0;
}


int AllHappy(){
 int c;
 for (c = 0; c<n; c++){
  if (!ThisKnightIsFriendOf(knightarr[c],GetKnightOnTheLeftOf(knightarr[c].id))) return 0;
  if (!ThisKnightIsFriendOf(knightarr[c],GetKnightOnTheRightOf(knightarr[c].id))) return 0;
 }
 return 1;
}



int GetKnightOnTheLeftOf(int id){
 int c;
 for (c=0; c<n; c++){ 
  if (disposition[c] == id) {
   if (c != 0) return disposition[c-1];
   else return disposition[n-1];
  }
 }
}

int GetKnightOnTheRightOf(int id){
 int c;
 for (c=0; c<n; c++){ 
  if (disposition[c] == id) {
   if (c != (n-1)) return disposition[c+1];
   else return disposition[0];
  }
 }
}

int main(void){
  FILE *in, *out;
  int i,j;
  int t;
  
  if ((in = fopen("input.txt","r")) == NULL) exit(1);
  fscanf(in,"%d",&n);
  
  
  knightarr = (struct knight *)malloc(sizeof(struct knight)*n);
  for (t=0; t<n; t++) knightarr[t].friends = (int *)malloc(sizeof(int)*n);
  disposition = (int *)malloc(sizeof(int)*n);
  
  
  for (i = 0; i<n; i++){
   knightarr[ i].id = i + 1;
   
   for (j = 0; j<n; j++){
     fscanf(in,"%d",&knightarr[ i].friends[j]);
   }  
  }
  
  firstdispose = 1;
  
  do{
    TryAssignment();
  }while(!AllHappy());
  
  
  if ((out = fopen("output.txt","w")) == NULL) exit(1);
  
  for (t = 0; t<n; t++) fprintf(out,"%d ",disposition[t]);
  
  fclose(out);
  fclose(in); 
  
 
}