1044 - Piramide

Sursa: [1]

Cerinţa

Scrieţi un program care să citească numerele naturale N (reprezentând numărul de cartonașe), X (reprezentând numărul unui cartonaș), K (reprezentând numărul de cartonașe albe), numerele celor K cartonașe albe c1, c2, …, cK și care să determine:

• a) numărul P al piramidei complete ce conține cartonașul numerotat cu X;

• b) numărul M maxim de piramide complete construite de Rareș;

• c) numărul C de cartonașe nefolosite;

• d) numărul A al primei piramide complete care conține cele mai multe cartonașe albe.

Date de intrare

Fișierul de intrare piramide.in conține pe prima linie cele trei numere N, X şi K, separate prin câte un spaţiu, cu semnificaţia din enunţ. A doua linie a fişierului conţine, în ordine, cele K numere c1, c2,…, cK, separate prin câte un spaţiu, reprezentând numerele celor K cartonașe albe din cele N.

Date de ieșire

Fișierul de ieșire piramide.out va conține pe prima linie numărul P sau valoarea 0 (zero) dacă niciuna dintre piramidele complete construite nu conține cartonașul cu numărul X. A doua linie a fișierului va conține numărul M. Cea de-a treia linie va conţine numărul C. Cea de-a patra linie va conține numărul A sau valoarea 0 (zero) dacă nicio piramidă completă nu conține cel puțin un cartonaș alb.

Restricţii şi precizări

• N, X, K, c1, c2,…, cK, P, M, A sunt numere naturale nenule.
• 3 ⩽ N ⩽ 100000
• 1 ⩽ N ⩽ X
• 1 ⩽ K ⩽ N
• 1 ⩽ c1 < c2 < ... < cK &les N

Exemplul 1

Intrare

numere18.in

1

4

Ieșire

numere18.out

34

Exemplul 2

Intrare

numere18.in

2

9

Ieșire

numere18.out

4 3

Rezolvare

#1044
def find_piramid(n, x, k, f):
    p = 0
    a = 0
    m = 0
    c = 0
    i = 1
    ca = int(f.readline().strip())
    b = 1
    cfol = 0
    nra = 0
    maxnra = 0
    while cfol < n:
        b += 1
        nra = 0
        cp = int(b * (b + 1) / 2)
        if cp + cfol <= n:
            m += 1
            if cfol < x and x <= cp + cfol:
                p = m
            cfol += cp
            while ca <= cfol and i <= k:
                nra += 1
                ca = int(f.readline().strip())
                i += 1
            if nra > maxnra:
                a = m
                maxnra = nra
        else:
            break
    c = n - cfol
    return p, a, m, c


def validate_input(n, x, k, c):
    try:
        n, x, k = int(n), int(x), int(k)
        c = list(map(int, c.split()))
        if not(3 <= n <= 100000 and 1 <= x <= n and 1 <= k <= n and all(1 <= ci <= n for ci in c)):
            return False
    except ValueError:
        return False
    return True


if __name__ == '__main__':
    with open("piramide.in") as f, open("piramide.out", "w") as g:
        n, x, k = map(str.strip, f.readline().split())
        c = f.readline().strip()
        if validate_input(n, x, k, c):
            p, a, m, c = find_piramid(int(n), int(x), int(k), f)
            g.write(str(p) + "\n" + str(m) + "\n" + str(c) + "\n" + str(a) + "\n")
            print("Datele introduse corespund cerintelor.")
        else:
            print("Datele introduse nu corespund cerintelor.")