4091 - Sss1

Sursa: [1]

Cerinţa 1

Determinați suma valorilor aflate pe ultimele K poziții în șir (unde K reprezintă valoarea celei mai din dreapta cifre nenule a primei valori din șir).

Cerința 2

Ne imaginăm împărțirea șirului în secvențe în următorul mod: prima secvență este formată din primele L elemente, a doua este formată din următoarele L-1 elemente, a treia este formată din următoarele L-2 elemente și așa mai departe, ultima secvență este formată dintr-un singur element și acesta coincide cu ultimul element din șir. Considerând suma valorilor fiecărei secvențe, să se determine cea mai mare dintre aceste sume.

Date de intrare

De la tastatură se citesc două numere C şi V. Dacă avem C = 1, trebuie determinată valoarea de pe poziția V din șir. Dacă avem C = 2 se cere să determinăm cea mai mică poziție din șir unde avem valoarea V.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corespund cerintelor.", apoi pe un rând nou afișează pe ecran se va afișa un singur număr natural corespunzător rezultatului obținut pentru rezolvarea fiecărei. În caz contrar, se va afișa pe ecran: "Datele introduse nu corespund cerintelor."

Restricţii şi precizări

• 1 ⩽ C ⩽ 2
• Pentru 25% din punctaj, C = 1 și V ⩽ 100.000
• Pentru 25% din punctaj, C = 1 și 100.000 < V ⩽ 1.000.000.000
• Pentru 50% din punctaj, C = 2 și 1 < V ⩽ 35.000

Exemplul 1

Intrare

Introduceti numar: 0

Introduceti alt numar: 0

Ieșire

Datele introduse nu corespund cerintelor.

Exemplul 2

Intrare

Introduceti numar: 1

Introduceti alt numar: 8

Ieșire

Datele de intrare corespund cerintelor.

3

Rezolvare

<syntaxhighlight lang="python" line>

1. 4091

def validate_input(C, N, a, K):

   if not (1 <= N <= 100000):
       print("Datele introduse nu corespund cerintelor")
       exit()
   if not all(0 < x <= 100000 for x in a[1:]):
       print("Datele introduse nu corespund cerintelor")
       exit()
   if C == 1 and len(a) <= K:
       print("Datele introduse nu corespund cerintelor")
       exit()
   if C == 2 and N <= 10:
       print("Datele introduse nu corespund cerintelor")
       exit()
   if C == 1 and len(str(a[1])) > 1 and not any(x.isdigit() for x in str(a[1])):
       print("Datele introduse nu corespund cerintelor")
       exit()

   print("Datele introduse corespund cerintelor.")

def read_input_file(filename):

   with open(filename, "r") as f:
       C, N = map(int, f.readline().split())
       a = [0] * (N+1)
       for i in range(1, N+1):
           a[i] = int(f.readline())
   return C, N, a

def write_output_file(filename, value):

   with open(filename, "w") as f:
       f.write(str(value))

def get_sum_last_n_nonzero_digits(C, N, a):

   def vcmddcn(n):
       while n:
           if n % 10:
               return n % 10
           else:
               n //= 10
       return -1
   c = vcmddcn(a[1])
   S = sum(a[N-c+1:])
   return S if C == 1 else None

def get_max_sum_subsequence(C, N, a):

   s = [0] * (N+1)
   for i in range(1, N+1):
       s[i] = s[i-1] + a[i]
   S, Max = 0, 0
   for i, j in zip(range(N, 0, -1), range(1, N+1)):
       S = s[i] - s[i-j]
       Max = max(S, Max)
   return Max if C != 1 else None

if __name__ == '__main__':

   C, N, a = read_input_file("sss.in")
   validate_input(C, N, a, K=2)
   result = get_sum_last_n_nonzero_digits(C, N, a) or get_max_sum_subsequence(C, N, a)
   if result is not None:
       write_output_file("sss.out", result)

</syntaxhighlight>

Explicatie rezolvare

Programul primește datele de intrare dintr-un fișier de intrare și le validează prin intermediul funcției validate_input. Dacă datele de intrare sunt corecte, atunci funcția get_sum_last_n_nonzero_digits sau funcția get_max_sum_subsequence este apelată în funcție de valoarea variabilei C, iar rezultatul este scris într-un fișier de ieșire.

Mai exact, dacă C este egal cu 1, atunci se va apela funcția get_sum_last_n_nonzero_digits pentru a calcula suma ultimelor n cifre nenule din primul element al listei a sau funcția get_max_sum_subsequence pentru a calcula suma maximă a unei subsecvențe nevide din lista a. Dacă C este diferit de 1, atunci se va apela doar funcția get_max_sum_subsequence pentru a calcula suma maximă a unei subsecvențe nevide din lista a.

Funcția validate_input se asigură că datele de intrare corespund cerințelor problemei, iar dacă nu corespund, atunci programul se va opri și va fi afișat un mesaj corespunzător. Funcția read_input_file citește datele de intrare din fișierul specificat, iar funcția write_output_file scrie rezultatul în fișierul specificat.