1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, pgurka=0, pmaly=0;
	cin >> N;
	vector<int> gurka, wys;
	for (int i=0; i<N; i++){
		int z;
		cin >> z;
		gurka.push_back(z);
	}
	vector<int>tezgrk=gurka;

	// dla pierwszego bedacego gorka
	int robimy=1;
	while(robimy==1){
		robimy=0;
			for (int i=0; i<N-1; i++){
				if (i%2==0){
					// chcemy gorke
					if (tezgrk[i]<=tezgrk[i+1]){
						if (i+2<N && tezgrk[i+2]<tezgrk[i]){
								tezgrk[i+1]=tezgrk[i+2]-1;
								robimy=1;
								pgurka++;
								continue;
						}
						tezgrk[i+1]=tezgrk[i]-1;
						robimy=1;
						pgurka++;
					}
				}
				if (i%2==1){
					// chcemy zeby byl mniejszy niz next
					if (tezgrk[i]>=tezgrk[i+1]){
						if (i+2<N && tezgrk[i+2]>tezgrk[i]){
								tezgrk[i+1]=tezgrk[i+2]+1;
								robimy=1;
								pgurka++;
								continue;
						}
						robimy=1;
						tezgrk[i+1]=tezgrk[i]+1;
						pgurka++;
					}
				}
			}
	}
	robimy=1;
	// dla pierwszego bedacego dolina
	while(robimy==1){
		robimy=0;
			for (int i=0; i<N-1; i++){
				if (i%2==1){
					// chcemy gurke
					if (gurka[i]<=gurka[i+1]){
						if (i+2<N && gurka[i+2]<gurka[i]){
								gurka[i+1]=gurka[i+2]-1;
								robimy=1;
								pmaly++;
								continue;
						}
						gurka[i+1]=gurka[i]-1;
						robimy=1;
						pmaly++;
					}
				}
				if (i%2==0){
					if (gurka[i]>=gurka[i+1]){
					// chcemy zeby byl mniejszy niz next
					if (i+2<N && gurka[i+2]>gurka[i]){
							gurka[i+1]=gurka[i+2]+1;
							robimy=1;
							pmaly++;
							continue;
					}
						robimy=1;
						gurka[i+1]=gurka[i]+1;
						pmaly++;
					}
				}
			}
	}
	if (pmaly>pgurka) pmaly=pgurka;
	cout << pmaly;


return 0;
}