Editing 2896 - binar1

Pentru a converti un număr din zecimal în binar îl vom împărți la <code>2</code> î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, <code>13(10)</code> <code>= 1101(2)</code>.

= 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 <code>n</code> numere date ce are număr maxim de valori de <code>1</code> în reprezentarea binară.

2) Determină cea mai lungă secvență de numere care au număr egal de valori de <code>1</code> î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 <code>input.txt</code> conţine pe prima linie numărul <code>C</code> reprezentând cerința (<code>1</code> sau <code>2</code>), pe a doua linie numărul natural <code>n</code>, iar pe a treia linie <code>n</code> numere naturale separate prin câte un spațiu.

= Date de ieșire =
Dacă <code>C = 1</code>, atunci pe prima linie a fișierului de ieșire <code>output.txt</code> se va scrie numărul ce reprezintă răspunsul la cerința <code>1</code>. Dacă <code>C = 2</code>, atunci pe prima linie a fișierului de ieșire <code>output.txt</code> 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 <code>n</code> numere date se găsește pe poziția <code>1</code>).

= Restricții și precizări =

* <code>1 ≤ n ≤ 1.000.000</code>

== Exemplul 1 ==
input.txt:

1

7

16 12 3 5 14 13 11

output.txt:

14

Explicație:

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

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

== 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 <code>1</code> în reprezentarea binară: <code>12 3 5</code> și <code>14 13 11</code>. O vom alege pe cea mai din stânga, care are lungimea <code>3</code> și începe la poziția <code>2</code>.

== 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>