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

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

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

<syntaxhighlight lang="python" line>

1. 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.