Vorrei chiedervi lo svolgimento dei quesiti 15.1 e 15.2 della gara scolastica di dicembre 2023.
Per il 15.1 ti puoi facilmente convincere che un approccio greedy funziona. Quindi, se puoi mettere un mattoncino lo metti. Per il 15.2 puoi provare a simulare il problema con d via via più grande, ne bastano pochi. Simulando su carta ci si impiega penso un paio di minuti
15.1 - h={1,2,7,3,6,4,5} d<=4
La risposta corretta risulta 7.
Però secondo me si può ottenere anche la sequenza di pile 14,14,14,15,18,16,15. Quindi la risposta sarebbe almeno per M=14.
15.2 - minimo valore di d per avere pile di almeno 11
La risposta corretta risulta 5.
sequenza di pile: 14 14 14 12 12 12 15
→ sarebbe d=3
Forse hai frainteso il testo. Non devi avere differenza tra gli elementi adiacenti al più d solo nella configurazione finale ma durante ciascun passaggio. Per passaggio intendo aggiungere una quantità h_i alla posizione corrispondente
1 Mi Piace
Leggendo così il testo puoi arrivare a [420k, 420k, 420k, 420k, 420k, 420k, 420k] per ogni k intero.
Dunque le risposte dovrebbero essere \infty e 0.
Non solo, queste sarebbero le risposte per ogni lista in input.
1 Mi Piace
Ti ringrazio del tuo suggerimento. Avevo frainteso il testo.
1 Mi Piace