Info Guide: marzo 2014

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