Hərflər üzrə tullanma (RIO_M2014)

Hərflər üzrə tullanma (RIO_M2014)

Məsələ #: 183   

Latın əlifbasının baş hərflərindən təşkil olunmuş N sayda simvollar zənciri verilmişdir. Ən çoxuK simvol tullanmaqla zəncirin birinci simvolundan axırıncı simvolunadək getmək lazımdır. Tullanma nəticəsində simvol dəyişmirsə, yəni əvvəlki ilə eyni olan hərfin üzərinə tullanılırsa, belə tullanmanın qiyməti 0-a, başqa simvolun üzərinə tullanılırsa, qiyməti 1-ə bərabər olur.

Birinci simvoldan axırıncı simvola çatmaq üçün qiyməti ən az olan keçidi hesablayan proqram yazın.

Giriş verilənlərinin formatı

Birinci sətirində iki tam ədəd verilir: simvollar zəncirinin uzunluğu – N (2 ≤ N ≤ 105) və maksimal tullanma uzunluğu – K (1 ≤ K < N). İkinci sətirdə N sayda hərfdən ibarət zəncir yerləşir.

Çıxış verilənlərinin formatı

Çıxışa bir ədəd – yerdəyişmənin minimum qiyməti verilir.

 Məlumat

Zaman limiti: 2 san.
Yaddaş limiti: 64 Mb
Bal: 10
Çətinlik: 31/95 (67 %)

Nümunə

Giriş verilənlərinə nümunə

10 2
ABABBCACBC

Çıxış verilənlərinə nümunə

2

#include <iostream>

#include <stdio.h>

using namespace std;

int main ()

{

int n,k;

char s[100001], c;

int M[100000], km1 , km2, i, j;

scanf ("%d%d", &n, &k);

scanf ("%s" , s);

M[n-1] = 0;

for (i = n-2; i>= n- k - 1; i--)

if (s[i] != s[n-1])

M[i]=1;

else

M[i]=0;

for (i = n-k-2; i>= 0; i--)

{

c=s[i];

km1 = km2 = n;

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

if (c != s[j])

{

if (M[j]<km1) km1=M[j];

}

else

{

if (M[j]<km2) km2=M[j];

}

if (km2<km1 +1)

M[i] = km2;

else

M[i] = km1 + 1;

}

printf("%d\n",M[0]);

return 0;

}