2487 - countbits

Se consideră un șir de numere naturale f[1], f[2], …, f[n]. Fiecărui element al șirului i se calculează numărul biților de 1 din reprezentarea în baza 2. De exemplu, numărul 15 are 4 biți de 1 în baza 2.

Cerința

Să se determine numărul total de biți de 1 al tuturor numerelor din șir.

Date de intrare

Fișierul de intrare countbits.in conține pe prima linie numerele n, A, B, C, D, E, unde n este numărul elementelor șirului. Șirul se va genera astfel: f[1] = A, f[2] = B, apoi pentru orice i = 3..n, f[i] = 1 + (f[i-2] * C + f[i-1] * D) % E.

Date de ieșire

Fișierul de ieșire countbits.out va conține pe prima linie un singur număr, reprezentând numărul total de biți de 1 al tuturor numerelor din șir.

Restricții și precizări

3 ≤ n ≤ 15 000 000 3 ≤ A, B, C, D ≤ 100 000 000 3 ≤ E ≤ 1 000 000 000 Atenție la generarea elementelor șirului ==Exemplu==: countbits.in

4 7 11 15 19 8999 countbits.out

17

Rezolvare

<syntaxhighlight lang="python3" line="1"> def count_set_bits(num):

  count = 0
  while num:
      count += num & 1
      num >>= 1
  return count

Citire date de intrare

with open("countbits.in", "r") as file:

  n, A, B, C, D, E = map(int, file.readline().split())

Generare șir și calcul număr total de biți de 1

total_bits = 0 f = [A, B] for i in range(3, n + 1):

  next_element = 1 + (f[i - 2] * C + f[i - 1] * D) % E
  f.append(next_element)
  total_bits += count_set_bits(next_element)

Scrierea rezultatului în fișierul de ieșire

with open("countbits.out", "w") as file:

  file.write(str(total_bits) + "\n")

</syntaxhighlight>