Foto Stellare (coefficiente di difficoltà D=4)
Il problema
Il dottor Hubb è un appassionato di astronomia. Possiede una
carta astronomica planare, composta dai due assi del piano
cartesiano aventi l'origine in posizione (0,0). La carta è suddivisa
in quattro quadranti delimitati dagli assi cartesiani, dove a
ciascun quadrante viene assegnata una lettera distinta come mostrato
in figura:
Le stelle nella carta
planare sono rappresentate mediante coordinate intere e un valore di
intensità. Precisamente, ciascuna stella è rappresentata da una
tripla x, y, k, per individuare le
coordinate (x, y) del centro della stella e
la sua intensità espressa mediante un intero k Î
{1,2,3}.
Al dottor Hubb piace
molto scattare delle foto digitali al cielo stellato. Ciascuna foto
digitale è composta da zeri e da uni. Lo sfondo del cielo è
rappresentato dagli zeri, mentre una stella x, y, k è rappresentata dagli uni
in accordo al valore di k: 1
1 111
1 111 11111
1 111
1
In tal caso, la
coordinata (x, y) si riferisce all'uno in
posizione centrale. Le stelle possono parzialmente sovrapporsi nelle
foto ma le loro coordinate sono sicuramente distinte come coppie di
valori.
Purtroppo il dottor
Hubb è un pasticcione. La sua carta astronomica contiene N stelle, e lui ha scattato
una foto digitale di taglia M x M, ma non ricorda in quali
quadranti. Per
l'elevata tecnologia adottata, non ci sono distorsioni ottiche:
basta sovrapporre la foto digitale alla carta planare in una
posizione opportuna, per farle combaciare e poter così ricostruire
il quadrante (o i quadranti) di appartenenza. Le risposte
ammissibili sono A, B, C, D, AD, AB, BC, CD, ABCD, mentre AC, BD,
ABC, ecc., non sono considerate valide.
Suggerimento: Quadrettare a
griglia il piano cartesiano con le coordinate intere, assegnando le
coordinate (x, y) al quadratino avente (x, y) come coordinata dello
spigolo inferiore sinistro.
Dati
in input
Il
file di input contiene una sequenza di righe. La prima riga contiene
il valore di N e M. Le N righe successive
rappresentano le N stelle
nella carta astronomica, ciascuna riga contenente una tripla x, y, k, interpretata in accordo a
quanto descritto sopra. Le M righe finali rappresentano
la foto digitale, ogni riga contenente una sequenza di M valori scelti tra zeri e
uni.
Dati
in output
Il
file di output contiene una sola delle risposte
ammissibili, A, B, C, D, AD, AB, BC, CD, ABCD, in base alla
posizione della foto digitale rispetto ai quadranti della carta
astronomica.
Assunzioni
I numeri sono rappresentati
con il segno. Le coordinate (x, y) sono coppie di numeri,
dove -1000 < x, y < 1000. Per la
conformazione della carta stessa e della foto c'è esattamente una
risposta da fornire (non è possibile che la foto appaia due o più
volte in posizioni distinte). La foto non taglia le stelle: una
stella è interamente catturata dalla foto oppure non è catturata
affatto. Infine, se una stella ha centro nel quadrante A ma la sua
intensità è tale che induca un uno nel quadrante B, per esempio,
allora la stella viene considerata a cavallo dei due quadranti A e B
(non conta solo il centro, ma anche l’intensità).
Esempio
di input e output
File input.txt
9 7 -3 7 1 -2 6 1 -1 2
2 -2 1 1 1 7 1 1 3 3 2 3 2 2 -1 1 -3 -1
1 1000100 0100000 0000100 0001110 0011111 0111110 0110100
File
output.txt
AB
Motivazione
per la risposta: la foto è stata scattata a cavallo dei quadranti A
e B, e contiene le prime 7 stelle elencate nel file input.txt.
La dieta di Poldo
(coefficiente di difficoltà D=3)
Il
problema
Il dottore ordina a Poldo di
seguire una dieta. Ad ogni pasto non può mai mangiare un panino che
abbia un peso maggiore o uguale a quello appena mangiato. Quando
Poldo passeggia per la via del suo paese da ogni ristorante esce un
cameriere proponendo il menù del giorno. Ciascun menù è composto da
una serie di panini, che verranno serviti in un ordine ben definito,
e dal peso di ciascun panino. Poldo, per non violare la regola della
sua dieta, una volta scelto un menù, può decidere di mangiare o
rifiutare un panino; se lo rifiuta il cameriere gli servirà il
successivo e quello rifiutato non gli sarà più servito.
Si deve scrivere un programma
che permetta a Poldo, leggendo un menù, di capire qual è il numero
massimo di panini che può mangiare per quel menù senza violare la
regola della sua dieta.
Riassumendo, Poldo può
mangiare un panino se e solo se soddisfa una delle due condizioni:
1)
il panino è il primo che mangia in un determinato
pasto;
2)
il panino non ha un peso maggiore o uguale all’ultimo
panino che ha mangiato in un determinato pasto.
Dati
in input
La prima linea del
file input.txt contiene il numero m di panini proposti nel
menu. Le successive m
linee contengono un numero intero non negativo che rappresenta il
peso del panino che verrà servito. I panini verranno serviti
nell’ordine in cui compaiono
nell’input.
Dati
in output
Il file output.txt
contiene il massimo numero di panini che Poldo può mangiare
rispettando la dieta.
Assunzioni
I pesi di panini sono
espressi in grammi, un panino pesa al massimo 10 Kg.
Un menù contiene al
massimo 100 panini.
Esempi
di input e output
Esempio 1
File
input.txt
8 389 207 155 300 299 170 158 65
File
output.txt
Esempio 2
File input.txt
3 22 23 27
File output.txt
Esempio
3
File input.txt
22 15 14 15 389 201 405 204 130 12 50 13 26 190 305 25 409 3011 43 909 987 1002 900
File output.txt
Giardinaggio (coefficiente di
difficoltà D=2)
Il
problema
Pippo ha deciso di spendere il proprio tempo
libero facendo giardinaggio. Poiché il numero di fiori piantati
nelle sue aiuole gli pare eccessivo, decide di ridurne il numero
eliminando quelli tra loro più vicini. A tale scopo, essendo
appassionato di informatica, decide di scrivere un programma che gli
permetta di risolvere il problema.
Di ogni fiore viene
identificata la posizione e questa viene memorizzata in un file
indicando le coordinate, in centimetri, rispetto l'angolo in basso a
sinistra dell'aiuola; ogni posizione è contenuta in una riga diversa
del file e codificata con due numeri interi separati da uno spazio.
Oltre alle righe che contengono le posizioni dei fiori, il file
contiene anche, nella prima riga, il numero di fiori che deve essere
eliminato.
In sostanza il
programma deve cercare la coppia di fiori con distanza minima ed
eliminare, dei due, il fiore più in alto (cioè quello la cui
ordinata è maggiore); ripetere, quindi, l'operazione tante volte
quanti sono i fiori da eliminare. Nel caso in cui l'ordinata dei due
fiori fosse uguale, il fiore da eliminare è quello con ascissa
maggiore.
Dati
in input
I dati di ingresso sono contenuti nel file
input.txt che contiene:
- nella prima
riga, un numero intero che rappresenta il numero di fiori da
eliminare;
- dalla seconda riga al termine, coppie di numeri
interi separati da uno o più spazi bianchi, il primo rappresenta
l'ascissa ed il secondo l'ordinata della piantina
Dati
in output
Il risultato deve essere scritto nel file di
testo output.txt indicando le coordinate dei punti eliminati nello
stesso formato del file in ingresso (esclusa la prima riga). I punti
devono essere ordinati, in modo crescente, rispetto all'ascissa, e
nel caso in cui avessero la stessa ascissa, rispetto l'ordinata.
Assunzioni
- Non ci
sono due o più fiori esattamente nello stesso punto;
- la
distanza è calcolata usando la formula euclidea;
- il numero
di piante da eliminare, indicato nel file di ingresso, è sempre
minore o uguale al numero di piante contenute nello stesso file;
- il file
di ingresso contiene almeno due piante;
- l'aiuola
ha dimensioni 1000 x 1000 cm.
Esempio
di input e output
File input.txt
2
30
20
50
80
40
60
10
100
File output.txt
40
60
50 80
|