Info Guide

ATTENZIONE

2014-08-07T18:19:00.001+02:00

ATTENZIONE!!!!!!!!!!!!!!!!!!!!!!!

ci siamo trasferiti a : http://dakation.altervista.org/infoguide/

Convertire un pdf in bianco e nero in un comando con Linux

2014-07-19T14:16:00.001+02:00

Grazie al software opensource To Black and White potremmo convertire i nostri documenti in bianco e nero in pochi secondi:

Installiamo To Black and White:

sudo add-apt-repository ppa:dpd-/ppa -y
sudo apt-get update -y
sudo apt-get install tobw -y

L'utilizzo è semplice:

tobw file.pdf

E otterremo il file risultante nella stessa cartella dell'input.

Creare un pacchetto e pubblicarlo su Launchpad

2014-07-19T13:16:00.001+02:00

Abbiamo realizzato un programma in bash, c, c++, python, gambas, .... e vogliamo pubblicarlo? ecco come si fa:

Inanzitutto compiliamo il nostro file come script eseguibile senza dargli l'estensione ".sh".
Il nome che scegliamo è importante in quanto sarà il shortname con cui richiameremo il programma dal terminale: se salviamo il file come "app" nel terminale sarà:
utente@pc:~$app
Questo implica il fatto che il nostro programma potrebbe avere problemi se si chiama come iun altro programma di un altro sviluppatore!

Bene ora si comincia: creiamo le seguenti cartelle (i nomi in corsivo sono a vostra scelta):
$ cd ~
$ mkdir pacchetti
$ cd pacchetti
$ mkdir app-1.0.0
$ cd app-1.0.0

Ora creiamo lo scheletro del pacchetto con debhelper:
$ dh_make -n

rispondiamo "s" alla prima domanda (stiamo creando un pacchetto singolo) e premiamo "invio" alla seconda domanda per accettare i suggerimenti su e-mail, nome del maintainer, licenza, ...
A questo punto si può notare che è stata creata una directory "debian".

In parte alla cartella "debian" creiamo una cartella "script" dove metteremo i nostri eseguibili.
Assicuriamoci che essi abbiamo i corretti permessi di esecuzione:
$ chmod 755 script1 script2....

Ora entriamo nella cartella "debian":
file control:

Source: app Section: utils
Priority: optional
Maintainer: Nome Cognome <mail>
Build-Depends: debhelper (>= 8.0.0)
Standards-Version: 3.9.4
Homepage:
Package: tobw
Architecture: all
Description: Descrizione breve Descrizione lunga Usare lo spazio a inizio riga per la descrizione

Se abbiamo bisogno di dipendenze possiamo aggiungerle: Depends: ghostscript (>=1.0.0)

file changelog
Qui dobbiamo cambiare la scritta unstable (o stable) con la versione attuale di Ubuntu (es.: trusty)

Ora creiamo un file install dove scriveremo:

script/* usr/bin/

A indicare che copi tutto il contenuto della cartella script in /usr/bin

Ora è tutto pronto per creare il pacchetto. Spostiamoci nella directory "app-1.0" ed eseguiamo:
$ dpkg-buildpackage -us -uc

Ora che abbiamo un pacchetto dobbiamo firmarlo:

Per prima cosa creiamo una chiave GPG:
$ gpg --gen-key

rispondiamo "1"alla prima domanda ovvero DSA e ElGamal, diamo invio;
come dimensione lasciamo pure 1024, diamo invio;
mettiamo "0" come scadenza, diamo invio;
rispondiamo "s", diamo invio;
ora ci verrà chiesto Nome e Cognome,indirizzo email e il commento per la coppia di chiavi
ora premiamo 'o' e invio;
ora ci verrà richiesta la password per le chiavi, inseriamola e invio.

In debian/changelog dobbiamo scrivere Nome Cognome (commento) <mail> con i dati spora inseriti.

Per caricare un pacchetto in rete dobbiamo registrare la nostra chiave presso il server di Ubuntu:
Apriamo Password e Chiavi e selezioniamo la nostra chiave.
Remoto -> Sincronizza e pubblica chiavi. e sincronizza chiave con hkp://keyserver.ubuntu.com

Spostiamoci nella directory "app-1.0.0" ed eseguiamo:
$ dpkg-buildpackage -s

Ora dobbiamo registrarci su Launchpad:
Colleghiamoci a launchpad.net e seguiamo la procedura guidata di log on.

Ora nella nostra Dashboard clicchiamo sulla matita nel cerchio giallo vicino a OpenPGP Keys:
diamo $gpg --fingerprint e copiamo la chiave nella casella di testo e premiamo import key.

Ora riceveremo una mail con un link di conferma, essendo cifrata per poterla leggere occorre un plugin il cui link è nella mail stessa.

Ora possiamo premere Create a new PPA e seguire la procedura guidata.

E ora:

dput ppa:nostroppa '*source.changes'

Per effettuare modifiche lavoriamo sulla directory di prima (se la abbiamo cancellata basta dare dpkg-source -x app_1.0.0.dsc per ricrearla) e alla fine dare:

dch -i

Che mette la data di aggiornamento e ci permette di scrivere un commento su ciò che abbiamo modificato.

Poi basta ridare dpkg-buildpackage -s e dput ppa:nostroppa 'app-1.0.0_source.changes'

UEFI Secure Boot: è sicuro per noi o per loro?

2014-06-09T15:25:00.001+02:00

Microsoft ha imposto già da tempo ai produttori di computer di venderli con UEFI attivato, ma cos'è
UEFI?

UEFI è un'alternativa al BIOS nelle schede madri che dovrebbe avere questi vantaggi:

Miglioramento della sicurezza nella fase di avvio.
Maggiore velocità dei tempi di avvio e di ripresa dallo stato di ibernazione.
Supporto di unità maggiori di 2,2 terabyte (TB).
Supporto di driver di dispositivi firmware a 64 bit che il sistema può utilizzare per indirizzare più di 17,2 miliardi di gigabyte (GB) di memoria durante l'avvio.
Possibilità di utilizzare il BIOS con hardware UEFI.
Fonte: Microsoft

Il bollino traditore, simbolo della presenza di UEFI.

Ma in pratica è una garanzia per la Microsoft dal momento in cui su una macchina UEFI puoi installare solo Windows e da Win 8 in poi; e una garanzia per i produttori di schede in quanto funzionano solo le schede certificate (il certificato è a pagamento).

Questo chiude il mondo dell' open: i sistemi open source come Linux non potranno più essere installati e molte schede open hardware non potranno essere utilizzate.

Microsoft si difende dicendo che non obbliga a usare UEFI: obbliga solo a vendere pc con UEFI attivato e che gli utenti possono disattivarlo dalle impostazioni del BIOS, ma il problema è che non in tutti i computer si può disattivare: in molti è obbligatorio!

La Free Software Foundation ha aperto una petizione contro il UEFI obbligatorio: se vuoi partecipare clicca su questo link!

Comunque Windows 8 e 8.1 si possono installare anche con UEFI disabilitato, quindi permettendo la coesistenza Win-Linux.

Per i computer con UEFI non disabilitabile si possono usare alcune versioni di Linux contenenti una chiave UEFI comprata da Matthew Garrett integrata nel loader Shim:

Ubuntu 12.10 (solo nella versione 64 bit) e Ubuntu 13.04
Fedora 18
Sabayon 11
Arch Linux (vedi Wiki)
openSUSE 12.3
Linux Mint 15 Olivia (anche se non confermato dovrebbe supportare UEFI)

VLC volume a 150%? portalo a 200%!

2014-06-03T18:34:00.001+02:00

Con gli ultimi aggiornamenti di VLC non si può alzare il volume più del 125%, questo è stato pensato

per evitare distorsioni, ma quando si ascoltano canzoni a basso volume occorre alzare oltre questa soglia.

In realtà in VLC il volume si può alzare fino al 300%: basta solo impostare il livello-soglia:

Aprite VLC, andate su strumenti-> preferenze
Ora aprite la visualizzazione tutto (1), poi andate su interfaccia (2) -> Qt (3) e in fondo trovate la voce "Volume massimo visualizzato" dove (4) potete mettere la vostra soglia fino a 300. Infine salvate (5).

Storia del computer

2014-05-22T15:00:00.001+02:00

È noto quasi a tutti che fin dalla prima metà dello scorso millennio i cinesi ebbero un particolare

Abaco cinese e abaco moderno

interesse per la matematica e per l'automazione dei calcoli: esempi che possiamo ancora vedere ai giorni nostri sono abaco e pallottoliere; ma pochi sanno che fin dal XIX secolo si sono create macchine molto vicine ai moderni computer.
La macchina analitica di Charles Babbage ne è l'esempio per eccellenza: era una macchina, di grandi dimensioni, che permetteva di fare le principali operazioni matematiche e di visualizzarne il risultato grazie a delle ruote con impresse le dieci cifre, inoltre il progetto originale prevedeva un sistema per stampare su carta la cronologia dei calcoli effettuati, ma non furono trovati i fondi necessari a costruirla. Recentemente è stata realizzata una macchina analitica compresa di "stampante" funzionante seguendo i progetti originali e utilizzando solo materiali all'epoca conosciuti: secondo alcuni esperti, se si fossero trovati i fondi necessari, i moderni computer potrebbero aver visto luce molti anni prima.

Macchina analitica

Ada Lovelace, figlia del poeta inglese Lord Byron e anche vissuta nel XIX secolo, compì studi approfonditi sulla macchina analitica e scrisse il primo programma della storia, appunto per questa macchina: si tratta di una serie di istruzioni, scritte su schede perforate, per calcolare i numeri della serie di Bernoulli.
Per molti anni le istruzioni vennero scritte su schede perforate. Un esempio famoso ne è l'Eniac, anche per un preciso fatto: un giorno un insetto (in inglese bug) si infilò in una scheda perforata danneggiando gravemente la macchina, è per questo che oggi quando c'è un problema o un errore in un programma informatico si parla di bug.

Agli inizi dello scorso secolo Alan Turing descrisse una macchina (Macchina di Turing) che non faceva

Versione della macchina analitica realizzata coi Lego

solo determinate operazioni, ma tante quante ne erano descritte nei vari programmi: la macchina leggeva una serie di uni e di zeri che descrivevano i processi da fare.
Questo permetteva di sviluppare algoritmi per ogni tipo di problema, a patto di dover semplificare ogni problema in problemi più piccoli (ricorsione).
Durante la seconda guerra mondiale Turing fece parte del dipartimento di comunicazione inglese per decriptare i messaggi in codice tedeschi, i quali erano codificati dalla macchina Enigma: un insieme di servomotori che facevano variare continuamente il codice.
Turing inoltre inventò un test per verificare quando l'intelligenza artificiale sarebbe stata pari a quella umana: una persona pone una domanda e riceve una risposta da una persona reale e una dalla macchina, quando non saprà distinguerle allora l'intelligenza artificiale avrà raggiunto alti livelli.

Doodle dedicato dalla Google ad Alan Turing

È grazie a queste e a molte altre persone che oggi abbiamo tutte quelle tecnologie basate sui calcoli automatici (computer,cellulari, ma anche orologi,riscaldamento,domotica,...) e se vediamo i progressi fatti in due secoli e i progressi fatti negli ultimi dieci anni possiamo notare come ci sia una sempre più crescente evoluzione di queste tecnologie; e non solo non possiamo immaginare cosa ci sarà fra un secolo: non possiamo immaginare cosa ci sarà fra un anno!

Alla ricerca del prodotto giusto...

2014-05-21T17:47:00.000+02:00

Le caratteristiche di un pc.

Anni fa era bello andare nei reparti informatici dei negozi perché si potevano osservare tutte le novità
del momento, alcune volte anche provarle, ma sopratutto avere una visione d' insieme di come si evolveva il mondo informatico.
Merito di tutto ciò erano le etichette curate che riportavano tutti i dettagli tecnici dei prodotti.

Dopo molti anni sono tornato in vari negozi nei reparti informatici e ho notato che purtroppo la storia è cambiata: la maggior parte dei prodotti in esposizione sono scatole, a volte trovi un' etichetta con scritta a volte la ram (la marca non il valore) o il processore e al posto dei dettagli tecnici trovi cartelli con scritto: "leggero, veloce, ergonomico, bello,..."
Purtroppo ho constatato questo anche nei siti dei produttori: solo pochi siti mantengono ancora le caratteristiche, e sono solitamente in una scheda secondaria, dopo foto e "leggero, veloce, ergonomico, bello,..."

Ora sul sito del produttore non scrivono più le caratteristiche, ma
solo le "impressioni d'uso".

I tempi sono cambiati e i computer non sono più una nicchia ma sono diventati il principale prodotto, quindi il commercio punta all' illusione e al far parere bello: chi va a comprare un computer se gli dici che ha 4 core da 2 GHz e 16GiB di ram? nessuno ma se gli dici ultrabook con superprocessore e durata eccezionale della batteria lo comprano al volo!
Anche gli schermi: perché farli lucidi? Essendo lucidi riflettono tutta la luce e diminuiscono la visibilità, mentre se fossero opachi sarebbe molto meglio; ma chi va a comprare un monitor opaco? I monitor lucidi quando sono spenti hanno un' estetica migliore e creano più guadagni.

I produttori stanno appunto attuando una strategia di commercio per vendere tutto a tutti, mettendo così in difficoltà chi sa cosa cercare, perché ormai non ti vendono il computer ma le parole.

Doppia icona Chrome in Luncher o Docky?

2014-05-14T18:21:00.001+02:00

inizio
2 icone

Chrome (ma questo vale anche per altri programmi come LibreOffice) a volte si apre in un'icona diversa da quella bloccata nella dock, questo perchè il suo collegamento non punta la programma ma ad un altro collegamento.
Per risolvere questo problema non ci vuole molto:

risultato

Apri un terminale e digita
xprop | grep WM_CLASS | awk '{print $4}'
e cliccando su una finestra di Chrome otterrai qualcosa tipo: Google-chrome-stable
Nel terminale digita
sudo nautilus /usr/share/applications/ (se usi un filemanager diverso da nautilus va bene comunque)
apri google-chrome.desktop con un editor di testo come gedit e aggiungi la segunete riga:
StartupWMClass=Google-chrome-stable
Riavvia Docky o Unity

Synapse, un'alternativa alla Dash

2014-05-14T17:45:00.002+02:00

Interfaccia di Synapse

Con le ultime versioni di Ubuntu il menù applicazioni è stato sostituito dall' innovativa dash.
La dash permette di cercare app, file, musica, video,.. semplicemente scrivendo alcune lettere del nome.
Il problema più grande è che occupa molta memoria ed è poco efficiente.

Più risulatiti

Synapse è un tool che occupa poca memoria e può sostituire la dash con la differenza di essere molto più veloce grazie all' indicizzazione dei file; Synapse è adatto a tutti i computer: dai nuovi modelli a quelli più vecchi e con qualsiasi distribuzione Linux e con qualsiasi DE.

Apri con...

Per avviarlo basta premere Ctrl+Space (ispirato al Cmd+Space di Spotligth), scorciatoia che potete cambiare, e digitare alcune lettere di ciò che cercate (anche saltandone alcune), poi premete invio per aprire.

Ci sono estensioni come la calcolatrice

Se volete più risultati premete la freccia giù e se cercate specificatamente un programma, un documento, un'immagine,... scorrete le sezioni con le frecce sx/dx.
Con Tab scorrendo con la fraccia giù potete cambiare il programma con cui aprire i file.

INSTALLAZIONE

sudo add-apt-repository ppa:synapse-core/ppa
sudo apt-get update -y
sudo apt-get install synapse -y

Ancora Windows?

2014-05-13T16:27:00.003+02:00

Esistono svariati sistemi operativi, fra cui ricordiamo Windows, le miriadi di release di Linux e OSX; eppure quando ci guardiamo attorno siamo circondati da computer Windows, quindi pensiamo che Windows sia il migliore, ma invece...

Un altro fatto importante è la fine di supporto di Windows XP: in realtà si potrà continuare a usare Windows XP senza problemi, con solo due differenze:
- Non riceverete più aggiornamenti dalla Microsoft (Alleleja!)
- La Microsoft non vi darà più supporto gratuito (Prima lo faceva?)
Invece quasi tutti hanno capito che dovevano cambiare compueter (proprio quello che la Microsoft voleva), ma a discapito di questa le vendite di Windows non sono salite di molto: alcuni hanno scelto Mac (con i relativi costi da supportare), mentre altri hanno optato per Linux.

Linux? Chi è sto sconosciuto?
Ebbene si in pochi conoscono Linux ed è un peccato, scopriremo ora perchè conviene passare a Linux che comprare un nuovo Windows.

REQUISITI MINIMI
Windows 8.1 Linux Ubuntu
20 GiB HDD 10 GiB HDD
2 GiB Ram 512 MiB Ram (= 0,5 GiB)
1 P Processore 0,7 P Processore [P = GHz * core]
Scheda grafica DirectX 9 Scheda grafica generica

Come si può notare Linux generalmente richiede meno risorse di Windows (esistono alcune versioni come Xubuntu o Lubuntu che addirittura richiedono meno prestazioni che Ubuntu !!!).
Con questo si può riutilizzare un vecchio computer o comprarne uno poco potente abattendo notevolmente i costi.
PREZZI
Beh Windows ha calato i prezzi con l' avvento di Windows 8, mentre Linux è rimasto sempre costante nei prezzi:
(prezzi medi in data di uscita)
Windows 7 300€ Ubuntu 9.10 gratis
Windows 8.1 100€ Ubuntu 13,10 gratis
SICUREZZA
Con Win chiunque sa prendere Virus: basta non avere l' antivirus o un antivirus impreparato ( e con la velocità con cui creano nuovi virus un antivirus risulta impreparato 15 minuti prima che esca l' aggiornamento).
Con Linux solo uno stupido sa installare i virus: bisogna scaricare i file, dargli il permesso di esecuzione, fare doppio click e digitare la password di amministratore.

Richiesta di password Linux

Questo in quanto Linux è un sistema a guscio: ogni livello è protetto, mentre Windows non è a guscio: dopo il primo accesso (quando accendete il computer) lascia la porta aperta, questo è comodo per chi non vuole mettere la password per ogni cosa ma è molto insicuro.
Appunto per questo si sono scoraggiati gli sviluppatori e i virus per Linux sono pochissimi.
INSTALLAZIONE
Se avete un computer vuoto i tempi di installazione sono molto diversi, riportiamo qui le medie:
Windows 50 minuti Linux 20 minuti
Guida passo passo
DRIVER
Windows per funzionare a bisogno di tutti i driver, solo con Windows 8 vengono inclusi alcuni driver fondamentali; questo comporta una perdita di tempo, un ingombro di memoria fisica (RAM) e di storage (HDD).
In Linux invece vi è incluso il 99% dei driver e appena lo installate lo potete subito usare.
TEMPI DI AVVIO E SPEGNIMENTO
Se siete utenti Windows di certo odierete gli avvii del sistema, ma con Linux i tempi si riducono

di quasi il 50%, inoltre quando compare lo sfondo Linux può essere usato, mentre su Win compare la clessidra e devi aspettare che carichi i componenti di sistema.
Da Windows 8 i tempi di avvio somigliano diminuiti, in realtà Win 8 e 8.1 non si spengono: chiudono tutti i programmi e si ibernano (attenzione però recuperare i dati da un HDD ibernato può causare perdite di dati).
DEFRAMMENTAZIONE
Un buon utente Win deframmenta regolarmente i suoi dischi, un buon utente Linux non sa cosa vuol dire deframmentare: scordatevi i pomeriggi lunghi ad attendere che il computer termini questo processo perchè Linux usa flesystem molto più avanzati di FAT e NTFS (unici di Win).
AGGIORNAMENTI
Su Windows bisogna aggiornare tutti i programmi manualmente e separatamente aggiornare il sistema operativo, quest' ultima procedura si compone di tre parti: attendi l' installazione degli aggiornamenti, attendi uno spegnimento molto più lungo del solito, attendi un tempo

Aggiornamento in un click

di avvio molto più lungo del solito.
Su Linux compare una finestrella, con un (1) click su aggiorna e in 5 minuti (mentre fai altro) aggiorna sistema operativo e tutti i programmi e non occorre attendere altro tempo.
SOFTWARE
Su Windows il buon software è a pagamento e spesso a caro prezzo, mentre

Microsoft Office su Linux

su Linux torvate il 99% dei programmi gratuiti che si trovano anche su Win e una miriade di programmi (tutti gratuiti) che sono allo stesso livello (a volte anche superiori) ai rispettivi a pagamento per Win.
Se siete affezionati ai software Win potete usare Wine: un programma che permette l' avvio di una buona parte degli applicativi Win su Linux.
Inoltre potete trovare tutto il software Linux su Ubuntu Software Center (simile a Windows Store di Win 8 ma uscito molti anni prima)
PERSONALIZZAZIONE
Su Windows ci sono alcune impostazioni personali e alcune personalizzazioni, su Linux puoi scegliere tutto al 100%: non solo nome e colori ma anche tantissime altre cose!!!

Alcuni DE di Linux
ASSISTENZA
Hai problemi con Win? Sul sito Microsoft non trovi nulla e devi pagare un tecnico, con Linux hai miriadi di forum (il più popolare è Ubuntu Forum) con utenti che gratuitamente danno supporto 24h su 24 e 365 giorni l' anno (io ho postato un problema la mattina di Natale e in meno di 15 minuti ho ricevuto già 3 risoluzioni)
RETI
Windows in rete comunica solo con Windows ( o Linux che gli danno il permesso) e a volte fa fatica anche così. Con Linux potete comunicare con tutti i sistemi informatici (non solo computer, ma anche consolle,...).
Le aziende possono usando Linux Server gestire tutti i computer della ditta indipendentemente che essi abbiano Linux, Win o Mac, mentre con Win Server puoi gestire solo i pc con Win.
MOBILE
Un argomento importante sono i sistemi operativi per Smartphone: Windows Phone vs Linux.

Linux su tutti i dispositivi

Windows Phone è uno dei sistemi mobile meno conosciuti, con un numero limitato di app (solitamente copioni di app Android e iOS) che punta all' estetica più che al software.
Dal lato Linux abbiamo Android, che si contende il podio con iOS, il cui unico punto debole è la sicurezza (Google ha scelto di abbandonare molti punti del guscio Linux a favore di un' interfaccia più semplice) e Ubuntu Phone: permette l' esecuzione delle app desktop per Linux con un interfaccia riscritta per i Touch.

Beh che dire Linux è risparmio e sicurezza, provare per credere.

Se volete potete provare Linux senza installarlo: usate il Live CD.

Compilare eseguibili Windows su Linux

2014-04-10T16:49:00.004+02:00

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

2014-04-10T14:23:00.001+02:00

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.

Indice di un processore in Pantal

2014-04-09T15:31:00.000+02:00

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

[C++] Eserciti Galattici

2014-04-01T18:16:00.000+02:00

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

2014-04-01T18:13:00.000+02:00

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

2014-04-01T18:11:00.001+02:00

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

2014-04-01T18:09:00.001+02:00

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

2014-04-01T18:03:00.000+02:00

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

2014-04-01T17:58:00.000+02:00

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

2014-04-01T17:48:00.000+02:00

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

2014-04-01T17:42:00.000+02:00

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

2014-04-01T17:37:00.001+02:00

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

2014-04-01T17:31:00.000+02:00

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

2014-04-01T16:46:00.001+02:00

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

[C++] Problemi

2014-03-31T18:22:00.003+02:00

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