Problem:


Score : 700 points

Problem Statement

Aoki loves numerical sequences and trees.

One day, Takahashi gave him an integer sequence of length N, a_1, a_2, ..., a_N, which made him want to construct a tree.

Aoki wants to construct a tree with N vertices numbered 1 through N, such that for each i = 1,2,...,N, the distance between vertex i and the farthest vertex from it is a_i, assuming that the length of each edge is 1.

Determine whether such a tree exists.

Constraints

2 ≦ N ≦ 100

1 ≦ a_i ≦ N-1

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

If there exists a tree that satisfies the condition, print Possible. Otherwise, print Impossible.

Sample Input 1

5
3 2 2 3 3

Sample Output 1

Possible

The diagram above shows an example of a tree that satisfies the conditions. The red arrows show paths from each vertex to the farthest vertex from it.

Sample Input 2

3
1 1 2

Sample Output 2

Impossible

Sample Input 3

10
1 2 2 2 2 2 2 2 2 2

Sample Output 3

Possible

Sample Input 4

10
1 1 2 2 2 2 2 2 2 2

Sample Output 4

Impossible

Sample Input 5

6
1 1 1 1 1 5

Sample Output 5

Impossible

Sample Input 6

5
4 3 2 3 4

Sample Output 6

Possible



Sample input:
5
3 2 2 3 3


Sample output:
Possible

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]

c = Counter()
for x in a:
    c[x] += 1

m = max(a)
chk = True
if m % 2:
    for i in range(1, m+1):
        if i < m//2+1 and c[i] > 0:
            chk = False
        elif i == m//2+1 and c[i] != 2:
            chk = False
        elif i > m//2+1 and c[i] < 2:
            chk = False
else:
    for i in range(1, m+1):
        if i < m//2 and c[i] > 0:
            chk = False
        elif i == m//2 and c[i] != 1:
            chk = False
        elif i > m//2 and c[i] < 2:
            chk = False

print("Possible" if chk else "Impossible")

Submission status: Accepted

Solution code:
import sys
n=int(input())
a=list(map(int,input().split()))
a.sort()
maxlen=a[-1]
thing={}
for i in range(n):
  if a[i] in thing:
    thing[a[i]]+=1
  else:
    thing[a[i]]=1
    
if maxlen%2==1:
  if not (maxlen+1)//2 in thing:
    print('Impossible')
    sys.exit()
  if thing[(maxlen+1)//2]!=2:
    print('Impossible')
    sys.exit()
if maxlen%2==0:
  if not (maxlen+1)//2 in thing:
    print('Impossible')
    sys.exit()
  if thing[(maxlen+1)//2]!=1:
    print('Impossible')
    sys.exit()
for i in thing:
  if i==(maxlen+1)//2:
    continue
  if i<(maxlen+1)//2:
    print('Impossible')
    sys.exit()
  if thing[i]<2:
    print('Impossible')
    sys.exit()
for i in range((maxlen+1)//2,maxlen):
  if not i in thing:
    print('Impossible')
    sys.exit()
print('Possible')

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A = np.array(read().split(), np.int32)[1:]

def f(A):
    diam = A.max()
    if np.any(2 * A < diam):
        return False
    count = np.bincount(A)
    if diam & 1:
        if count[(diam + 1) // 2] != 2:
            return False
        return np.all(count[(diam + 1) // 2:] >= 2)
    if count[diam // 2] != 1:
        return False
    return np.all(count[diam // 2 + 1:] >= 2)

print('Possible' if f(A) else 'Impossible')

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort(reverse=True)
    res = []
    k = a[0]
    d = defaultdict(int)
    for i in a:
        d[i] += 1
    if k&1:
        if a[-1] <= k//2:
            print("Impossible")
            exit()
        if d[k//2+1] != 2:
            print("Impossible")
            exit()
        for i in range(k//2+2,k+1):
            if d[i] < 2:
                print("Impossible")
                exit()
    else:
        if a[-1] < k//2:
            print("Impossible")
            exit()
        if d[k//2] != 1:
            print("Impossible")
            exit()
        for i in range(k//2+1,k+1):
            if d[i] < 2:
                print("Impossible")
                exit()
    print("Possible")



    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
x = sorted(set(a))
if (max(a) - 1) // 2 + 1 == min(a):
  if max(a) & 1:
    m = m = a.count(x[0]) != 2
    for i in range(x[0],x[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
  else:
    m = a.count(x[0]) != 1
    for i in range(x[0]+1,x[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

mx = max(A)
cnt = [0] * 200

for i in A:
  cnt[i] += 1

inc = []
NN = mx + 1
while NN > 0:
  tm = min(2, NN)
  cnt[mx] -= tm
  # print(NN, cnt)
  if cnt[mx] < 0:
    print("Impossible")
    exit(0)
  inc.append(mx)
  mx -= 1
  NN -= tm

for i in inc[:-1]:
  cnt[i] = 0

for i in cnt:
  if i > 0:
    print("Impossible")
    exit(0)

print("Possible")

Submission status: Accepted

Solution code:
N=int(input())
a=list(map(int,input().split()))
M=max(a)
data=[0 for i in range(N)]
for i in range(N):
    data[a[i]]+=1

if M%2==0:
    check="Possible"
    for i in range(M//2+1,M+1):
        if data[i]<2:
            check="Impossible"
    if data[M//2]!=1:
        check="Impossible"
    print(check)
else:
    check="Possible"
    for i in range((M+1)//2+1,M+1):
        if data[i]<2:
            check="Impossible"
    if data[(M+1)//2]!=2:
        check="Impossible"
    print(check)

Submission status: Accepted

Solution code:
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
l=L()
l.sort()
def im():
    print("Impossible")
    quit()
def po():
    print("Possible")
    quit()
if l[0]!=(l[-1]+1)//2:
    im()
import collections
c=collections.Counter(l)
if l[-1]%2:
    if c[l[0]]!=2:
        im()
    for i in range(l[0]+1,l[-1]+1):
        if c[i]<2:
            im()
    po()
if c[l[0]]!=1:
    im()
for i in range(l[0]+1,l[-1]+1):
    if c[i]<2:
        im()
po()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
a.sort()
m, n = max(a), min(a)
if n * 2 == m:
    cnt = [0] * (m - n + 1)
    for i in range(N):
        cnt[a[i] - n] += 1
    if cnt[0] == 1 and all(c >= 2 for c in cnt[1:]):
        print('Possible')
    else:
        print('Impossible')
elif n * 2 - 1 == m:
    cnt = [0] * (m - n + 1)
    for i in range(N):
        cnt[a[i] - n] += 1
    if cnt[0] == 2 and all(c >= 2 for c in cnt[1:]):
        print('Possible')
    else:
        print('Impossible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N,*A = map(int, open(0).read().split())
Cnt = Counter(A)
if Cnt[1]>1:
  if N==2:
    print('Possible')
  else:   
    print('Impossible')
  sys.exit()
m = max(A)
S = set()
for i in range(m):
  S.add(max(m-1-i,i+1))
for a in A:
  if a not in S:
    print('Impossible')
    sys.exit()
for c in S:
  if Cnt[c]==0:
    print('Impossible')
    sys.exit()
n = min(A)
if m%2==1:
  if Cnt[n]!=2:
    print('Impossible')
    sys.exit()
else:
  if Cnt[n]!=1:
    print('Impossible')
    sys.exit()
print('Possible')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()

import collections
d = collections.Counter(a)

if -(-max(a)//2) != min(a):
    print("Impossible")
    exit()

if max(a)%2==0:
    if d[min(a)]!=1:
        print("Impossible")
        exit()
else:
    if d[min(a)]!=2:
        print("Impossible")
        exit()

for num in range(min(a)+1,max(a)+1):
    if d[num]<2:
        print("Impossible")
        exit()

print("Possible")

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
k = max(A)
m = min(A)
C = Counter(A)
if m < (k+1)//2:
  print("Impossible")
else:
  if k & 1:
    for i in range((k+3)//2, k+1):
      if i not in C or C[i] < 2:
        print("Impossible")
        exit()
    if not (k+1)//2 in C or C[(k+1)//2] != 2:
      print("Impossible")
      exit()
  else:
    for i in range(1+k//2, k+1):
      if i not in C or C[i] < 2:
        print("Impossible")
        exit()
    if k//2 not in C or C[k//2] != 1:
      print("Impossible")
      exit()
  print("Possible")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = max(a)
p = [0]*(t+1)
for x in a:
  p[x] += 1
if t%2:
  if any(p[:t//2+1]) or p[t//2+1] != 2 or min(p[t//2+1:]) < 2:
    print('Impossible')
  else:
    print('Possible')
else:
  if any(p[:t//2]) or p[t//2] != 1 or min(p[t//2+1:]) < 2:
    print('Impossible')
  else:
    print('Possible')

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=Counter(list(map(int,input().split())))
b=[]
for i in a:
    b.append([i,a[i]])
b.sort()
x=b[-1][0]
if b[0][0]!=(x+1)//2:
    print("Impossible")
    exit()
if not(x%2==0 and b[0][1]==1 or x%2==1 and b[0][1]==2):
    print("Impossible")
    exit()
if x>n-1:
    print("Impossible")
    exit()
n=len(b)
cnt=2
k=b[0][0]  
# print(b)
for i in range(1,n):
    if b[i][1]<2 or b[i][1]<cnt or b[i][0]!=k+1:
        # print(i,b[i][1]<2,b[i][1]<cnt,b[i][0]!=k+1)
        print("Impossible")
        exit()
    b[i][1]=cnt
    k+=1
print("Possible")

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
if a[0]!=a[1]:
  print("Impossible")
  exit()
m=[0]*n
for i in range(1,a[0]):m[max(i,a[0]-i)]+=1
for i in a:m[i]-=1
for i in m:
  if i>0:print("Impossible");exit()
if m[0--a[0]//2]!=0 and a[0]>1:print("Impossible");exit()
print("Possible")

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

def canMake():
    if N == 2:
        return A == [1, 1]

    cntA = Counter(A)
    mi = min(A)
    mx = max(A)

    if mi < mx // 2:
        return False

    if mx % 2 == 0 and cntA[mi] > 1:
        return False
    if mx % 2 == 1 and cntA[mi] > 2:
        return False

    for i in range(mi + 1, mx + 1):
        if cntA[i] < 2:
            return False

    return True

print('Possible' if canMake() else 'Impossible')

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    N,*A=map(int, open(0).read().split())
    ans=True
    C=Counter(A)
    m=min(A)
    M=max(A)
    if C[m]>2:
        ans=False
    if N>2 and m==1:
        if C[1]!=1:
            ans=False
    if C[m]==1:
        if m*2!=M:
            ans=False
    else:
        if m*2-1!=M:
            ans=False
    for i in range(m+1,M+1):
        if i not in C or C[i]<2:
            ans=False
    print("Possible" if ans else "Impossible")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#C
n = int(input())
a = [int(i) for i in input().split()]

diameter = max(a)
mini     = min(a)

dic = dict()
for v in a:
    if v in dic:
        dic[v] += 1
    else:
        dic[v] = 1
#print(dic)
        
        
for i in range(diameter+1):
    v = max(i, diameter - i)
    #print(v)
    if (v not in dic) or dic[v]==0:
        print("Impossible")
        #print(v)
        break
    else:
        dic[v] -= 1
else:
    threshold = (diameter+1)//2 #girigiri out
    if threshold < mini: #somosomo tiisaike-su
        print("Impossible")
    elif dic[mini]>0:
        print("Impossible")
    else:
        print("Possible")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
a.sort()
d = [[10 ** 6 for _ in range(N)] for _ in range(N)]
#print(a)

if N == 2:
  if a != [1, 1]:
    print("Impossible")
    exit(0)
else:
  if max(a) < 2:
    print("Impossible")
    exit(0)

mn = min(a)
mnl = []
for i in range(N):
  if a[i] == mn: mnl.append(i)
if len(mnl) > 2:
  print("Impossible")
  exit(0)
for i in range(len(mnl)):
  for j in range(len(mnl)): d[i][j] = 1

for x in range(min(a), max(a)):
  l = []
  r = []
  for i in range(N):
    if a[i] == x: l.append(i)
  for i in range(N):
    if a[i] == x + 1: r.append(i)
  if len(l) == 0:
    print("Impossible")
    exit(0)
  for i in range(len(r)):
    y = l[i % len(l)]
    z = r[i]
    d[y][z] = 1
    d[z][y] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][k] + d[k][j], d[i][j])

#print(d)
for i in range(N):
  if a[i] != max(d[i]):
    print("Impossible")
    exit(0)
print("Possible")

Submission status: Accepted

Solution code:
_,a=open(0)
*a,=map(int,a.split())
m=max(a)
c=[0]*-~m
for i in a:c[i]+=1
print(sum(c[:-~m//2])<1and~m%-2+2==c[-~m//2]and all(c[i+1]>1for i in range(m//2,m))and'Possible'or'Impossible')

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
D={}
for i in range(N):
    if L[i] not in D:
        D[L[i]]=1
    else:
        D[L[i]]+=1
L=list(D.items())
L.sort()
#print(L)

if L[-1][1]<=1:
    print("Impossible")
    exit()
if L[-1][0]%2==1:
    if L[-1][0]//2+1==L[0][0] and L[0][1]==2:
        for i in range(1,len(L)):
            if L[i][0]==L[i-1][0]+1 and L[i][1]>=2:
                continue
            else:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")
else:
    if L[-1][0]//2==L[0][0] and L[0][1]==1:
        for i in range(1,len(L)):
            if L[i][0]==L[i-1][0]+1 and L[i][1]>=2:
                continue
            else:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")

Submission status: Accepted

Solution code:
import sys
N = int(input())
a = list(map(int, input().split()))
count = [0]*N
for ai in a:
    count[ai]+=1
m = max(a)
if min(a)<m-m//2:
    print('Impossible')
    sys.exit()
flag = True
for i in range(m, m-m//2-1, -1):
    if m%2 == 0 and i == m//2:
        if count[i] != 1:
            flag = False
            break
    elif m%2 == 1 and i == m//2+1:
        if count[i] != 2:
            flag = False
            break
    else:
        if count[i] <= 1:
            flag = False
            break
if flag:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
x=max(a)
c=Counter(a)
flg=1
for i in range((x+1)//2,x+1):
  if i == (x+1)//2:
    if x%2==0:
      if c[i]!=1:
        flg=0
    else:
      if c[i]!=2:
        flg=0
  else:
    if c[i]<=1:
      flg=0
if flg:
  print("Possible")
else:
  print("Impossible")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = sorted(Counter(A).items())

if C[0][1] > 2:
    print('Impossible')
    exit()

is2src = C[0][1] == 2
src = C[0][0]
depth = src - is2src + 1

if len(C) != depth:
    print('Impossible')
    exit()

for i, (k, v) in enumerate(C[1:], 1):
    prevk, prevv = C[i-1]
    if k != prevk + 1:
        print('Impossible')
        exit()
    if 2 > v:
        print('Impossible')
        exit()
print('Possible')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = sorted(Counter(A).items())
M = len(C)

if C[0][1] > 2:
    print('Impossible')
    exit()

is2src = C[0][1] == 2
src = C[0][0]
depth = src - is2src + 1

if not is2src and C[1][1] < 2:
    print('Impossible')
    exit()

if len(C) != depth:
    print('Impossible')
    exit()

for i, (k, v) in enumerate(C[1:], 1):
    prevk, prevv = C[i-1]
    if k != prevk + 1:
        print('Impossible')
        exit()
    if 2 > v:
        print('Impossible')
        exit()
print('Possible')

Submission status: Accepted

Solution code:
from collections import Counter

N, *A = map(int, open(0).read().split())

C = Counter(A)
ma = max(C)
mi = min(C)

if (ma == 2 * mi and C[ma] >= 2 and C[mi] == 1) or \
    (ma == 2 * mi - 1 and C[ma] >= 2 and C[mi] == 2):
    if any(C[i] < 2 for i in range(mi + 1, ma)):
        print("Impossible")
    else:
        print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
from collections import Counter as C
n=int(input())
a=sorted(C(list(map(int,input().split()))).items())
d=0
if a[-1][0]%2==0:
    d=1
q=1
for i in range(len(a)-1,-1,-1):
    if d:
        if a[i][0]==a[-1][0]//2 and a[i][1]!=1:
            q=0
            break
        elif a[i][0]<a[-1][0]//2:
            q=0
            break
        elif a[i][0]!=a[-1][0]+i-len(a)+1:
            q=0
            break
        elif a[i][1]<2 and i!=0:
            q=0
            break
    else:
        if a[i][0]<(a[-1][0]+1)//2:
            q=0
            break
        elif a[i][0]!=a[-1][0]+i-len(a)+1:
            q=0
            break
        elif a[i][0]==(a[-1][0]+1)//2 and a[i][1]!=2:
            q=0
            break
        elif a[i][1]<2:
            q=0
            break
if q:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:

N = int(input())

a = list(map(int,input().split()))
maxi = max(a)

dic = {}

for i in range(N):

    if a[i] not in dic:
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1

flag = True

if maxi % 2 == 0:

    for i in range(maxi + 1):

        if i < maxi // 2 and i in dic:
            flag = False

        if i == maxi // 2 and (i not in dic or dic[i] != 1):
            flag = False

        if i > maxi // 2 and (i not in dic or dic[i] < 2):
            flag = False

else:

    for i in range(maxi + 1):

        if i <= maxi // 2 and i in dic:
            flag = False

        if i == maxi // 2 + 1 and (i not in dic or dic[i] != 2):
            flag = False

        if i > maxi // 2 + 1 and (i not in dic or dic[i] < 2):
            flag = False

if flag:
    print ("Possible")
else:
    print ("Impossible")

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))

A.sort()
C = collections.Counter(A)

mx = A[-1]
mn = A[0]

flag = True

if mx % 2 == 0:
    if mn != mx // 2:
        flag = False
    if C[mn] != 1:
        flag = False
else:
    if mn != mx // 2 + 1:
        flag = False
    if C[mn] != 2:
        flag = False

for i in range(mn + 1, mx + 1):
    if C[i] < 2:
        flag = False
        break

if flag:
    print("Possible")
else:
    print("Impossible")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from collections import defaultdict
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    D=defaultdict(int)
    for a in A: D[a]+=1

    m=max(A)
    B=list(range(m//2+1,m+1))*2
    if(m&1==0): B.append(m//2)

    for b in B:
        if(D[b]==0):
            print("Impossible")
            return
        D[b]-=1

    s=min(B)
    for key,val in D.items():
        if(val==0): continue
        if(not (s+1<=key<=m)):
            print("Impossible")
            return

    print("Possible")
resolve()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・直径の長さをdとする。だいたい、半径より下の長さは存在できない
・だいたいd/2より上は任意に足せる。ただし中心は1組のみ
"""

N,*A = map(int,read().split())

def test(A):
    D = max(A)
    r = (D+1)//2
    counter = [0] * (D+1)
    for x in A:
        counter[x] += 1
    if (D&1) and (counter[r] != 2):
        return False
    if (not (D&1)) and (counter[r] != 1):
        return False
    if any(x < r for x in A):
        return False
    if any(counter[x] <= 1 for x in range(r+1,D+1)):
        return False
    return True

answer = 'Possible' if test(A) else 'Impossible'

print(answer)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]+[0]
m=max(A)
import collections
C=collections.Counter(A)
chk=True
if m%2==0:
  for i in range(m//2,m+1):
    if i==m//2:
      if C[i]!=1:
        chk=False
    else:
      if C[i]<2:
        chk=False
else:
  for i in range((m+1)//2,m+1):
    if i==(m+1)//2:
      if C[i]!=2:
        chk=False
    else:
      if C[i]<2:
        chk=False
print("Possible" if chk else "Impossible")

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans='Possible'
n=I()
a=LI()
M=max(a)
m=min(a)
c=[0]*(M+1)
for i in range(n):
    c[a[i]]+=1
    
if all([c[i]>=2 for i in range(m+1,M+1)]):
    0
else:
    ans='Impossible'

if c[m]!=1+M%2:
    ans='Impossible'
    
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 +10 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase

#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

ans='Possible'
n=I()
a=LI()
M=max(a)
m=min(a)
c=[0]*(M+1)
for i in range(n):
    c[a[i]]+=1
if sum([min(c[i],1) for i in range(m,M+1)])!=M-m+1:
    ans='Impossible'
if c[m]!=1+M%2:
    ans='Impossible'
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import Counter as ct
    n = int(input())
    a = list(map(int, input().split()))
    c = ct(a)
    min_a = min(a)
    max_a = max(a)
    if min_a == 1:
        if c[min_a] == 1:
            pass
        elif a == [1, 1]:
            print("Possible")
            return 0
        else:
            print("Impossible")
            return 0
    if c[min_a] == 1 and (max_a+1)//2 > min_a:
        print("Impossible")
        return 0
    if c[min_a] == 2 and (max_a+2)//2 > min_a:
        print("Impossible")
        return 0
    if c[min_a] > 2:
        print("Impossible")
        return 0
    for i in range(min_a+1, max_a+1):
        if c[i] < 2:
            print("Impossible")
            return 0
    print("Possible")
main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
a = [int(i) for i in input().split()]

def solve() :
    cnt = list(Counter(a).items())
    cnt.sort()
    
    if cnt[0][1] == 1 and cnt[-1][0] != 2 * cnt[0][0] :
        return 'Impossible'
    if cnt[0][1] == 2 and cnt[-1][0] != 2 * cnt[0][0] - 1 :
        return 'Impossible'
    if cnt[0][1] > 2 :
        return 'Impossible'

    for i in range(1, len(cnt)) :
        if cnt[i][0] != cnt[i-1][0] + 1 :
            return 'Impossible'
        if cnt[i][1] < 2 :
            return 'Impossible'
            
    return 'Possible'
    
print(solve())

Submission status: Accepted

Solution code:
import numpy as np

def checker(n ,da):
    mx = max(da)
    mi = min(da)
    if n == 2:
        return (da == [1, 1])
    if mx < 2 or n <= mx: return False
    arr = np.zeros(mx + 1, dtype=int)
    for i in range(n):
        arr[da[i]] += 1
    if mx % 2:
        if arr[mi] > 2 or (mx + 1) // 2 != mi:
            return False
    else:
        if arr[mi] > 1 or mx // 2 != mi:
            return False
    for i in range(mi, mx):
        if arr[i + 1] < 2:
            return False
    return True

    

def main():
    n = int(input())
    da = list(map(int,input().split()))
    print('Possible') if checker(n, da) else print('Impossible')
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

def solve():
    N = int(input())
    A = list(map(int, input().split()))

    m = max(A)

    dic = {}
    for n in range((m+1)//2, m+1):
        dic[n] = 0

    for a in A:
        if not a in dic.keys():
            return False
        else:
            dic[a] += 1

    if m % 2 == 0:
        half = m//2
        if dic[half] != 1:
            return False
    else:
        half = m//2+1
        if dic[half] != 2:
            return False
    for n in range(half+1, m+1):
        if dic[n] < 2:
            return False
    return True


if __name__ == "__main__":
    if solve():
        print('Possible')
    else:
        print('Impossible')

Submission status: Accepted

Solution code:
from collections import Counter


def solve(n, aaa):
    if n == 2:
        return aaa == [1, 1]

    count = Counter(aaa)
    min_a = min(count)
    max_a = max(count)
    # 最大値（直径）が所定の範囲内か
    if not 2 <= max_a <= n - 1:
        return False
    # 最小値は半径以下にはならない & 直径パス上の中点として半径である点が必要
    if min_a != (max_a + 1) // 2:
        return False
    # 中点は直径が偶数なら1個、奇数なら2個しかあり得ない
    if count[min_a] != max_a % 2 + 1:
        return False
    # 直径パス上の点として半径+1～直径の各距離が2点ずつ必要
    if any(count[a] < 2 for a in range(min_a + 1, max_a + 1)):
        return False
    # 後の頂点は直径パスの適当な箇所に接続すれば任意の距離に出来る
    return True


n = int(input())
aaa = list(map(int, input().split()))
print('Possible' if solve(n, aaa) else 'Impossible')

Submission status: Accepted

Solution code:
from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	D = defaultdict(int)
	a = sorted(getlist())
	if N == 2:
		if a[0] != 1 or a[1] != 1:
			print("Impossible")
		else:
			print("Possible")
	else:
		for i in range(N):
			D[a[i]] += 1
		if a[-1] % 2 != 0:
			if a[0] * 2 - 1 != a[-1]:
				print("Impossible")
			else:
				judge = "Possible"
				if D[a[0]] != 2:
					judge = "Impossible"
				for i in range(a[0], a[-1] + 1):
					if D[i] < 2:
						judge = "Impossible"
						break
				print(judge)
		else:
			judge = "Possible"
			if a[0] * 2 != a[-1]:
				print("Impossible")
			else:
				judge = "Possible"
				if D[a[0]] != 1:
					judge = "Impossible"
				for i in range(a[0] + 1, a[-1] + 1):
					if D[i] < 2:
						judge = "Impossible"
						break
				print(judge)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import Counter


def check(N, A):
    d = max(A)
    if d >= N:
        return False
    c = Counter(A)
    cnt = 0
    if d % 2 == 0:
        if c[d//2] != 1:
            return False
        cnt += 1
        mn = d//2+1
    else:
        if c[d//2+1] != 2:
            return False
        cnt += 2
        mn = d//2+2
    for i in range(mn, d+1):
        if c[i] < 2:
            return False
        cnt += c[i]
    return cnt == N


def main():
    N = int(input())
    A = list(map(int, input().split()))
    if check(N, A):
        print("Possible")
    else:
        print("Impossible")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
def solve():
    d = {}
    r = max(a)
    mi = (r+1)//2
    for i in a:
        if i < mi:
            return False
        d[i] = d.get(i, 0) + 1

    if not(mi in d and d[mi] == 1+r%2):
        return False
    for i in range(mi+1, r+1):
        if i not in d or d[i] < 2:
            return False
    return True

if solve():
    print("Possible")
else:
    print("Impossible")