2047 - Ghinde

Enunț

Scrat și Scratte sunt două veverițe devoratoare de ghinde. Ele trăiesc într-un stejar înalt și culeg ghinde din cele N ramuri ale acestuia. Veverițele vor organiza un concurs: cine culege cele mai multe ghinde în K ture. Într-o tură,

fiecare veveriță se va deplasa de la vizuină până la o ramură a stejarului, de unde va culege cât mai multe ghinde, dar

nu mai mult de M ghinde, după care va reveni în vizuină. Veverițele vor efectua alternativ fiecare câte K ture, prima

care începe fiind Scratte.

Supărat că la concurs nu va începe primul, Scrat decide să se antreneze separat și să vadă câte ghinde ar culege în K

ture, dacă ar fi singur

Cerința

Să se realizeze un program care determină:

Câte ghinde culege Scrat în timpul antrenamentului;

Câte ghinde a cules fiecare veveriță pe durata concursului.

Date de intrare

Fișierul de intrare Pe prima linie a fișierului ghindein.txt conţine pe prima linie un număr natural C. Pentru toate testele, C poate lua numai valorile 1 sau 2. Pe a doua linie se găsesc numerele N, M și K reprezentând numărul de

ramuri ale stejarului, numărul maxim de ghinde culese la o tură, respectiv numărul de ture. Pe următoarele N

linii se găsesc numărul de ghinde de pe fiecare ramură în parte.

Date de ieșire

Dacă valoarea lui C este 1, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire ghindeout.txt va conține numărul total de ghinde cules în timpul antrenamentului de Scrat.

Dacă valoarea lui C este 2, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire ghindeout.txt va conține pe aceeași linie două numere naturale, separate printr-un spațiu, reprezentând în ordine, numărul de ghinde culese de Scratte respectiv Scrat, pe durata concursului.

Restricții și precizări

• 1 ≤ N ≤ 500 000
• 1 ≤ K ≤ 2 000 000 000
• 1 ≤ M ≤ 500 000
• 0 ≤ numărul de ghinde de pe o ramură ≤ 500 000
• Pentru rezolvarea corectă a primei cerințe se obțin 20 de puncte, iar pentru rezolvarea corectă a celei de a

doua cerințe se obțin 80 puncte

Exemplul 1

ghindein.txt

1

3 10 3

13

19

4

ghindeout.txt

29

Explicație

Scart culege 10 ghinde de pe prima ramura, apoi 10 de pe a doua ramura și alte 9 de pe a doua ramura, adică

10+10+9 = 29

Exemplul 2

ghindein.txt

pre.2

4 10 3

13

19

4

7

ghindeout.txt

23 20

Explicație

Scratte: 10 de pe ramura a doua;

Scrat: 10 de pe ramura unu;

Scratte: 9 de pe ramura doi;

Scrat: 7 de pe ramura patru;

Scratte: 4 de pe ramura trei;

Scrat: 3 de pe ramura unu;

Scratte: 10+9+4=23

Scrat: 10+7+3=20

Rezolvare

def este_valoare_valida(C, N, M, K):
    if not (1 <= N <= 500000 and 1 <= K <= 2000000000 and 1 <= M <= 500000):
        return False
    return True


def rezolva(C, N, M, K, a):
    rez = nr = rez1 = rez2 = 0

    for i in range(1, N + 1):
        x = int(f.readline())
        nr += x // M
        a[x % M] += 1

    if C == 1:
        if nr >= K:
            return 1 * K * M,

        K -= nr
        rez = 1 * nr * M

        j = M - 1
        while j and K:
            if a[j]:
                rez += j
                K -= 1
                a[j] -= 1
            else:
                j -= 1

        return rez,

    if nr >= 2 * K:
        return 1 * K * M, 1 * K * M

    rez1 = (nr + 1) // 2 * M
    rez2 = nr // 2 * M
    K = 2 * K - nr

    j = M - 1
    while j > 0 and K:
        if K % 2 == 0:
            if a[j]:
                rez1 += j
                a[j] -= 1
                K -= 1
            else:
                j -= 1
        else:
            if a[j]:
                rez2 += j
                a[j] -= 1
                K -= 1
            else:
                j -= 1

    return rez1, rez2


if __name__ == "__main__":
    Nmax = 500005
    Mmax = 500005

    a = [0] * Mmax

    with open("ghindein.txt", "r") as f, open("ghindeout.txt", "w") as g:
        linie = f.readline().split()

        if len(linie) != 4:
            print("Format invalid în 'ghindein.txt'")
            exit(1)

        C, N, M, K = map(int, linie)

        if not este_valoare_valida(C, N, M, K):
            print("Valori invalide în 'ghindein.txt'")
            exit(1)

        rezultat = rezolva(C, N, M, K, a)
        g.write(" ".join(map(str, rezultat)) + "\n")