Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Soluzione problema oii 2009 TE CON GLI AMICI
Forum - C/C++ - Soluzione problema oii 2009 TE CON GLI AMICI

Avatar
aazzarone (Normal User)
Newbie


Messaggi: 11
Iscritto: 03/10/2009

Segnala al moderatore
Postato alle 11:32
Domenica, 25/10/2009
Questo topic è stato chiuso dal moderatore

Codice sorgente - presumibilmente C++

  1. #include <fstream>
  2. using namespace std;
  3.  
  4. /* Costanti */
  5. const int MAX_N = 1000000;
  6. const int MAX_K = MAX_N-1;
  7.  
  8. /* Variabili globali */
  9. int N, K, T;
  10. int adj[MAX_N];
  11. int vetK1[MAX_K]; /* dove si trova l'amico i */
  12. bool vetK2[MAX_K]; /* nella posizione i si trova qualche amico ? */
  13. int vetK3[MAX_K]; /* nella posizione i quale amico si trova?*/
  14. bool madeK[MAX_N]; /* é già stata calcolato precedentemente? */
  15.  
  16. /* dist1 e dist2 si riferiscono a seconda del ciclo a origini diverse (in questo
  17.  * modo evitiamo di creare matrici di grosse dimensioni */
  18. int dist1[MAX_N]; /* la posizione x a quale distanza si trova? */
  19. int dist2[MAX_N]; /* alla distanza x quale posizione del tavolo si trova? */
  20.  
  21. int sol1[MAX_N]; /* utilizzato nel momento in cui più amici si trovano nello stesso ciclo */
  22. bool sol2[MAX_N]; /* alla fine se sol2[i] == true allora sappiamo che nella posizione i si trova un 'amico */
  23.  
  24.  
  25. int main ()
  26. {
  27.         /* Variabili di input */
  28.         ifstream in ("input.txt");
  29.        
  30.         /* Variabili di output */
  31.         ofstream out ("output.txt");
  32.        
  33.         /* Variabili contatore */
  34.         int i, j, k, l;
  35.        
  36.         /* Variabili di lavoro */
  37.         int a;
  38.        
  39.         /* Lettura file di input */
  40.         in >> N >> K >> T;
  41.        
  42.         for (i=0; i<N; i++)
  43.         {
  44.                 in >> adj[i];
  45.                 adj[i]--;
  46.         }
  47.        
  48.         for (i=0; i<K; i++)
  49.         {
  50.                 in >> vetK1[i];
  51.                 vetK1[i]--; /* consideriamo gli indici a partire da 0 e nn da 1 */
  52.                 vetK2[vetK1[i]] = true;
  53.                 vetK3[vetK1[i]] = i;
  54.         }
  55.        
  56.         /* Fine lettura file di input */
  57.         l = 0;
  58.         for (i=0; i<K; i++)
  59.         {      
  60.                 if (!madeK[i])
  61.                 {                      
  62.                         k = 0;
  63.                         dist1[vetK1[i]] = 0;
  64.                         dist2[0] = vetK1[i];
  65.                         sol1[0] = vetK1[i];
  66.                        
  67.                         l = 0;
  68.                        
  69.                         for (j=adj[vetK1[i]]; j!=vetK1[i]; j=adj[j])
  70.                         {
  71.                                 dist1[j] = ++k;
  72.                                 dist2[k] = j;
  73.                                
  74.                                 if (vetK2[j])
  75.                                         sol1[++l] = j;
  76.                                        
  77.                         }
  78.                        
  79.                         /* ... e se due amici si trovassero nello stesso ciclo? */     
  80.                         for (j=0; j<=l; j++)
  81.                         {
  82.                                 a = (dist1[sol1[j]] + T) % (k+1);
  83.                                
  84.                                 sol2[dist2[a]] = true;
  85.                                
  86.                                 madeK[vetK3[sol1[j]]] = true;
  87.                         }
  88.                 }
  89.         }
  90.        
  91.         if (sol2[N-1])
  92.         {
  93.                 for (i=N-1; sol2[i]; i--) ;
  94.                 i++;
  95.         }
  96.         else
  97.                 for (i=0; !sol2[i]; i++) ;
  98.        
  99.         /* Stampa le soluzioni */      
  100.         out << i+1 << endl; /* Ricorda che nel programma gli indici partivano da 0 e non da 1 */
  101.        
  102.         /* Fine programma */
  103.         in.close ();
  104.         out.close ();
  105.         return 0;
  106. }


Ultima modifica effettuata da aazzarone il 25/10/2009 alle 11:35
PM
Avatar
theprogrammer (Normal User)
Guru^2


Messaggi: 2509
Iscritto: 28/01/2009

Segnala al moderatore
Postato alle 12:00
Domenica, 25/10/2009
Cosa vuol dire questo thread?

E' una richiesta di aiuto? Per cosa?

PM
Avatar
aazzarone (Normal User)
Newbie


Messaggi: 11
Iscritto: 03/10/2009

Segnala al moderatore
Postato alle 12:52
Domenica, 25/10/2009
niente... ho semplicemente postato la mia soluzione

PM
Avatar
theprogrammer (Normal User)
Guru^2


Messaggi: 2509
Iscritto: 28/01/2009

Segnala al moderatore
Postato alle 13:01
Domenica, 25/10/2009
Testo quotato

Postato originariamente da aazzarone:

niente... ho semplicemente postato la mia soluzione



Ma chi aveva posto il problema? Di quale thread parliamo?

Un forum non funziona cosi' ...

PM
Avatar
HeDo (Founder Member)
Guru^2


Messaggi: 2765
Iscritto: 21/09/2007

Segnala al moderatore
Postato alle 16:57
Domenica, 01/11/2009
Testo quotato

Postato originariamente da aazzarone:

niente... ho semplicemente postato la mia soluzione



un post con solo un programma senza spiegazioni/presentazioni/richieste è inammissibile.

chiudo.

PM