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
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> ambers(n);

	int wynik = n;
	int max = 0;
	int min = 1000000;
	long long sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> ambers[i];
		if (ambers[i] > max) {
			max = ambers[i];
		}
		if (ambers[i] < min) {
			min = ambers[i];
		}
		sum += ambers[i];
	}

	if (min == max) {
		cout << wynik << endl;
		return 0;
	}

	wynik = (sum / max) + 1;
	if (wynik > n) wynik = n;

	do {
		wynik--;
		bool lipa = false;
		//cout << "Sprawdzam dla " << wynik << endl;
		// Nierówne fale
		if (sum % wynik != 0) continue;
		// Liczba fal
		long long waves = sum / wynik;
		// Nie może byc mniej fal niż pik
		if (waves < max) continue;

		vector<int> ambersTemp = ambers;
		/*
		for (int a = 0; a < n; a++) {
			cout << ambersTemp[a] << " ";
		}
		cout << endl;
		*/
		int i = 0;
		for (int j = 0; j < waves; j++) {
			while (i < n && ambersTemp[i] == 0) {
				i++;
			}
			if (i + wynik -1 >= n) {
				break;
			}
			int delta = ambersTemp[i];
			for (int k = 0; k < wynik; k++) {
				if (ambersTemp[i + k] >= delta) {
					ambersTemp[i + k] -= delta;
				}
				else {
					lipa = true;
					break;
				}
			}
			if (lipa) break;
			/*
			for (int a = 0; a < n; a++) {
				cout << ambersTemp[a] << " ";
			}
			cout << endl;
			*/
		}
		if (lipa) continue;
		while (i < n && ambersTemp[i] == 0) {
			i++;
		}
		if (i == n) {
			break;
		}
	} while (wynik > 1);

	cout << wynik << endl;

	return 0;

}