Info Guide

martedì 1 aprile 2014

[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;
}

lunedì 31 marzo 2014

[C++] Problemi

Per il server centrale di questo istituto transitano tutte le connessioni ad internet, che, a quanto pare, stanno intasando tutta la rete. Il docente responsabile, quindi, sta procedendo con un’indagine per capire quali sono le cause di questi rallentamenti.
La rete della scuola è strutturata ad albero, in cima si trova il server centrale che è collegato a dei server periferici, i quali a loro volta possono essere collegati ad altri server, ecc. Ognuno di questi server viene deﬁnito “nodo di articolazione” se è collegato direttamente ad almeno un altro nodo di articolazione. I server che non sono collegati a nessun altro (le foglie dell’al— bero) sono i computer di un laboratorio e sono proprio quelli che utilizzano la banda!
A tutti i nodi di articolazione è associato un peso che rappresenta il valore massimo che può sopportare prima di causare problemi, a tutti gli altri nodi invece è associato un peso che rappresenta l’utilizzo medio della banda in quel laboratorio.
La banda passante per un nodo di articolazione viene calcolata sommando la banda passante di tutti i nodi di articolazione collegati in quel nodo più la banda dei laboratori direttamente collegati. Un nodo di articolazione da problemi se la banda passante è maggiore o uguale alla banda massima supportata.
Scrivere quindi un programma che, dato in input la rete della scuola, calcoli il numero dei nodi di articolazione che causano problemi.

Input
Il programma deve leggere da un ﬁle di nome ‘input.txt’. Nella prima riga sono presenti due interi separati da uno spazio: N e S, rispettivamente il numero di server in rete (compreso il server centrale e i server del laboratorio) e il numero del server centrale. Nelle successive N righe sono presenti due interi i, j.
i è il numero del server a cui il server corrente è collegato, j è la banda massima se è un nodo di articolazione, la banda media se è un server di un laboratorio.

Output
Il programma deve scrivere in un ﬁle di nome ‘output/cxt’. Deve venire stampato un unico intero, la soluzione del problema.

Assunzioni
0 < N <= 100.000
0 <= S < N
0 <= i < N
1<= j <= 1.000.000
Il server S è collegato a S

Nell'esempio i nodi 3 e 4 causano problemi:
input.txt output.txt
5 4 2
4 1
3 2
3 2
4 1
4 2

Questo è un classico problema ad albero: partendo dalle foglie (i computer che consumano banda) scriviamo il consumo nei padri, che lo scriveranno ai loro padri tramite una funzione ricorsiva.
Alla fine contando i nodi in cui il consumo supera la banda avremo la soluzione.

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

#define N 100000

using namespace std;

ifstream in;
ofstream out;

struct nodo{
int banda;
int padre;
int consumo;};

int n,s,p=0,t,size;
nodo pc[N];
int figli[N];

void pa(int k){if (k==s) return;
pc[pc[k].padre].consumo+=pc[k].banda;
pa(pc[k].padre);}

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

in>>n>>s;

memset(figli,0,n);

for (int i=0;i<n;i++){
 in >>t>>pc[i].banda;
 figli[t]++;
 pc[i].padre=t;
 pc[i].consumo=0;}

for (int i=0;i<n;i++){
// scrivi nel padre il consumo
if (figli[i] ==0){//foglia
pc[pc[i].padre].consumo+=pc[i].banda;
pa(pc[i].padre);
}}

for (int i=0;i<n;i++)
 if (pc[i].consumo > pc[i].banda)
  p++;

out<<p;

return 0;}

[C++] Pazzo

Questa mattina è successo un fatto piuttosto insolito... L’assistente tecnico del laboratorio è uscito di senno e si è messo a cambiare gli ip dei computer in rete! Questo non sarebbe un grosso problema se non fosse per il fatto che anche l’IP del server è stato modiﬁcato... Adesso ci sono grossi problemi a capire quale degli N computer del laboratorio è il server. Fino a ieri i computer erano numerati da 0 a N-l e il computer che si trovava nella prima posizione (la posizione 0) era il server, tutti gli altri computer da 1 a N-l sono ordinati secondo la loro posizione. Fortunatamente il laboratorio possiede un ﬁle di log dove vengono salvate tutte le modiﬁche agli indirizzi di rete dei vari dispositivi. Allo stato attuale in questo ﬁle sono presenti M righe. Ogni riga di questo ﬁle contiene due numeri, i e j che indicano i numeri dei pc che sono stati scambiati dal tecnico. Dopo un’analisi preliminare Edoardo, l’allievo incaricato di risolvere questo pasticcio, si è accorto che in ogni scambio i pc coinvolti avevano una posizione adiacente!
Scrivere un programma che dato in input N, M e la lista degli M scambi ritorni il numero del pc con l’IP del server.

Input
Il programma deve leggere da un ﬁle di nome ‘input.txt’. Nella prima riga sono presenti due interi, N e M separati da uno spazio. Nelle successive M righe sono presenti delle coppie di interi i, j separate da spazio

Output
Il programma deve scrivere in un ﬁle di nome ‘outpu.txt’. Deve essere scritto un solo intero, il numero del PC con l’IP del server.

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

Basta tenere conto, negli spostamenti, del pc a cui è assegnato l' ip del server:

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

using namespace std;

int main()
{ ifstream in("input.txt");
  ofstream out("output.txt");
  
int m,n,v1,v2,ip=0;

in>> n>>m;

int pc[m][2];

for (int i=0;i<m;i++)
   in >> pc[i][0]>>pc[i][1];

for (int i=0;i<m;i++)
    if (pc[i][0] == ip)
       ip = pc[i][1];
    else if (pc[i][1] == ip)
       ip = pc[i][0];

out<<ip;

    return 0;
}

[C++] Criptografia

La password di questo laboratorio è una stringa di N caratteri minuscoli, alquanto semplice da ricordare ma dato che ci sono molti assistenti tecnici in questa scuola è stato deciso di scriverla in un foglio. Pessima idea! La stringa criptata è ﬁnita nelle mani di Edoardo! Sara in grado il giovane studente di decifrarla ed ottenere l’accesso alle preziosissime cartelle sul server?
La stringa criptata è una stringa di L caratteri minuscoli dell’alfabeto latino ed ha la caratteristica di essere palindroma, si può quindi leggere da destra verso sinistra e viceversa senza che cambi. All’ interno di questa stringa alcune lettere sono state sostituite da delle cifre comprese tra 0 e N-1. La password può essere ricostruita se e solo se tutte le N cifre distinte hanno una corrispondenza con una lettera mantenendo la stringa palindroma.
Scrivi un programma che dato N, L e la stringa criptata ricostruisca la corrispondenza cifra-carattere
La password viene ottenuta concatenando in ordine i caratteri delle corrispondenze

Input
Il programma deve leggere da un ﬁle di nome ‘input.txt’. Nella prima riga sono presenti due interi separati da uno spazio: N e L, rispettivamente il numero di cifre incognite e il numero di caratteri della stringa. Nella seconda riga è presente ls stringa di L caratteri senza spazi.

Output
Il programma deve scrivere in un ﬁle di nome ‘output.txt’. Deve venire stampata la stringa ‘impossibile’ se non esiste una corrispondenza cifra-carattere 0 se ne esistono molteplici. Altrimenti stampare nel ﬁle una stringa di N caratteri: la password decodiﬁcata.

Assunzioni
0 < N <= 10
2 <= L <= 200.000 (un caso con L = 50.000.000)
0 <= i < N
L è pari

Esempio
inputﬂ.txt outputﬂcxt
2 10 nw
01lrbbrlwn
inputﬂ.txt output .txt
1 10 impossibile
ebg00hdgbe
inputﬂ.txt output.txt
1 10 impossibile
0VWqttqWV0

Note
Nel secondo caso non esiste una corrispondenza per la cifra 0. Nel terzo invece ne esistono molteplici.

Qui basta scorrere e sostituire n volte la stringa. Se non ci sono lacune corrispondenze stampare "imossibile"

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

#define no "impossibile";

using namespace std;

int main()
{ ifstream in("input.txt");
  ofstream out("output.txt");
  
int n,l,j=0,k,f,sl,si;
string s;
bool iff =true;

in>> n>>l>>s;
sl=s.length();

char vect[n];

for (int i=0; i< sl;i++){
    si=s[i];
    k =  si - '0';
    f =s[sl-1-i];
    if ( isdigit(s[i])&& k ==j){
         if (isdigit(f))
         iff=false;
          for (int i=0;i<sl;i++)
              if(s[i]== si)
                        s[i]=f;
          vect[j++] = f;
       }}
       
for (int i=0; i< s.length();i++)
    if (s[i] != s[s.length()-1-i])
       iff=false;
       
if (iff)
for (int i=0; i< n;i++)
out << vect[i];
else
out<<no;


    return 0;
}

[C++] Sacchi

Mario lavora in una fabbrica di zucchero come uomo delle consegne. Ha appena ricevuto un ordine:
deve consegnare esattamente N kilogrammi di zucchero a un negozio di caramelle sulla costa
dell'Adriatico. Mario può usare due tipi di pacchi: quelli che contengono 3 kg, e quelli che
contengono 5 kg di zucchero (non ci sono pacchi con misure intermedie, può usare solo pacchi
pieni da 3k o 5kg).
Mario vorrebbe usare il numero minore di pacchi possibile. Se per esempio deve consegnare 18kg
di zucchero, potrebbe usare 6 pacchi da 3kg. Ma sarebbe meglio utillizare tre pacchi da 5kg e 1
pacco da 3kg, per un totale di 4 pacchi.
Aiutate Mario a trovare il numero minore di pacchi necessari per trasportare esattamente N
kilogrammi di zucchero

INPUT (input.txt)
La prima e unica riga dell'input contiene un intero N (3 <= N <= 5000).

OUTPUT (output.txt)
L'output deve consistere di un unico numero, il numero minore di pacchi che Mario deve usare. Se è
impossibile trasportare esattamente N kilogrammi, stampare in output -1.

input.txt input.txt input.txt
4 9 18
output.txt output.txt output.txt
-1 3 4

Sfruttiamo al massimo i pacchi da 5, poi, se non bastano, usiamo quelli da tre:

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

using namespace std;

int main(){
    ifstream in ("input.txt");
    ofstream out ("output.txt");
   
   int k,d5,d3,s3;
      in>>k;

d5= k/5;
d3= k-d5*5;
s3=d3/3;

while (d3%3 != 0 && d5-1 >-1){
d3= k-(--d5)*5;
s3=d3/3;}

 
if (d3%3 ==0 )
out<< d5+s3;
else
   out<< -1;
    return 0;}

[C++] Numeri

Carlo ha un fratello minore, Marco, che ha appena iniziato ad andare a scuola e ha qualche
problema con i numeri. Per aiutarlo a fargli capire il valore dei numeri, il suo insegnante scrive due
numeri con tre cifre alla lavagna. Poi chiede a Marco di comparare i due numeri, ma invece di
interpretarli con la cifra più significativa a sinistra, deve interpretarli con la cifra più significativa a
destra. Marco deve dire all'insegnante quale sia il maggiore dei due numeri.
Scrivere un programma che controlli le risposte di Marco.

INPUT (input.txt)
La prima e unica riga dell'input contiene due numeri da tre cifre, A e B. A e B non sono uguali e non
contengono zeri.

OUTPUT (output.txt)
La prima e unica riga dell'output deve contenere il maggiore tra i due numeri dati in input,
comparato con i metodi previsti nel testo. Il numero deve essere scritto al contrario, come
Marco dovrebbe leggerlo.

input.txt input.txt input.txt
734 893 221 231 839 237
output.txt output.txt output.txt
437 132 938

Con l' operatore modulo (%, a%b è il resto della divisione intera a:b) scomponiamo le cifre dei due numeri e una volta assemblate al contrario possiamo confrontarle:

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

using namespace std;

int main(){
    ifstream in ("input.txt");
    ofstream out ("output.txt");
   int a,b,c,d,e;
   in>>a>>b;
   
   c= a/100;
   d= a%100 /10;
   e= a%10;
   a= 100*e+10*d+c;
   
   c= b/100;
   d= b%100 /10;
   e= b%10;
   b= 100*e+10*d+c;
   
    out <<max(a,b);
    
    return 0;}

_________________________________________________________________________________

[C++] Gara di informatica

Ogni anno l'università organizza una competizione a squadre di informatica. Ogni squadra
è composta da tre studenti.
Tradizionalmente le migliori sono sempre state le ragazze, che quindi partecipavano in
sovrannumero rispetto al numero di ragazzi a questa competizione. Quest'anno i ragazzi con le loro
proteste hanno fatto approvare una regola: ogni squadra deve essere composta da esattamente 1
ragazzo e 2 ragazze.
Per rendere l'organizzazione della competizione ancora più difficile, il preside della scuola ha
deciso che dovranno essere mandati K dei ragazzi (maschi o femmine) che si erano iscritti alla gara
in uno stage all'estero. Questi K ragazzi non potranno ovviamente fare parte di nessuna squadra,
non potendo partecipare alla gara.
Definito come M il numero di ragazze iscritte alla gara, con N il numero di ragazzi (maschi) iscritti
alla gara e con K il numero di ragazzi (maschi o femmine) che, scelti tra gli N + M ragazzi iscritti
alla gara, dovranno essere mandati allo stage all'estero, si determini qual è il massimo numero di
squadre che si possono iscrivere alla gara.
Per esempio se M è 6, N è 3 e K è 2, il preside può mandare una ragazza e un ragazzo (maschio)
allo stage, così rimangono 5 ragazze e 2 ragazzi. Allora si potranno iscrivere alla gara due squadre
(e una ragazza sarà lasciata senza squadra).

INPUT (input.txt)
La prima e unica riga dell'input contiene tre numeri, separati da uno spazio: M ( 0 <= M <= 100), il
numero di ragazze, N (0 <= N <= 100), il numero di ragazzi e K (0 <= K <= M+N), il numero di
iscritti alla gara che devono essere mandati in uno stage.

OUTPUT (output.txt)
L'output dovrà contenere un solo numero: il numero massimo di squadre che possono essere
composte.

input.txt input.txt input.txt
6 3 2 2 1 1 6 10 3
output.txt output.txt output.txt
2 0 3

Semplicemente dividendo il numero di ragazze a metà, la differenza fra ragazze/2 e ragazzi saranno gli alunni partecipanti allo stage, coi rimanenti si formano le squadre:

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

using namespace std;

int main(){
    ifstream in ("input.txt");
    ofstream out ("output.txt");
   
   int m,n,k,diff;
   
   in>>m>>n>>k;
   
   diff= m- 2*n;
   
   if (diff >0){
   k -= diff;
   if (k<0){diff+=k;k=0;}
   m-=diff;}else{
   k += diff;
   if (k<0){diff-=k;k=0;}
   n += diff;}
   
   diff = k/3;
   k -= 3*diff;
   if (k<0){diff+=k;k=0;}
   m -= 2*diff;
   n -= diff;
      
if (k>0)
if (2*n > m)
n-=k;
else
m-=k;

out << min(n,m/2);
    
    return 0;}

giovedì 27 marzo 2014

[C++] Canoa

Una gara di canoe sta per iniziare. Sfortunatamente dei forti venti hanno danneggiato alcune canoe e
la gara sta per iniziare!
Per fortuna alcune squadre hanno portato una canoa di riserva. Siccome le canoe sono pesanti e
difficili da trasportare, le squadre sono disposte a prestare la loro canoa di riserva (se ce l'hanno) a
una squadra avversaria se e solo se sono disposti immediatamenti vicini a loro (alla partenza, cioè
se hanno numeri di partenza immediatamente vicini). Per esempio, la squadra con il numero di
partenza 4, sarà disposta a prestare la sua canoa di riserva solo alle squadre con numero di partenza
3 e 5. Ovviamente se una squadra che ha portato la canoa di riserva ha la sua canoa danneggiata,
utilizzerà la canoa di riserva per sè.
Tu, come organizzatore della gara, vuoi sapere qual è il minimo numero di squadre che non possono
iniziare la gara, neanche con canoe imprestate.

INPUT (input.txt)
La prima riga dell'input contiene tre interi: N, (2 <= N <= 10), il numero totale di squadre, S (2 <=
S <= N), il numero delle squadre con canoe danneggiate e R ( 2 <= R <= N), il numero di squadre
con canoe di riserva.
La seconda riga dell'input contiene esattamente S numeri, i numeri delle posizioni alla partenza
delle squadre con canoe danneggiate. Questa riga non contiene duplicati.
La terza riga dell'input contiene esattamente R numeri, i numeri delle posizioni alla partenza delle
squadre con canoe di riserva. Questa riga non contiene duplicati.

OUTPUT (output.txt)
L'output contiene un singolo numero, il numero minimo di squadre che non possono iniziare la
gara.

input.txt    input.txt
5 2 3        5 2 1
2 4          2 4
1 3 5        3

output.txt output.txt
0          1

SOLUZIONE:
Procediamo con ordine: se una squadra ha una canoa:
* gli serve? se la tiene
* serve a sinistra? la da alla squadra di sisnistra
*la da alla squadra di destra

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

using namespace std;

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

int n,s,r,d=0;

in >>n>>s>>r;
int dann[s],ris[r];
bool pos[n][2];

for (int i=0;i<s;i++)
in>> dann[i];
for (int i=0;i<r;i++)
in>> ris[i];

for (int i=0;i< n;i++)
    pos[i][0]=pos[i][1]= 0;
    
for (int i=0;i< s;i++)
    pos[dann[i]][0]=1;
for (int i=0;i< r;i++)
    pos[ris[i]][1]=1;
    
for (int i=0;i< n;i++)
if (pos[i][0] && pos [i][1])
   pos[i][0] = pos [i][1]=0;

for (int i=0;i< n;i++)
if ( i-1 >= 0 && pos[i-1][0] && pos [i][1])
pos[i-1][0] = pos [i][1]=0;
else if (i+1<n && pos[i+1][0] && pos [i][1])
pos[i+1][0] = pos [i][1]=0;

for (int i=0;i< n;i++)
if (pos[i][0]) d++;

out<<d;


    return 0;}

giovedì 20 febbraio 2014

Rhinoceros 5 su Wine

1) Scarica lessmsi e avvialo con wine:

wget "https://lessmsi.googlecode.com/files/lessmsi-v1.0.10.zip"
unzip -d lessmsi lessmsi-v1.0.10.zip 
cd lessmsi
wine lessmsi.exe

2) Ora selezione il .msi di installazione di Rhino 5 e aprilo con lessmsi. Vai su "Exctract" e premi "select all".Non preoccuparti se la finestra dovesse divenatre nera. Clicca poi su "extract" e scegli una cartella dove estrarre il programma.
3) Vai alla cartella con i file estratti ed avvia SourceDir/Rhinoceros 5.0/System/Rhino4.exe


Purtroppo non è possibile salvare in quanto non funziona la gestione delle licenze

giovedì 30 gennaio 2014

[C++] Colore

Gianni ha N palline, disposte in fila, numerate da 1 a N. Queste palline sono speciali,
perchè sono colorate o di nero o di bianco. In particolare la pallina i sarà bianca se
A[i] = 0 e sarà nera se A[i] = 1. Gianni ha in mente un numero K. Questo numero K è
particolare, perchè divide N (cioè la divisione N / K ha resto 0). Gianni ha a
disposizione tantissima vernice nera e bianca, ma è molto pigro. Si definisca come
distanza tra due palline i,j il valore assoluto della differenza della posizione della
pallina i e della pallina j. Si vuole che se due palline hanno distanza K, allora siano
dello stesso colore. Qual è il numero minimo di palline che Gianni deve colorare per
soddisfare suddetta condizione?

Input (input.txt)
La prima riga dell'input consiste in due numeri, N e K, separati da uno spazio. La
seconda riga dell'input consiste in una sequenza di N numeri, cioè i valori di A[0],
A[1], ..., A[N].

Output (output.txt)
Il file di output dovrà contenere esattamente un numero, il numero minimo di palline
da colorare.
input.txt output.txt
10 2 3
1 0 1 1 0 1 1 0 1 1

SOLUZIONE
Partendo da un punto (0) si salta k palline e si contano quante sono nere e quante sono bianche. Il valore minimo fra bianche e nere è il numero minimo di palline da colorare di quella serie. Sommando i minimi di tutte le serie si ottiene il minor numero di palline da colorare:

[C++] Gara

C'è una gara di corsa in città. A partecipare a questa gara ci sono N persone. La gara
viene svolta in un rettilineo ("infinito"). Tutti i corridori corrono nella stessa
direzione. I partecipanti sono numerati da 1 a N. La gara non è completamente equa.
Infatti ogni partecipante non parte dallo stesso punto, ma ha un vantaggio di un certo
numero di metri (considerato rispetto al punto di partenza). Si consideri il vettore A,
A[i] denota il vantaggio in metri del partecipante numero i. Inoltre non ogni
partecipante della corsa procede alla stessa velocità. In particolare il partecipante con
numero i correrà con una velocità di B[i], espressa in metri per unità di tempo.
Vengono dati in input M valori di tempo, dire per ogni valore di tempo fornito in
input qual è il partecipante che si trova in vantaggio, ovvero più distante dal punto di
partenza, considerando che corra con una velocità costante (se più partecipanti si
trovano alla stessa distanza dalla partenza, considerare quello con numero più
piccolo).

Input (input.txt)
La prima riga dell'input contiene due numeri, N e M, separati da uno spazio.
La riga successiva contiene N numeri separati da uno spazio, cioè i valori di A[1],
A[2], ... , A[N].
La riga successiva contiene N numeri separati da uno spazio, cioè i valori B[1],
B[2], ..., B[N].
L'ultima riga dell'input contiene M numeri, separati da uno spazio, gli M valori di
tempo per cui si dovrà computare una risposta come descritto dal testo del problema.

Output (output.txt)
Il file di output dovrà contenere esattamente M righe. Data la sequenza degli M
valori di tempo, si stampi per ogni riga il numero del giocatore che si trova in
vantaggio (seguendo la consegna del testo del problema).

input.txt output.txt
2 2 1 2
1 0
4 6
0 1

SOLUZIONE
Per ogni valore di tempo si calcola la distanza di arrivo, poi si terrà conto della distanza massima.

[C++] Salto

Un clown si diverte a saltare. Ha a disposizione N blocchi. I blocchi sono numerati da
1 a N. Il blocco i ha un'altezza di A[i]. Si definisce come difficoltà del salto la
differenza di altezza tra due blocchi (il valore può essere sia negativo che positivo,
negativo se si salta verso il basso, positivo se si salta verso l'alto). Qual è il valore del
salto con difficoltà maggiore, potendo scegliere liberamente due blocchi?

Input (input.txt)
La prima riga dell'input contiene un singolo valore N.
La seconda riga dell'input contiene N valori, separati da uno spazio, cioè i valori
A[1], A[2],..., A[N].

Output (output.txt)
Il file di output dovrà contenere esattamente un numero, cioè il valore del salto con
difficoltà maggiore.

input.txt   output.txt
5            6

5 1 6 3 7

SOLUZIONE
Il salto più difficile è quello fra la pedana con punteggio minore e quella con punteggio maggiore.

[C++] Magia

Un numero si dice magico se composto da 1, 14, 144 combinati anche più volte in modo casuale.
Il programma prende un numero e ritorna YES se è magico, altrimenti NO

esempi:
1441414411 ->YES
1514 -> NO
14444 -> NO

giovedì 9 gennaio 2014

DE Survey

Piccolo sondaggio sui DE di Linux, il sondaggio durerà per un lungo periodo di tempo e può essere compilato più volte. I risultati possono essere visti qui.

Versioni di Ubuntu

Cosa curiosa è che il numero delle versioni di Ubuntu non è casuale o incrementato, ma indica l' anno e il mese di uscita della versione ufficiale (anno.mese), e il nome? Il nome è sempre composto da un aggettivo e un nome di animale che inziziano con la stessa lettera, e dalla 6.06 (Dapper Drake) vanno in ordine alfabetico:

Versione	Nome	Rilascio
4.10	Warty Warthog (Facocero Verrucoso)	20 ottobre 2004
5.04	Hoary Hedgehog (Riccio Veterano)	8 aprile 2005
5.10	Breezy Badger (Tasso Arioso)	12 ottobre 2005
6.06 LTS	Dapper Drake (Papero Signorile)	1º giugno 2006
6.10	Edgy Eft (Tritone Tagliente)	26 ottobre 2006
7.04	Feisty Fawn (Cerbiatto Esuberante)	19 aprile 2007
7.10	Gutsy Gibbon (Gibbone Coraggioso)	18 ottobre 2007
8.04 LTS	Hardy Heron (Airone Audace)	24 aprile 2008
8.10	Intrepid Ibex (Stambecco Intrepido)	30 ottobre 2008
9.04	Jaunty Jackalope(Lepre cornuta Disinvolta)	23 aprile 2009
9.10	Karmic Koala (Koala Karmico)	29 ottobre 2009
10.04 LTS	Lucid Lynx (Lince Lucida)	29 aprile 2010
10.10	Maverick Meerkat (Suricato Indipendente)	10 ottobre 2010
11.04	Natty Narwhal (Narvalo Elegante)	28 aprile 2011
11.10	Oneiric Ocelot (Gattopardo Onirico)	13 ottobre 2011
12.04 LTS	Precise Pangolin (Pangolino Preciso)	26 aprile 2012
12.10	Quantal Quetzal (Quetzal Quantico)	18 ottobre 2012
13.04	Raring Ringtail (Lemure Impaziente)	25 aprile 2013
13.10	Saucy Salamander (Salamandra Impertinente)	17 ottobre 2013
14.04	Trusty Tahr (Capra Affidabile)	17 aprile 2014