Selezioni Regionali 101 2004

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:
	A	B

D	   c

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 e { 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:
k= 1	k=2	k=3
		  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 cosi 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 gAglia 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 unì.

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:

I) 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 !

File input.txt
8
389
207
155
300
299
170
158
65

File output.txt
6

3

Esempio 2

File input.txt
3
22
23
27

File output.txt
1

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 outpitt.txt
6

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
1.	Non ci sono due o più fiori esattamente nello stesso punto;
2.	la distanza è calcolata usando la formula euclidea;
3.	il numero di piante da eliminare, indicato nel file di ingresso, è sempre minore o uguale al numero di piante contenute nello stesso file;
4.	il file di ingresso contiene almeno due piante;
5.	l'aiuola ha dimensioni  1000 x 1000 cm.

Esempio di input e output

File input.txt
2
30 20
50 80
10 60
40 60
10 100

File output.txt
40 60
50 80
5