Cod sursa(job #3001184)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 13 martie 2023 12:18:02
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
///frumoasa simulare
///3 resturi 3 valori
///toate subsecventele
///tranzitie

#include <fstream>
#include <string>

using namespace std;

ifstream cin ("oji.in");
ofstream cout ("oji.out");

const int INF = 1e9;

int rest[4][4];

char a[4][4] = {"OJI", "IOJ", "JIO"};

int n, k, mn = INF;

string s;

char get (char ch)
{
    if (ch == 'O')
        return 1;
    if (ch == 'J')
        return 2;
    return 3;
}

void transfer ()
{
    ///2->1
    ///1->0
    ///0->2
    int f[5];
    for (int i = 1; i <= 3; ++i)
        f[i] = rest[0][i];
    for (int i = 1; i <= 3; ++i)
        rest[0][i] = rest[1][i], rest[1][i] = rest[2][i], rest[2][i] = f[i];

}

int main()
{
    cin >> n >> k >> s;
    for (int i = 0; i < k; ++i)
        rest[i % 3][get(s[i])]++;
    for (int l = 0; l <= 2; ++l)
    {
        int sum = 0;
        for (int j = 0; j <= 2; ++j)
        {
            int toate = rest[j][1] + rest[j][2] + rest[j][3];
            sum += toate - rest[j][get(a[l][j])];
        }
        mn = min (mn, sum);
    }
    for (int i = k; i < n; ++i)
    {
        rest[0][get(s[i - k])]--;
        transfer();
        rest[(k - 1) % 3][get(s[i])]++;
        for (int l = 0; l <= 2; ++l)
        {
            int sum = 0;
            for (int j = 0; j <= 2; ++j)
            {
                int toate = rest[j][1] + rest[j][2] + rest[j][3];
                sum += toate - rest[j][get(a[l][j])];
            }
            mn = min (mn, sum);
        }
    }
    cout << mn << '\n';
    return 0;
}