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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

from collections import defaultdict


def main():
    n = int(input())
    a = list(map(int, input().split()))
    maxa = max(a)
    mina = min(a)
    dica = defaultdict(lambda: 0)
    for _a in a:
        dica[_a] += 1
    if dica[maxa] < 2:
        print("Impossible")
    elif mina != (maxa+1)//2:
        print("Impossible")
    else:
        if ((maxa+1)%2 == 1 and dica[mina] != 1) or ((maxa+1)%2 == 0 and dica[mina] != 2):
            print("Impossible")
        else:
            mina += 1
            for _a in range(mina, maxa+1):
                if _a not in dica or dica[_a] < 2:
                    print("Impossible")
                    break
            else:
                print("Possible")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
cntA = Counter(A)
valA= list(set(A))
valA.sort()

if valA[-1] % 2 == 1:
    if valA[0] != -(-valA[-1] // 2) or cntA[valA[0]] != 2:
        print('Impossible')
        exit()

    for a in range(valA[0], valA[-1] + 1):
        if cntA[a] < 2:
            print('Impossible')
            exit()
else:
    if valA[0] != valA[-1] // 2 or cntA[valA[0]] != 1:
        print('Impossible')
        exit()

    for a in range(valA[0] + 1, valA[-1] + 1):
        if cntA[a] < 2:
            print('Impossible')
            exit()

print('Possible')

Submission status: Accepted

Solution code:
from collections import Counter, deque

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

cntA = Counter(A)
valA = list(set(A))
valA.sort(reverse=True)

pathLeng = [0] * (N + 1)

if cntA[valA[0]] < 2 or cntA[valA[-1]] > 2:
    print('Impossible')
    exit()

pathLeng[1] = valA[0]
pathLeng[2] = valA[0]
cntA[valA[0]] -= 2
maxNode = 2

pr = [[] for _ in range(N + 1)]
ch = [[] for _ in range(N + 1)]

for i, a in enumerate(valA[1:], start=2):
    if a == valA[-1] and cntA[valA[-1]] == 1:
        prevLeft = maxNode
        prevRight = maxNode - 1
        maxNode += 1
        ch[prevLeft].append(maxNode)
        ch[prevRight].append(maxNode)
        pr[maxNode].append(prevLeft)
        pr[maxNode].append(prevRight)
        pathLeng[maxNode] = valA[-1]
        cntA[valA[-1]] -= 1
        break

    prevLeft = (i - 1) * 2 - 1
    prevRight = (i - 1) * 2
    nowLeft = i * 2 - 1
    nowRight = i * 2

    maxNode = max(maxNode, nowRight)
    if maxNode > N:
        print('Impossible')
        exit()

    pathLeng[nowLeft] = a
    pathLeng[nowRight] = a

    cntA[a] -= 2

    ch[prevLeft].append(nowLeft)
    ch[prevRight].append(nowRight)
    pr[nowLeft].append(prevLeft)
    pr[nowRight].append(prevRight)
else:
    ch[maxNode].append(maxNode - 1)
    pr[maxNode - 1].append(maxNode)

for a, c in cntA.items():
    for _ in range(c):
        maxNode += 1
        i = pathLeng.index(a)
        ch[maxNode].append(ch[i][0])
        pr[ch[i][0]].append(maxNode)
        pathLeng[maxNode] = a
        cntA[a] -= 1

def search(index):
    visited = [False] * (N + 1)
    visited[index] = True
    st = deque([(index, 0)])
    ret = 0

    while st:
        now, d = st.pop()
        ret = max(ret, d)

        for to in pr[now]:
            if not visited[to]:
                st.append((to, d + 1))
                visited[to] = True
        for to in ch[now]:
            if not visited[to]:
                st.append((to, d + 1))
                visited[to] = True
    return ret

for i, d in enumerate(pathLeng[1:], start=1):
    if search(i) != d:
        print('Impossible')
        exit()

for v in cntA.values():
    if v != 0:
        print('Impossible')
        exit()

A.sort()
pathLeng.sort()

if A == pathLeng[1:]:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
yes = 'Possible'
no = 'Impossible'

if N == 2:
    if a[0] != 1 and a[1] != 1:
        print(no)
        exit()
    else:
        print(yes)
        exit()
if a[-1] != (a[0] + 1) // 2:
    print(no)
    exit()
else:
    if a[0] % 2 == 0:
        if a[-2] == a[-1]:
            print(no)
            exit()
    else:
        if a[-3] == a[-1]:
            print(no)
            exit()

ok = [0] * N
for i in range(N):
    ok[a[i]] += 1
for i in range(a[-1] + 1, a[0] + 1):
    if ok[i] < 2:
        print(no)
        exit()

print(yes)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = [int(x) for x in input().split()]
D = defaultdict(int)
for a in A:
  D[a] += 1
if D[1] == 2 and N > 2:
  print('Impossible')
elif D[min(A)] > 2:
  print('Impossible')
elif -(-max(A) // 2) != min(A):
  print('Impossible')
elif D[min(A)] != 1 + (max(A) % 2):
  print('Impossible')
else:
  for a in range(min(A) + 1, max(A) + 1):
    if D[a] < 2:
      print('Impossible')
      break
  else:
    print('Possible')

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
m = max(a)



flag = True

for i in range(1, m+1):
    if i<m//2:
        if c[i]!=0:
            flag = False
    elif i==m//2:
        if m%2 == 0:
            if c[i]!=1:
                flag = False
                break
        else:
            if c[i]!=0:
                flag = False
                break
    elif i == m//2+1:
        if m%2 == 0:
            if c[i]<2:
                flag = False
                break
        else:
            if c[i]!=2:
                flag = False
                break
    else:
        if c[i]<2:
            flag = False
            break

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
m = max(a)

flag = True

if m%2 == 0:
    for i in range(1,m+1):
        if i<m//2:
            if c[i]!=0:
                flag = False
                break
        elif i==m//2:
            if c[i]!=1:
                flag = False
                break
        else:
            if c[i]<2:
                flag = False
                break
else:
    for i in range(1,m+1):
        if i<=m//2:
            if c[i]!=0:
                flag = False
                break
        elif i==m//2+1:
            if c[i]!=2:
                flag = False
                break
        else:
            if c[i]<2:
                flag = False
                break

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

n = getN()
nums = getList()

# nums.sort(reverse=True)
mx = max(nums)
mn = (mx+1) // 2
mndx = (mx % 2) + 1

from collections import Counter

cnt = Counter(nums)

for i in range(mn+1, mx+1):
    if cnt[i] < 2:
        print("Impossible")
        sys.exit()

if cnt[mn] != mndx:
    print("Impossible")
else:
    print("Possible")

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
A=list(map(int,input().split()))
def solve(N,A):
    dic=defaultdict(lambda: 0)
    for a in A: dic[a]+=1
    m=max(A)
    for i in range((m+1)//2,m+1):
        if m%2==0 and i==m//2:
            dic[i]-=1
        else:
            dic[i]-=2
    return not any([cnt<0 or (n<((m-m//2)+1) and cnt>0) for n,cnt in dic.items()])

print("Possible" if solve(N,A) else "Impossible")

Submission status: Accepted

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

cnt = {}
for i in range(n):
    if a[i] not in cnt:
        cnt[a[i]] = 1
    else:
        cnt[a[i]] += 1

max_a = max(a)
min_ = 10000000000
diameter = max_a + 1
for i in range(diameter):
    tmp = max(max_a - i, i)
    min_ = min(min_, tmp)
    if tmp not in cnt:
        print("Impossible")
        exit()
    if cnt[tmp] == 0:
        print("Impossible")
        exit()
    cnt[tmp] -= 1

for i in cnt:
    if cnt[i] > 0 and i <= min_:
        print("Impossible")
        exit()
print("Possible")

Submission status: Accepted

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

if n == 2:
    if a[0] == 1 and a[1] == 1:
        print("Possible")
        exit()
    else:
        print("Impossible")
        exit()

cnt = [0] * 100
for item in a:
    cnt[item] += 1

maxa = max(a)
mina = (maxa + 1) // 2

ans = True
for i in range(100):
    if i < mina:
        if(cnt[i] > 0):
            ans = False
    elif i == mina:
        if i == 1 and cnt[i] != 1:
            ans = False
        if i > 1:
            if maxa % 2 == 1 and not cnt[i] == 2:
                ans = False
            if maxa % 2 == 0 and not cnt[i] == 1:
                ans = False
    elif i > mina and i <= maxa: 
        if cnt[i] < 2:
            ans = False

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

Submission status: Accepted

Solution code:
import os
import sys
from collections import Counter

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

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

counts = Counter(A)
ma = max(A)
mi = min(A)
ok = True
if ma % 2 == 0:
    ok &= mi == ma // 2
    ok &= counts[mi] == 1
else:
    ok &= mi == ma // 2 + 1
    ok &= counts[mi] == 2
for d in range(ma, mi, -1):
    ok &= counts[d] >= 2
if ok:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

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

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

counts = Counter(A)
m = max(A)
ok = True
if m % 2 == 0:
    ok &= min(A) == max(A) // 2
    ok &= counts[min(A)] == 1
else:
    ok &= min(A) == max(A) // 2 + 1
    ok &= counts[min(A)] == 2
for d in range(max(A), min(A), -1):
    ok &= counts[d] >= 2
if ok:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
mi = min(A)
cntA = Counter(A)
cnt_mi = cntA[mi]
if cnt_mi>2:
    print("Impossible")
    exit()
elif cnt_mi==1:
    ma = 2 * mi
else:
    ma = 2 * mi - 1
cnt = cnt_mi
for i in range(mi+1, ma+1):
    c = cntA[i]
    if c < 2:
        print("Impossible")
        exit()
    cnt += c
if cnt!=N:
    print("Impossible")
else:
    print("Possible")

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from collections import Counter

# 直径が分かる。中心からの距離が分かる。

N = int(input())
A = [int(x) for x in input().split()]

diag = max(A)

def solve_even():
    # 中心が1頂点
    depth = [x-diag//2 for x in A]
    if any(x < 0 for x in depth):
        return False
    counter = Counter(depth)
    if counter[0] != 1:
        return False
    for i in range(1,diag//2+1):
        if counter[i] < 2:
            return False
    return True

def solve_odd():
    # 直径の隣を深さ0と扱う
    depth = [x-(diag+1)//2 for x in A]
    if any(x < 0 for x in depth):
        return False
    counter = Counter(depth)
    if counter[0] != 2:
        return False
    for i in range((diag+1)//2):
        if counter[i] < 2:
            return False
    return True

bl = solve_odd() if diag&1 else solve_even()
answer = 'Possible' if bl else 'Impossible'
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N = input()
a = map(int, raw_input().split())

L = max(a)
m = defaultdict(int)
for num in a:
    if num < (L + 1) / 2:
        print "Impossible"
        exit()
    m[num] += 1
for num in range(L / 2 + 1, L + 1):
    if not num in m or m[num] < 2:
        print "Impossible"
        exit()
if L % 2 == 0 and (not L / 2 in m or m[L / 2] >= 2):
    print "Impossible"
    exit()
if L % 2 == 1 and m[L / 2 + 1] > 2:
    print "Impossible"
    exit()
print "Possible"

Submission status: Accepted

Solution code:
from collections import Counter
from sys import exit
def imp():
    print('Impossible')
    exit()

N = int(input())
A = list(map(int, input().split()))
mia = min(A)
maa = max(A)
if mia != -(-maa//2):
    imp()
if maa % 2:
    CA = Counter(A)
    if CA[mia] != 2:
        imp()
    for i in range(mia +1, maa+1):
        if CA[i] < 2:
            imp()
else:
    CA = Counter(A)
    if CA[mia] != 1:
        imp()
    for i in range(mia +1, maa+1):
        if CA[i] < 2:
            imp()
print('Possible')

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

YES = "Possible"  # type: str
NO = "Impossible"  # type: str

def solve(N: int, a: "List[int]"):
    amax = max(a)
    vmin = (amax + 1) // 2
    nmin = amax % 2 + 1

    for i in range(1, amax+1):
        if i < vmin and a.count(i) > 0:
            print(NO)
            return
        if i == vmin and a.count(i) != nmin:
            print(NO)
            return
        if i > vmin and a.count(i) < 2:
            print(NO)
            return
    print(YES)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

maxA = max(As)
minA = (maxA+1) // 2
cnt = Counter(As)

for A, num in cnt.items():
    if A < minA:
        print('Impossible')
        break
    elif A == minA:
        if (maxA % 2 and num != 2) or (maxA % 2 == 0 and num != 1):
            print('Impossible')
            break
    elif num < 2:
        print('Impossible')
        break
else:
    for A in range(minA+1, maxA+1):
        if A not in cnt:
            print('Impossible')
            break
    else:
        print('Possible')

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from math import ceil
input()
A=list(map(int,input().split()))
maxA=max(A)
minA=min(A)
if minA!=ceil(maxA/2):
    print('Impossible')
else:
    if maxA%2:
        for i in range(minA,maxA+1):
            if i==minA:
                if A.count(i)!=2:
                    print('Impossible')
                    break
            else:
                if A.count(i)<2:
                    print('Impossible')
                    break
        else:
            print('Possible')
    else:
        for i in range(minA,maxA+1):
            if i==minA:
                if A.count(i)!=1:
                    print('Impossible')
                    break
            else:
                if A.count(i)<2:
                    print('Impossible')
                    break
        else:
            print('Possible')

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
D=max(A)
L=[0]*(D+1)
for i in range(N):
  L[A[i]]+=1
if D==1:
  if N>2:
    print("Impossible")
    exit()
elif D%2==0:
  for i in range(D+1):
    if i<D//2 and L[i]>0:
      print("Impossible")
      exit()
    elif i==D//2 and L[i]!=1:
      print("Impossible")
      exit()
    elif i>D//2 and L[i]<2:
      print("Impossible")
      exit()
elif D%2==1:
  for i in range(D+1):
    if i<D//2+1 and L[i]>0:
      print("Impossible")
      exit()
    elif i==D//2+1 and L[i]!=2:
      print("Impossible")
      exit()
    elif i>D//2+1 and L[i]<2:
      print("Impossible")
      exit()
print("Possible")

Submission status: Accepted

Solution code:
from collections import Counter as C

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
N=int(input())
A=[int(i) for i in input().split()]
dd=defaultdict(int)
K=[0]*N
for a in A:
    dd[a]+=1
    K[a]+=1
L=list(dd.items())
L.sort()

if L[-1][1]<=1:
    print('Impossible')
    sys.exit()
m=L[-1][0]
if m%2==1:
    if L[0][0]!=m//2+1 or L[0][1]!=2:
        print('Impossible')
        sys.exit()
if m%2==0:
    if L[0][0]!=m//2 or L[0][1]!=1:
        print('Impossible')
        sys.exit()
s=L[0][0]
for i in range(s+1,m+1):
    if K[i]<=1:
        print('Impossible')
        sys.exit()
print('Possible')

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
ctr = Counter(A)
maxa = max(A)
mina = min(A)

def ok():
    if mina != (maxa+1)//2:
        return False
    if maxa%2:
        if ctr[mina] != 2: return False
    else:
        if ctr[mina] != 1: return False
    for n in range(mina+1, maxa+1):
        if ctr[n] < 2:
            return False
    return True

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

Submission status: Accepted

Solution code:
n = int(input())

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

a = sorted(a)

m = a[-1]
f = 1
if m % 2 == 1:
    s = m // 2 + 1
    count = 0
    if n == 2:
        if a[0] != 1 or a[1] != 1:
            f = 0
    elif a[0] != s or a[2] == s:
        f = 0
    else:
        for i in range(n):
            if a[i] < s:
                continue
            elif a[i] == s:
                if count == 0:
                    count = 1
                else:
                    count = 0
                    s += 1
            else:
                f = 0
                break
        if count == 1:
            f = 0
else:
    s = m // 2 + 1
    count = 0
    if a[0] != s-1 or a[1] == s-1:
        f = 0
    else:
        for i in range(1, n):
            if a[i] < s:
                continue
            elif a[i] == s:
                if count == 0:
                    count = 1
                else:
                    count = 0
                    s += 1
            else:
                f = 0
                break
        if count == 1:
            f = 0
        
if f == 1:
    print('Possible')
else:
    print('Impossible')

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a.sort()
m,s = a[-1],a[0]
if m!=a[-2] or (m+1)//2!=s or (m%2 and s-a[1]) or ((not m%2) and s==a[1]) or any(a.count(i)<2 for i in range(s+1,m)) or (n!=2 and s==a[1]==a[2]): print("Impossible")
else: print("Possible")

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
ok = True

d_max = max(a)
if n > 2 and d_max == 1:
	ok = False
if c[d_max] == 1:
	ok = False
else:
	if d_max % 2 == 0:
		d_min = d_max // 2
		if min(a) < d_min:
			ok = False
		if c[d_min] != 1:
			ok = False
		for d in range(d_min + 1, d_max):
			if c[d] < 2:
				ok = False

	else:
		d_min = (d_max + 1) // 2
		if min(a) < d_min:
			ok = False
		if c[d_min] != 2:
			ok = False
		for d in range(d_min + 1, d_max):
			if c[d] < 2:
				ok = False

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

Submission status: Accepted

Solution code:
def check(a):
    a = sorted(a)
    d = {}
    for x in a:
        if x not in d.keys():
            d[x] = 1
        else:
            d[x] += 1
    if (a[-1]+1)>>1 != a[0]:
        return False
    if (a[-1]&1) != 1 and d[a[0]]!=1:
        return False
    if (a[-1]&1) == 1 and d[a[0]]!=2:
        return False
    for i in xrange(a[-1], a[0], -1):
        if i not in d.keys() or d[i]<2:
            return False
    return True

def main():
    n = int(raw_input().strip())
    a = [int(x) for x in raw_input().strip().split()]
    if check(a):
        print 'Possible'
    else:
        print 'Impossible'

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def solve(c):
    max_length = max(c)
    for i in range(max_length, max_length // 2, -1):
        if c[i] < 2:
            return False

    if max_length % 2 == 0:
        if c[max_length // 2] != 1:
            return False
    else:
        if c[max_length - max_length // 2] != 2:
            return False

    return True


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
p = "Possible"
imp = "Impossible"

n = int(raw_input())
a = map(int, raw_input().split())
mx = max(a)
mn = min(a)
if mx == 1 and  mn == 1:
    if n == 2:
        print p
        exit()
    else:
        print imp
        exit()
cnt = [0] * 100
for i in xrange(n):
    cnt[a[i]] += 1
if mx % 2 == 0:
    if mx / 2 != mn:
        print imp
        exit()
    if cnt[mn] != 1:
        print imp
        exit()
    for i in xrange(mn + 1, mx + 1):
        if cnt[i] < 2:
            print imp
            exit()

else:
    if mx / 2 + 1 != mn:
        print imp
        exit()
    if cnt[mn] != 2:
        print imp
        exit()
    for i in xrange(mn + 1, mx + 1):
        if cnt[i] < 2:
            print imp
            exit()
print p

Submission status: Accepted

Solution code:
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    mina=a[0]
    maxa=a[-1]
    if (a[-1]+1) // 2 != mina:
        return False

    b=[0]*n
    for v in a:
        b[v] += 1
    if (maxa & 1) > 0:
        if b[mina] != 2:
            return False
    elif b[mina] != 1:
        return False

    for v in range(mina+1, maxa+1):
        if b[v] < 2:
            return False
    return True

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

Submission status: Accepted

Solution code:
import sys

def solve(A):
    nc = 1
    while nc < len(A) and A[nc] == A[0]:
        nc += 1
    if nc > 2:
        return False
    for i in xrange(1, len(A)):
        if A[i] - A[i-1] > 1:
            return False
    c = 2
    prev = -1
    for j in xrange(nc, len(A)):
        if A[j] == prev:
            c += 1
        else:
            if c < 2:
                return False
            prev = A[j]
            c = 1
    if c < 2:
        return False
    if nc == 1:
        return A[0] * 2 == A[-1]
    else:
        return A[0] * 2 - 1 == A[-1]

sys.stdin.readline()
A = map(int, sys.stdin.readline().split())
A.sort()
print "Possible" if solve(A) else "Impossible"

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A.sort()
maxv1 = A[-1]
maxv2 = A[-2]
if maxv1 != maxv2:
    print("Impossible")
    exit()

K = maxv1
if K % 2 == 0:
    for i in range(K // 2):
        for j in range(2):
            if K - i in A:
                A.remove(K - i)
            else:
                print("Impossible")
                exit()
    if K // 2 in A:
        A.remove(K // 2)
    else:
        print("Impossible")
        exit()
else:
    for i in range(K // 2 + 1):
        for j in range(2):
            if K - i in A:
                A.remove(K - i)
            else:
                print("Impossible")
                exit()
if len(A) == 0:
    print("Possible")
    exit()
else:
    for a in A:
        if K % 2 == 0:
            if a < K // 2 + 1:
                print("Impossible")
                exit()
        else:
            if a < (K + 1) // 2 + 1:
                print("Impossible")
                exit()
    print("Possible")

Submission status: Accepted

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n=i()
a=ii()
m=max(a)
if m%2==0:
    x=[m-j for j in range(m/2)]
    x=[m/2]+x+x
else:
    x=[m-j for j in range((m+1)/2)]
    x=x+x

for y in x:
    if y in a:
        a.remove(y)
    else:
        print "Impossible"
        break
else:
    if len(a)==0:
        print "Possible"
    else:
        if min(a)>=(m+1)/2+1:
            print "Possible"
        else:
            print "Impossible"

Submission status: Accepted

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

def resolve(a):
    if a == [1, 1]:
        return True

    if a.count(1) >= 2:
        return False

    max_num = max(a)
    min_num = min(a)

    if a.count(max_num) < 2:
        return False

    if max_num / 2 > min_num:
        return False

    if max_num & 1:
        # 奇数
        for i in range(max_num // 2 + 1, max_num):
            if i not in a: return False

        if a.count(min_num) > 2:
            return False
    else:
        # 偶数
        for i in range(max_num // 2, max_num):
            if i not in a: return False

        if a.count(min_num) > 1:
            return False
    return True

print("Possible" if resolve(a) else "Impossible")

Submission status: Accepted

Solution code:
from collections import Counter
n = input()
c = Counter(map(int, raw_input().split()))

ma = max(c)
mi = min(c)

if (ma+1)/2 == mi and c[mi] == (ma%2) + 1:
    if all(c[x] >= 2 for x in xrange(mi+1, ma+1)):
        print "Possible"
        exit(0)
print "Impossible"

Submission status: Accepted

Solution code:
n=int(raw_input())
a=map(int,raw_input().split())
maxa=max(a)
cmaxa=a.count(maxa)
ca=[0]*(maxa+1)
for i in xrange(n):
    ca[a[i]]+=1
if maxa%2==1:
    l=maxa/2+1
    if a.count(l)==2:
        for i in xrange(n):
            if a[i]<l:
                print("Impossible")
                exit()
        for i in xrange(l+1,maxa+1):
            if ca[i]<2:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")
else:
    l=maxa/2
    if a.count(l)==1:
        for i in xrange(n):
            if a[i]<l:
                print("Impossible")
                exit()
        for i in xrange(l+1,maxa+1):
            if ca[i]<2:
                print("Impossible")
                exit()
        print("Possible")
    else:
        print("Impossible")

Submission status: Accepted

Solution code:
N = int(raw_input())
a = [int(x) for x in raw_input().split(' ')]

sorteda = sorted(a)

maxlen = sorteda[-1]
numpathsoflen = [0 for x in range(maxlen+1)]
if(sorteda[0] < (maxlen+1)/2):
    print 'Impossible'
else:
    for x in sorteda:
        numpathsoflen[x] += 1            
    valid = True
    starti = (maxlen+1)/2
    if(maxlen % 2 == 0):
        if(numpathsoflen[starti] != 1):
            valid = False
    else:
        if(numpathsoflen[starti] != 2):
            valid = False
    starti += 1        
    for x in range(starti, maxlen+1):
        if(numpathsoflen[x] < 2):
            valid = False
    if(valid):
        print 'Possible'
    else:
        print 'Impossible'

Submission status: Accepted

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

haves = [0] * (len(A) + 1)
for aa in xrange(max(A)+1):
    w = max(max(A) - aa, aa)
    haves[w] += 1

QQ = [0] * (len(A)+1)
for q in A:
    QQ[q] += 1 

Z = [QQ[x] - haves[x] for x in xrange(len(A)+1)]
if min(Z) < 0: print "Impossible"
else:

    waiting = [0] * (len(A) + 1)
    for z in reversed(xrange(len(A))):
        aa = A[z]
        if haves[aa] > 0:
            haves[aa]-=1
        else:
            waiting[aa] += 1



    for a in xrange(len(waiting)):
        if waiting[a] > 0:
            break

    if max(A) % 2 == 0:
        if a <= max(A) / 2:
            print "Impossible"
        else: print "Possible"
    else:
        if a <= (max(A)+1)/2:
            print "Impossible"
        else: print "Possible"