Info Guide: aprile 2014

giovedì 10 aprile 2014

Compilare eseguibili Windows su Linux

Tempo fa avevamo visto come compilare C++ per Linux su Linux, oggi vedremo come compilare per Windows su Linux (il risultante sarà in 32bit):

inanzitutto installiamo MingW:

sudo apt-get install g++ -y
sudo apt-get install mingw32 -y
sudo apt-get install mingw32-binutils -y
sudo apt-get install mingw32-runtime -y

Non preoccupatevi se da errore su uno dei quattro

Poi andiamo a compilare:

i586-mingw32msvc-g++ sorgente.cpp -o compilato.exe

Tutti i caratteri con Linux

Ecco un semplice schema esemplificativo di come fare tutti i caratteri con Linux (schema relativo alla tastiera italiana):

Ricordo che è inoltre possibile inserire direttamente il codice Unicode del carattere:

Ctrl+Shift+u seguito dal codice

Ecco la tabella Unicode.

mercoledì 9 aprile 2014

Indice di un processore in Pantal

Le caratteristiche principali di un processore son la velocità (operazioni al secondo) e il numero di sottoprocessori (core).
Il pantal [P] è un' unità di misura che li raggruppa in un unico dato.

Pantal = core x GHz

Sapendo il pantal di un processore è facile stimarne le caratteristiche:
dividendo il numero di pantal per due (che sono i GHz medi di un processore attuale) si ottiene all' incirca il numero di core; sapendo che il numero di core è una potenza di due si arrotonda tale numero e di conseguenza si calcolano i GHz, per esempio:
un processore da 7 P
7 P : 2 GHz = 3,5 core -> 4 core
7 P : 4 core = 1,75 GHz

Ecco alcuni valori di pantal:

processore GHZ core Pantal
Intel i3-4000M 2,40 2 4,8
Intel i7-4810MQ 2,80 4 11,2
AMD Athlon II 2,30 2 4,6

martedì 1 aprile 2014

[C++] Eserciti Galattici

L'esercito della Signoria è riuscito a costruire un'arma segreta: il temibile Sarcofago Nero. Esso legge una parola segreta S costituita da lettere minuscole dell'alfabeto: a, b, c, ..., z (ogni lettera può comparire zero, una o più volte).
Il Sarcofago Nero può assumere N configurazioni al suo interno, numerate da 1 a N. La parola segreta viene accettata se raggiunge la configurazione finale (avente numero N) a partire dalla configurazione iniziale (avente numero 1) dopo aver letto tutte le lettere in S una alla volta. Per ogni configurazione I del Sarcofago Nero, la tripletta (I,J,c) indica che la lettera c lo fa transitare dalla configurazione I alla configurazione J.
L'esercito rivale ha carpito una parola segreta S, ma non sa se è quella del Sarcofago Nero. Il tuo compito è quello di trovare la configurazione interna Q che esso raggiunge, dopo aver letto S, a partire dalla configurazione iniziale.

Dati di input
Il file input.txt è composto da M+2 righe. La prima riga contiene tre interi positivi separati da uno
spazio, che rappresentano il numero M delle triplette, il numero N di configurazioni e il numero K di
lettere nella sequenza S. La seconda riga contiene K lettere separate da uno spazio, le quali formano la
sequenza S. Ciascuna delle rimanenti M righe contiene due interi positivi I e J e una lettera c, separati da una spazio, che rappresentano la tripletta (I,J,c) per la transizione del Sarcofago Nero.
Dati di output
Il file output.txt è composto da una sola riga contenente il numero Q della configurazione raggiunta
dal Sarcofago Nero a partire dalla sua configurazione iniziale (avente numero 1), dopo aver letto tutta la
sequenza S.
Assunzioni
2 ≤ M ≤ 100.
2 ≤ N ≤ 100.
2 ≤ K ≤ 10.
1 ≤ Q ≤ N.

Esempi di input/output
File input.txt File output.txt
5 3 6 2
a a a b a b
1 3 a
1 2 b
2 1 a
3 2 b
3 3 a

Niente di più facile che modificare una variabile <Q> in base alle istruzioni memorizzate in un vettore trami te coppi char-int:

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

#define K 10
#define N 100

using namespace std;

ifstream in;
ofstream out;

typedef pair<char,int> ci;

int m,n,k,q=1,t1,t2;
char s[K],t3;
vector<ci> ijc [N+1];

int main(){
in.open("input.txt");
out.open("output.txt");

in>>m>>n>>k;
 
for (int i=0;i<k;i++)
 in>>s[i];

for (int i=0;i<m;i++){
 in>>t1>>t2>>t3;
 ijc[t1].push_back(ci(t3,t2));}

for (int i=0;i<k;i++)
 for (int j=0; j< ijc[q].size();j++)
  if (ijc[q][j].first ==s[i])
   q= ijc[q][j].second;


out<<q;

return 0;}

[C++] Nanga

Durante la lunga scalata delle cime attorno al Nanga Parbat, Reinhold Messner riesce a trasmettere al
campo base, a intervalli regolari, solo il dislivello percorso rispetto all'ultima trasmissione. Se invia un
numero positivo P, allora è salito di P metri rispetto alla precedente trasmissione; se invia un numero
negativo P, allora è sceso di P metri rispetto alla precedente trasmissione; se infine invia P=0, non ha
cambiato altitudine. Messner parte dal campo base a 5000 metri.
I suoi collaboratori al campo base ricevono tali rilevamenti: aiutali a identificare l'altitudine che risulta
più frequentemente rilevata in questo modo.

Dati di input
Il file input.txt è composto da N+1 righe. La prima riga contiene l'intero positivo N, il numero dei
rilevamenti trasmessi da Messner. Ciascuna delle successive N righe contiene un intero che rappresenta
il dislivello percorso rispetto alla precedente trasmissione.
Dati di output
Il file output.txt è composto da una sola riga contenente l'altitudine che risulta più frequentemente
rilevata in questo modo dal campo base.

Assunzioni
2 ≤ N ≤ 1000.
100 ≤ P ≤ 100.

Esempi di input/output
File input.txt File output.txt
8 5002
3
-1
6
-7
1
4
0
-4

Registriamo i risultati su un vettore, poi cercheremo il massimo:

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

#define base 5000 //metri
#define N 10000
#define no -1

using namespace std;

ifstream in;
ofstream out;

int n,t,h=base,a[N][2],l=0,maxn=0,maxi;

int cerca (int k){
for (int i=0;i<l;i++)
 if (a[i][0]==k)
  return i;
return no;}

int main(){
in.open("input.txt");
out.open("output.txt");

in>>n;

for (int i=0;i<n;i++){
 in>>t;
 h+=t;
 t=cerca(h);
 if (t==no){
  a[l][0]=h;
  a[l++][1]=1;
 }else
  a[t][1]++;
}

for (int i=0;i<l;i++)
 if (a[i][1]>maxn){
  maxn =a[i][1];
  maxi=a[i][0];}

out<<maxi;

return 0;}

[C++] Domino

Sono date N tessere di domino, dove ogni tessera contiene due numeri compresi da 0 a 6 in
corrispondenza delle sue due estremità. Le tessere possono essere ruotate e la regola impone che due
tessere possono essere concatenate se le loro estremità in contatto hanno inciso lo stesso numero. Aiuta a
trovare il maggior numero di tessere che si possono concatenare a formare un'unica catena: non è detto
che si riescano sempre a usare tutte le tessere; inoltre, possono esserci due o più tessere uguali a meno di
rotazioni.

Dati di input
Il file input.txt è composto da N+1 righe. La prima riga contiene l'intero positivo N, il numero delle
tessere a disposizione. Ciascuna delle successive N righe contiene due interi positivi (compresi da 0 a 6)
separati da una spazio, che rappresentano i numeri incisi sulle estremità delle tessere.
Dati di output
Il file output.txt è composto da una sola riga contenente il massimo numero di tessere che possono
essere concatenate con le regole del domino.

Assunzioni
2 ≤ N ≤ 10.

Esempi di input/output
File input.txt File output.txt
6 5
3 0
4 0
2 6
4 4
0 1
1 0

Il risultato è dato dalla somma delle metà di tutte le somme di presenze di un numero meno 1:

#include<cstdlib>
#include<iostream>
#include<fstream>
#include<cstring>

#define N 10

using namespace std;

ifstream in;
ofstream out;

int n, t1,t2,v[7],tes=1;

int main(){
in.open("input.txt");
out.open("output.txt");

in>>n;
 
memset(v,0,7);

for (int i=0; i<n;i++){
 in>>t1>>t2;
v[t1]++;
v[t2]++;
}

for (int i=0;i<7;i++){
 if (v[i]%2==1)
  v[i]--;
 tes+=v[i]/2;}

out<<tes;

return 0;}

[C++] Trovaparola

Luciano, patito di giochi di
tutti i tipi, ha ideato un nuovo gioco, che funziona nel modo seguente: avete una
griglia di caratteri e una parola da trovare nella griglia, partendo dalla cella in alto a
sinistra. Le uniche mosse consentite sono gli spostamenti a destra o in basso. Ad
esempio, considerate la seguente griglia e la parola “olimpiadi”:

O L I V E N T
G Q M P W E R
G T R I A Y E
I U I C D P E
A F C O I G H
J K X C V R S
R O M I T A A
S T A N L E E

In questo caso, la sequenza di spostamenti è “DDBDBDBB”, rappresentando gli
spostamenti a destra con il carattere D e quelli in basso con il carattere B. Non esiste
nessuna soluzione, invece, se la parola da cercare è “olimpionico”. Il vostro compito
consiste nello scrivere un programma che, ricevute in ingresso una parola (da cercare)
e una griglia, restituisca la sequenza di spostamenti, qualora esista una soluzione,
oppure stampi “ASSENTE”. Se dovessero esistere molteplici sequenze di spostamenti
corrette, è sufficiente stamparne una qualunque.
Dati di input
Il file input.txt è composto da 2+R righe. La prima riga contiene due interi positivi R e
C: le dimensioni della griglia, ovvero il numero di righe R e il numero di colonne C.
La riga successiva contiene P, una parola da cercare, rappresentata da una stringa
lunga almeno 2 caratteri (alfabetici maiuscoli) e al massimo R+C1 caratteri. Le
rimanenti R righe del file contengono le righe della griglia, rappresentate da stringhe
di C caratteri alfabetici maiuscoli.
Dati di output
Il file output.txt è composto da una sola riga contenente una stringa di testo: la
sequenza di spostamenti necessari per trovare la parola nella griglia, se la parola è
presente, oppure la stringa “ASSENTE” (senza le virgolette).
Assunzioni
• 2 ≤ R, C ≤ 100
Esempi di input/output
File input.txt File output.txt
8 7 DDBDBDBB
OLIMPIADI
OLIVENT
GQMPWER
GTRIAYE
IUICDPE
AFCOIGH
JKXCVRS
ROMITAA
STANLEE

File input.txt File output.txt
8 7 ASSENTE
OLIMPIONICO
OLIVENT
GQMPWER
GTRIAYE
IUICDPE
AFCOIGH
JKXCVRS
ROMITAA
STANLEE

Basta provare ad andare a destra e a sinistra con una funzione ricorsiva, arrivati alla fine si stampano i passaggi:

#include<cstdlib>
#include<iostream>
#include<fstream>
#include <string>

#define M 101
#define no "ASSENTE"

using namespace std;

ifstream in;
ofstream out;

bool t=true;
int r,c;
string p;
char g [M][M];

void cerca(int rr, int cc,string storia,int ch){
//prova a cercare la parola. Se non trova si ferma. Se trova stampa
if ( ++ch == p.length()){
 out<<storia;
t=false;
return;}
if (r>rr+1 && g [rr+1][cc]==p[ch])
 cerca (rr+1,cc,storia+"B",ch);
if (c>cc+1 && g [rr][cc+1]==p[ch])
 cerca (rr,cc+1,storia+"D",ch);
return;
}

int main(){
in.open("input.txt");
out.open("output.txt");

in>>r>>c>>p;
 
for (int i=0;i<r;i++)
 for (int j=0;j<c;j++)
  in>> g[i][j];

if (p[0]==g[0][0])
cerca (0,0,"",0);

if (t)
out<<no;

return 0;}

[C++] Gardaland

Nel 2012 le Olimpiadi Internazionali di Informatica (IOI) si sono svolte,
per la prima volta, in Italia, a Sirmione. Come da tradizione, nella
giornata tra le due gare i concorrenti sono andati a divertirsi in un parco
giochi, in questo caso, Gardaland. La mattina di quel giorno decine di
pullman hanno prelevato i quattro ragazzi che costituiscono la squadra
olimpica di ciascuna nazione dal Garda Village, dove erano stati
alloggiati, e li hanno portati a Gardaland. Come sempre negli
spostamenti, le varie nazioni erano state ripartite a blocco unico tra i
pullman, ossia tutti gli atleti di una stessa nazione trovavano posto su
uno stesso pullman. Per esempio, sul pullman dell’Italia viaggiavano
anche Giappone, Israele e Irlanda. Al ritorno però, come sempre
succede alle IOI, dopo una giornata in un parco giochi i ragazzi hanno
fatto amicizia tra di loro, e al momento di tornare sui pullman sono saliti
alla rinfusa. Grazie al lavoro delle guide, per ogni pullman è stata stilata
una lista contenente, per ogni nazione, il numero di ragazzi a bordo. Il
vostro compito è quello di aiutare Monica, responsabile
dell’organizzazione, a capire se i pullman possono partire, ovvero se
tutti i quattro ragazzi di ogni nazione che sono arrivati a Gardaland
sono saliti sui pullman. In caso contrario, dovete segnalare a Monica in
quanti mancano all’appello, divisi per nazioni.

Dati di input
Il file input.txt è composto da 1+N+L righe. La prima riga contiene due
interi positivi separati da uno spazio: il numero N delle nazioni e il
numero L di righe contenenti informazioni su chi è attualmente già
salito sui pullman. (Ciascuna nazione verrà qui rappresentata con un
intero compreso tra 0 e N1). Ognuna delle successive N righe
contiene un intero positivo: nella riga i+1 (con i >= 1) troviamo il numero
totale di ragazzi della nazione i1. Ciascuna delle rimanenti L righe
contiene due interi positivi: un intero compreso tra 0 e N1 che
rappresenta la nazione, e un intero positivo che specifica quanti ragazzi
di quella nazione sono su un certo pullman. Ovviamente una stessa
nazione può comparire diverse volte nelle L righe, e più precisamente
compare su tante righe quanti sono i pullman ospitanti atleti di quella
nazione.
Dati di output
Il file output.txt è composto da una sola riga contenente l’intero 0 (zero)
se non manca alcun ragazzo. Altrimenti, il file contiene 1+C righe: la
prima riga contiene un intero C, ovvero il numero di nazioni che hanno
ragazzi ancora a Gardaland. Le restanti C righe contengono due interi:
l’identificativo della nazione e il numero di ragazzi di quella nazione che
non sono ancora saliti su alcun pullman. E’ necessario stampare le
nazioni nell’ordine in cui sono state lette, ovvero in ordine crescente in
base all’identificativo.

Assunzioni
2 ≤ N ≤ 100
N ≤ L ≤ 1000

Contrariamente alle olimpiadi di informatica reali, dove gareggiano (massimo) 4 ragazzi per ogni nazione, nei casi di input si assume che ogni nazione abbia al massimo 100 ragazzi, e almeno 1 ragazzo.
Quindi, indicando con Ri il numero
di ragazzi della iesima nazione, vale sempre 1 ≤ Ri ≤ 100.

Esempi di input/output
File input.txt File output.txt
3 5 2
4 0 1
4 2 1
3
0 2
1 3
0 1
2 2
1 1
File input.txt File output.txt
3 6 0
4
4
4
0 2
1 3
2 1
0 2
2 3
1 1

Basta contare quanti ragazzi non sono sugli autobus:

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

using namespace std;

ifstream in;
ofstream out;

int n,l,t1,t2,persi=0;

int main(){
in.open("input.txt");
out.open("output.txt");

in>>n>>l;

int rag[n];

for (int i=0;i<n;i++)
 in>>rag[i];

for (int i=0;i<l;i++){
in>>t1>>t2;
rag[t1]-=t2;
}
 
for (int i=0;i<n;i++)
 if(rag[i]>0)
  persi++;

out<<persi;

for (int i=0;i<n;i++)
 if(rag[i]>0)
  out<<"\n"<<i<<" "<<rag[i];

return 0;}

[C++] Brisbane

Nel 2013, le IOI si svolgeranno a Brisbane (in Australia). La rappresentativa italiana
ha già iniziato a studiare la città, per capire cosa ci sia di interessante da vedere, e
come ci si possa spostare nella giornata libera successiva alla seconda gara delle
Olimpiadi. L’offerta di trasporto pubblico a Brisbane è abbastanza variegata: ci sono
due linee di bus, di cui una gratuita che gira intorno alla città, e due linee di traghetti
che fermano in diversi punti del fiume Brisbane, che taglia la città in due; per quello
che riguarda i prezzi, esiste un abbonamento giornaliero a tutti i trasporti pubblici,
bus e traghetti insieme, oppure è possibile prendere un più economico abbonamento
giornaliero ai soli traghetti, o un ancor più economico abbonamento ai soli bus.
La squadra italiana vorrà visitare il maggior numero di attrazioni possibile e per
questo motivo Monica, la responsabile dell’organizzazione, ha deciso di cercare un
buon compromesso tra il prezzo dei biglietti e le attrazioni che sarà possibile
raggiungere partendo dall’hotel. Data una lista di attrazioni e la mappa dei
collegamenti delle diverse linee del trasporto pubblico, il vostro compito è quello di
aiutare Monica a capire quante attrazioni sono raggiungibili per ogni possibile scelta
dei biglietti per i trasporti pubblici.

Per esempio, possiamo fare riferimento alla figura qui a destra, dove ad ogni fermata è
associato un cerchio (o un quadrato nel caso di luogo di attrazione) e i collegamenti
sono:
tratteggiati – collegamenti gratuiti (bus gratuiti e brevi percorsi a piedi);
rossi – bus a pagamento;
gialli – traghetto.
Il punto di partenza della rappresentativa italiana è la fermata numero 0; le attrazioni
da vedere sono quelle rappresentate con un quadrato, numerate rispettivamente 8, 12,
15, 22 e 28. Come si può vedere, spostandosi con i mezzi gratuiti si raggiungono solo
due attrazioni (la numero 8 e la numero 14); comprando il biglietto del bus si
raggiungono tutte le attrazioni; comprando il biglietto del traghetto si raggiungono,
oltre alla 8 e la 14, anche la 12 e la 15 per un totale di quattro attrazioni. Il biglietto
combinato, in questo caso, raggiunge tutte le attrazioni.

Dati di input
Il file input.txt è composto da 1+A+Mg+Mb+Mt righe. La prima riga contiene cinque
interi positivi separati da uno spazio, che rappresentano il numero N delle fermate, il
numero A di attrazioni, il numero Mg dei collegamenti gratuiti, il numero Mb dei
collegamenti via bus e il numero Mt dei collegamenti via traghetto. Ogni fermata è
rappresentata da un intero compreso tra 0 e N1. Le successive A righe contengono
ognuna una fermata (un intero compreso tra 0 e N1) corrispondente ad una delle
attrazioni che la rappresentativa italiana può visitare. Ognuna delle successive
Mg+Mb+Mt righe contiene un collegamento del trasporto pubblico, rappresentato da
due interi positivi: le fermate collegate. Le prime Mg righe contengono i collegamenti
gratuiti (bus gratuiti e brevi percorsi a piedi), poi le successive Mb contengono i
collegamenti del bus a pagamento e infine le ultime Mt righe contengono i
collegamenti dei traghetti. Il punto di partenza della rappresentativa italiana è la
sempre la fermata numero 0.
Dati di output
Il file output.txt è composto da 4 righe contenenti ognuna un intero non negativo,
rispettivamente, il numero di attrazioni raggiungibili:
1. senza comprare biglietti (solo con mezzi gratis);
2. comprando solo il biglietto giornaliero dei bus;
3. comprando solo il biglietto giornaliero dei traghetti;
4. comprando entrambe le tipologie di biglietti.

Assunzioni
• 2 ≤ N ≤ 1000
• N ≤ Mg+Mb+Mt ≤ 10000

Esempi di input/output

File input.txt                 File output.txt
6 2 2 4 2                         1
1                                 1
5                                 2
0 1                               2
2 5
0 3
1 3
2 4
4 5
1 2
3 4 1

File input.txt  (corrisponde alla figura)  File output.txt
30 5 18 14 11                                          2
8                                                      5
12                                                     4
15                                                     5
22  
28
0 5
0 24
1 8
1 25
2 3
2 23
5 11
8 14
11 16
13 17
14 19
16 20
18 22
19 21
20 22
21 22
23 24
23 25
1 4
2 28
2 29
4 7
4 8
7 29
12 26
14 15
15 19
15 21
17 21
18 21
26 27
27 28
3 7
3 25
6 9
6 13
7 15
9 10
10 17
12 16
12 18
13 15
17 18

Qui bisogna scrivere le città nei grafi {gratis, col bus, col treno, tutti} e contare per ogni grafo quante tappe si possono raggiungere.

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

#define M 10000

using namespace std;

ifstream in;
ofstream out;

int n,a,cg,cb,ct,t1,t2,tg=0,tb=0,tt=0,tc=0;

vector<int> vg[M];
vector<int> vb[M];
vector<int> vt[M];
vector<int> vc[M];

int attr[M];
bool vis[M];


void gg(int k){
//esplora il grafo gratuito e somma le fermate con punti di attrazione
vis[k]=false;
if (binary_search(attr,attr+a,k))
 tg++;
for (int i=0;i<vg[k].size();i++)
 if(vis[vg[k][i]])
  gg(vg[k][i]);}
void gb(int k){
//esplora il grafo bus e somma le fermate con punti di attrazione
vis[k]=false;
if (binary_search(attr,attr+a,k))
 tb++;
for (int i=0;i<vb[k].size();i++)
 if(vis[vb[k][i]])
  gb(vb[k][i]);}
void gt(int k){
//esplora il grafo treno e somma le fermate con punti di attrazione
vis[k]=false;
if (binary_search(attr,attr+a,k))
 tt++;
for (int i=0;i<vt[k].size();i++)
 if(vis[vt[k][i]])
  gt(vt[k][i]);}
void gc(int k){
//esplora il grafo combinato e somma le fermate con punti di attrazione
vis[k]=false;
if (binary_search(attr,attr+a,k))
 tc++;
for (int i=0;i<vc[k].size();i++)
 if(vis[vc[k][i]])
  gc(vc[k][i]);}


int main(){
in.open("input.txt");
out.open("output.txt");

in>>n>>a>>cg>>cb>>ct;

for (int i=0;i<a;i++)
 in>>attr[i];
sort(attr,attr+a);
for (int i=0;i<cg;i++){
 in>>t1>>t2;
 vg[t1].push_back(t2);
 vb[t1].push_back(t2);
 vt[t1].push_back(t2);
 vc[t1].push_back(t2);
 vg[t2].push_back(t1);
 vb[t2].push_back(t1);
 vt[t2].push_back(t1);
 vc[t2].push_back(t1);
 }
for (int i=0;i<cb;i++){
 in>>t1>>t2;
 vb[t1].push_back(t2);
 vc[t1].push_back(t2);
 vb[t2].push_back(t1);
 vc[t2].push_back(t1);
 }
for (int i=0;i<ct;i++){
 in>>t1>>t2;
 vt[t1].push_back(t2);
 vc[t1].push_back(t2);
 vt[t2].push_back(t1);
 vc[t2].push_back(t1);
 }
 


memset(vis,true,n);
gg(0);
memset(vis,true,n);
gb(0);
memset(vis,true,n);
gt(0);
memset(vis,true,n);
gc(0);


out<<tg<<"\n"<<tb<<"\n"<<tt<<"\n"<<tc;

return 0;}

[C++] Zig Zag

Una sequenza viene detta una sequenza a zig-zag se i valori delle differenze tra numeri successivi si alterna tra valori positivi e valori negativi. La prima differenza può essere negativa 0 positiva, se è negativa quella dopo deve essere positiva, se è positiva quella dopo deve essere negativa e così via. Una sequenza con meno di due elementi è anche una sequenza a zigzag. Ti viene data una sequenza di numeri, tu puoi decidere di eliminare quanti numeri vuoi dalla sequenza in modo che i numeri rimanenti formino una sequenza a zigzag. Trovare la sequenza a zigzag più lunga che è possibile ottenere e stampare la sua lunghezza.

Input
Il programma deve leggere dal ﬁle : la prima riga contiene un intero N. La seconda riga contiene N valori positivi, i valori della sequenza di partenza.
Output
Il programma deve scrivere nel ﬁle la risposta al problema.

Assunzioni
1 ≤ N ≤ 800

Esempio
input output
10 7
1 17 5 10 13 15 10 5 16 8

Basta sfogliare la sringa ed eliminare tutti gli "errori" che si incontrano:

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

using namespace std;

ifstream in;
ofstream out;

int n;

     
int iz(int *c, int n){
     bool positive;
     int nc=n;
     positive= (c[0]-c[1] < 0);
     for (int i=0;i<n-1;i++){
     int d=c[i]-c[i+1];
      if (d==0||(d<0 && !positive)||(d>0 && positive))
         nc--;
      else
      positive= (d > 0);
         }
      return nc;
     }
 
 


int main()
{   in.open("input.txt");
    out.open("output.txt");
    
in>>n;
int c [n]; 
for (int i=0;i<n;i++)
    in>>c[i];
    
if (n<2)
   out<<1;

        
else 
out << iz(c,n);

    return 0;
}

[C++] Ristorante

Edoardo possiede un ristorante per al massimo N persone. L’entrata del ristorante ha un guardaroba con N appendini. Ogni cliente può usare un appendino del guardaroba per metterci le proprie giacche. Utilizzare l’iesimo gancio ha un costo ai in euro. Ogni persona può utilizzare al massimo un gancio.
Stasera Edoardo si aspetta di ricevere M clienti al ristorante. Naturalmente ogni cliente vorrà utilizzare gli appendini con il costo minimo (se ce ne sono di più con lo stesso costo, ne prenderà uno a caso tra questi). Purtroppo, se nel momento in cui un cliente arriva non ci sono appendini disponibili, Edoardo deve pagare una multa di D euro al cliente.
Aiuta Edoardo a trovare il proﬁtto in euro (può anche essere negativo) che avrà questa sera per quanto riguarda il guardaroba. Puoi assumere che prima che i clienti arrivino tutti gli appendini siano disponibili e che nessun altro a parte gli m clienti visiterà il ristorante.

Input
Il programma deve leggere da un ﬁle di nome “input.cxt”. La prima riga contiene due interi N e D.
La riga successiva contiene N interi, cioè a1, a2, ..., aN. La terza riga contiene l’intero M.

Output
Il programma deve stampare sul ﬁle la risposta al problema.

Assunzioni
1 ≤ N ≤ 100.000
1 ≤ M ≤ 200.000
1 ≤ ai ≤ 1000
1 ≤ D ≤ 2000

Esempio
input output
2 1 -5
2 1
1 0

Ordinati i prezzi in ordine crescente li prendiamo tutti in ordine, finiti sottraiamo al profitto la multa:

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

using namespace std;

ifstream in;
ofstream out;

int n,d,m,profitto;

int main()
{   in.open("input.txt");
    out.open("output.txt");
    
in >> n>>d;
int prezzi[n];
for (int i=0;i<n;i++)
    in>>prezzi[i];
in>>m;

profitto=0;
sort(prezzi,prezzi+n);

for (int i=0;i<m;i++)
    if(i<n)
           profitto+=prezzi[i];
    else
        profitto-=d;
        
out<<profitto;

    return 0;
}

[C++] Ponti

Pesanti piogge hanno colpito il territorio e molte strade sono state rese totalmente inagibili. Diverse città sono quindi state totalmente disconnesse rendendo falso questo motto: "ogni città è raggiungibile da ogni altra città".
E' necessario quindi trovare il numero mimino di strade necessario per poter riaffermare il motto del territorio.

Input
Il programma deve leggere da un ﬁle di nome “input.txt” nel quale, nella prima riga, sono presenti due interi: il numero di citta N e il numero di strade M.
Le successive M righe contengono una coppia di interi i e j. Ogni coppia rappresenta un percorso ancora agibile tra la citta i e la citta j (e viceversa).

Output
Il programma deve scrivere in un ﬁle “output.txt” il numero minimo di strade da construire per ricollegare tutte le città disconnesse.

Assunzioni
1 ≤ N ≤ 10.000
1 ≤ M ≤ 20.000
0 ≤ i, j < N

Esempio
input.txt output.txt
52 2
21
34

Con un grafo contiamo quanti settori (gruppi di città non collegati fra loro) e al loro numero sottraiamo 1.

#include<cstdlib>
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring> //memset

#define NODI 10000

using namespace std;

int m,n,x,y,b=0,s;

vector<int> c [NODI];
bool v [NODI];

ifstream in;
ofstream out;

void e(int k){
//esplora il grafo e quando si ferma aggiunge un blocco
v[k]=1;
s=c[k].size();
if(s > 0)
 for(int i = 0; i < s; i++){
  int f = c[k][i]; 
  if(v[f] == 0) 
   e(v[f]);} 
else 
 b++;
}

int main(){

in.open("input.txt");
out.open("output.txt");

in >> n>>m;


memset(v,0,n);

for (int i=0;i<m;i++){
in>>x>>y;
c[x].push_back(y);
c[y].push_back(x);}

for (int i=0;i<n;i++)
 if(v[i]==0)
  e(i);

out << (b-1);

return 0;}

[C++] Triangolo

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Questo è un triangolo!
Scrivete un programma che calcoli la più grande somma di numeri ottenibile seguendo un percorso che parta dalla cima del triangolo e termini da qualche parte sulla sua base. Ad ogni passo si può procedere diagonalmente in basso o a destra o a sinistra.

Input
Il programma deve leggere da un ﬁle di nome ‘input.txt’. La prima riga del ﬁle contiene un’unico intero N, il numero di righe del triangolo. Le successive N righe contengono un numero crescente di interi 2', la n-esima riga contiene n interi separati da uno spazio.

Output
Il programma deve scrivere in un ﬁle di nome ‘output.txt’ la somma massima ottenibile dal triangolo.

Assunzioni
1 < N ≤ 100
0 < i < 100

input.txt output.txt
5 30
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Partendo dal basso salviamo il punteggio maggiore fra i figli nel padre, il nonno di tutti (il vertice) avrà la risposta:

#include<cassert>
#include<fstream>
#include<iostream>

using namespace std;

#define UNKNOWN  -1
#define N  100

int t[N][N],n,memoRisp[N+1][N+1];


int main() {
  ifstream fin("input.txt"); assert( fin );
  fin >> n;
  for(int i = 0; i < n; i++)
    for(int j = 0; j <= i; j++)
       fin >> t[i][j];
  fin.close();


  for(int i = 0; i < n; i++)
    for(int j = 0; j <= i; j++)
       memoRisp[i][j] = UNKNOWN;


  for(int j = 0; j <= n; j++)
     memoRisp[n][j] = 0;
  for(int i = n-1; i >= 0; i--)
    for(int j = 0; j <= i; j++)
       memoRisp[i][j] = t[i][j] + max( memoRisp[i+1][j], memoRisp[i+1][j+1] );

  ofstream fout("output.txt"); assert( fout );
  fout << memoRisp[0][0] << endl;
  fout.close();

  return 0;
}

[C++] Piastrelle

Giovanni vuole piastrellare il suo bagno. Il suo bagno è grande lxN e lui vorrebbe piastrellarlo con piastrelle grandi 1x2 e 1X1. Giovanni vuole decidere come piastrellare il suo bagno. Stampa a Giovanni tutte le possibili piastrellature del bagno, in modo da aiutarlo a scegliere.

Input
Il ﬁle ‘input.txt’ è costituito da un unico numero N, la dimensione del bagno.

Output
In questo ﬁle devono comparire tante righe quante sono le possibili piastrellature del bagno. Ogni piastrellatura possibile deve essere stampata in questo modo. Se la piastrella è da 1X1, stampare [O] (senza virgolette). Se la piastrella è da 1X2, stampare [OOOO], senza virgolette. Le piastrellature devono essere stampate in ordine lessicograﬁco in base alla grandezza delle piastrelle.

Assunzioni 1 ≤ N ≤ 25

input.txt output.txt
4 [O][O][O][O]
[O][O][OOO]
[O][OOO][O]
[OOO][O][O]
[OOO][OOO]

Noi andremo, con una funzione ricorsiva, a scrivere riga per riga le piastrellature.
Se ci fate caso questo problema si basa sui numeri di Fibonacci; per risolvere il numero di Fibonacci ci sono due principali algoritmi: uno basato sulla ricorsione (molto lento) e uno molto veloce iterativo.
Risolvere questo problema iterativamente però è molto difficile, e considerato che in questo caso il massimo è 25 (numero relativamente basso) la soluzione ricorsiva non da problemi.

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <string>
#include <cassert>

#define p1 "[O]"
#define p2 "[OOOO]"

using namespace std;

int n;
ifstream in;
ofstream out;

void stampaPiastr(int n, string storia){
// stampa, una per riga, tutte le possibili diverse piastrallature del bagno 1xn.
// ciascuma prefissata dalla stringa <storia>

assert (n>=0);

    if (n==0) { // caso base
       out << storia <<"\n";}
    else if (n==1) { // saso base
       out << storia+p1<<"\n";}
    else {
       stampaPiastr(n-1, storia+p1);
       stampaPiastr(n-2, storia+p2);
    }
}

int main() {
in.open ("input.txt");
out.open ("output.txt");

in >> n;

stampaPiastr(n,"");

    return 0;
}