Premetto di non aver letto la discussione riguardante una probabile soluzione per questo problema perché vorrei riuscirci da solo, ma almeno ditemi se sono sulla giusta strada: forse una soluzione utile sarebbe quella di salvare con un array a indirizzamento diretto(correggetemi se mi sbaglio), tutti i vari giorni già usati per studiare argomenti da sapere per le verifiche precedenti.Facendo così, vado a controllare se quel giorno che mi serve l’ho già utilizzato(nell’array sarà uguale a 1) e quindi non incrementerò la var che mi tiene conto dei giorni minimi, o se non l’ho ancora utilizzato(nell’array sarà messo uguale a 0) allora incrementarò di uno la var e setterò l’array con indice chiave di quel giorno a 1. Questo è possibile farlo in O(n^2) perché si devono utilizzare due for annidati e la ricerca di un giorno nell’array avviene in O(1). L’unico dubbio che mi era venuto è per gli indici dell’array che dovrebbero essere numeri naturali(mi sembra) ma in realtà si considerano in questo problema anche giorni < 0. Questo forse potrei risolverlo inizializzando il vettore ad un valore doppio di MAX e considerando l’indice 0 il numero di giorno massimo minore dove potrei studiare.
Esistono “array a indirizzamento indiretto”?
Idea corretta, incluso l’accorgimento per i giorni negativi. Generalizzando, se hai un intervallo [-MAX, MAX] puoi sempre ricondurti all’intervallo [0, 2 \cdot MAX] e considerare ogni valore v come v + MAX.
Si,scusami non trovavo modo di esprimermi, sapevo che avevo detto cazzate ahah! Comunque perfetto, è così che sto facendo, grazie per aver letto.
Mi falliscono 2 output negli ultimi 2 subtasks (il codice è un po confusionario).
Ecco qui il codice
#include<iostream>
#include<fstream>
#define MAX 1000
using namespace std;
int main()
{
ifstream in("input.txt");
ofstream out("output.txt");
int N,T,K,esami[MAX],giorni[MAX+MAX],g = 0;
in>>N>>T>>K;
N+=1000;
for(int i = 1000; i<N;i++) in>>esami[i];
for(int i = 0;i<MAX*2;i++) giorni[i] = 0;
for(int i = esami[0]-K;i<esami[0];i++)
{
if(K>T){g = -1;break;}
if(giorni[i] == 0)
{
giorni[i] = 1;
g++;
}
}
if(g == -1)
out<<g;
else
{
for(int i = 1001;i<N;i++)
for(int j = esami[i]-T;j<esami[i];j++)
{
if(esami[i]-T>esami[i-1]-K)
{
if(giorni[j] == 0)
{
giorni[i] = 1;
g++;
}
}else if(esami[i]-T<=esami[i-1]-K)
break;
}
}
out<<g;
return 0;
}
Sei sicuro che questo codice sia all’ultima versione?
N+=1000;
for(int i = 1000; i<N;i++) in>>esami[i];
Stai accedendo alle posizioni [1000, 1000 + N) di un array le cui posizioni valide sono [0, 1000)
Pensi che l’errore sia solo qui oppure c’è qualche controllo sbagliato? Ho provato un algorotmo leggermente differente ma ancora non mi risolve 2 outputs
Non ho guardato il resto del codice perché già quella riga mi sembrava sospetta. Copia-incollando in locale il tuo codice sbaglia un po’ ovunque, come mi aspettavo.
Ho risolto.