2115 - Prajituri

Cerința

Ilinca şi verişoara ei Daria, merg la un curs de gătit. Ilinca a făcut o prăjitură cu N straturi, iar Daria a făcut o prăjitură cu M straturi, straturile prăjiturilor fiind aşezate unul după altul pe orizontală şi având diverse culori. E posibil ca unele straturi din prăjitură să aibă aceeaşi culoare.

Ilinca a observat că dacă ar tăia prăjitura ei la capete ar putea obţine o prăjitură la fel ca prăjitura Dariei. Ilinca spune că astfel „extrage” din prăjitura ei prăjitura Dariei. La o extragere, Ilinca taie întotdeauna un număr minim de straturi din partea stângă (straturi pe care le mănâncă imediat) şi câte straturi sunt necesare în partea dreaptă pentru a obţine o prăjitură identică cu prăjitura Dariei. Prăjitura extrasă o aşază pe o farfurie şi continuă „extragerile” din bucata rămasă în partea dreaptă.

Scrieţi un program care să citească numerele naturale N şi M (reprezentând numărul de straturi din prăjitura Ilincăi respectiv Dariei) şi a1,a2,...,aN şi b1,b2,...,bM (reprezentând culorile straturilor din prăjitura Ilincăi respectiv din prăjitura Dariei) şi care să determine:

a) numărul de straturi pe care le taie Ilinca din capătul din stânga şi numărul de straturi pe care le taie din capătul din dreapta la prima extragere;

b) numărul de prăjituri identice cu prăjitura Dariei care se vor afla pe farfurie, după efectuarea tuturor extragerilor;

c) numărul maxim de prăjituri la fel ca prăjitura Dariei care pot fi obţinute din prăjitura Ilincăi dacă aceasta ar rearanja straturile prăjiturii ei într-o ordine convenabilă.

Date de intrare

Fişierul de intrare prajituri.in conţine pe prima linie numerele naturale N M reprezentând numărul de straturi din prăjitura Ilincăi, respectiv a Dariei. A doua linie a fişierului conţine, în ordine, cele N numere a1,a2,...,aN, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Ilincăi. A treia linie a fişierului conţine, în ordine, cele M numere b1,b2,...,bM, separate prin câte un spaţiu, reprezentând, în ordine de la stânga la dreapta, culorile straturilor din prăjitura Dariei.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se vor afișa două numere, separate printr-un spaţiu, reprezentând numărul de straturi tăiate din stânga, respectiv numărul de straturi tăiate din dreapta din prăjitura Ilincăi la prima extragere, separate prin spaţiu. Al treilea rând va conţine un număr natural reprezentând numărul de prăjituri aflate pe farfurie după efectuarea tuturor extragerilor. Al patrulea rând va conţine un număr natural reprezentând numărul maxim de prăjituri la fel ca prăjitura Dariei care se pot obţine din prăjitura Ilincăi dacă aceasta ar rearanja convenabil straturile prăjiturii ei.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 1 ≤ M ≤ N ≤ 10.000
• 1 ≤ ai ≤ 100, (1 ≤ i ≤ N)
• 1 ≤ bi ≤ 100, (1 ≤ i ≤ M)
• N, M, a1, a2, ..., aN, b1, b2, ..., bM sunt numere naturale;
• Întotdeauna se poate obţine din prăjitura Ilincăi cel puţin o prăjitură la fel ca prăjitura Dariei

Exemplu 1

Intrare

5 3

6 2 2 2 2

6 2 2

Ieșire

Datele de intrare corespund restricțiilor impuse.

0 2

1

1

Explicație

Prăjitura Ilincăi are 5 straturi, iar a Dariei 3 straturi, pentru a obţine prăjitura Dariei, Ilinca trebuie să taie din stânga 0 straturi şi din dreapta 2 straturi, se poate obţine doar o prăjitură ca a Dariei indiferent de procedeul folosit

Exemplu 2

Intrare

10 2

5 6 8 8 6 8 6 8 6 6

6 8

Ieșire

Datele de intrare corespund restricțiilor impuse.

1 7

3

4

Explicație

Prăjitura Ilincăi are 10 straturi, iar a Dariei 2 straturi, pentru a obţine prăjitura Dariei, Ilinca trebuie să taie din stânga 1 strat şi din dreapta 7 straturi. Prin procedeul de tăiere se pot obţine 3 prăjituri la fel ca prăjitura Dariei. Prin rearanjarea straturilor se pot obţine maxim 4 prăjituri la fel ca prăjitura Dariei.

Exemplu 3

Intrare

2 10

5 0 8 8 101 8 6 0 6 6

101 0

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#2115 Prajituri

def conditii(n, m, straturi_ilinca, straturi_daria):
    if not 1 <= m <= n <= 10_000:
        return False
    for i in range(n):
        if not 1 <= straturi_ilinca[i] <= 100:
            return False
    for i in range(m):
        if not 1 <= straturi_daria[i] <= 100:
            return False

    return True


def prajituri(n, m, straturi_ilinca, straturi_daria):
    # Ținem cont de frecvența fiecărui element din cele două liste
    frecv_ilinca = [0] * 101
    frecv_daria = [0] * 101

    # Calculăm frecvența fiecărui element din cele două liste folosind lungimea listelor (n și m)
    for i in range(n):
        frecv_ilinca[straturi_ilinca[i]] += 1
    for i in range(m):
        frecv_daria[straturi_daria[i]] += 1

    nr, stanga, dreapta, ok = 0, -1, 0, 1

    # Iterăm toate pozițiile de început posibile pentru straturi_daria în straturi_ilinca
    i = 0
    while i <= n - m:
        ok = 1
        # Verificăm dacă subșirul curent din straturi_ilinca coincide cu cu straturi_daria
        for j in range(m):
            if straturi_ilinca[i + j] != straturi_daria[j]:
                ok = 0
                break

        # Dacă da, actualizăm variabilele folosite pentru a calcula numărul de apariții
        # ale lui straturi_daria în straturi_ilinca
        if ok:
            nr += 1
            if stanga == -1:
                stanga, dreapta = i, n - m - i
            i += m
        # Dacă nu, trecem la următorul subșir din straturi_ilinca
        else:
            i += 1

    # Calculăm numărul de apariții ale lui straturi_daria în straturi_ilinca găsind numărul minim de apariții
    # ale fiecărui element din straturi_daria în straturi_ilinca
    aparitii = n
    for i in range(1, 101):
        if frecv_daria[i] != 0:
            aparitii = min(aparitii, frecv_ilinca[i] // frecv_daria[i])

    print(f"{stanga} {dreapta}")
    print(nr)
    print(aparitii)


if __name__ == "__main__":
    n, m = [int(x) for x in input().split()]
    straturi_ilinca = [int(x) for x in input().split()]
    straturi_daria = [int(x) for x in input().split()]

    if not conditii(n, m, straturi_ilinca, straturi_daria):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        prajituri(n, m, straturi_ilinca, straturi_daria)