Ланцюжки ромашок#10365

Ланцюжки ромашок (Розбір)

Розв'язок за $O (n^{3})$ O(n^3). Переберемо всі можливі інтервали $[i; j] (0 \leq i \leq j < n)$ [i; j]~(0 \le i \le j < n) і перевіримо, чи міститься в них середня квітка. Для цього повинно існувати таке $p_{k} (i \leq k \leq j)$ p_k~(i \le k \le j), що

p_{k} = t o t a l P e t a l s / (j - i + 1),

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

де $t o t a l P e t a l s$ totalPetals — загальна кількість пелюсток у квіток на інтервалі $[i; j]$ .

Реалізація алгоритму — $O (n^{3})$ O(n^3)

Оголосимо масив для зберігання кількості пелюстків $p_{i}$ p_i у кожній квітці.

#define MAX 101
int p[MAX];

Читаємо вхідні дані.

scanf("%d", &n);
for (i = 0; i < n; i++)
  scanf("%d", &p[i]);

Кількість фотографій, на яких присутня середня квітка, зберігатимемо у змінній $p h o t os$ .

photos = 0;

Переберемо всі можливі інтервали $[i; j] (0 \leq i \leq j < n)$ [i; j]~(0 \le i \le j < n) і перевіримо, чи збігається середнє арифметичне числа пелюсток квіток на цьому інтервалі з кількістю пелюстків хоча б однієї з них.

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

У змінній $t o t a l P e t a l s$ totalPetals зберігаємо загальну кількість пелюсток у квіток на інтервалі $[i; j]$ .

  int totalPetals = 0;
  for (k = i; k <= j; k++)
    totalPetals += p[k];

Перебираємо значення $p_{k}$ p_k на інтервалі $[i; j] (i \leq k \leq j)$ [i; j]~(i \le k \le j). Якщо $p_{k}$ p_k збігається зі середнім арифметичним числа пелюсток серед усіх квіток фотографії на інтервалі $[i; j]$ , то збільшуємо значення $p h o t os$ на $1$ . Для цього повинна виконуватися умова:

p_{k} = t o t a l P e t a l s / (j - i + 1)

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++;
}

Виводимо відповідь.

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