Gara di Allenamento Tor Vergata

[mr96]

il 4 non l'ho fatto in modo generico xD Ho messo solo una serie di if-else if tutti incolonnati xDD
nel 3) esatto! Bisognava esplorare il grafo ricorsivamente

Comunque sul fatto della difficoltà non saprei.... Ho pochi esempi con cui confrontare... però una volta avevo visto un paio di problemi della fase nazionale (forse quella dell'ultimo anno) e devo dire che a parte la maggior attenzione all'ottimizzazione... non erano tanto più difficili di questi xD
La differenza è che lì bisognava sforzarsi di trovare un modo veloce e qui no.

La territoriale ha il vizio di avere un problema davvero tosto ogni anno... Qualche volta anche due, e su 3 sono tanti... Il problema "Brisbane" dell'altr'anno solo una persona l'ha risolto completamente, in tutta italia... In piemonte si passava con 24/50, ma in alcune regioni con 11/50... Cioè è un po' ridicola la cosa...

[xXStephXx]

In effetti le territoriali non le ho mai viste. Forse solo una volta nel 2011 perchè conoscevo uno che ha partecipato. Può essere che ci sia qualcuno molto difficile xD
Quello a cui mi riferivo erano un paio di problemi delle nazionali che avevo visto qualche mese fa.
In uno c'era uno spiedino dove bisognava mangiare da entrambi i lati assicurandosi di non sforare un certo valore mi pare.
Nell'altro c'era una specie di lista con le preferenze e forse si voleva accontentare un po' tutti.

In entrambi serviva una certa idea iniziale in modo da rendere le cose molto veloci e rimanere nei limiti di tempo. Però comunque erano idee "in linea" con i problemi di matematica che vediamo spesso, quindi comunque nulla di calato dal cielo.. Fatto ciò, la stesura del codice era abbastanza veloce e non c'erano ambiguità. Qua magari servivano pure meno idee, però capire cosa si doveva fare è stata una faticaccia xD


Giusto per rendere l'idea.. in quello della lista con le preferenze mi pare che si trattava di ordinarle dalla più alta alla più bassa e prendere le più alte xD

[Livex]

Ho appena finito: 340/400 in 4 ore (o forse in 3, non lo so l'ora legale mi ha fregato) circa senza aiutini da internet e senza ritrattare le soluzioni già date al correttore, considerando che fino a 3 giorni fa i problemi più complicati che avevo mai fatto erano "verificare se un numero n è primo" o "riordinare e stampare un vettore in ordine crescente" direi che va piuttosto bene come punteggio

1) 45 minuti, boh ora ho un'idea nuova del fuorigioco ma non era difficile, anzi. 100 punti
2) 25 minuti, questo era anche più semplice del 1. 100 punti
4) un' ora e venti minuti, il problema non è stato tanto trovare l'idea ma codificarla nel modo giusto evitando di perdere punti. 100 punti
3) ho perso la cognizione del tempo, non lo so, ho provato a creare una struttura iterativa (non ho idea di come scrivere una ricorsione) con il risultato di dover creare una struttura ricorsiva a mano, ha funzionato in parte, fa un po' di controlli all'interno ma non potevo nidificare 20 iterazioni. 40 punti

[xXStephXx]

Più o meno così: (tanto non c'erano altri che devono fare no? )

Codice: Seleziona tutto

void ric(int partenza, int escluso, bool visitati[11])
{
   visitati[partenza]=true;
   for(int i=0; i<11;i++)
   {
      if(i==partenza) continue;
      if(passaggi[partenza][i] && !visitati[i] && i!=escluso)     //passaggi[a][b] era l'array che salva se c'è passaggio tra a e b                 
      ric(i, escluso, visitati);   
   }   
}

dove nell'array visitati inizialmente si setta tutto su false. Quando la funzione termina si va a guardare quali elementi dell'array sono ancora settati su false e quelli lì non erano collegati al portiere.

Per richiamarla si usa dal main:

Codice: Seleziona tutto

ric(0, giocatore_escluso,  array_di_11_elementi_settati_a_0);

[Livex]

Codice: Seleziona tutto

void ric(int partenza, int escluso, bool visitati[11])
{
   visitati[partenza]=true;
   for(int i=0; i<11;i++)
   {
      if(i==partenza) continue;
      if(passaggi[partenza][i] && !visitati[i] && i!=escluso)     //passaggi[a][b] era l'array che salva se c'è passaggio tra a e b                 
      ric(i, escluso, visitati);   
   }   
}

Esattamente, non sapevo la sintassi nel caso specifico con array e funzioni ricorsive e, detto fra noi, cominciavo ad aver sonno

[Xeanort]

Quando è finita la gara potete mettermi le vostre soluzioni?
Io ci ho provato, ma è troppo lunga e difficile (soprattutto non so bene come prendere i dati di input)...

Grazie

P.S.: meglio se in C++

[mr96]

Quando è finita la gara potete mettermi le vostre soluzioni?
Io ci ho provato, ma è troppo lunga e difficile (soprattutto non so bene come prendere i dati di input)...

Grazie

P.S.: meglio se in C++

Ti metto le mie, premettendo che sono scritte nel modo più rapido possibile, quindi male a livello sintattico e algoritmico, ma visto che alle provinciali questo non conta, basta che funzionino...

Es.1

Testo nascosto:

Qua, per esempio, il controllo si poteva fare in maniera molto più furba, ma la prima cosa che mi è venuta in mente era il vector... Oppure la variabile "dec" si poteva già dichiarare float, ma, essendomene accorto dopo, ho fatto che castarla direttamente...

Codice: Seleziona tutto

#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

int main(int argc, char *argv[])
{
    ifstream in("input.txt");
    ofstream out("output.txt");
    int a,d,dec;
    vector<float> att;
    vector<float> dif;
    char o;
    
    in>>dec;
    in>>a;
    in>>d;
    
    for(int i = 0;i<a;i++){
       float x,y1,y2;
       in>>x;
       in>>y1;
       in>>x;
       in>>y2;
       att.push_back((y2-y1)*((float)(dec)/10)+y1);        
    }
    
    for(int i = 0;i<d;i++){
       float x,y1,y2;
       in>>x;
       in>>y1;
       in>>x;
       in>>y2;
       float ap = (y2-y1)*((float)(dec)/10)+y1;
       dif.push_back(ap);        
    }
    
    vector<bool> test(a,false);
    o = 'R';
    
    for(int i = 0;i<a;i++){
      for(int j = 0;j<d;j++){
         if(att[i]>dif[j]) test[i] = true;
      }
    }
    
    for(int i = 0;i<a;i++){
      if(test[i]==false) o = 'F';
    }
    out<<o;

    return EXIT_SUCCESS;
}

Es.2

Testo nascosto:

Qua ho incluso librerie inutili e fatto un controllo due volte, sempre per metterci meno tempo possibile a pensare...

Codice: Seleziona tutto

#include <cstdlib>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

struct gioc{
  int id,gol;
  bool operator<(const gioc& b)const{
    if(id<b.id) return true;
    else return false;
  }
};

int main(int argc, char *argv[])
{
    ifstream in("input.txt");
    ofstream out("output.txt");
    vector<gioc> lista;
    int n;
    int max,idmax,ap;
    
    in>>n;
    
    for(int i = 0;i<n;i++){
      gioc tmp;
      in>>tmp.id;
      in>>tmp.gol;
      lista.push_back(tmp);
    }
    
    sort(lista.begin(),lista.end());
    
    max = lista[0].gol;
    idmax = lista[0].id;
    ap = lista[0].gol;
    
    for(int i = 1;i<n;i++){
      if(lista[i].id == lista[i-1].id){
        ap += lista[i].gol;
        if(ap>max){
         max = ap;
         idmax = lista[i].id;
        }
      }
      else{
        ap = lista[i].gol;
        if(ap>max){
         max = ap;
         idmax = lista[i].id;
        }
      }
    }
    
    
    out<<idmax<<" "<<max;
    
    return EXIT_SUCCESS;
}

Es.3

Testo nascosto:

Qua il codice non c'è, non l'ho fatto
Detto a parole, leggendolo l'idea che mi è venuta subito era provare a togliere tutti i nodi eccetto l'1 (era un vincolo del testo), poi, per ogni nodo che togli, rappresenti il grafo con una matrice e provi a raggiungere tutti i punti con una visita in ampiezza... Come metodo non è ottimale a livello di tempo di stesura ed esecuzione, infatti non l'ho fatto per stare nelle 3 ore della gara vera e propria... E se hai letto che ho fatto 310 punti e ti stai chiedendo come abbia fatto quei 10... Quando sai che l'output è per forza tra 2 e 11, spedendo un valore random hai buona probabilità di azzeccarne uno in 10 tentativi Potresti considerarlo barare, ma uno che conosco l'altr'anno ha vinto nella sua regione con un random "ragionato" nell'esercizio più difficile, nel quale ha fatto 4/20, ma che non avrebbe saputo fare comunque

Es.4

Testo nascosto:

Qua tocchiamo il fondo, la scrittura su file fatta con lo switch, ma quando hai pochi input puoi permettertelo

Codice: Seleziona tutto

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;



int main(int argc, char *argv[])
{
    vector<int> squadre;
    ifstream in("input.txt");
    ofstream out("output.txt");
    char o;
    int n;
    int ngir;
    int gir[16][4];
    int me;
    bool test = false;
    int current = 0;
    int matches[31][2];
    int ngir2, counter=1;
    int lastid=-1;
    
    in>>n;
    in>>me;
    ngir = n/4;
    ngir2 = ngir;
    counter = ngir;
    
    for(int i = 0;i<n;i++){
      int tmp;
      in>>tmp;
      squadre.push_back(tmp);
    }
    
    for(int i = 0;i<ngir;i++){
      if(!test && squadre[current] < me){
         test = true;
         gir[i][0] = me;
         gir[i][1] = squadre[current++];
         gir[i][2] = squadre[current++];
         gir[i][3] = squadre[current++];
      }
      else{
         gir[i][0] = squadre[current++];
         gir[i][1] = squadre[current++];
         gir[i][2] = squadre[current++];
         gir[i][3] = squadre[current++];
      }
    }
    
    for(int i = 0;i<ngir;i+=2){
         matches[i/2][0] = gir[i][0];
         matches[i/2][1] = gir[i+1][1];
         matches[ngir-(i/2)-1][0] = gir[i+1][0];   
         matches[ngir-(i/2)-1][1] = gir[i][1]; 
    }
    
    while(ngir2 > 1){
        for(int i = 0;i<ngir2;i+=2){        
            matches[counter+i/2][0] = max(matches[counter-ngir2+i][0],matches[counter-ngir2+i][1]);
            matches[counter+i/2][1] = max(matches[counter-ngir2+i+1][0],matches[counter-ngir2+i+1][1]);
        }
        counter += ngir2/2;
        ngir2 /= 2;       
    }
    
    for(int i = 0;i<counter;i++){
       if(matches[i][0] == me || matches[i][1] == me) lastid = i;
    }
    
    switch(n){
      case 16:
         if(lastid==6){
            if(max(matches[6][1],matches[6][0]) == me) o = 'V';
            else o = 'F';
         }
         else if(lastid>3) o = 'H';
         else if(lastid>-1) o = 'Q';
         else o = 'G';
      break;     
      case 32:
         if(lastid==14){
            if(max(matches[14][1],matches[14][0]) == me) o = 'V';
            else o = 'F';
         }
         else if(lastid>11) o = 'H';
         else if(lastid>7) o = 'Q';
         else if(lastid>-1) o = 'O';
         else o = 'G';    
      break;
      case 64:
         if(lastid==30){
            if(max(matches[30][1],matches[30][0]) == me) o = 'V';
            else o = 'F';
         }
         else if(lastid>27) o = 'H';
         else if(lastid>23) o = 'Q';
         else if(lastid>15) o = 'O';
         else if(lastid>-1) o = 'S';
         else o = 'G';  
      break;           
    }
    out<<o;
    return EXIT_SUCCESS;
}

[Livex]

Metto anche i miei che sono in C:

Fuorigioco

Testo nascosto:

Per sbaglio quando sono andato a codificare "Fulcro del gioco" l'ho sovrascritto e questo codice non esiste più

Capocannoniere

Testo nascosto:

Il motto è "sprecare memoria per fare prima!", infatti sono veramente poche righe:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
int main()
{
    FILE *in; 
    int n,i,x,p,max,sw;
    int v[100];
    in = fopen("input.txt","r");
    fscanf(in,"%d",&n);
    for (i=0;i<100;i++) {v[i]=0;} /*inizializzo il vettore*/
    for (i=0;i<n;i++)
    {
        fscanf(in,"%d %d",&x,&p); /*x e' il giocatore, p e' il numero di goal che ha fatto in una partita, sommo in v[x] tutti i goal scorrendo la for*/
        v[x]+=p;
    } 
    max=-2;  
    for (i=0;i<100;i++)
    {
        if (v[i]>max) {max=v[i]; sw=i;}  /*mi cerco l'elemento massimo, cioe il giocatore che ha fatto piu goal*/
    }
    
    FILE *out;
    out = fopen("output.txt","w"); 
    fprintf(out,"%d %d\n",sw,v[sw]);    
    return 0;
}

Fulcro del gioco

Testo nascosto:

L'idea l'avevo intuita ma non sapendo come implementare una funzione ho semplificato il problema (sbagliandolo) in modo che possa fare al piu due controlli ricorsivi, 40 punti l'ho presi però

Codice: Seleziona tutto

int main()
{
    FILE *in; 
    int m,sw,i,j,cont,max;
    int g[12][12];
    int a[121],b[121];
    for (i=1;i<=121;i++)
    {a[i]=0; b[i]=0;}
    for (i=1;i<=11;i++)
    {
        for (j=1;j<=11;j++)
        {g[i][j]=0;}
    }
    in = fopen("input.txt","r");
    fscanf(in,"%d",&m);
    for (i=1;i<=m;i++)
    { 
         fscanf(in,"%d %d",&a[i],&b[i]);
    } 
    sw=10;
    for (i=1;i<=m;i++)
    {
        g[a[i]][b[i]]=1;
    }
    int f,s,k,z,r=0;
    max=-1;
    cont=0;
    for (i=m;i>=2;i--)
    {
       for (j=m;j>=2;j--)
       {
          if (g[i][j]==1) 
          {
                          
             for (z=1;z<=m;z++)
             {if (g[z][j]==1) r++;}
             if (r==1) cont++;                 
             r=0;          
          }
       }
       if (max<cont) {sw=i; max=cont;}
       cont=0;
    }
    
    
    FILE *out;
    out = fopen("output.txt","w"); 
    fprintf(out,"%d\n",sw);    
    return 0;
}

Sorteggio

Testo nascosto:

In due parole..If-Else

Codice: Seleziona tutto

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

int f(int x)
{
    return x;
}

int main()
{
    FILE *in; 
    int n,i,x,p,max,sw,m,cont,italia;
    int v[65];
    in = fopen("input.txt","r");
    fscanf(in,"%d",&m);
    fscanf(in,"%d",&italia);
    for (i=0;i<m-1;i++)
    { 
         fscanf(in,"%d",&v[i]);
    }
    cont=0;
    for (i=0;i<m-1;i++)
    { 
         if (italia>v[i]) {cont++;}
    }
    if (cont==m-1) {sw='V';}
       if (m==16)
       {
       if ((cont==1)||(cont==0)) {sw='G';}
       else
       {
          if ((cont>=2)&&(cont<6))
             {
                 sw='Q';
             }  
        
          if ((cont>=6)&&(cont<13))
             {
                 sw='H';
             }
          if ((cont>=13)&&(cont<m-1))
             {
                 sw='F';
             }
       }
       }
       if (m==32)
       {
       if ((cont==1)||(cont==0)) {sw='G';}
       else
       {
          if ((cont>=2)&&(cont<6))
             {
                 sw='O';
             }  
        
          if ((cont>=6)&&(cont<13))
             {
                 sw='Q';
             }
          if ((cont>=13)&&(cont<27))
             {
                 sw='H';
             }
          if ((cont>=27)&&(cont<m-1))
             {
                 sw='F';
             }
       }
       }
       if (m==64)
       {
       if ((cont==1)||(cont==0)) {sw='G';}
       else
       {
          if ((cont>=2)&&(cont<6))
             {
                 sw='S';
             }  
        
          if ((cont>=6)&&(cont<13))
             {
                 sw='O';
             }
          if ((cont>=13)&&(cont<27))
             {
                 sw='Q';
             }
          if ((cont>=27)&&(cont<55))
             {
                 sw='H';
             }
          if ((cont>=55)&&(cont<m-1))
             {
                 sw='F';
             }
       }
       }
       
    FILE *out;
    out = fopen("output.txt","w"); 
    fprintf(out,"%c\n",sw);    
    return 0;
}

[xXStephXx]

Es.3
... Come metodo non è ottimale a livello di tempo di stesura ed esecuzione

E' abbastanza ottimale in questi casi Con i dovuti controlli la funzione ricorsiva viene eseguita una sola volta per ogni nodo, non si spreca niente xD
In realtà, premetto che l'avevo usato altre volte e che comunque approcci del genere li conoscevo, anche il tempo di stesura è buono. Di solito le funzioni ricorsive fanno sempre risparmiare molte righe Il difetto è che spesso non salvano ciò che hanno già calcolato... infrangendo il motto:

"sprecare memoria per fare prima!"

Ad esempio i numeri di fibonacci calcolati col "for" impiegano un tempo lineare.... Se invece provi ad usare la funzione ricorsiva.... sì.. è bella da vedere... però passi da $O(n)$ a $O(2^n)$

Un esempio in cui conviene sprecare memoria è quello del problema "Si ha una stringa molto lunga di numeri... si vuole calcolare la massima somma ottenibile prendendone alcuni consecutivi"
Qua facendolo brutalmente viene $O(n^3)$ se invece si usa il trucchetto di salvare tutte le somme parziali cominciando dall'inizio e fermandosi in una posizione $i$ per ogni $i$ da $1$ a $n$ (dove n è la lunghezza), si può trovare il valore massimo in $O(n^2)$


PS: in realtà con un trucchetto più sofisticato i fibonacci possono essere calcolati in $O(log(n))$ una spada E forse sotto alcune condizioni anche il problema di sopra si poteva fare in $O(n)$ ma non ricordo nè quali nè come.

[xXStephXx]

Sono usciti i risultati... 14 full score e la cosa brutta è che sono ordinati in base al cognome... La prossima volta sarò Marco Abdullah!


Sono uscite pure le soluzioni xD Più o meno stessi approcci tranne per il cannoniere che l'avevo fatto così:

Codice: Seleziona tutto

#include <iostream>
#include <map>
#include <stdio.h>
using namespace std;

int main()
{
    map<int, int> giocatori;
    FILE* f = fopen("input.txt", "r");
    int p;
    fscanf(f, "%d", &p);
    int id, reti;
    for(int i=0; i<p;i++)
    {
         fscanf(f, "%d", &id);
         fscanf(f, "%d", &reti);
         giocatori[id]+=reti;   
    }
    int max=0, max_reti=0;
    for(map<int,int>::iterator it=giocatori.begin(); it!=giocatori.end(); it++)
    {
       if(it->second>max_reti) {max_reti=it->second; max=it->first;}                      
    }
    fclose(f);
    f=fopen("output.txt", "w");
    fprintf(f, "%d %d", max, max_reti);
    fclose(f);
}

Usando il map<int, int> che forse è un po' un cannone visto il contesto...

Mentre quello del fulcro del gioco l'avevo fatto con la ricorrenza così:

Codice: Seleziona tutto

#include <iostream>
#include <stdio.h>
#include <list>

using namespace std;

bool passaggi[11][11];

void ric(int partenza, int escluso, bool visitati[11])
{
   visitati[partenza]=true;
   for(int i=0; i<11;i++)
   {
      if(i==partenza) continue;
      if(passaggi[partenza][i] && !visitati[i] && i!=escluso)                      
      ric(i, escluso, visitati);   
   }   
}

int main()
{
    FILE* f= fopen("input.txt", "r");
    int m;
    fscanf(f, "%d", &m);
    int a, b;
    for(int i=0; i<m;i++)
    {
            fscanf(f, "%d", &a);
            fscanf(f, "%d", &b);
            passaggi[a-1][b-1]=true;
    }
    fclose(f);
    int max_esclusi=0, rimosso;
    bool visitati[11];
    for(int i=1; i<11;i++)
    {
       int count=0;    
       for(int j=0; j<11;j++)
       visitati[j]=false;
       visitati[0]=true;
       ric(0, i, visitati);
       for(int i=0; i<11;i++)
       if(visitati[i]==false)count++;
       if(count > max_esclusi) {max_esclusi=count; rimosso=i;}     
    }
    
    
    f=fopen("output.txt", "w");
    fprintf(f, "%d", rimosso+1);
    fclose(f);
}

E' bella la soluzione ufficiale dove viene esplorato usando lo stack, in effetti usando anche la lista dei passaggi al posto della matrice quadrata si risparmiano pure iterate inutili del for che io uso nella funzione ricorsiva... Però forse pure lo stack<int> e le struct sono cannoni quanto il map<int,int>