/*
>>Creato da<<: Barberis Enrico
>>Data<<: 6 febbraio 2011 completato in 3 ore circa
>>Descrizione<<: tutte le info del problema sono disponibli nel pdf allegato al programma.
>>Descrizione breve<<: Dato in unput un'elenco di comandi(di 3 tipi: aggiungere una persona, togliere una persona, calcolare bunga bunga) interpetarli correttamente
e nel caso del comando bungabunga <giorno> <n> dare in output i gruppi migliori del bunga bunga in base alle specifiche del problema.
>>Utilizzo<<:
Linux: ./bunga persone.txt
Windows: bunga.exe persone.txt
Persone.txt è il file di testo con l'elendo dei comandi
>>Algoritmo<<: l'algoritmo è molto semplice: semplicemente nella funziona di lettura del file di input il programma legge il comando e in base al comando fa un'azione.
In particolare:
Comando "IN" : aggiunge una persona alla tabella persone[]
Comando "OUT": elimina la persona dalla tabella (persone[x].out=true;)
Comando "BUNGABUNGA": calcola i gruppi migliori del bunga bunga
Specifiche del calcolo del bunga bunga:
1)Calcolo tutte le discrepanze tra le possibili coppie e le salvo in una tabella (coppie[])
2)scelgo le N migliori e le metto in un vettore (v[][] matrice di adiacenza)
3)Percorro il grafo e stampo l'output
*/
#include<iostream>
#include<fstream>
using namespace std;
const int M = 2000;//Numero massimo di persone
//===STRUTTURE DATI===\\
//PERSONE
struct persona{
string nome; //Nome
char sesso; //Sesso M o F
int denaro; //Denaro
int eta; //EtÃ
int altezza; //Altezza in cm
int peso; //Peso in Kg
double capelli; //Capelli 0.0 albini 1.0 corvini
double costituzione; //0.0 esile 1.0 procace
string presenze; //Es: LM è disponibile il giorno LUNEDI' E MARTEDI' (LMEGVSD) e: mercoledì
bool out; //Se è vero la persona è uscita dai bungabunga altrimenti ne fa ancora parte
};
persona persone[M]; //Tabella dell'elenco delle persone dei bunga bunga
int c_per=0; //Contatore delle persone
//COPPIE
struct coppia{
int id1; //Indice della prima persona
int id2; //Indice della seconda persona
double discrepanza; //Discrepanza della coppia (più è piccola più sono "affini")
bool preso; //Variabile per scegliere le 10 migliori coppie(evita di riprendere la stessa coppia)
};
coppia coppie[M]; //Tabella delle coppie possibili
int c_cop=0;
//MATRICE DI ADIACENZA PER CALCOLARE I GRUPPI
int v[M][M];
//===FINE STRUTTRA DATI===\\
//Stampa l'elenco delle persone
void stampaPersone(){
cout<<"ID\t\tNOME\t\tSESSO\t\tDENARO\t\tETÀ\t\tALTEZZA\t\tPESO\t\tCAPELLI\t\tCOSTIT.\t\tPRESEN.\t\tOUT"<<endl<<endl;
for(int i=0; i<c_per; i++){
cout<<i<<"\t\t"<<persone[i].nome<<"\t\t"<<persone[i].sesso<<"\t\t"<<persone[i].denaro<<"\t\t"<<persone[i].eta<<"\t\t"<<persone[i].altezza<<"\t\t"
<<persone[i].peso<<"\t\t"<<persone[i].capelli<<"\t\t"<<persone[i].costituzione<<"\t\t"<<persone[i].presenze<<"\t\t"<<persone[i].out<<endl;
}
}
bool vuoto(int x){
for(int i=0; i<c_per; i++) if(v[x][i]==1) return false;
return true;
}
//Percorre il grafo, la variabili evita serve per non stampare più volte il nome del chiamante alla funzione
void percorri(int x){
cout<<persone[x].nome<<";";
for(int i=0; i<c_per; i++){
if(v[x][i]==1){
v[x][i]=0;
v[i][x]=0;
percorri(i);
}
}
}
//Calcola il migliore bunga bunga
void bunga(char g, int n){
int c=0; //Contatore per le presenze: se vale 0 vuold dire che nessuno dei due c'è. se vale 1 solo uno dei due c'è. Se 2 tutti e due ci sono
double dis=0; //Discrepanza tra due persone
double x=0; //variabile temporanea per il calcolo della discrepanza
c_cop=0;
for(int i=0; i<c_per; i++){
for(int j=0; j<c_per; j++){
//Per tutte le combinazioni possibili delle persone
//Controllo che siano del sesso opposto e che sia un maschio(evita doppioni questo)
//e che non siano stati eliminati
if(persone[i].sesso!=persone[j].sesso && persone[i].sesso=='M' && persone[i].out==false && persone[j].out==false){
//Controllo disponibilitÃ
c=0;
for(int k=0; k<persone[i].presenze.length(); k++){if(persone[i].presenze[k]==g)c++;}
for(int k=0; k<persone[j].presenze.length(); k++){if(persone[j].presenze[k]==g)c++;}
if(c>=2){
//Se è una coppia "valida"
//cout<<"Coppia "<<persone[i].nome<<" e "<<persone[j].nome<<endl;
//Calcolo discrepanza tra i due:
dis=0;
x=persone[i].denaro-persone[j].denaro;//Discrepanza
if(x<0)x=x*-1;//Modulo
dis=dis+x*0.00009;//Aggiungo disprepanza
x=persone[i].eta-persone[j].eta;//Discrepanza
if(x<0)x=x*-1;//Modulo
dis=dis+x*1.0;//Aggiungo disprepanza
x=persone[i].altezza-persone[j].altezza;//Discrepanza
if(x<0)x=x*-1;//Modulo
dis=dis+x*0.1;//Aggiungo disprepanza
x=persone[i].peso-persone[j].peso;//Discrepanza
if(x<0)x=x*-1;//Modulo
dis=dis+x*0.15;//Aggiungo disprepanza
x=persone[i].capelli-persone[j].capelli;//Discrepanza
if(x<0)x=x*-1;//Modulo
dis=dis+x*0.5;//Aggiungo disprepanza
x=persone[i].costituzione-persone[j].costituzione;//Discrepanza
if(x<0)x=x*-1;//Modulo
dis=dis+x*2.0;//Aggiungo disprepanza
//... e la salvo nella tabella coppie[]
coppie[c_cop].id1=i;
coppie[c_cop].id2=j;
coppie[c_cop].discrepanza=dis;
coppie[c_cop].preso=false;
c_cop++;
}
}
}
}
//Una volta ottenuto le coppie possibili vengono scelte le n migliori che poi verrano "salvate" nella matrice di adiacenza
//for(int j=0; j<c_cop; j++) cout<<coppie[j].id1<<"\t"<<coppie[j].id2<<"\t"<<coppie[j].discrepanza<<"\t"<<coppie[j].preso<<endl;
double min=100000;
int temp;
for(int i=0; i<n; i++){
for(int j=0; j<c_cop; j++){
if(coppie[j].discrepanza<min &&coppie[j].preso==false){
temp=j;
min=coppie[j].discrepanza;
}
}
coppie[temp].preso=true;
//cout<<"PRENDO "<<coppie[temp].id1<<" "<<coppie[temp].id2<<" "<<endl;
v[coppie[temp].id1][coppie[temp].id2]=1; //Aggiungo il collegamento nella matrice di adiacenza tra le due persone
v[coppie[temp].id2][coppie[temp].id1]=1; //Aggiugno anche l'altro collegamento
//cout<<persone[coppie[temp].id1].nome<<" "<<persone[coppie[temp].id2].nome<<endl;
min=100000;
}
//Una volta ottenuta la matrice di adiacenza si percorre per trovare i gruppi:
for(int i=0; i<c_per; i++){
if(persone[i].sesso=='M' && !vuoto(i)){
cout<<" -"<<persone[i].nome<<";";
for(int j=0; j<c_per; j++){
if(v[i][j]==1){
v[i][j]=0;
v[j][i]=0;
percorri(j);
}
}
cout<<endl;
}
}
}
//Procedura leggi() : legge dal file di testo input i comandi e li "mette in pratica"
void leggi(string file){
//Variabili locali per la lettura
string s;
char c;
int x;
double d;
ifstream fin(file.c_str());
cout<<"Caricamento dati dal file "<<file<<"..."<<endl<<endl;
while(!fin.eof()){ //Fino alla fine del file testo
fin>>s; //leggo il comando
if(s=="in"){
//Aggiungo persona
fin>>s;
persone[c_per].nome=s;
fin>>c;
persone[c_per].sesso=c;
fin>>x;
persone[c_per].denaro=x;
fin>>x;
persone[c_per].eta=x;
fin>>x;
persone[c_per].altezza=x;
fin>>x;
persone[c_per].peso=x;
fin>>d;
persone[c_per].capelli=d;
fin>>d;
persone[c_per].costituzione=d;
fin>>s;
persone[c_per].presenze=s;
persone[c_per].out=false;
c_per++;
s="";
}
if(s=="out"){
fin>>s;
for(int i=0; i<c_per; i++) if(persone[i].nome==s)persone[i].out=true;
s="";
}
if(s=="bungabunga"){
fin>>c>>x;
cout<<"BungaBunga del giorno "<<c<<" con "<<x<<" donazioni: "<<endl;
bunga(c,x);
cout<<endl;
s="";
}
}
fin.close();
}
int main(int argc, char *argv[]){
leggi(argv[1]);
return 0;
}
