Ventesima Gara di Informatica per studenti delle Scuole Superiori

Esercizi di gara

AVVISI:

•        Se non specificato altrimenti negli esercizi, le sequenze iniziali su nastro si intendono non vuote, ovvero contenenti almeno un simbolo.

•        Per numero decimale si intende un numero positivo o nullo rappresentato con le cifre 0, 1, 2, ..., 9, senza zeri iniziali non significativi; per esempio 0 e 19 sono numeri validi, mentre 0032 deve essere scritto come 32.

•        Nel fornire le soluzioni, ricordarsi di pulire il nastro finale da ogni simbolo che non costituisca la risposta!

NASTRO INIZIALE	NASTRO FINALE
EEEEE	5
EEEEEEEEEEEEEEEEEEEEEEE	23
	0
E	1

•        Ogni volta che si salva la soluzione di un esercizio con il simulatore della macchina di Turing, il “timestamp” dell’esercizio viene aggiornato con il tempo trascorso fino a quel momento.

Esercizio 1: In tempi di crisi. [Punti 1] La prima regola della buona amministrazione casalinga è: fai economia su ogni piccola spesa. Ogni euro risparmiato è un euro guadagnato. Se ieri spendevi k euro per qualcosa, cerca oggi di comprarlo per k-1. E per aiutare a fare questi conti, si scriva un programma per macchina di Turing che, ricevuto su nastro un intero maggiore di 0, rappresentante la spesa di ieri, lasci sul nastro l'intero k-1, che è quello che possiamo spendere oggi.

NASTRO INIZIALE	NASTRO FINALE
12	11
1	0
1240	1239

Esercizio 2: Il salvadanaio. [Punti 2] Mettiamo ogni euro risparmiato in un salvadanaio a colonna. Questi salvadanai consistono di un tubo (solitamente trasparente) disposto in verticale, in cui le monete si dispongono per gravità in una colonna ordinata la cui altezza indica direttamente il valore del contenuto. Nella nostra versione, rappresenteremo ogni moneta (da 1 euro) inserita nel salvadanaio con un simbolo E sul nastro. Si scriva un programma per macchina di Turing che, ricevuta sul nastro la rappresentazione di un salvadanaio (anche vuoto) come indicato sopra, lasci sul nastro al termine della computazione la rappresentazione del totale risparmiato, in euro, espressa come numero intero.

Esercizio 3: Risparmio. [Punti 4] Naturalmente, se si può risparmiare più di un euro, tanto meglio! Si scriva un programma per macchina di Turing che, ricevuto sul nastro un intero rappresentante la spesa di ieri k, seguito da uno spazio e dalla spesa di oggi h, con h e k strettamente positivi e h<k, lasci sul nastro il risparmio, ovvero k-h.

NASTRO INIZIALE	NASTRO FINALE
17 15	2
1020 950	70
2 1	1
10000 9000	1000

Esercizio 4: Centesimo per centesimo. [Punti 5] Sulle piccole spesucce, anche qualche centesimo può fare la differenza.

Rappresentiamo una quantità di denaro (in euro) nella consueta notazione con il punto a fungere separatore fra la parte in euro (espresso come numero decimale) e la parte in centesimi (espressa come numero decimale compreso fra 0 e 99, e rappresentato sempre con due cifre). Per esempio, l'ammontare di diciotto euro e cinque centesimi si denota con “18.05”. Si ripeta l'esercizio precedente, utilizzando questa volta la notazione in denaro per tutti i valori.

NASTRO INIZIALE	NASTRO FINALE
102.00 100.00	2.00
4.50 3.80	0.70
13.20 12.20	1.00
2000.00 1870.70	129.30

Esercizio 5: Il libro mastro [Punti 7] Ogni buon massaio o massaia tiene un libro di tutte le spese fatte nel corso della settimana. Nel nostro caso, il libro conterrà una sequenza di voci, ciascuna composta da una descrizione (sull'alfabeto A-Z più lo spazio), seguita da uno spazio, seguita ancora dall'importo espresso in denaro. Le singole voci sono a loro volta separate da uno spazio. Si scriva un programma per macchina di Turing che, ricevuto sul nastro un libro mastro come descritto sopra, lasci sul nastro il totale speso nella settimana, ovvero la somma di tutte le spese nel libro, anch'essa espressa in denaro.

NASTRO INIZIALE	NASTRO FINALE
AFFITTO 420.00 BENZINA 42.50 LIBRI 31.10	493.60
PRANZO 3.50 CENA 6.10 PRANZO 4.10 CENA 12.00 PRANZO 5.65 CENA 22.50	53.85
VIAGGIO A MADRID 1282.51	1282.51
CAMBIO GOMME 650.10 ASSICURAZIONE 365.72	1015.82

Esercizio 6: Calcolo degli interessi. [Punti 12] Risparmiando risparmiando, abbiamo messo su un piccolo capitale. È ora di farlo fruttare! Il rendimento di un investimento è di solito espresso come una percentuale, che va applicata all'importo investito. Si scriva un programma per macchina di Turing che, ricevuto un ammontare in denaro k, seguito dal simbolo “%” e da un rendimento r espresso come numero decimale (con k>0 e 0 ≤ r ≤ 9), lasci sul nastro il guadagno calcolato applicando all'investimento k il tasso di rendimento r. Il risultato sarà espresso a sua volta in denaro, e andrà approssimato al centesimo inferiore.

NASTRO INIZIALE	NASTRO FINALE
1200.00%4	48.00
1217.44%4	48.69
31.50%1	0.31
0.60%3	0.01
0.01%1	0.00
99.99%9	8.99
5729372.34%6	343762.34

Esercizio 7: Andamento di borsa. [Punti 16] Ogni giorno, i nostri investimenti in Borsa hanno un guadagno o una perdita, a seconda dell'andamento delle contrattazioni. Guadagni e perdite vengono generalmente riportate dalla stampa sotto forma di percentuali rispetto al valore del giorno precedente. Ovviamente, le percentuali non si elidono: se ho investito 100 euro in un titolo, e nel primo giorno del mio investimento il titolo guadagna il 10%

(guadagno di 10 euro, per un totale di 110), e nel secondo perde il 10% (perdita di 11 euro, pari al 10% di 110), avrò alla fine 99 euro, non i 100 originali. Assumiamo che le regole di Borsa blocchino le contrattazioni quando un titolo guadagna o perde più del 10%, e che (per semplicità) le percentuali di guadagno e perdita siano sempre intere. Si può dunque formulare il seguente problema: dato un importo iniziale investito in un titolo, e una sequenza di variazioni del valore titolo in Borsa, a quanto corrisponde il valore del titolo alla fine del periodo? Per scoprirlo, si scriva un programma per macchina di Turing che, ricevuto sul nastro il valore investito k≥0 (espresso come denaro), e una sequenza di variazioni percentuali espresse come +v o -v (con 0≤v<10, e lo 0 considerato sempre positivo), lasci sul nastro il valore finale dell'investimento (espresso come denaro). Nel calcolo, si approssimino ad ogni passo i risultati al centesimo inferiore.

 

NASTRO INIZIALE	NASTRO FINALE
1000.00+5­4+0+3+6	1100.53
1000.00+0	1000.00
12000.00+9+9	14257.20
333.33­7+7	331.68
333.33+7­7	331.69
100000.00+1+1+1+1+1+1	106152.01
100000.00+1+1+1+1+1+1­6	99782.88

Esercizio 8: I campioni di borsa [Punti 20] Ogni giorno, la Borsa pubblica i dati relativi al fixing, ovvero al momento in cui si chiudono ufficialmente le contrattazioni, si rileva il prezzo corrente di ogni azione nel listino (in base agli scambi effettuati), e si fornisce un prezzo di riferimento – da cui le contrattazioni partiranno il giorno successivo. Rappresentiamo il fixing come un elenco di nomi di azioni (rappresentate dal loro ticker, un'abbreviazione di 3 o 4 caratteri garantita unica per ogni azione quotata) seguita dalla percentuale di incremento (o decremento), espressa in percentuale (per semplicità, come numero intero con segno, con lo 0 assunto sempre positivo). Si scriva un programma per macchina di Turing che, ricevuto sul nastro di input un fixing come descritto sopra, lasci sul nastro i ticker delle migliori azioni, ovvero quelle che hanno avuto il maggiore guadagno percentuale, o almeno la minima perdita. Si noti che ci possono essere più azioni con uguali guadagni o perdite: in questo caso, occorre elencare i ticker di tutti i campioni nello stesso ordine con cui comparivano nel fixing ricevuto.

NASTRO INIZIALE	NASTRO FINALE
AAPL +6 IBM ­2 GOOG +1 MSFT ­3	AAPL
AAPL ­3 IBM ­2 GOOG ­2 MSFT ­3	IBM GOOG
NOKI ­14 SSN +0 PSX ­3 ORA +1	ORA
FIAT +12 VWA ­15 RNLT +4 HON +6 RACE +12	FIAT RACE
FCA +0 ADR ­2 MPXA +0 CDP ­1 UNIP +0	FCA MPXA UNIP

Esercizio 9: Trattare sul prezzo! [Punti 21] Non sempre il venditore sarà disponibile a trattare sul prezzo, ma a volte con una contrattazione dura si potrà spuntare uno sconto maggiore. La contrattazione si svolge così: il venditore chiede un prezzo iniziale k₀, che diventa il primo prezzo corrente k. Il compratore può rispondere con una delle seguenti mosse, ciascuna identificata da una lettera: D = offri k/10 (approssimato in basso); M = offri k-1; A = accetta. Ad ogni mossa il venditore può replicare con: R = chiedi 2k; P = chiedi k+1; Z = accetta. La traccia di una contrattazione è costituita da un numero intero (k₀) seguito da una serie di mosse, alternativamente da compratore e venditore, che termina quando entrambe le parti accettano il prezzo corrente. È garantito che nel corso della trattativa, sarà sempre vero che 0 < k ≤ k₀. Si scriva un programma per macchina di Turing che, ricevuta sul nastro di input la traccia di una contrattazione (terminata con l'accordo di entrambe le parti), lasci sul nastro alla fine della computazione il prezzo concordato per l'acquisto.

NASTRO INIZIALE	NASTRO FINALE
150DRARMZMZA	58
1200DADRARARMPAZ	96
33AZ	33
33MZMZMZDRARAZ	12
58DZA	5

Esercizio 10: Buone notizie. [Punti 30] Un vecchio adagio di Borsa dice: compra le azioni di cui la gente parla, vendi quelle di cui nessuno parla. Si supponga di avere in portafoglio un certo insieme di azioni, ciascuna identificata dal suo ticker. Si supponga inoltre che un'agenzia di notizie di Borsa ci fornisca i suoi lanci stampa, al cui interno compaiono i ticker delle azioni di cui si parla, con ciascun ticker prefissato dal simbolo “%”. Vogliamo implementare la seguente strategia: dato un portafoglio titoli e una sequenza di notize (sull'alfabeto: {A, …, Z, %, spazio, punto}, vogliamo: (1) vendere tutte le azioni che abbiamo in portafoglio che non compaiono affatto nelle notizie, e (2) acquistare azioni del titolo che compare più frequentemente nelle notizie, fra quelli che non abbiamo già in portafoglio (in caso di parità, si acquisteranno tutti i titoli in parità). Si scriva dunque un programma per macchina di Turing che, ricevuto sul nastro di ingresso un portafoglio titoli (codificato come una sequenza di ticker separati da spazio, eventualmente vuota), seguito dal simbolo “:” fra spazi, seguito da un elenco di notize come descritto sopra (eventualmente vuoto), lasci sul nastro al termine della computazione la raccomandazione secondo la strategia indicata, codificata come un elenco di ticker (quelli da vendere, nell'ordine in cui compaiono in portafoglio) separati da spazi, seguito dal simbolo “/” sempre fra spazi, e infine da un elenco di ticker (quelli da acquistare, nell'ordine in cui compaiono nelle notizie), anche questi separati da spazi.

NASTRO INIZIALE	NASTRO FINALE
IBM MSFT AAPL : OGGI %IBM CONFERMA ACQUISIZIONE %VZN IN CONTANTI. RIUSCITO IL COLLOCAMENTO IN BORSA DI %FBK. LASCIA IL CEO DI %MSFT. %MSFT AUMENTA VENDITE.	AAPL / VZN FBK
FIAT VZN : OGGI %IBM CONFERMA ACQUISIZIONE %VZN IN CONTANTI. RIUSCITO IL COLLOCAMENTO IN BORSA DI %FBK. LASCIA IL CEO DI %MSFT. %MSFT AUMENTA VENDITE.	FIAT / MSFT
IBM FBK MSFT : OGGI %IBM CONFERMA ACQUISIZIONE %VZN IN CONTANTI. RIUSCITO IL COLLOCAMENTO IN BORSA DI %FBK. LASCIA IL CEO DI %MSFT. %MSFT AUMENTA VENDITE.	/ VZN
: OGGI %IBM CONFERMA ACQUISIZIONE %VZN IN CONTANTI. RIUSCITO IL COLLOCAMENTO IN BORSA DI %FBK. LASCIA IL CEO DI %MSFT. %MSFT AUMENTA VENDITE.	/ MSFT
IBM VZN MSFT FBK ORA: OGGI %IBM CONFERMA ACQUISIZIONE %VZN IN CONTANTI. RIUSCITO IL COLLOCAMENTO IN BORSA DI %FBK. LASCIA IL CEO DI %MSFT. %MSFT AUMENTA VENDITE.	ORA /
IBM VZN MSFT FBK : OGGI %IBM CONFERMA ACQUISIZIONE %VZN IN CONTANTI. RIUSCITO IL COLLOCAMENTO IN BORSA DI %FBK. LASCIA IL CEO DI %MSFT. %MSFT AUMENTA VENDITE.	/
FIAT :	FIAT /
FIAT ATL IVEC : %FIAT FIRMA ACCORDO CON %GOOG PER SW PROSSIME AUTO. %AAPL INTERESSATA ACQUISIZIONE %FORD O %RNLT ENTRO TRE ANNI.	ATL IVEC / GOOG AAPL FORD RNLT
:	/