Papatyalar zəncirləri#10365

Papatyalar zəncirləri (Həll təhlili)

$O (n^{3})$ O(n^3) həll üsulu. Bütün mümkün intervalları $[i; j] (0 \leq i \leq j < n)$ [i; j]~(0 \le i \le j < n) yoxlayaraq, bu intervallarda orta gülü tapıb-tapmadığımızı yoxlayırıq. Bunun üçün belə bir $p_{k} (i \leq k \leq j)$ p_k~(i \le k \le j) mövcud olmalıdır ki,

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

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

burada $t o t a l P e t a l s$ totalPetals — $[i; j]$ intervalında olan güllərin ümumi ləçək sayını göstərir.

Alqoritmın reallaşdırılması — $O (n^{3})$ O(n^3)

Hər bir gülün ləçək sayını saxlamaq üçün bir massiv elan edək.

#define MAX 101
int p[MAX];

Giriş məlumatlarını oxuyuruq.

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

Orta gülün iştirak etdiyi şəkillərin sayını $p h o t os$ dəyişənində saxlayacağıq.

photos = 0;

Bütün mümkün intervalları $[i; j] (0 \leq i \leq j < n)$ [i; j]~(0 \le i \le j < n) yoxlayaraq, bu intervallardakı güllərin ləçək saylarının arifmetik ortasının onlardan ən az birinin ləçək sayına uyğun gəlib-gəlmədiyini yoxlayırıq.

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

$t o t a l P e t a l s$ totalPetals dəyişənində $[i; j]$ intervalı üzrə güllərin ləçək saylarının cəmini saxlayırıq.

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

Intervalda hər bir $p_{k}$ p_k qiymətini $[i; j] (i \leq k \leq j)$ [i; j]~(i \le k \le j) yoxlayırıq. Əgər $p_{k}$ p_k $[i; j]$ intervalında fotoşəkildəki bütün güllərin ləçək saylarının arifmetik ortasına bərabərdirsə, $p h o t os$ dəyişəninin dəyərini $1$ artırırıq. Bunun üçün aşağıdakı şərt təmin edilməlidir:

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

Cavabı çıxışa veririk.

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