2896 - binar1

Pentru a converti un număr din zecimal în binar îl vom împărți la 2 în mod repetat, până ce obținem câtul zero. Apoi vom colecta resturile obținute de la ultimul către primul. Aceste resturi sunt cifrele din reprezentarea binară a numărului dat, de la stânga la dreapta. De exemplu, 13(10) = 1101(2).

Cerința

Scrieți un program care, pentru un șir dat de n numere naturale, rezolvă următoarele cerințe:

1) Determină cel mai mare dintre cele n numere date ce are număr maxim de valori de 1 în reprezentarea binară.

2) Determină cea mai lungă secvență de numere care au număr egal de valori de 1 în reprezentarea binară. Dacă sunt mai multe astfel de secvențe de lungime maximă, se va alege cea mai din stânga. O secvență este un subșir de numere care apar pe poziții consecutive în șirul inițial.

Date de intrare

Fișierul de intrare input.txt conţine pe prima linie numărul C reprezentând cerința (1 sau 2), pe a doua linie numărul natural n, iar pe a treia linie n numere naturale separate prin câte un spațiu.

Date de ieșire

Dacă C = 1, atunci pe prima linie a fișierului de ieșire output.txt se va scrie numărul ce reprezintă răspunsul la cerința 1. Dacă C = 2, atunci pe prima linie a fișierului de ieșire output.txt se vor scrie, separate printr-un spațiu, lungimea maximă a secvenței determinate și poziția primului termen din secvență (se consideră că primul număr din cele n numere date se găsește pe poziția 1).

Restricții și precizări

• 1 ≤ n ≤ 1.000.000

Exemplul 1

input.txt:

1

7

16 12 3 5 14 13 11

output.txt:

14

Explicație:

16(10) = 10000(2); 12(10) = 1100(2); 3(10) = 11(2); 5(10) = 101(2); 14(10) = 1110(2); 13(10) = 1101(2); 11(10) = 1011(2);

Cel mai mare număr de valori de 1 dintr-o reprezentare binară este 3; cel mai mare număr ce are 3 de 1 în reprezentarea binară este 14.

Exemplul 2

input.txt:

2

7

16 12 3 5 14 13 11

output.txt:

3 2

Explicație:

Sunt două secvențe de lungime maximă de numere care au număr egal de valori de 1 în reprezentarea binară: 12 3 5 și 14 13 11. O vom alege pe cea mai din stânga, care are lungimea 3 și începe la poziția 2.

Exemplul 3

input.txt:

2

99999999999999

16 12 3 5 14 13 11

Output:

Input-ul nu convine conditiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> NM = 1000001

def verificare(n):

   if not(1<=n<=1000000):
       print("Input-ul nu convine conditiilor")
       exit()

def count_set_bits(num):

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

with open("input.txt", "r") as fin, open("output.txt", "w") as fout:

   c = int(fin.readline())
   n = int(fin.readline())

   verificare(n)

   l=list(map(int, fin.readline().split()))

   a = [0] * (n + 1)
   
   xmax = 0
   nr1max = 0
   
   for i in range(1, n + 1):
       x = l[i-1]
       aux = x
       nr1 = 0
       
       while aux > 0:
           nr1 += 1
           aux = aux & (aux - 1)
       
       if nr1 > nr1max or (nr1 == nr1max and x > xmax):
           nr1max = nr1
           xmax = x
       
       a[i] = nr1
   
   if c == 1:
       # cerinta 1
       fout.write(str(xmax))
   else:
       # cerinta 2
       lgm = 0
       lgc = 1
       pc = 1
       
       for i in range(2, n + 1):
           if a[i] == a[i - 1]:
               lgc += 1
           else:
               if lgc > lgm:
                   lgm = lgc
                   pm = pc
               lgc = 1
               pc = i
       
       if lgc > lgm:
           lgm = lgc
           pm = pc
       
       fout.write(f"{lgm} {pm}")

</syntaxhighlight>