Ois_streetlights

Ciao a tutti, stavo provando a risolvere (streetlights) delle OIS 2017, tuttavia ottengo solo 25 / 100 pt.
La mia idea, che ritengo corretta se non per qualche dettaglio che ho trascurato, è:
Salvo tutti i valori in un array di bool, successivamente prendo Q blocchi da M lampioni, se le luci accese sono minori di K allora: risultato finale += K - (numero di luci accese).
Nel caso in cui vi possa servire, qui c’è il mio codice: https://pastebin.com/5iJKkQfQ.
Grazie in anticipo :slight_smile:

Premetto che non posso testarlo ma ad occhio questo tc porrebbe risultarti sbagliato:

5 3 1
0 0 0 0 0
1 Mi Piace

Tieni questo caso di input che il tuo programma sbaglia:

10 6 3
0 0 0 0 0 0 0 0 0 0

Output corretto: 4
Output del tuo programma : 6
Devi considerare che una volta accesa una luce la devi considerare tale anche per il prossimo range.
La disposizione per il caso d’ esmpio fornito :
0 0 0 1 1 1 0 0 0 1
ps
Stavo già scrivendo il post quando frakkiobello ti ha rispoto ma non mi va di cancellarlo <.<

Lol. Già che ci sei riesci a provare se il mio tc ha senso? Altrimenti cancello.

1 Mi Piace

Si ha senso. L’ algoritmo di ElephanZ risponde 2 al posto di 1.

Ma se ho capito bene il modo in cui vanno presi i blocchi, non vedo il perchè io debba aggiornare il valore nell’array… Mi puoi spiegare cosa intendi in modo più preciso?

I blocchi vanno considerati un questo modo:
immagine
Immagina di avere una finestra scorrevole aperta e vuoi chiuderla, per farlo devi trascinarla per tutto il percorso fin quando non la chiudi.
Quando dico di aggiornare i valori dopo aver contato le luci da accendere è per non doverle ricontarle per il prossimo range.
Ora non ti resta che capire quali luci accendere in un range e come farlo nei migliori dei modi.

Okay ora ho capito il testo… ma devo trovare un modo per capire quali luci accendere… Per caso serve la DP ?

No, non serve. è greedy.

Come dice @zJack1342 é greedy, quindi se in un blocco lungo M ne devi accendere necessariamente x quali ti conviene accendere?

1 Mi Piace