# Problema Torre di controllo

**URL:** <https://forum.olinfo.it/t/problema-torre-di-controllo/3983>\
**Category:** Aiuto\
**Created:** [10 Settembre 2016, 10:55am UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983 "2016-09-10T10:55:34Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [10 Settembre 2016, 10:55am UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/1 "2016-09-10T10:55:34Z")

</div>

Ciao,  
stavo provando a risolvere il problema Torre di Controllo ([https://cms.di.unipi.it/#/task/aeroporto/statement](https://cms.di.unipi.it/#/task/aeroporto/statement)), ma non riesco proprio a trovare una soluzione possibile… L’unica che mi viene in mente è una dinamica, ma con 100000 atterraggi e un tempo massimo di 1000000000 (minuti?) una quadratica non sembra assolutamente andare bene.  
Qualcuno che mi da’ una mano?

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [10 Settembre 2016, 7:07pm UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/2 "2016-09-10T19:07:13Z")

</div>

Provo con questo suggerimento 🙂  
 Supponi di conoscere già un tempo T: sei in grado di determinare, in complessità lineare nel numero di atterraggi, se è possibile effettuare tutti gli atterraggi aspettando **_almeno_** T minuti?  
In questo caso, cosa potresti fare per determinare qual è il valore accettabile di T più grande?

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [10 Settembre 2016, 10:39pm UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/3 "2016-09-10T22:39:42Z")

</div>

Comincio a seguirti… Il tempo massimo lo trovo facendo il massimo di tutti gli istanti finali degli intervalli. Poi da li potrei provare una ricerca binaria di qualche tipo. Domani provo a implementare qualcosa, grazie!

p.s.: tranquillo, chiederò ancora 😁

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [11 Settembre 2016, 4:56pm UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/4 "2016-09-11T16:56:25Z")

</div>

Riprendendo il discorso di prima, una volta ottenuto T massimo, ancora non riesco ad andare molto più avanti. Avevo pensato ad una ricerca binaria di qualche tipo, magari inizialmente da 0 a T, ogni volta che divido il problema dico che in ogni metà ci deve essere lo stesso numero di atterraggi (e se sono dispari?) e posso andare avanti così. Il problema è che non riesco a dimostrare che una cosa del genere funzioni.  
Un’altra idea era quella di dividere non a metà ma con lo stesso numero di intervalli da una parte e dall’altra… bocciata, per ogni divisione avrei una complessità lineare. Come complessità della soluzione verrebbe O(nlogn)

Non ci sto capendo molto 😖

Dario

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [11 Settembre 2016, 6:36pm UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/5 "2016-09-11T18:36:28Z")

</div>

Mmmmh no, forse non ci eravamo intesi bene 🙂  
La domanda del mio primo messaggio era questa: riesci a sapere se puoi completare tutti gli atterraggi distanziandoli almeno di un valore **K**? Se sì, con quale complessità?  
Non mi ero accorto che la lettera **T** fosse già usata all’interno del problema, errore mio 😇

Comunque cerca di ragionare su questa parte, poi potrai pensare a come cercare il valore più alto che puoi assegnare a **K**

---

<div class="post-metadata">

**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\
**Post date:** [11 Settembre 2016, 9:07pm UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/6 "2016-09-11T21:07:31Z")

</div>

Prima di tutto grazie per l’aiuto!  
Nonostante non abbia implementato la ricerca del K massino in tempo lineare come dicevi, ma con una sorta di ricerca binaria (parto da 1, raddoppio ogni volta finchè non è troppo grande, altra ricerca tra Kmax e Kmax / 2 per trovare K finale) sono riuscito ad ottenere 100/100.  
Grazie ancora, sei un grande

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [12 Settembre 2016, 12:43pm UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/7 "2016-09-12T12:43:44Z")

</div>

No no la ricerca di K andava fatta proprio tramite una ricerca binaria, lineare è il tempo necessario per testare se un determinato intervallo K può essere rispettato, comunque sono contento che tu abbia risolto 🙂

---

<div class="post-metadata">

**Author:** ![Nunzio](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/n/f17d59/32.png) [@Nunzio](https://forum.olinfo.it/u/Nunzio)\
**Post date:** [4 Luglio 2019, 9:39pm UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/8 "2019-07-04T21:39:05Z")

</div>

Approfitto di questa discussione sul tema “Torre di controllo” per condividere il mio problema: il sorgente allegato viene compilato correttamente, nel momento in cui lo sottopongo alla piattaforma (commentando ovviamente il main e lasciando solo la funzione) mi da “Compilazione fallita”. Grazie a chi potrà rispondermi.[aeroporto.zip](https://forum.olinfo.it/uploads/default/original/1X/77ee160750058880c1b8b27f22c29a02cd253de9.zip) (890 Byte)

---

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [5 Luglio 2019, 3:24pm UTC](https://forum.olinfo.it/t/problema-torre-di-controllo/3983/9 "2019-07-05T15:24:47Z")

</div>

Ho mandato il tuo codice rimuovendo il main con le annesse variabili e non ho nessun problema di compilazione. Dovresti trovare una soluzione più veloce, se hai bisogno di suggerimenti basta leggere i post precedenti.

```auto
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void pianifica(int R, int A[], int B[], int T[]) {
	
	int i,c,kmin,imin;
	bool trovato,fine=false;
	int *K = (int*)malloc(R * sizeof(int));
	
	T[0]=A[0];
	
	//inizializza array T e K
	for(i=1; i<R; i++) {		
		T[i]=B[i];
		K[i-1]=T[i]-T[i-1];	
	}
	
	//c=2; //primo e ultimo vincolati
	
	while(!fine) {
		//cerca minimo ki tal che abbia alla sua sinistra un ki-1 maggiore
		fine=true;
		for(i=1,kmin=1000000000,trovato=false; i<R-1; i++) {		
			if(K[i]<kmin && K[i-1]>K[i] && T[i]>=A[i]) {
				kmin=K[i];
				imin=i;
				trovato=true;
				fine=false;
			}
		}
		//se trovato...
		if(trovato) {		
			if(T[i]>=A[i]) {
				K[imin]++;
				K[imin-1]--; 
				T[imin]--;					
			} 				
		}	
	}
}

```