https://codeforces.com/contest/1624/problem/C
시간 3초, 메모리 256MB

input :

• t (1 ≤ t ≤ 104)
• n (1 ≤ n ≤ 50)
• a1, a2, …, an (1 ≤ ai ≤ 109)

output :

• "YES" if you can make the array a become a permutation of numbers from 1 to n, "NO" otherwise.
  배열의 원소가 1 ~ n까지로 이루어지는 경우 "YES", 그렇지 않은 경우 "NO"를 출력하시오.

조건 :

• In one operation you can replace any element of the array ai with ⌊ai/2⌋, that is, by an integer part of dividing ai by 2 (rounding down).
  배열의 원소에 적용할 수 있는 연산으로 2로 나눈 후 내림 연산을 수행함.

---

연산의 횟수로는 0번 아무 것도 하지 않을 수도 있음.

다음 풀이

1. 연산을 수행하는 경우?
2. 동일한 원소인 경우?

결국 연산을 수행하긴 해야한다. 이 조건을 잘 생각해야 한다.
1 ~ n까지를 다 가지고 있을 때 "1" 원소의 개수가 2개 이상이 되는 경우 "NO"를 출력해야 한다.
동일한 원소가 있는 경우에는 2개 이상인 경우에 계속 연산을 수행한다.

위와 같은 조건을 가지고 계산을 한다면 옳은 답을 얻을 수 있다. 동일한 원소의 값을 계속 축적해나가는 방식이고 배열을 이루는 원소의 개수가 최대 50이기 떄문에 해당 원소가 최대값이고 50개가 있다 하더라도

log (10 ^ 9) * 50 => 450 밖에 안 나오는 걸 보면 충분히 연산을 수행해도 된다.

import sys
from math import floor

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    idx, total = [0] * (n + 1), 0

    for item in data:
        if item < n + 1:
            idx[item] += 1
            total += 1

    if idx[1] > 1:
        print("NO")
        continue

    while idx[1] <= 1 and idx[1:].count(0):
        for i in range(len(data)):
            item = data[i]

            if item == 1 or (item < n + 1 and idx[item] == 1):
                continue

            if item < n + 1 and idx[item] > 1:
                idx[item] -= 1
                data[i] = floor(item / 2)
                idx[data[i]] += 1
                continue

            data[i] = floor(item / 2)
            if data[i] < n + 1:
                idx[data[i]] += 1

    if idx[1] > 1:
        print("NO")
    else:
        print("YES")