L'alçada del cim d'una muntanya X33007
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.
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