-
Notifications
You must be signed in to change notification settings - Fork 24
/
ConvexSequence.html
14 lines (14 loc) · 4.09 KB
/
ConvexSequence.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
<html><body bgcolor="#000000" text="#ffffff"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td><p>
A sequence x[0], ..., x[N-1] of integers is called <i>convex</i> if for every 1<=i<=N-2, x[i-1]+x[i+1]>=2*x[i].
For example, sequences 7,3,4,5,7 and 4,2,1,3 are convex, while 4,3,1,2 and 5,7,3 are not.
A sequence with one or two elements is always convex.
</p><p>
You are given a vector <int> <b>a</b> containing N elements. You can perform an operation that chooses an index i and replaces <b>a</b>[i] with <b>a</b>[i]-1.
Return the minimum number of operations needed to make the sequence convex.
</p></td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>ConvexSequence</td></tr><tr><td>Method:</td><td>getMinimum</td></tr><tr><td>Parameters:</td><td>vector <int></td></tr><tr><td>Returns:</td><td>long long</td></tr><tr><td>Method signature:</td><td>long long getMinimum(vector <int> a)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>    </td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>a</b> will contain between 1 and 50 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>a</b> will be between 0 and 10^9, inclusive.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{6,5,1,5,3,3}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 7</pre></td></tr><tr><td><table><tr><td colspan="2">You can change the given sequence into a convex sequence by seven operations: doing the operation on <b>a</b>[1] twice, on <b>a</b>[3] four times and on <b>a</b>[4] once yields a convex sequence 6,3,1,1,2,3.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{3,0,1,4}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2">No operation is needed; the sequence is already convex. </td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{1,1,1,0,2,2,2}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 5</pre></td></tr><tr><td><table><tr><td colspan="2">You can change the sequence into 1,0,0,0,0,1,2 by five operations.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{854159326, 317144183, 781399725, 287076509, 894967145, 882577367, 174517516, 134415519,
274494874, 709819883, 59717133, 732212854, 40551288, 232526958, 811785438, 930853743,
946882902, 321325300, 397702677, 376192501, 599310562, 889156198, 135776890, 882710939,
823196361, 681959076, 318666702, 94469186, 536320456, 116468376, 530320850, 436708006,
903344748, 659080120, 774722507, 967315412, 566063635, 43970906, 497687103, 781266213,
876086123, 366960001, 587364849, 191948103, 172568553, 539762057, 83507466, 71569625,
686305822, 663789601}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 20178337330</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">4)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{5}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. </p></body></html>