L'alçada del cim d'una muntanya X33007

Statement

Heu d’implementar una funció que rep un vector $v$ de naturals que té dues parts, una primera part estrictament creixent i una segona part estríctament decreixent. En altres paraules, existeix un índex $i$ vàlid del vector tal que, per a tot $j$ anterior a $i$ es cumpleix $v[j]<v[j+1]$ , i per a tot $j$ posterior a $i$ es cumpleix $v[j-1]>v[j]$ . Es garanteix que el vector té com a mínim tres elements i que el seu valor màxim (és a dir $v[i]$ , per al $i$ que hem mencionat) no es troba ni exactament al principi ni exactament al final.

La funció haurà de retornar el valor màxim de $v$ . Aquesta és la capcelera:

// Pre:  Let n be v.size(). Then n >= 3 and for all i in {0..n-1}, v[i] >= 0.
//       Also, there exists i in {1..n-2} such that v[0..i] is strictly increasing and
//                                                  v[i..n-1] is strictly decreasing.
// Post: Returns the maximum value of v.
int summitOfMountain(const vector<int> &v);

Observació

Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació

Avaluació sobre 10 punts:

Solució lenta: 5 punts.
solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost logarítmic i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.

Sample session

summitOfMountain([10, 11, 15, 7]) = 15
summitOfMountain([7, 12, 6, 3]) = 12
summitOfMountain([28, 65, 63, 59, 56, 51, 47, 44, 41, 36, 35, 32, 25, 24, 21, 16, 13, 9, 7]) = 65
summitOfMountain([9, 51, 46, 45, 42, 41, 36, 33, 29, 24, 22, 21, 19, 16, 11, 10, 7]) = 51
summitOfMountain([14, 17, 19, 21, 26, 31, 32, 33, 38, 42, 9]) = 42
summitOfMountain([6, 11, 21, 16]) = 21
summitOfMountain([2, 4, 5, 10, 16, 18, 21, 25, 27, 28, 34, 39, 53, 50, 48, 44, 30, 13]) = 53
summitOfMountain([5, 9, 11, 12, 16, 17, 27, 32, 37, 40, 42, 46, 48, 51, 52, 62, 59, 57, 22]) = 62
summitOfMountain([13, 21, 17, 9, 5]) = 21
summitOfMountain([10, 16, 13]) = 16
summitOfMountain([13, 26, 21, 20, 19, 14, 10, 5, 4]) = 26
summitOfMountain([18, 23, 29, 27, 14, 11, 9]) = 29
summitOfMountain([1, 5, 6, 7, 14, 16, 20, 24, 26, 33, 38, 44, 41, 29, 19, 9]) = 44
summitOfMountain([10, 12, 24, 28, 19, 17]) = 28
summitOfMountain([1, 2, 12, 9, 7]) = 12
summitOfMountain([11, 15, 23, 30, 31, 34, 37, 39, 45, 48, 50, 41, 28, 18, 8]) = 50
summitOfMountain([8, 13, 5]) = 13
summitOfMountain([6, 9, 10, 11, 3]) = 11
summitOfMountain([9, 15, 14, 8, 4]) = 15
summitOfMountain([5, 10, 20, 15]) = 20

Information

Author: PRO1
Language: Catalan
Other languages: English Spanish
Official solutions: C++
User solutions: C++