# Problema "Verifiche"

**URL:** <https://forum.olinfo.it/t/problema-verifiche/4055>\
**Category:** Aiuto\
**Created:** [7 Ottobre 2016, 1:43pm UTC](https://forum.olinfo.it/t/problema-verifiche/4055 "2016-10-07T13:43:35Z")\
**Posts on this page:** 8\
**Page:** 2

<div class="post-metadata">

**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\
**Post date:** [23 Febbraio 2017, 8:50pm UTC](https://forum.olinfo.it/t/problema-verifiche/4055/21 "2017-02-23T20:50:12Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [24 Febbraio 2017, 6:01pm UTC](https://forum.olinfo.it/t/problema-verifiche/4055/22 "2017-02-24T18:01:39Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\
**Post date:** [24 Febbraio 2017, 6:04pm UTC](https://forum.olinfo.it/t/problema-verifiche/4055/23 "2017-02-24T18:04:01Z")

</div>

Si,scusami non trovavo modo di esprimermi, sapevo che avevo detto cazzate ahah! Comunque perfetto, è così che sto facendo, grazie per aver letto. 🙂

---

<div class="post-metadata">

**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\
**Post date:** [24 Febbraio 2017, 8:37pm UTC](https://forum.olinfo.it/t/problema-verifiche/4055/24 "2017-02-24T20:37:09Z")

</div>

Mi falliscono 2 output negli ultimi 2 subtasks (il codice è un po confusionario).  
Ecco qui il codice

```auto
#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;
}

```

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [25 Febbraio 2017, 9:00am UTC](https://forum.olinfo.it/t/problema-verifiche/4055/25 "2017-02-25T09:00:43Z")

</div>

Sei sicuro che questo codice sia all’ultima versione?

```auto
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) 🤔

---

<div class="post-metadata">

**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\
**Post date:** [25 Febbraio 2017, 9:11am UTC](https://forum.olinfo.it/t/problema-verifiche/4055/26 "2017-02-25T09:11:03Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![lucach](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lucach/32/539_2.png) [@lucach](https://forum.olinfo.it/u/lucach)\
**Post date:** [25 Febbraio 2017, 9:13am UTC](https://forum.olinfo.it/t/problema-verifiche/4055/27 "2017-02-25T09:13:40Z")

</div>

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.  
 ![](https://forum.olinfo.it/uploads/default/original/1X/f3758c82084050e39334c45181fb4e044556325b.png)

---

<div class="post-metadata">

**Author:** ![Gazzara](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/g/41988e/32.png) [@Gazzara](https://forum.olinfo.it/u/Gazzara)\
**Post date:** [25 Febbraio 2017, 12:23pm UTC](https://forum.olinfo.it/t/problema-verifiche/4055/28 "2017-02-25T12:23:43Z")

</div>

Ho risolto. 🙂

[Pagina precedente](https://forum.olinfo.it/t/problema-verifiche/4055.md?page=1)