1473 - Grupa Pregătitoare: Difference between revisions

From Bitnami MediaWiki
Dragos1234 (talk | contribs)
Dragos1234 (talk | contribs)
Line 5: Line 5:
2. Care poate fi lungimea maximă L a unei secvenţe de copii de pe cerc pentru care suma numerelor de pe cartonaşele scoase de către oricare doi vecini din secvenţă este pară?
2. Care poate fi lungimea maximă L a unei secvenţe de copii de pe cerc pentru care suma numerelor de pe cartonaşele scoase de către oricare doi vecini din secvenţă este pară?
== Date de intrare ==
== Date de intrare ==
Fișierul de ieșire '''grupapregatitoare.out''' va conține pe prima linie numărul '''S''', iar pe a doua linie numărul '''L'''.
Fișierul de intrare '''grupapregatitoare.in''' conține pe prima linie numerele '''n''' şi '''p''', iar pe următoarele n linii câte două numere naturale reprezentând numerele de pe cartonaşele fiecărui elev, în ordinea în care s-au aşezat pe cerc


== Date de ieșire ==  
== Date de ieșire ==  

Revision as of 12:08, 9 April 2023

Sursa: [1]

Cerinţa

Cei n elevi de la grupa pregătitoare au primit câte două cartonaşe, fiecare cartonaş având scris pe el un număr natural. Ei s-au aşezat în cerc şi, la un semnal dat, fiecare a scos la întâmplare un cartonaş din buzunar. Copiii vă roagă să răspundeţi la următoarele întrebări: 1. Care poate fi suma maximă S a numerelor de pe cartonaşele scoase, ştiind că produsul acestora este divizibil cu un număr prim p? 2. Care poate fi lungimea maximă L a unei secvenţe de copii de pe cerc pentru care suma numerelor de pe cartonaşele scoase de către oricare doi vecini din secvenţă este pară?

Date de intrare

Fișierul de intrare grupapregatitoare.in conține pe prima linie numerele n şi p, iar pe următoarele n linii câte două numere naturale reprezentând numerele de pe cartonaşele fiecărui elev, în ordinea în care s-au aşezat pe cerc

Date de ieșire

Programul va afișa pe ecran, mesajul "Datele introduse corespund cerințelor" și pe o linie nouă se vor afișa pe 3 linii numerele de ordine separate prin spații, numerele dintr-o mașină pe câte un rând. În caz contrar programul va afișa pe o linie noua mesajul NU.

Restricţii şi precizări

  • 3 ⩽ n ⩽ 2000
  • 2 ⩽ p ⩽ 1000
  • numerele de pe cartonaşele elevilor sunt nenule şi mai mici decât 1001
  • există cel puţin un număr divizibil cu p pe un cartonaş

Exemplul 1

Intrare
grupapregatitoare.in
3 7
1 2
21 4
5 6
Ieșire
grupapregatitoare.out
29
3


Exemplul 2

Intrare
grupapregatitoare.in
100000000 1000000
1 2
21 4
5 6
Ieșire
grupapregatitoare.out
Datele introduse nu corespund cerintelor.


Rezolvare

<syntaxhighlight lang="python" line>

  1. 1473

def read_input():

   with open("grupapregatitoare.in", "r") as in_file:
       n, p = map(int, in_file.readline().split())
       values = []
       for _ in range(n):
           x, y = map(int, in_file.readline().split())
           values.append((x, y))
   return p, values


def validate_input(n, p, values):

   if not (3 <= n <= 2000):
       print("Datele introduse nu corespund cerintelor.")
       exit()
   if not (2 <= p <= 1000):
       print("Datele introduse nu corespund cerintelor.")
       exit()
   for x, y in values:
       if not (0 < x < 1001 and 0 < y < 1001):
           print("numerele de pe cartonas trebuie sa fie nenule si mai mici decat 1001")
           exit()
       if x % p == 0 or y % p == 0:
           return  # satisface conditia ca exista cel putin un numar divizibil cu p pe un cartonas
   print("nu exista cel putin un numar divizibil cu p pe un cartonas")
   exit()


def compute_result(p, values):

   nr1, nr2 = 0, 0
   suma = 0
   flag = False
   minim = 20000
   secpar = 0
   secimp = 0
   lp = 0
   li = 0
   maxim = 0
   lungi = 0
   lungp = 0
   for x, y in values:
       if x > y:
           suma += x
       else:
           suma += y
       if ((x % p == 0) and (x >= y)) or ((y % p == 0) and (y >= x)):
           flag = True
       if (x % p == 0) and (x < y) and (y - x < minim):
           minim = y - x
           nr1 = x
           nr2 = y
       if (y % p == 0) and (y < x) and (x - y < minim):
           minim = x - y
           nr1 = y
           nr2 = x
       if (x % 2 == 0) or (y % 2 == 0):
           secpar += 1
       else:
           if lp == 0:
               lungp = secpar
               lp = 1
           if secpar > maxim:
               maxim = secpar
           secpar = 0
       if (x % 2 == 1) or (y % 2 == 1):
           secimp += 1
       else:
           if li == 0:
               lungi = secimp
               li = 1
           if secimp > maxim:
               maxim = secimp
           secimp = 0
   if secpar + lungp > maxim:
       maxim = secpar + lungp
   if secimp + lungi > maxim:
       maxim = secimp + lungi
   return suma, flag, nr1, nr2, maxim


def write_output(result):

   with open("grupapregatitoare.out", "w") as out_file:
       suma, flag, nr1, nr2, maxim = result
       if flag:
           out_file.write(str(suma))
       else:
           out_file.write(str(suma - nr2 + nr1))
       out_file.write("\n" + str(maxim))


def main():

   with open("grupapregatitoare.in", "r") as in_file, open("grupapregatitoare.out", "w") as out_file:
       n, p = map(int, in_file.readline().split())
       values = [tuple(map(int, line.split())) for line in in_file]
       validate_input(n, p, values)
       result = compute_result(p, values)
       print("Datele corespund cerintelor.")
       write_output(result)


main() </syntaxhighlight>

Explicatie rezolvare