101AC - ABC069C: 4-adjacent

ABC069-C (400 points)

問題

長さ の数列 が与えられたときに, 各 について が の倍数であるように要素を並び替えられるかを判定.

• 
• 
• 入力は全て整数

方針

• 奇数の前後は必ず の倍数
• の倍数でない偶数の前後は必ず偶数
• 邪魔なのは奇数なので, 奇数と の倍数を先に並べていく
• 奇数, の倍数, 奇数, の倍数, 奇数, ... となり, 最後が..., の倍数, 奇数, 4の倍数でない数 となった時点で終了.
• 奇数の個数 の倍数の個数 が必要条件
• 奇数の個数 の倍数の個数 の場合は, の倍数でない偶数がなければOK

# input
N = int(input())
a = list(map(int, input().split()))

# 4の倍数, 4の倍数でない偶数, 奇数の数
i, j, k = 0, 0, 0

for n in range(N):
    if a[n] % 4 == 0:
        i += 1
    elif a[n] % 2 == 0:
        j += 1
    else:
        k += 1

if k >= i + 2:
    print('No')
elif k == i + 1 and j >= 1:
    print('No')
else:
    print('Yes')