Aiuto per il problema "Anno luce"

Aiuto
1

Non lo so… il procedimento mi pare che funzioni ma non riesco a beccare neanche un punto…
Problema di riferimento: Anno luce

include fstream
include algorithm
include math.h

using namespace std;

int N, a, b, c, f;
int V[10000];

bool comp(int a, int b){
    return b>a;
}

ifstream fin("input.txt");
ofstream fout("output.txt");

int main()
{
	fin >> N;
	for(int l=0; l<N; l++) {
		fin >> a;
		fin >> b;
		fin >> c;
		V[l] = sqrt(pow(a,2)+pow(b,2)+pow(c,2));
	}
	fin >> c;
	sort(V, V+N, comp);
	for(int l=0; l<c; l++){
	    fin >> a;
	    f=0;
	    while (V[f] <= a){
	        f++;
	    }
	    fout << f << " ";
	}
	return 0;
}
2

Non ho visto ora cosa fa il tuo codice ma prova a sostituire i pow con una semplice moltiplicazione n*n.

3

Ci sono alcuni errori. Essendo alle prime armi, provo a guidarti nel riconoscerli e nel correggerli.

  • Quanto può essere grande al più N? Non importa se pensi che la tua soluzione sarà troppo lenta per N grandi, dimensiona comunque il vettore correttamente.
  • Evita di usare sqrt con parametri di tipo intero (se ne era già discusso qua; in generale prova sempre a cercare sul forum se qualcuno ha già risposto a un problema simile al tuo)
  • La radice quadrata di un numero intero è sempre un numero intero?
  • Cosa succede con il tuo programma se, data una query D, tutte le stelle sono raggiungibili in D anni?
  • Come deve essere stampato l’output del problema?
4

Ok, dovrei essere riuscito a mettere a posto i primi tre punti.
Riguardo al quarto (sono seriamente alle prime armi) non capisco… Non è corretto come ho scritto io?
Per il risultato va bene fout << f << endl;?

5

Ti riporto il frammento di codice coinvolto

    f=0;
    while (V[f] <= a){
        f++;
    }

Nelle tue intenzioni - e come è giusto che sia - questo ciclo termina quando una stella è a una distanza maggiore di quella percorribile. Ma se non ci fosse nessuna stella a una distanza maggiore? In quest’ultimo caso, quando termina il ciclo while?

Sì. Infatti ora rispetta la consegna (Q righe contenenti un intero ciascuna), mentre prima producevi una singola riga con Q interi separati da spazio.

6

Ho capito… Quindi legge le posizioni che dovrebbero essere vuote come zeri.
f=0; while (V[f] <= a && f<N){ f++; }
Andrebbe bene questo tipo di scrittura?
Ho però un’altro problema… Certe volte non mi da l’output esatto, altre l’esecuzione sfora il secondo…
Come potrei velocizzarlo o quale altra strada dovrei seguire? (Solo come consiglio)

7

Come hai risolto va bene, perché non va più out-of-bound (legge “zero” se sei fortunato, altrimenti potrebbe leggere un valore sporco oppure venire bloccato dal sistema operativo per un accesso illegale alla memoria).

Il problema “sfora il secondo” è completamente diverso. Quando hai un programma sempre funzionante puoi preoccuparti di come renderlo più veloce. Posso consigliarti di guardare queste slide utilizzate durante un mio incontro di preparazione alla selezione territoriale 2016. In tale incontro il tema era proprio la risoluzione efficiente di “Anno luce”; quello che ti serve è dalla pagina 23 in poi.