Editing 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 <code>N</code> straturi, iar Daria a făcut o prăjitură cu <code>M</code> 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 <code>N</code> şi <code>M</code> (reprezentând numărul de straturi din prăjitura Ilincăi respectiv Dariei) şi <code>a1,a2,...,aN</code> şi <code>b1,b2,...,bM</code> (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 <code>prajituri.in</code> conţine pe prima linie numerele naturale <code>N M</code> 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 <code>N</code> numere <code>a1,a2,...,aN</code>, 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 <code>M</code> numere <code>b1,b2,...,bM</code>, 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==
Fişierul de ieşire <code>prajituri.out</code> va conţine pe prima linie 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. A doua linie va conţine un număr natural reprezentând numărul de prăjituri aflate pe farfurie după efectuarea tuturor extragerilor. A treia linie 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.

==Restricții și precizări==

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

==Exemplu 1==
;Intrare
:5 3
:6 2 2 2 2
:6 2 2
;Ieșire
:0 2
:1
:1

===Explicație===
Prăjitura Ilincăi are <code>5</code> straturi, iar a Dariei <code>3</code> straturi, pentru a obţine prăjitura Dariei, Ilinca trebuie să taie din stânga <code>0</code> straturi şi din dreapta <code>2</code> 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
:1 7
:3
:4

===Explicație===
Prăjitura Ilincăi are <code>10</code> straturi, iar a Dariei <code>2</code> straturi, pentru a obţine prăjitura Dariei, Ilinca trebuie să taie din stânga <code>1</code> strat şi din dreapta <code>7</code> straturi. Prin procedeul de tăiere se pot obţine <code>3</code> prăjituri la fel ca prăjitura Dariei. Prin rearanjarea straturilor se pot obţine maxim <code>4</code> 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
:Date de intrare gresite!

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#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 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):
        return print("Date de intrare gresite!")

    frecv_ilinca = [0] * 101
    frecv_daria = [0] * 101
    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

    i = 0
    while i <= n - m:
        ok = 1
        for j in range(m):
            if straturi_ilinca[i + j] != straturi_daria[j]:
                ok = 0
                break
        if ok:
            nr += 1
            if stanga == -1:
                stanga, dreapta = i, n-m-i
            i += m
        else:
            i += 1

    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__":
    main()

</syntaxhighlight>