# Missioni segrete 20/100

**URL:** <https://forum.olinfo.it/t/missioni-segrete-20-100/5646>\
**Category:** Aiuto\
**Created:** [2 Aprile 2019, 8:48pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646 "2019-04-02T20:48:16Z")\
**Posts on this page:** 14\
**Page:** 1

<div class="post-metadata">

**Author:** ![Antonio\_Prisco](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/bb73d2/32.png) [@Antonio\_Prisco](https://forum.olinfo.it/u/Antonio_Prisco)\
**Post date:** [2 Aprile 2019, 8:48pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/1 "2019-04-02T20:48:16Z")

</div>

Ecco qui:  
Il codice prende come prima missione quella che ha somma fra durata e scadenza minima;  
Va avanti e prende la missione con la durata minima e per la quale la somma dei giorni fino ad ora è minore della scadenza;  
Se invece ci sono più durate uguali, prendo la missione con la scadenza minore;  
(Errore di battitura: nel programma riportato d è la scadenza e s la durata)

```auto
#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
const int MAX=100;
int d[MAX],s[MAX],v[MAX];
void solve(int n,int dim,int& cont,int somm);
int main()
{
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
   int n;
   cin>>n;

   for(int i=0;i<n;i++)
   {
   	cin>>s[i]>>d[i];
   }
   
   int min=INT_MAX,cont=0,dim=0,somm,ind;
   for(int i=0;i<n;i++)
   {
   	if(d[i]+s[i]<min)
   	{
   		min=d[i]+s[i];
   		ind=i;
   	}
   }
   v[0]=ind;
   dim++;
   cont++;
   somm=s[ind];
   solve(n,dim,cont,somm);
   cout<<cont;
}
void solve(int n,int dim,int& cont,int somm)
{
   bool contr,trov=false;
   int mind=INT_MAX,mins=INT_MAX,ind;
   for(int i=0;i<n;i++)
   {
   	contr=false;
   	for(int j=0;j<dim and contr==false;j++)
   	{
   		if(v[j]==i) contr=true;
   		else contr=false;
   	}
   	if(contr==false)
   	{
   		if(s[i]<mins and somm+s[i]<=d[i])
   		{
   			mins=s[i];
   			mind=d[i];
   			ind=i;
   			trov=true;
   		}
   		else if(s[i]==mins)
   		{
   			if(d[i]<mind)
   			{
   				mins=s[i];
   				mind=d[i];
   				ind=i;
   				trov=true;
   			}
   		}
   	}
   }
   if(trov==true)
   {
   v[dim]=ind;
   somm+=mins;
   dim++;
   cont++;
   solve(n,dim,cont,somm);}
}

```

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [3 Aprile 2019, 4:55am UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/2 "2019-04-03T04:55:39Z")

</div>

Da come l’hai descritto se l’ultima missione è la seconda più breve allora ne svolgi al più 2, ti ricordo che devi mantenere l’ordine cronologico con le missioni.

---

<div class="post-metadata">

**Author:** ![Antonio\_Prisco](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/bb73d2/32.png) [@Antonio\_Prisco](https://forum.olinfo.it/u/Antonio_Prisco)\
**Post date:** [3 Aprile 2019, 5:34am UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/3 "2019-04-03T05:34:29Z")

</div>

Ti sbagli. Se l’input d’esempio fosse  
3 5, 3 9, 4 8, 6 12,  
Il programma prende come prima missione 3 5 perché è quella con somma fra durata e scadenza minima, poi prende 3 9 perché è quella con durata più piccola fra le restanti e 3+3=6\<9, 4 8 non può prenderlo perché 3+3+4=10\>8 quindi prende 6 12.  
3 missioni

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [3 Aprile 2019, 2:55pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/4 "2019-04-03T14:55:17Z")

</div>

Quindi cerchi sempre quella che finirebbe prima tra le disponibili giusto?

---

<div class="post-metadata">

**Author:** ![Antonio\_Prisco](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/bb73d2/32.png) [@Antonio\_Prisco](https://forum.olinfo.it/u/Antonio_Prisco)\
**Post date:** [3 Aprile 2019, 2:56pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/5 "2019-04-03T14:56:36Z")

</div>

Giusto, così ho maggiori possibilità di rientrare nei limiti di scadenza

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [3 Aprile 2019, 3:15pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/6 "2019-04-03T15:15:40Z")

</div>

Non rischi di fare un prima una missione breve che potrai fare tra molto togliendoti la possibilità di fare una missione un po’ più lunga ma che puoi fare solo ora?

---

<div class="post-metadata">

**Author:** ![Antonio\_Prisco](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/bb73d2/32.png) [@Antonio\_Prisco](https://forum.olinfo.it/u/Antonio_Prisco)\
**Post date:** [3 Aprile 2019, 3:19pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/7 "2019-04-03T15:19:03Z")

</div>

Hai ragione…  
Alla luce di quanto detto proverò più tardi a modificare il codice. Tu hai già qualche idea in mente?

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [3 Aprile 2019, 4:17pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/8 "2019-04-03T16:17:22Z")

</div>

Onestamente non ricordavo la soluzione che avevo scritto in passato quindi l’ho risolto da 0.  
Quello che ho notato è che le assunzioni sono veramente piccole, quindi puoi analizzare le missioni in ordine di scadenza(in questo modo per ogni missione che aggiungi utilizzi i primi d giorni liberi che hai) e per ogni missione decidere di compierla o meno, ovviamente nel caso in cui la sua durata + i giorni già usati superano la scadenza non puoi compierla.

Scrivendola in Top-Down puoi memorizzare il miglior valore ottenuto avendo utilizzato già g giorni all’iesima missione, ottenendo quindi al più 100\*365 stati.

---

<div class="post-metadata">

**Author:** ![Antonio\_Prisco](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/bb73d2/32.png) [@Antonio\_Prisco](https://forum.olinfo.it/u/Antonio_Prisco)\
**Post date:** [3 Aprile 2019, 4:32pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/9 "2019-04-03T16:32:39Z")

</div>

Quindi potrebbe essere una soluzione valida prendere in ordine crescente le missioni in ordine di scadenza e considerarle se la somma dei giorni non supera la scadenza? Mi sembra troppo facile

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [3 Aprile 2019, 5:12pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/10 "2019-04-03T17:12:55Z")

</div>

Quello non funziona, quello che funziona è provare ogni possibile combinazione andando in ordine di scadenza.

---

<div class="post-metadata">

**Author:** ![Antonio\_Prisco](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/bb73d2/32.png) [@Antonio\_Prisco](https://forum.olinfo.it/u/Antonio_Prisco)\
**Post date:** [4 Aprile 2019, 4:11pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/11 "2019-04-04T16:11:31Z")

</div>

Ok, ho modificato il programma: 70/100

```auto

#include <iostream>
#include <fstream>
#include <limits.h>
using namespace std;
const int MAX=100;
int d[MAX],s[MAX],v[MAX],soluz[100*365];
int solve(int ind,int n,int dim,int passo,int ora,int max);
int main()
{
   freopen("input.txt","r",stdin);
   freopen("output.txt","w",stdout);
   int n;
   cin>>n;
   for(int i=0;i<n;i++)
   	cin>>d[i]>>s[i];
   
   int max=-INT_MAX,caso,dim=0,passo=1,ora=0,mass=-INT_MAX;
   //PER OGNI MISSIONE LA FUNZIONE SOLVE RITORNA IL MASSIMO NUMERO DI MISSIONI CONSECUTIVE: STAMPIAMO IL MASSIMO NUMERO DI CASI 
   for(int i=0;i<n;i++)
   {
   	caso=solve(i,n,dim,passo,ora,mass);
   	if(caso>max)
   		max=caso;
   	//cout<<endl<<endl<<max<<endl<<endl;
   }
   cout<<max;
}
int solve(int ind,int n,int dim,int passo,int ora,int max)
{
   bool contr;
   int presi=0,somm=0;
   for(int i=ind;presi<n;)
   {
   	//CONTROLLO CHE NON SIA GIA' STATA CONSIDERATA LA MISSIONE
   	contr=false;
   	for(int j=0;j<dim and contr==false;j++)
   		if(v[j]==i) contr=true;
   		
   	if(contr==false)
   	{
   		presi++;
   		if(d[i]+ora<=s[i]) 
   		{
   			v[dim]=i;
   			dim++;
   			somm++;
   			ora+=d[i];
   		
   		}
   	}
   	if(i==n-1) i=-1;
   	 
   	if(i==ind and contr==false)	i+=passo;
   	else i++;
   	
   	if(i>=n) i=i-n;

   }
   for(int i=0;i<dim;i++)
   	v[i]=-1;

   
   if(passo<n-1)
   {
   	//cout<<"somm: "<<somm<<", max: "<<max<<endl;
   	if(somm>max) max=somm;
   	//cout<<"somm2: "<<somm<<", max2: "<<max<<endl<<endl;
   	somm=solve(ind,n,dim,passo+1,0,max);
   }
   else if(passo==n-1) 
   {
   	//cout<<"somm: "<<somm<<", max: "<<max<<endl;
   	if(somm>max) max=somm;
   	//cout<<"somm2: "<<somm<<", max2: "<<max<<endl<<endl;
   }
   //cout<<max<<endl;
   return max;
}

```

Ora dovrebbe considerare tutti i percorsi.  
Il problema è che per alcuni input, come quello d’esempio, return max non ritorna effettivamente la somm massima

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [4 Aprile 2019, 4:54pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/12 "2019-04-04T16:54:48Z")

</div>

Ti da wrong answer oppure TLE?

Preciso che potresti snellire molto il codice, soprattutto la funzione ricorsiva può essere qualcosa come (è una specie di pseudocidc):

```auto
int f(int pos, int giorno){
    if(pos==n) return 0;
    int res=f(pos+1,giorno); // non faccio questa missione 
    if(sta nella scadenza)
        res=max(res+f(pos+1,giorno+scadenza);
    return res;
}

```

Aggiungendo la memoizzazione.

E basta richiamarla con f(0,0), gli altri stati verranno richiamati automaticamente

---

<div class="post-metadata">

**Author:** ![Antonio\_Prisco](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/bb73d2/32.png) [@Antonio\_Prisco](https://forum.olinfo.it/u/Antonio_Prisco)\
**Post date:** [4 Aprile 2019, 8:13pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/13 "2019-04-04T20:13:02Z")

</div>

Mi da Output isn’t correct… non capisco dove sbaglio 🤨

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [9 Aprile 2019, 5:10pm UTC](https://forum.olinfo.it/t/missioni-segrete-20-100/5646/14 "2019-04-09T17:10:28Z")

</div>

La mia idea per la prima parte è come quella proposta da @frakkiobello: andare in ordine di sequenza ed accettare tutte le missioni che non terminerebbero oltre la scadenza ma quando questo non è verificato, ovviamente non la posso aggiungere ma posso vedere se è possibile scambiarla con una già accettata ma di … il numero di impegni non aumenta ma in seguito avrò maggiori chance per accettarne altre.  
Può servire un maxheap (priority\_queue)