ABC100 C - *3 or /2

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    ans = 0
    for a in A:
        while a % 2 == 0:
            ans += 1
            a //= 2

    print(ans)


if __name__ == '__main__':
    main()

考え方

数列Aのすべての値に対して 「2で割る」または「3倍にする」を行う。
上記の操作で「全ての整数に対して3倍にする」ことはできないので、
必ずどこか１つの整数を「2で割る」必要がある。
つまり、「２で割る」ことが出来る整数がなくなった時点が操作の終了となる。

この条件から、「２で割る」ことが出来る回数を数えることで回答が得られる。
何度「２で割る」ことができるかを数列Aの中からすべての値に対して試すことで、
「２で割る」ことが出来る回数を求める。