sto cercando di risolvere questo problema implementando una sottospecie di binary search per trovare il valore giusto col quale distanziare gli atterraggi degli aerei ma apparte i primi 2 test tutti gli altri testcase mi danno Excecution Timed Out, ho sbagliato qualcosa?
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("input.txt");
ofstream fout ("output.txt");
void pianifica(int R, int A[], int B[], int T[])
{
int massimoTeorico= (B[R-1]-A[0]+1)/R;
int l=1;
int r=massimoTeorico;
int distanziamento;
distanziamento=(l+r)/2;
if((l+r)%2!=0)
{
distanziamento++;
}
bool impossibile=false;
T[0]=A[0];
int soluzione[R];
while(true)
{
for(int i=1; i<R; i++)
{
//se l'aereo finirebbe prima di quando puo atterrare
if(T[i-1]+distanziamento<A[i])
{
//lo posizioniamo prima possibile
T[i]=A[i];
}
else
//se finirebbe dopo
if(T[i-1]+distanziamento>B[i])
{
//è impossibile
impossibile=true;
break;
}
else
{
//se va bene
T[i]=T[i-1]+distanziamento;
}
}
//se il distanziamento era troppo grande
if(impossibile)
{
r=distanziamento;
}
else
{
//se era troppo piccolo
l=distanziamento;
for(int x=0; x<R; x++)
{
soluzione[x]=T[x];
}
}
distanziamento=(l+r)/2;
//arrotondo per eccesso
if((l+r)%2!=0)
{
distanziamento++;
}
impossibile=false;
if(l==r)
{
break;
}
}
for(int i=0; i<R; i++)
{
fout<<soluzione[i]<<endl;
}
}
int main()
{
int R;
fin>>R;
int A[R],B[R],T[R];
for(int i=0; i<R; i++)
{
fin>>A[i]>>B[i];
}
pianifica(R,A,B,T);
}
Per risolvere il task devi implementare una binary search standard per trovare il minimo distanziamento e il tuo codice questo giĂ fa ma va appunto in TLE non essendo la tua bs sufficientemente veloce.
Una volta trovato il minimo distanziamento si calcolano i tempi Ti della soluzione.
Ho modificato un po’ il codice in modo che calcoli dopo quanto i Ti ma ancora non riesco a capire perchè la mia binary search non ha la complessità richiesta, cosa non sto capendo?
scusa per la mia ignoranza.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("input.txt");
ofstream fout ("output.txt");
void pianifica(int R, int A[], int B[], int T[])
{
int massimoTeorico= (B[R-1]-A[0])/R;
if((B[R-1]-A[0])%R!=0)
{
massimoTeorico++;
}
int l=1;
int r=massimoTeorico;
int distanziamento;
int K=1;
T[0]=A[0];
distanziamento=(l+r)/2;
if((l+r)%2!=0)
{
distanziamento++;
}
bool impossibile=false;
T[0]=A[0];
while(true)
{
for(int i=1; i<R; i++)
{
if(i*distanziamento+A[0]>B[i])
{
impossibile=true;
break;
}
}
//se il distanziamento era troppo grande
if(impossibile)
{
r=distanziamento;
}
else
{
//se era troppo piccolo
l=distanziamento;
if (distanziamento>K)
{
K=distanziamento;
}
}
distanziamento=(l+r)/2;
//arrotondo per eccesso
if((l+r)%2!=0)
{
distanziamento++;
}
impossibile=false;
if(l==r)
{
break;
}
}
fout<<T[0]<<endl;
for(int i=1; i<R; i++)
{
//se l'aereo finirebbe prima di quando puo atterrare
if(T[i-1]+K<A[i])
{
//lo posizioniamo prima possibile
T[i]=A[i];
}
else
{
T[i]=T[i-1]+K;
}
fout<<T[i]<<endl;
}
}
int main()
{
int R;
fin>>R;
int A[R],B[R],T[R];
for(int i=0; i<R; i++)
{
fin>>A[i]>>B[i];
}
pianifica(R,A,B,T);
}
Il codice che funziona correttamente è quello pubblicato per primo.
Per una binary search corretta puoi seguire questo link e applicarla senz’alcuna modifica al tuo programma.
Ed infine come hai fatto con il secondo programma calcolare i tempi Ti di atterraggio.
ora raggiungo 22/100 rispetto ai 5/100 di prima ma non capisco dove sbaglio nell’implementazione, ho provato a farla uguale al link ma dopo non mi calcola l’ultma K visto che per esempio nel secondo caso di Test partiamo con l=1 e r=2, quindi col while del link (while(l<r-1)) non entriamo nemmeno nel ciclo e non calcolerà mai la K.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("input.txt");
ofstream fout ("output.txt");
void pianifica(int R, int A[], int B[], int T[])
{
int massimoTeorico= (B[R-1]-A[0]+1)/R;
if((B[R-1]-A[0]+1)%R!=0){massimoTeorico++;}
int l=1;
int r=massimoTeorico;
int distanziamento;
distanziamento=(l+r)/2;
bool impossibile=false;
T[0]=A[0];
int K=1;
while(l<=r)
{
for(int i=1; i<R; i++)
{
//se l'aereo finirebbe prima di quando puo atterrare
if(T[i-1]+distanziamento<A[i])
{
//lo posizioniamo prima possibile
T[i]=A[i];
}
else
//se finirebbe dopo
if(T[i-1]+distanziamento>B[i])
{
//è impossibile
impossibile=true;
cout<<"imp"<<endl;
break;
}
else
{
//se va bene
T[i]=T[i-1]+distanziamento;
}
}
cout<<"r= "<<r<<" l= "<<l<<endl;
//se il distanziamento era troppo grande
if(impossibile)
{
r=distanziamento-1;
}
else
{
//se era troppo piccolo
l=distanziamento+1;
if(distanziamento>K){K=distanziamento;}
}
distanziamento=(l+r)/2;
impossibile=false;
}
if(distanziamento>K){K=distanziamento;}
fout<<T[0]<<endl;
for(int i=1; i<R; i++)
{
if(T[i-1]+K<A[i])
{
//lo posizioniamo prima possibile
T[i]=A[i];
}
else
{
T[i]=T[i-1]+K;
}
fout<<T[i]<<endl;
}
}
int main()
{
int R;
fin>>R;
int A[R],B[R],T[R];
for(int i=0; i<R; i++)
{
fin>>A[i]>>B[i];
}
pianifica(R,A,B,T);
}
Hai ragione sul fatto che la bs non entra nel ciclo while() {} con l=1 e r=2;
Ma nella bs suggerita hai trascurato un fattore importante, quello riguardante gli estremi dell’intervallo che sono [l,r), ossia che si tratta di un intervallo aperto a destra: pertanto il tuo distanziamento K viene considerato tra 1 <= K < 2 per come viene scelto il massimo teorico r. Pertanto per rientrare nell’intervallo voluto [l,r] si deve aggiungere 1 al massimo teorico senza nessuna condizione.
Lo ho modificato come hai detto tu e i risultati vanno ma resta comunque 22/100 per excecution timed out.
scusa se ti sto facendo perdere tempo su questo problema molto semplice ma davvero non sto capendo.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("input.txt");
ofstream fout ("output.txt");
void pianifica(int R, int A[], int B[], int T[])
{
int massimoTeorico= (B[R-1]-A[0]+1)/R;
int l=1;
int r=massimoTeorico+1;
int distanziamento;
distanziamento=(l+r)/2;
bool impossibile=false;
T[0]=A[0];
int K=1;
while(l<r-1)
{
for(int i=1; i<R; i++)
{
//se l'aereo finirebbe prima di quando puo atterrare
if(T[i-1]+distanziamento<A[i])
{
//lo posizioniamo prima possibile
T[i]=A[i];
}
else
//se finirebbe dopo
if(T[i-1]+distanziamento>B[i])
{
//è impossibile
impossibile=true;
cout<<"imp"<<endl;
break;
}
else
{
//se va bene
T[i]=T[i-1]+distanziamento;
}
}
cout<<"r= "<<r<<" l= "<<l<<endl;
//se il distanziamento era troppo grande
if(impossibile)
{
r=distanziamento;
}
else
{
//se era troppo piccolo
l=distanziamento;
if(distanziamento>K){K=distanziamento;}
}
distanziamento=(l+r)/2;
impossibile=false;
}
if(distanziamento>K){K=distanziamento;}
fout<<T[0]<<endl;
for(int i=1; i<R; i++)
{
if(T[i-1]+K<A[i])
{
//lo posizioniamo prima possibile
T[i]=A[i];
}
else
{
T[i]=T[i-1]+K;
}
fout<<T[i]<<endl;
}
}
int main()
{
int R;
fin>>R;
int A[R],B[R],T[R];
for(int i=0; i<R; i++)
{
fin>>A[i]>>B[i];
}
pianifica(R,A,B,T);
}