Il dottore ordina a Poldo di seguire una dieta. Ad ogni pasto non può mai mangiare un panino che abbia un peso maggiore o uguale a quello appena mangiato. Quando Poldo passeggia per la via del suo paese, da ogni ristorante esce un cameriere proponendo il menù del giorno. Ciascun menù è composto da una serie di panini, che verranno serviti in un ordine ben definito, e dal peso di ciascun panino. Poldo, per non violare la regola della sua dieta, una volta scelto un menù, può decidere di mangiare o rifutare un panino; se lo rifiuta il cameriere gli servirà il successivo e quello rifiutato non gli sarà più servito.
Si deve scrivere un programma che permetta a Poldo, leggendo un menù, di capire qual è il numero massimo di panini che può mangiare per quel menù senza violare la regola della sua dieta.
Riassumendo, Poldo può mangiare un panino se e solo se sodddisfa una delle due condizioni:
La prima linea del file input.txt contiene il numero m di panini proposti nel menù. Le successive m linee contengono un numero intero non negativo che rappresenta il peso del panino che verrà servito. I panini verranno serviti nell'ordine in cui compaiono nell'input.
Il file output.txt contiene il massimo numero di panini che Poldo può mangiare rispettando la dieta.
| File input.txt | File output.txt |
8 389 207 155 300 299 170 158 65 | 6 |
| File input.txt | File output.txt |
3 22 23 27 | 1 |
| File input.txt | File output.txt |
22 15 14 15 389 201 405 204 130 12 50 13 26 190 305 25 409 3011 43 909 987 1002 900 | 6 |