AtCoder Regular Contest 184 A,B,C問題メモ

n, m, q = map(int, input().split())
imitation = []
for i in range(50):
    s = i * 20 + 1
    zero = []
    one = []
    for j in range(s + 1, s + 20):
        print(f'? {s} {j}')
        res = input()
        if res == '0':
            zero.append(j)
        elif res == '1':
            one.append(j)
        else:
            exit()
    if len(zero) >= 10:
        # sとあわせて同種11枚
        imitation.extend(one)
    elif len(one) >= 11:
        imitation.append(s)
        imitation.extend(zero)
    else:
        # ちょうど10枚ずつ
        if i == 0:
            t = 21
        else:
            t = 1
        for j in range(s, s + 19):
            print(f'? {t} {j}')
            res = input()
            if res == '0':
                pass
            elif res == '1':
                imitation.append(j)
            else:
                exit()
        if len(imitation) < m:
            imitation.append(s + 19)

    if len(imitation) == m:
        break

    if i == 48 and len(imitation) == 0:
        s = 981
        t = 1
        for j in range(s, s + 19):
            print(f'? {t} {j}')
            res = input()
            if res == '0':
                pass
            elif res == '1':
                imitation.append(j)
            else:
                exit()
        if len(imitation) < m:
            imitation.append(s + 19)
        break

print('!', *imitation)

from bisect import bisect_right

import numpy as np
from numba import njit


@njit
def precompute():
    # ↓2倍, →3倍 という2次元表を考える
    #  1  3  9 27 81 ...
    #  2  6 18 54 ...
    #  4 12 36
    #  8 24 72

    # この表に出現する x <= 10^9 の各 x につき、
    # x 以下の全ての数を逆L字型（┌）のスタンプで塗るための最小個数を求めたい。
    # 出現する数の個数は300個程度と十分少ないため、事前計算して埋め込む。

    # x を決めたら、以下のDPで求められる。
    # DP[i,S] = i+1 行目以降の必要な数は全て塗られ、i 行目で塗られている列が集合 S である場合の最小回数
    # ※ i の大きい方から更新

    def loga(a, x):
        # 切り捨てる対数
        k = 1
        e = 0
        while k * a <= x:
            k *= a
            e += 1
        return e

    def pop_count_32(n):
        c = (n & 0x55555555) + ((n >> 1) & 0x55555555)
        c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
        c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f)
        c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff)
        c = (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff)
        return c

    n = 10 ** 9
    n_log2 = loga(2, n) + 1
    n_log3 = loga(3, n) + 1
    table = np.ones((n_log2, n_log3), np.int64)
    for j in range(1, n_log3):
        table[0, j] = table[0, j - 1] * 3
    for i in range(1, n_log2):
        table[i, :] = table[i - 1, :] * 2
        table[i, table[i, :] > n] = 0

    print(table)

    INF = 1 << 30
    result = {}
    for ti in range(n_log2):
        for tj in range(n_log3):
            x = table[ti, tj]
            if x == 0:
                break
            print(x)
            s = loga(2, x)
            limit = []
            for i in range(s, -1, -1):
                limit.append(loga(3, x >> i) + 1)
            dp = np.full(1 << limit[0], INF, np.int32)
            dp[0] = 0
            for i in range(s, 0, -1):
                lim0 = limit[s - i]
                lim1 = limit[s - i + 1]
                ndp = np.full(1 << lim1, INF, np.int32)
                mask0 = (1 << lim0) - 1
                mask1 = (1 << lim1) - 1
                for bitset in range(1 << lim0):
                    remain = bitset ^ mask0
                    sub_bitset = bitset
                    while True:
                        stamp = remain | sub_bitset
                        cnt = pop_count_32(stamp)
                        nxt = (stamp | (stamp << 1)) & mask1
                        ndp[nxt] = min(ndp[nxt], dp[bitset] + cnt)
                        if sub_bitset == 0:
                            break
                        sub_bitset = (sub_bitset - 1) & bitset

                dp = ndp

            result[x] = dp[-1]

    print(result)


# 事前計算
# precompute()

# 埋め込み（省略）
result23 = {
    1: 1, 3: 1, 9: 3, 27: 5, 81: 8, 243: 11, 729: 16, 2187: 20, 6561: 25, 19683: 31, 59049: 37, 177147: 44,
    # ...
}


def solve(n):
    if n <= 3:
        return 1
    if n <= 4:
        return 2
    if n <= 6:
        return 3

    xxx, counts = zip(*sorted(result23.items()))

    # 整数 k によって floor(N/k) と表せる整数の集合を求める
    lo = []
    hi = []
    for i in range(1, int(n ** 0.5) + 1):
        if i * i > n:
            break
        lo.append(i)
        h = n // i
        if h != i:
            hi.append(h)
    hi.reverse()
    lo.extend(hi)
    qqq = lo
    q_len = len(qqq)
    qqq_idx = {}
    for i in range(q_len):
        qqq_idx[qqq[i]] = i

    # qqq にある数 q に付き、「q以下のうち2と3の倍数でない数」の個数をLucyDPで求める
    dp0 = [q - 1 for q in qqq]
    for p in (2, 3):
        l = qqq_idx[p - 1]
        for j in range(q_len - 1, -1, -1):
            q = qqq[j]
            if p * p > q:
                break
            k = qqq_idx[q // p]
            dp0[j] -= dp0[k] - dp0[l]
    m = len(qqq)
    for i in range(2, m):
        dp0[i] -= 2
    dp0[1] -= 1
    ans = counts[bisect_right(xxx, n) - 1]
    for i in range(m - 1):
        c = dp0[i + 1] - dp0[i]
        ans += c * counts[bisect_right(xxx, n // qqq[i + 1]) - 1]
    return ans


n = int(input())

ans = solve(n)
print(ans)

from bisect import bisect_right

import numpy as np
from numba import njit


@njit('(i8,)')
def calc_patterns(x):
    """ x 以下の 2^a * 3^b という素因数分解で表される数を全て加えるまでの最少操作回数 """

    # x 以下の 2^a*3^b 数が全て現れる ↓2倍, →3倍 という2次元表を考える。
    #  1  3  9 27 81 ...
    #  2  6 18 54 ...
    #  4 12 36
    #  8 24 72

    # 以下のDPで求められる。
    # DP[i,S] = i+1 行目以降の必要な数は全て塗られ、i 行目で少なくとも塗られている列が集合 S である場合の最小回数
    # ※ i の大きい方から更新

    # DP[i+1,S]→DP[i,T] の遷移において、Sで埋まっていない部分を最低限埋めた時のi行目を S' とすると、S' ⊃ T である T に遷移できる。
    # これは、とりあえず DP[i,S'] のみ更新しておいて、最後に高速ゼータ変換をおこなうことで高速化できる。

    def loga(a, x):
        # 切り捨てる対数
        k = 1
        e = 0
        while k * a <= x:
            k *= a
            e += 1
        return e

    def pop_count_32(n):
        c = (n & 0x55555555) + ((n >> 1) & 0x55555555)
        c = (c & 0x33333333) + ((c >> 2) & 0x33333333)
        c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f)
        c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff)
        c = (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff)
        return c

    if x == 1:
        return 1

    INF = 1 << 30
    s = loga(2, x)
    limit = []
    for i in range(s, -1, -1):
        limit.append(loga(3, x >> i) + 1)
    dp = np.full(1 << limit[0], INF, np.int32)
    dp[0] = 0
    for i in range(s, 0, -1):
        lim0 = limit[s - i]
        lim1 = limit[s - i + 1]
        ndp = np.full(1 << lim1, INF, np.int32)
        mask0 = (1 << lim0) - 1
        mask1 = (1 << lim1) - 1
        for bitset in range(1 << lim0):
            if dp[bitset] == INF:
                continue
            remain = bitset ^ mask0
            new_bitset = (remain | (remain << 1)) & mask1
            ndp[new_bitset] = min(ndp[new_bitset], dp[bitset] + pop_count_32(remain))
        dp = ndp
        for j in range(lim1):
            bit = 1 << j
            for k in range(1 << lim1):
                if k & bit == 0:
                    dp[k] = min(dp[k], dp[k | bit])

    return dp[-1]


def solve(n):
    # N 以下の 2^a * 3^b と表せる数を列挙
    q = [1]
    while q[-1] * 2 <= n:
        q.append(q[-1] * 2)
    factor23 = []
    while q:
        x = q.pop()
        factor23.append(x)
        if x * 3 <= n:
            q.append(x * 3)
    factor23.sort()

    # 整数 k によって floor(N/k) と表せる整数の集合を求める
    lo = []
    hi = []
    for i in range(1, int(n ** 0.5) + 1):
        if i * i > n:
            break
        lo.append(i)
        h = n // i
        if h != i:
            hi.append(h)
    hi.reverse()
    lo.extend(hi)
    qqq = lo
    q_len = len(qqq)
    qqq_idx = {}
    for i in range(q_len):
        qqq_idx[qqq[i]] = i
    m = len(qqq)

    cache = {}
    k = factor23[bisect_right(factor23, n) - 1]
    ans = cache[k] = calc_patterns(k)
    for i in range(m - 1):
        q0 = qqq[i]
        q1 = qqq[i + 1]
        # q0 より大きく q1 以下の、2の倍数でも3の倍数でも無いものの数
        d0, m0 = divmod(q0, 6)
        d1, m1 = divmod(q1, 6)
        t0 = d0 * 2 + int(m0 >= 1) + int(m0 >= 5)
        t1 = d1 * 2 + int(m1 >= 1) + int(m1 >= 5)
        k = factor23[bisect_right(factor23, n // q1) - 1]
        if k not in cache:
            cache[k] = calc_patterns(k)
        ans += (t1 - t0) * cache[k]
    print(len(cache))
    return ans


n = int(input())

ans = solve(n)
print(ans)

def solve(aaa):
    n = len(aaa)
    if n == 0:
        return 0
    if n == 1:
        return 1
    res1 = 0
    res3 = 0
    even0 = []
    even2 = []
    for a in aaa:
        if a & 1:
            if a & 2:
                res3 += 1
            else:
                res1 += 1
        else:
            even0.append(a >> 1)
            even2.append((a + 2) >> 1)
    res1 += solve(even2)
    res3 += solve(even0)
    return max(res1, res3)


n = int(input())
aaa = list(map(int, input().split()))
ans0 = solve(aaa)
ans1 = solve([a + 1 for a in aaa])
ans = max(ans0, ans1)
print(ans)