Solved by 358 users: ...
UserDateAttemptTimeCMSC
fetetriste`23 nov 2007`C++1400.51189
Micota`11 mar 2010`FPC600.33192
glueray`11 nov 2006`C++600.02195
Philip_PV`12 jul 2008`C++500.14195
glueray`11 nov 2006`C++500.02198
Aleris_S`30 sep 2015`C1300.01199
Philip_PV`12 jul 2008`C++400.13199
tnsantosh`26 dec 2007`C++2400.44199
cyberian`07 may 2007`C++1303.53199
Zorgan`24 oct 2011`C++800.02203
Micota`11 mar 2010`FPC500.33204
tnsantosh`19 dec 2007`C++2300.44204
Zorgan`24 oct 2011`C++700.02207
g201513`09 may 2006`C++100.02209
zmy`23 apr 2006`C++600.02209
Zorgan`24 oct 2011`C++600.02210
fetetriste`23 apr 2007`C++800.49210
 C++ 186 FPC 106 Java 37 C 19 Kylix 13 Ruby 1
` >  >  >  >  >  >  >  >  >  > `

Minimizing number of steps

Time limit = 5 seconds

Petya wants to organize programming contest in his institute and he has to pass some consecutive bureaucratic procedures.

At each step Petya get or pay some money.

He may pay 100 coins to skip next bureaucratic procedures or 200 coins to skip next two procedures or k*100 coins to skip next k.

Please, help Petya to minimize number of bureaucratic procedures.

At the beginning Petya has 0 coins. The last and the first procedures should be passed.

He cannot have negative number of coins.

Input The first line contains number N, (1 ≤ N ≤ 1000 ). Next line contains N integer numbers each less than 10000 in absolute value.

Output Output minimal number of procedures Petya should pass through. or output "-1" if it is impossible to pass trough bureaucratic barrier.

 Input#1```1 100 ``` Output#1```1 ```
 Input#2```1 -20 ``` Output#2```-1 ```
 Input#3```4 120 20 20 20 ``` Output#3```3 ```
 Input#4```6 30 30 30 30 30 30 ``` Output#4```5 ```

Author:

<PREV | Problem set | Search related messages | NEXT>

 © acm.mipt DevGroupThe page was generated in 190ms