[C++ o Pascal] L'essenza di un fiore raro

[CertainDeath]

Ragazzi mi serve urgente aiuto con questo programma da creare o in Pascal o in C++

L'essenza di un fiore raro è molto ricercata tra i profumieri. Il prezzo di mercato viene fissato giornalmente dal CGE, il Consorzio dei Grossisti di Essenze. Inoltre, essendo di natura organica, l'essenza acquistata da un profumiere deperisce dopo un certo periodo e quindi può essere rivenduta so
*soltanto entro K giorni dall'acquisto (data di scadenza).

*Un profumiere è venuto a conoscenza del prezzo di mercato dell'essenza che il CGE prevede per i prossimi N giorni (N ≥ K), per semplicità numerati da 1 a N. Ritenendo molto affidabili le previsioni del CGE, il profumiere intende comprare una certa quantità di essenza il giorno i per rivenderla il giorno j, tenendo presente però che non può andare oltre la data di scadenza (quindi deve essere i ≤ j
*(quindi deve essere i ≤ j ≤ i+K). Il profumiere intende fare un solo acquisto e una sola vendita successiva all'acquisto.

*Aiutate il profumiere a calcolare il massimo guadagno che può ottenere, calcolato come la differenza tra il prezzo dell'essenza al giorno j e quello al giorno i. Notate che è permesso scegliere j=i: in questo modo, anche se il prezzo di mercato dell'essenza fosse in discesa per tutto il periodo considerato, sarebbe possibile evitare perdite.


*Dati di input
Il file input.txt è composto da due righe.

La prima riga contiene due interi positivi separati da uno spazio, rispettivamente il numero K di giorni per la data di scadenza e il numero N di prossimi giorni.

La seconda riga contiene N interi positivi separati da uno spazio, i quali rappresentano il prezzo di vendita dell'essenza nei prossimi N giorni.


*Dati di output
Il file output.txt è composto da una sola riga contenente un intero che rappresenta il massimo guadagno del profumiere, con le regole descritte sopra.

Assunzioni
1 ≤ N ≤ 1000,
1 ≤ K ≤ N .

*Esempi di input/output

File input.txt File output.txt
2 6
3 6 2 6 9 6
7



Nota/e
Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in input.txt, non totalizza alcun punteggio in aggiunta a quello ottenuto per la sua compilazione

Qualcuno può darmi una mano?

[shinya]

[[OT]]
Non penso che questo post ti sarà d'aiuto, ho scritto la soluzione in factor, giusto come esercizio personale (sto cercando di imparare il linguaggio)...

USING: kernel sequences grouping math math.parser splitting 
prettyprint strings ascii ;

: collect-data ( seq -- max ) 
    dup first [ - ] curry map supremum ;

: flower-power ( seq k -- )
    <clumps> [ collect-data ] [ max ] map-reduce ;

: read-valid-days ( -- k )
    readln " " split1 drop string>number 1+ ;

: read-previsions ( -- seq )
    readln [ blank? not ] filter >array 
    [ 1string string>number ] map ;

: main ( -- )
    read-valid-days read-previsions swap flower-power . ;

Considerando che più della metà del programma serve solo a prendere in pasto l'input, non mi sembra malvagio. L'ho già detto che mi piace da matti factor?

Tornando in topic cmq... l'idea è quella di prendere tutte le sottosequenze che vanno da i a i+k, fare la differenza tra il primo valore e gli altri, e prendere il massimo. Poi prendere il massimo dei massimi delle varie sottosequenze.
Ma credo di essermi spiegato malissimo...

[Krat0s]

Dicono che fare come hai fatto tu corrisponde a barare

[shinya]

Originariamente inviato da Krat0s

Dicono che fare come hai fatto tu corrisponde a barare

Come ho fatto io? Come ho fatto che? Dove sarebbe la truffa?
Comunque, l'ho riscritto, magari ora è più leggibile (e c'era pure un bug nel prendermi in pasto le previsioni).

USING: kernel sequences grouping math math.parser splitting
prettyprint strings ascii ;

: get-valid-days ( -- k+1 )
    readln " " split1 drop string>number 1+ ;

: get-previsions ( -- seq )
    readln " " split [ string>number ] map ;

: best-group-sell ( seq -- max ) 
    dup first [ - ] curry [ max ] map-reduce ;

: best-global-sell ( seq k -- best-sell )
    <clumps> [ best-group-sell ] [ max ] map-reduce ;

: flower-power ( -- )
    get-valid-days get-previsions swap best-global-sell . ;

[banryu79]

Originariamente inviato da shinya

Come ho fatto io? Come ho fatto che? Dove sarebbe la truffa?

Sospetto fortemente che la "truffa" di cui sei accusato sia dovuta al fatto che non hai utilizzato C++ o Pascal per dare dimostrazione di una possibile soluzione del problema posto, ma, ah marrano, ti sei appoggiato pesantemente ad un esotico linguaggio ad alto livello di astrazione
Eh non si fa, non si fa...

[shinya]

Originariamente inviato da banryu79

Sospetto fortemente che la "truffa" di cui sei accusato sia dovuta al fatto che non hai utilizzato C++ o Pascal per dare dimostrazione di una possibile soluzione del problema posto, ma, ah marrano, ti sei appoggiato pesantemente ad un esotico linguaggio ad alto livello di astrazione
Eh non si fa, non si fa...

Eh, non posso mica fargli l'esercizio io però

[wizard1993]

l'hanno dato alle olimpiadi di informatica; ora non mi ricordo come l'ho risolto; ma bastano un paio di cicli annidati confrontando dal presso di un dato giorno fino a quello della scadenza

[Krat0s]

L'ho fatto anch'io
Del baro lo davo a lui (CertainDeath) che in piena prova chiedeva che glie lo risolvessero =.=

[gugoXX]

Forse mi manca un dato.
Ma il guadagno dovrebbe essere infinito oppure 0.
Se esiste anche solo un giorno tale per cui il prezzo e' inferiore a qualsiasi dei giorni successivi (fatta salva la scadenza), allora comprero' infinite essenze in quel giorno per rivenderle il giorno giusto...

O forse il limite e' che si puo' comprare una sola essenza al giorno?
Edit: Si infatti e' cosi'. Ho letto dopo il vincolo. Anche venderne una sola pero'. Vabbe'. Bruttino come limite questo ma vabbe'.

[Krat0s]

Nono, non è infinito. Devi prendere il guadagno di una essenza. Praticamente il se il file di input era così:
3 9
1 5 7 4 9 2 6 1 8

il risultato era un file di output contenente il valore 7

[shinya]

Originariamente inviato da Krat0s

Nono, non è infinito. Devi prendere il guadagno di una essenza. Praticamente il se il file di input era così:
3 9
1 5 7 4 9 2 6 1 8

il risultato era un file di output contenente il valore 7

Orgh! C'era un errore colossale nel mio sorgente... sistemato!

USING: kernel sequences grouping math math.parser splitting
prettyprint strings ;
IN: flower-power

: get-valid-days ( -- k+1 )
    readln " " split1 drop string>number 1+ ;

: fix-previsions ( k seq -- k newseq )
    over [ 0 ] replicate append ;

: get-previsions ( -- seq )
    readln " " split [ string>number ] map ;

: best-group-sell ( seq -- max ) 
    dup first [ - ] curry [ max ] map-reduce ;

: best-global-sell ( seq k -- best-sell )
    <clumps> [ best-group-sell ] [ max ] map-reduce ;

: flower-power ( -- )
    get-valid-days get-previsions fix-previsions
    swap best-global-sell . ;

MAIN: flower-power

[CertainDeath]

Originariamente inviato da Krat0s

L'ho fatto anch'io
Del baro lo davo a lui (CertainDeath) che in piena prova chiedeva che glie lo risolvessero =.=

Magari fosse per me.. Ho gia partecipato al Mediashow2009 posizionandomi 34 su 175.. no l'esercizio era per un amico non avendo io ancora dimestichezza con la programmazione l'ho girato qui il problema.
Poi alla fine il mio amico è arrivato ultimo

[Krat0s]

A noi i risultati non ce li hanno dati, ma mi sa che anch'io tanto bene non mi sono posizionato