mercoledì 27 marzo 2013

Compilare in C++ su Windows

Per compilare in c++ su Windows si può utilizzare sempre GCC che è incluso in Code::Blocks (download)

WINDOWS 7/8 64bit

Per i processori a 64 bit bisogna installare anche MinGW-w64.

1)Installa Code::Blocks
2)Installa MinGW-w64 (Scarica versione testata)
3)Apri Code Blocks ->Sttings -> Compiler
4)Seleziona la scheda toolchain Executables
5)

martedì 26 marzo 2013

Compilare C++ in Ubuntu e altri Linux

Usando il compilatore gcc

Dal terminale scriviamo:

g++ sorgente.cpp -o indirizzo programma compilato

Per avere un avvio automatico possiamo nominare il file compilato in .sh, ma l' estensione non influisce sul funzionamento del programma

Usando un ide che include gcc

Per sempificarsi le cose vi consiglio di usare l' IDE Code::Blocks disponibile dal Software Center.

INSTALLA ORA (apt)

Creare una lista di adiacenza di un grafo in C++

#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
int nodi,narchi;
int main()
{ ifstream in ("input.txt");
ofstream out ("output.txt");
in >>nodi>>narchi;
int adiacenza [nodi+1][nodi+1];
for(int i=1;i<nodi+1;i++)
for(int j=1;j<nodi+1;j++)
adiacenza [i][j] =0;
for(int i=0;i<narchi;i++) {
        int u,v;
        in >> u >> v >> adiacenza[u][v];
        adiacenza[v][u]=adiacenza[u][v];
}
for(int i=1;i<nodi+1;i++){
for(int j=1;j<nodi+1;j++)
if(j==nodi) out<<adiacenza[i][j];
else out<<adiacenza[i][j]<<" ";
out<<"\n";}
    return  0;
}

lunedì 18 marzo 2013

Dobri (COCI 3/13)

TESTO

SOLUZIONE:

#include <cstdlib>
#include <iostream>

using namespace std;


int main()
{
    int A [1001], N;
cin >> N;
int S [N] [N];
for (int i = 0; i <N; i++){
    for (int j = 0;j <N; j++){
        cin >> S[j][i];
        }
    }
                                    if (N==2){
                                    cout << S[0][1]/2<<" "<<S[0][1]/2;
                                    return 0;}
    A[2] = (S[1][0]-S[2][0]+S[2][1])/2;
    A[1] = S[1][0]-A[2];
    int k =2;
    for (int i = 0; i <N; i++){
    for (int j = 0;j <N; j++){
        A[++k]= S[k-1] [0] -A[1];
        }
    }
    for (int i = 1; i <= N ; i++)
    cout << A [i] << " ";
   
    return 0;
}

Baka (COCI 3/13)

TESTO

Soluzione 1:

#include <cstdlib>
#include <iostream>

using namespace std;

string parole;
int main()
{
 cin >> parole;
 char get = parole [0];
 int i =0, tempo = 0;
 while (i != 200){
       switch (get){
              case 'A':
             case 'B':
             case 'C':
                  tempo +=3 ;
                   break;
             case 'D':
                           case 'E':
                            case 'F':
                                  tempo +=4 ;
                   break;
              case 'G':
                               case 'H':
                               case 'I':
                                     tempo +=5 ;
                   break;  
                     case 'J':
             case 'K':
             case 'L':
                   tempo +=6 ;
                   break; 
               case 'M':
             case 'N':
             case 'O':
                   tempo +=7 ;
                   break;  
                     case 'P':
             case 'Q':
             case 'R':
                    case 'S':
                          tempo +=8 ;
                   break;
          case 'T':
             case 'U':
             case 'V':
                   tempo += 9;
                   break;  
                                        case 'X':
             case 'W':
             case 'Y':
                    case 'Z':
                          tempo +=10 ;
                   break;
                            
              }
              get = parole [++i];
             if (get  == '\0') i =200;
       }
 
 cout << tempo;
 
    return 0;
}

Sapendo però che 'c' - 'a' = 2

Soluzione 2:

#include <cstdlib>
#include <iostream>

using namespace std;

string parole;
int main()
{
 cin >> parole;
 char get = parole [0];
 int i =0, tempo = 0, time []={3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,8,9,9,9,10,10,10,10};
 while (i != 200){
        tempo+=time[get-'A'];
                    get = parole [++i];
                                if (get  == '\0') i =200;
       }
 
 cout << tempo;
 
    return 0;
}

Grand Prix (OII 2012)

TESTO DEL PROBLEMA

Selezioni Territoriali 2012 - Olimpiadi Italiane dell' Informatica

Grand Prix

Descrizione del problema

State assistendo a un Gran Premio di Formula 1. Prima dell'inizio, il tabellone riporta la griglia di partenza, ovvero l'ordine in cui le vetture partiranno dalla linea del traguardo. Non appena inizia il gran premio, per ogni sorpasso, il tabellone scrive due numeri: quello della vettura che ha effettuato il sorpasso, e quello della vettura che è stata superata. Il vostro compito è di scrivere un programma che, ricevuti in ingresso l'ordine di partenza e la lista dei sorpassi, calcoli chi ha vinto il gran premio.
Per esempio, considerate il seguente gran premio, con 3 macchine e 4 sorpassi. L'ordine iniziale di partenza è stato: la vettura numero 2, poi la vettura numero 1 e infine la vettura numero 3. I sorpassi sono stati, nell'ordine:

la numero 3 ha superato la numero 1;
la numero 3 ha superato la numero 2;
la numero 1 ha superato la numero 2;
la numero 2 ha superato la numero 1;

In questo caso, è facile vedere che la vettura numero 3 ha vinto il gran premio. Come si può notare dall'esempio, i sorpassi avvengono sempre tra due vetture consecutive.

Dati di input

Il file di input è costituito da 1+N+M righe di testo. La prima riga contiene due interi positivi separati da uno spazio: N che è il numero di vetture e M che è il numero di sorpassi. Le successive N righe contengono l'ordine di partenza: per ogni riga c'è un numero intero K che rappresenta una vettura, con 1 ≤ K ≤ N. La vettura che parte in i-esima posizione nell'ordine di partenza si trova quindi nella riga (i+1) del file. Le restanti M righe contengono tutti i sorpassi, nell'ordine in cui sono avvenuti, uno in ogni riga. Ogni riga contiene due interi separati da uno spazio: A, ovvero il numero della vettura che ha effettuato il sorpasso, e B, ovvero il numero della vettura che ha subito il sorpasso.

Dati di output

Il file di output deve contenere un solo intero: il numero della vettura che ha vinto il gran premio.

Assunzioni

2 ≤ N ≤ 30
1 ≤ M ≤ 100

Soluzione

In lettura basta assegnare ad una variabile <primo> il numero di chi sorpassa la prima vettura e stampare questa variabile.

#include <cstdlib>
#include <iostream>
#include<assert.h>
#include <fstream>

using namespace std;
int i;
ifstream in("input.txt");
ofstream out("output.txt"); 

  
int main()
{int macchine, sorpassi, uno, x, y;
in >> macchine;
in >> sorpassi;
in >> uno;
                for(i=1; i< macchine;i++)
                in >> x;
      for (i=0; i< sorpassi;i++){
      in >> x >> y;
      if (y == uno)
      uno = x;
      }
out << uno;
    return 0;
}

Ordinare un vettore con costo N log2 (N)

Ordinare un vettore è un' operazione che solitamente (con algoritmi tra i quali c'è il Bubble Sort) ha un costo N².
Con Merge Sort questo no è un problema.

void mergesort(int* V, int g){
      if(g == 1)      
      return;
      int k = (g /2);
      int s2 = g-k;
      int V1 [k];
      assert(V1!=NULL);
      int V2 [s2];
      assert(V2!=NULL);
      for ( i = 0; i < k ; i++)
      V1[ i ] = V[ i ];
      for ( i = 0; i < s2 ; i++){
      V2[i] = V[k+i];
      }
                 merge(V1,k);
                 merge(V2,s2);
                 int i1,i2;
     i1=i2 =0;
      while (i1 <k && i2<s2){
            if (V1[i1] <= V2[i2]) {
                  V[i1+i2] = V1[i1];     
                  i1++;
                       }
                       else{
                            V[i1+i2]=V2[i2];
                            i2++;
                            }}
      while (i1 < k) {
            V[i1+i2] = V1[i1];
            i1++;
            }
      while (i2 <s2) {
            V[i1+i2] = V2[i2];
            i2++;
            }
            return;
            }

Info Guide