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
#include <iostream>
#include <stdio.h>

using namespace std;

/*
Pliszka alternująca (Motacilla alterna) to gatunek ptaka z rodziny pliszkowatych. Wyróżnia go charakterystyczny śpiew, w którym wysokość tonu kolejnych dźwięków naprzemiennie rośnie i maleje. Dla przykładu,
jeżeli będziemy reprezentować wysokości dźwięków za pomocą liczb całkowitych, to pliszka alternująca może
zaśpiewać [2, 1, 3] i [4, 5, −6, −5], ale nie [1, 2, 3, 2] i [6, 5, 5, 4]. W celu nagrania tych fascynujących stworzeń
ornitolog Bajtazar pozostawił swój dyktafon na kilka dni w lesie. Teraz zastanawia się, czy nagrane dźwięki
są podobne do śpiewu pliszki.
Napisz program, który dla danego ciągu wysokości dźwięków wyznaczy minimalną liczbę jego wyrazów,
które trzeba zmienić na dźwięk o dowolnej całkowitoliczbowej wysokości z przedziału [−109
, 109
], żeby ciąg
przedstawiał możliwy śpiew pliszki alternującej.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita n (3 ≤ n ≤ 50 000), oznaczająca długość nagrania.
Kolejny wiersz zawiera n liczb całkowitych a1, a2, . . . , an (−1 000 000 ≤ ai ≤ 1 000 000), gdzie ai jest
wysokością i-tego dźwięku w nagraniu.
Wyjście
Na wyjściu powinna znaleźć się jedna liczba całkowita, oznaczająca minimalną liczbę zmienionych dźwięków.
Przykład
Dla danych wejściowych:
5
4 1 3 3 1
poprawnym wynikiem jest:
1
Natomiast dla danych wejściowych:
4
-1000000 -1000000 -1000000 -1000000
poprawnym wynikiem jest:
2
Wyjaśnienie przykładów: W pierwszym teście przykładowym, aby ciąg mógł zostać zaśpiewany przez pliszkę
alternującą, wystarczy zmienić czwarty wyraz ciągu, na przykład na −1. W drugim teście przykładowym trzeba
zmienić co najmniej dwa wyrazy, otrzymując na przykład ciąg [−1 000 001, −1 000 000, −1 000 002, −1 000 000]
*/
int sig(int x) {
    return (x > 0) ? 1 : ((x < 0) ? -1 : 0);
}
int orn(int tones[], int len) {
    int expected = 1;
    
    int errors1 = 0;
    int errors2 = 0;
    
    bool justWasError1 = false;
    bool justWasError2 = false;
    
    for (int i=1; i<len; i++) {
        int changeSign = sig(tones[i] - tones[i - 1]);
        
        if (changeSign != expected && !justWasError1) {
            errors1++;
            justWasError1 = true;
        } else {
            justWasError1 = false;
        }
        
        if (changeSign != -expected && !justWasError2) {
            errors2++;
            justWasError2 = true;
        } else {
            justWasError2 = false;
        }
        
        expected = -expected;
    }
    //cout << "(e1, e2): " << errors1 << " " << errors2 << endl;
    return min(errors1, errors2);
}

int main() {
    int tonesNumber;
    cin >> tonesNumber;
    int tones[tonesNumber];
    for (int i = 0; i < tonesNumber; i++)
        cin >> tones[i];
    cout << orn(tones, tonesNumber) << endl;
}