1727 - Culori 3

Fiecare dintre cei N copii, numerotați de la 1 la N, primește câte un cartonaș colorat. Doamna dirigintă îi așează în cerc, în ordinea numerotării, în sens orar. Astfel, fiecare copil are doi vecini, așezați în stânga, respectiv în dreapta lui.

Andrei, pasionat de informatică, asociază fiecărei culori distincte un cod, reprezentat printr-un număr natural nenul, și inscripționează fiecare cartonaș cu codul corespunzător culorii acestuia.

Cerința

Scrieţi un program care citeşte două numere naturale N şi K şi determină pentru Andrei:

a) numărul copiilor din cerc care au cartonaşe de aceeaşi culoare cu cartonaşele vecinilor;

b) numărul maxim de cartonaşe de aceeaşi culoare ce sunt deţinute de copiii aşezaţi pe K poziţii consecutive în cercul format.

Date de intrare

Fişierul de intrare culori.in conţine pe prima linie numerele naturale N şi K, separate printr-un spaţiu, şi pe fiecare dintre următoarele N linii, câte un număr natural. Cele N numere reprezintă codurile culorilor cartonaşelor, în ordinea numerotării copiilor, începând cu copilul 1.

Date de ieșire

Fişierul de ieşire culori.out conţine:

pe prima linie, numărul natural determinat la cerinţa a);

pe a doua linie, numărul natural determinat la cerinţa b).

Restricții și precizări

• 2 < N ≤ 1000
• 2 < K ≤ N
• codurile culorilor sunt numere naturale nenule, consecutive, mai mici sau egale cu 100
• dacă C este codul maxim asociat unei culori ( 1 ≤ C ≤ 100 ) atunci există cel puţin C cartonaşe care au codurile distincte: 1,2,3,…,C.

Exemplu:

culori.in

8 5
3
1
2
1
1
1
3
3

culori.out

2
4

Explicație

Sunt doi copii care au, fiecare, cartonaşe identice cu cei doi vecini (copilul 5 şi copilul 8).

Numărul maxim de cartonaşe de aceeaşi culoare deţinute de copiii aşezaţi pe K = 5 poziţii consecutive în cercul format este 4 (dintre copiii 2,3,4,5,6 doar copiii 2,4,5 şi 6 au cartonaşe de culoarea 1).

Încărcare soluție

Lipește codul aici

def read_input(filename):
    with open(filename, 'r') as fin:
        N, k = map(int, fin.readline().split())
        x = [0] * (2 * N + 3)
        x[1] = int(fin.readline())
        x[N + 1] = x[1]
        c = x[1]
        x[2] = int(fin.readline())
        x[N + 2] = x[2]
        if x[2] > c:
            c = x[2]
        for i in range(3, N + 1):
            x[i] = int(fin.readline())
            x[N + i] = x[i]
            if x[i] > c:
                c = x[i]
        nrc = sum(1 for i in range(2, N) if x[i - 1] == x[i - 2] == x[i])
        if x[1] == x[N] == x[N - 1]:
            nrc += 1
        if x[1] == x[2] == x[N]:
            nrc += 1
    return N, k, x, c, nrc

def main():
    N, k, x, c, nrc = read_input('culori.in')
    maxck = 0
    apc1 = [0] * (c + 1)
    for i in range(1, k + 1):
        apc1[x[i]] += 1
        maxck = max(maxck, apc1[x[i]])
    for i in range(2, N + 1):
        apc1[x[i - 1]] -= 1
        apc1[x[i + k - 1]] += 1
        for j in range(1, c + 1):
            maxck = max(maxck, apc1[j])
    with open('culori.out', 'w') as fout:
        fout.write(f"{nrc}\n{maxck}\n")

if __name__ == "__main__":
    main()