Editing 1044 - Piramide

Sursa: [https://www.pbinfo.ro/probleme/1044/piramide]
== 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 == 
În cazul în care datele introduse sunt corecte în consolă se va afișa mesajul "Datele introduse corespund cerintelor" și 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. În caz contrar programul va afișa în consolă mesajul "Datele introduse nu corespund cerintelor."

== Restricţii şi precizări ==
* '''N, X, K, c1, c2,…, cK, P, M, A''' sunt numere naturale nenule.
* 3 &les; '''N''' &les; 100000
* 1 &les; '''N''' &les; '''X'''
* 1 &les; '''K''' &les; '''N'''
* 1 &les; '''c1''' &lt; '''c2''' &lt; ... &lt; '''cK''' &les '''N'''

== Exemplul 1 ==
; Intrare
: ''piramide.in''
: 75 15 23
: 5
: 9
: 11
: 18
: 20
: 21
: 25
: 27
: 28
: 30
: 35
: 37
: 45
: 46
: 51
: 55
: 60
: 65
: 68
: 69
: 70
: 71
: 72
; Ieșire
: Datele introduse corespund cerintelor.
: ''piramide.out''
: 3
: 5
: 20
: 4
<br>

== Exemplul 2 ==
; Intrare
: ''piramide.in''
: 1000000000000000000000 100000000000000000000 10000000000000000000000000000
: 5
: 9
: 11
: 18
: 20
: 21
: 25
: 27
: 28
: 30
: 35
: 37
: 45
: 46
: 51
: 55
: 60
: 65
: 68
: 69
: 70
: 71
: 72
; Ieșire
: Datele introduse nu corespund cerintelor.
<br>

== Rezolvare == 
<syntaxhighlight lang="python" line>
#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):
            print("Datele introduse corespund cerintelor.")
            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")
        else:
            print("Datele introduse nu corespund cerintelor.")

</syntaxhighlight>

== Explicatie rezolvare ==
Acest program citeste datele de intrare dintr-un fisier numit '''piramide.in''' si valideaza intrarea folosind functia '''validate_input'''. Daca intrarea este valida, se apeleaza functia '''find_piramid''' pentru a calcula si afisa rezultatele intr-un fisier numit '''piramide.out'''.

Functia find_piramid are patru parametri: '''n, x, k si f'''. '''n''' este numarul total de blocuri dintr-o piramida, '''x''' este numarul blocului care trebuie gasit, '''k''' este numarul maxim de blocuri care pot fi intr-o singura randul piramidei, iar '''f''' este un obiect fisier care contine lista de blocuri care au fost deja luate.

Functia calculeaza randul piramidei unul cate unul pana cand blocul '''x''' este gasit, si tine evidenta randului '''p''' unde '''x''' este localizat, numarul total de randuri '''m''', randul a cu cele mai multe blocuri disponibile si blocurile ramase '''c''' care nu fac parte din piramida.

Functia validate_input are patru parametri: '''n, x, k si c'''. Mai intai, incearca sa converteasca '''n, x si k''' la numere intregi. Daca conversiile nu reusesc, functia returneaza False. In caz contrar, verifica daca '''n, x si k''' se afla in intervalul necesar si daca toate blocurile enumerate in '''c''' se afla de asemenea in intervalul necesar.

Daca intrarea este valida, programul scrie rezultatul in fisierul '''piramide.out''' folosind obiectul fisier '''g'''. Rezultatul consta in patru numere intregi separate prin linii noi: '''p, m, c si a'''. Aceste numere intregi reprezinta randul piramidei care contine blocul '''x''', numarul total de randuri din piramida, numarul de blocuri ramase care nu fac parte din piramida si randul cu cele mai multe blocuri disponibile, respectiv.