1044 - Piramide

Sursa: [1]

Cerinţa[edit | edit source]

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[edit | edit source]

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[edit | edit source]

Î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[edit | edit source]

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[edit | edit source]

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

Exemplul 2[edit | edit source]

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.

Rezolvare[edit | edit source]

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[edit | edit source]

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.