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 numere18.in conține pe prima linie un număr natural C reprezentând cerința din problemă care trebuie rezolvată (1 sau 2).

Dacă C este egal cu 1, a doua linie din fișier conține un număr natural n, reprezentând numărul liniei pe care trebuie să se calculeze suma.

Dacă C este egal cu 2, a doua linie din fișier conține numărul natural m, reprezentând numărul care trebuie căutat în triunghi.

Date de ieșire

Fișierul de ieșire numere18.out va conține o singură linie. Dacă C=1, va fi scrisă suma cerută la punctul 1. Dacă C=2, vor fi scrise nouă numere: linia pe care a află numărul m, respectiv poziția acestuia pe această linie, separate printr-un spațiu.

Restricţii şi precizări

1 ⩽ n ⩽ 1000
1 ⩽ m ⩽ 1.000.000.000

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.")

</syntaxhighlight>