Miawinator: Pagină nouă: Se dau numerele naturale `n` și `k`, precum și un șir `a[1]`, `a[2]` ,…, `a[n]` de numere naturale nenule. Din șir de poate elimina o singură secvență (eventual vidă) `a[i]`, `a[i+1]`, …, `a[j]` astfel că în șir rămân elementele `a[1]`, `a[2]`, …, `a[i-1]`, `a[j+1]`, …, `a[n]`. De exemplu, din șirul `a=(1,2,...`


2024-01-05T02:39:28Z
Pagină nouă: Se dau numerele naturale <code>n</code> și <code>k</code>, precum și un șir <code>a[1]</code>, <code>a[2]</code> ,…, <code>a[n]</code> de numere naturale nenule. Din șir de poate elimina o singură secvență (eventual vidă) <code>a[i]</code>, <code>a[i+1]</code>, …, <code>a[j]</code> astfel că în șir rămân elementele <code>a[1]</code>, <code>a[2]</code>, …, <code>a[i-1]</code>, <code>a[j+1]</code>, …, <code>a[n]</code>.  De exemplu, din șirul <code>a=(1,2,...
New page
Se dau numerele naturale <code>n</code> și <code>k</code>, precum și un șir <code>a[1]</code>, <code>a[2]</code> ,…, <code>a[n]</code> de numere naturale nenule. Din șir de poate elimina o singură secvență (eventual vidă) <code>a[i]</code>, <code>a[i+1]</code>, …, <code>a[j]</code> astfel că în șir rămân elementele <code>a[1]</code>, <code>a[2]</code>, …, <code>a[i-1]</code>, <code>a[j+1]</code>, …, <code>a[n]</code>.



De exemplu, din șirul <code>a=(1,2,3,4,5,7)</code> se poate elimina secvența <code>3,4,5</code> și rămâne <code>1,2,7</code>; sau se poate elimina secvența vidă și rămâne șirul inițial <code>1,2,3,4,5,7</code>; sau se poate elimina <code>1,2,3,4</code> și rămâne șirul <code>5,7</code>.



După eliminarea secvenței, elementele rămase formează un șir inno dacă aplicându-se operația <code>&</code> pe biți asupra lor rezultatul este un număr care are cel puțin <code>k</code> biți de <code>1</code> în baza <code>2</code>. De exemplu, dacă <code>a=(1,2,3,4,5,7)</code> și <code>k=2</code>, atunci prin eliminarea secvenței <code>1,2,3,4</code> rămân elementele <code>5,7</code>, iar <code>5 & 7 = 5</code>, care are <code>2</code> biți de <code>1</code> în baza <code>2</code>. Dar dacă se elimină secvența <code>3,4,5</code> atunci rămân elementele <code>1,2,7</code>, iar <code>1 & 2 & 7 = 0</code>, deci nu este șir inno.



= Cerința =

Să se determine în câte moduri se poate elimina o secvență astfel încât elementele rămase să formeze șir inno.



= Date de intrare =

Fișierul de intrare <code>input.txt</code> conține pe prima linie numerele naturale <code>n</code> și <code>k</code>. Pe linia a doua se află <code>n</code> numere naturale reprezentând elementele șirului.



= Date de ieșire =

Fișierul de ieșire <code>output.txt</code> va conține pe prima linie un singur număr natural reprezentând numărul de moduri de a elimina o secvență astfel încât șirul rămas să fie inno.



= Restricții și precizări =



* <code>3 ≤ n ≤ 200.000</code>;

* <code>1 ≤ k ≤ 29</code>;



== Exemplul 1 ==

input.txt:



4 2



10 7 5 15



output.txt:



5



Explicație:



Modalitățile sunt:



- se elimină <code>10</code> și rămâne șirul <code>7 5 15</code>, iar <code>7 & 5 & 15 = 5</code>, care are <code>2</code> biți de <code>1</code>



- se elimină <code>10 7</code> și rămâne șirul <code>5 15</code>, iar <code>5 & 15 = 5</code>, care are <code>2</code> biți de <code>1</code>



- se elimină <code>10 7 5</code> și rămâne șirul <code>15</code>, iar <code>15</code> are <code>4</code> biți de <code>1</code>



- se elimină <code>7 5</code> și rămâne șirul <code>10 15</code>, iar <code>10 & 15 = 10</code> are <code>2</code> biți de <code>1</code>



- se elimină <code>7 5 15</code> și rămâne șirul <code>10</code>, iar <code>10</code> are <code>2</code> biți de <code>1</code>



== Exemplul 2 ==

input.txt:



5 4



7 7 6 1 62



output.txt:



1



Explicație:



Singura posibilitate este eliminarea secvenței <code>7 7 6 1</code>. Rămâne doar numărul <code>62</code>, care are <code>5</code> biți de <code>1</code>.



== Exemplul 3 ==

input.txt:



999999999999 4



7 7 6 1 62



Output:



Invalid input constraints.



== Rezolvare ==

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

def verify_constraints(n, k):

    if not (3 <= n <= 200000 and 1 <= k <= 29):

        print("Invalid input constraints.")

        exit()



def count_bit(v):

    v = v - ((v >> 1) & 0x55555555)

    v = (v & 0x33333333) + ((v >> 2) & 0x33333333)

    c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24

    return c



def bsearch(p, u, key, k):

    m = 0

    while p < u:

        m = (p + u) // 2

        if dr[m] & key < k:

            p = m + 1

        else:

            u = m



    m = (p + u) // 2

    if dr[m] & key < k:

        m += 1

    return m



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

    n, k = map(int, fin.readline().split())

    verify_constraints(n,k)

    a = [0] + list(map(int, fin.readline().split()))

    st = [0] * (n + 1)

    dr = [0] * (n + 1)

    x = -1

    y = 0

    val = 0

    sol = 0



    st[1] = a[1]

    dr[n] = a[n]



    for i in range(2, n + 1):

        st[i] = st[i - 1] & a[i]



    for i in range(n - 1, 0, -1):

        dr[i] = dr[i + 1] & a[i]



    if count_bit(st[1]) < k:

        x = 0



    if count_bit(dr[n]) < k:

        y = n + 1



    if x < 0:

        x = 1

        i = 2

        while i <= n:

            if count_bit(st[i]) >= k:

                x = i

            i += 1



    if not y:

        y = n

        i = n - 1

        while i >= 1:

            if count_bit(dr[i]) >= k:

                y = i

            i -= 1



    if x == n:

        fout.write(str(n * (n + 1) // 2))

    elif x == 0 and y == n + 1:

        fout.write("0")

    elif 1 <= x < n and y == n + 1:

        fout.write(str(x))

    elif x == 0 and 1 < y <= n:

        fout.write(str(n - y + 1))

    elif x == 0 and y == 0:

        fout.write("1")

    else:

        sol = n - y + 1

        for i in range(1, x + 1):

            val = bsearch(y, n, st[i], k)

            sol += (n - val + 2)



        fout.write(str(sol))



</syntaxhighlight>
3758 - inno - Revision history
