10365. Daisy chains

Every day, while walking around the farm, Bessie the cow visits her favorite pasture, where n flowers (all multicolored daisies) grow in a row, numbered from 1 to n. Flower i has p_i petals.

As an aspiring photographer, Bessie decided to take some pictures of these flowers. In particular, for every pair of indices (i, j) with 1 ≤ i ≤ j ≤ n, she takes a photograph of all flowers from i to j (inclusive).

Later, while looking at these photographs, Bessie notices that some of them contain a median flower – a flower with p petals, where p is equal to the average number of petals among all flowers in that photograph.

Determine how many photographs contain a median flower.

Input. The first line contains an integer n (1 ≤ n ≤ 100).

The second line contains n integers p₁, ..., p_n (1 ≤ p_i ≤ 1000).

Output. Print the number of photographs that contain a median flower.

Sample input	Sample output
4 1 1 2 3	6

SOLUTION

full serarch

Algorithm analysis

The solution runs in O(n³). Iterate over all possible intervals [i; j] (0 ≤ i ≤ j < n) and check whether they contain a median flower. For this, there must exist some p_k (i ≤ k ≤ j) such that

p_k = totalPetals / (j – i + 1),

where totalPetals is the total number of petals of the flowers in the interval [i; j].

Algorithm implementation – O(n³)

Declare an array to store the number of petals p_i in each flower.

#define MAX 101

int p[MAX];

Read the input data.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &p[i]);

The number of photographs that contain a median flower will be stored in the variable photos.

photos = 0;

Iterate over all possible intervals [i; j] (0 ≤ i ≤ j < n) and check whether the average number of petals of the flowers in this interval matches the number of petals of at least one of them.

for (i = 0; i < n; i++)

for (j = i; j < n; j++)

{

The variable totalPetals stores the total number of petals of the flowers in the interval [i; j].

int totalPetals = 0;

for (k = i; k <= j; k++)

totalPetals += p[k];

Iterate over the values p_k in the interval [i; j] (i ≤ k ≤ j). If p_k is equal to the average number of petals among all flowers in the photograph on the interval [i; j], then increase the value of photos by 1. For this, the following condition must hold:

p_k = totalPetals / (j – i + 1)

present = 0;

for (int k = i; k <= j; k++)

if (p[k] * (j - i + 1) == totalPetals) present = 1;

if (present) photos++;

}

Print the answer.

printf("%d\n", photos);