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:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from collections import Counter

pos = "Possible"
imp = "Impossible"
def judge(nums):
    N = len(nums)
    count = Counter(nums)
    mx = max(nums)

    if mx == 1:
        if N == 2:
            return pos
        else:
            return imp
    elif mx == 2:
        if count[1] == 1 and count[2] >= 2:
            return pos
        else:
            return imp
    else:
        mid = (mx + 1) // 2

        for i in range(1, mid):
            if count[i] != 0:
                return imp
        if mx % 2 == 1:
            if count[mid] != 2:
                return imp
        else:
            if count[mid] != 1:
                return imp

        for i in range(mid+1, mx+1):
            if count[i] < 2:
                return imp

        return pos
                
dummy = int(input())
nums = list(map(int,input().split()))
print(judge(nums))


def mk(array):
    ret = []
    n = 1
    for e in array:
        ret += [n] * e
        n += 1
    print(ret)
    return ret

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    b = [0] * (n + 1)
    for x in a:
        b[x] += 1
    m = max(a)
    l = 0
    r = m
    f = []
    while l <= r:
        b[r] -= 1
        if l < r:
            b[m-l] -= 1
        l += 1
        r -= 1
        if l <= r:
            f.append(max(m - l + 1, r + 1))
    for x in f:
        if b[x] > 0:
            b[x] = 0
    print "Possible" if all(not x for x in b) else "Impossible"
main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    i = 1
    if n > 2 and a[-1] == 1:
        return 'Impossible'
    if a[-1] != a[-2]:
        return 'Impossible'
    if a[-1] % 2 == 1:
        if a[-1] // 2 + 1 != a[0]:
            return 'Impossible'
        if a[0] != a[1]:
            return 'Impossible'
        if n > 2 and a[0] == a[2]:
            return 'Impossible'
        i = 2
    else:
        if a[-1] // 2 != a[0]:
            return 'Impossible'
        if a[0] == a[1]:
            return 'Impossible'
    c = 2
    t = a[0]
    for j in range(i,n):
        if t != a[j]:
            if c < 2:
                return 'Impossible'
            if t + 1 != a[j]:
                return 'Impossible'
            c = 0
            t = a[j]
        c += 1
    return 'Possible'

print(f())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys,copy,math,heapq,itertools as it,fractions,re,bisect,collections as coll

def solve():
    N = int(raw_input())
    a = map(int, raw_input().split())
    if N == 2 and a == [1, 1]:
        return True

    cnt = [0]*(N + 1)
    for ai in a:
        cnt[ai] += 1

    mx = max(a)
    l, r = 0, mx
    for i in xrange(1, mx):
        l += 1
        r -= 1
        cnt[max(l, r)] -= 1

    if cnt[mx] < 2: return False
    for i in xrange(1, (mx + 1)/2 + 1):
        if cnt[i] > 0:
            return False
    for i in xrange(1, N):
        if cnt[i] < 0:
            return False
    return True

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def no():
    print("Impossible")
    quit(0)

def yes():
    print("Possible")
    quit(0)

cnts = defaultdict(int)
for x in xs:
    cnts[x] += 1

d = max(xs)
delems = []
for i in range(d+1):
    delems.append(max(i, d - i))

for delem in delems:
    if cnts[delem] <= 0:
        no()
    cnts[delem] -= 1

minx = min(delems) + 1
for x, rem in cnts.items():
    if rem > 0:
        if not minx <= x <= d:
            no()
yes()

Submission status: Accepted

Solution code:
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
from collections import Counter
def rl(s): return xrange(len(s))


INF = 2147483647


import sys
stdin = sys.stdin

N =        int( stdin.readline().strip() )

dists = map(int, stdin.readline().strip().split())

counts = Counter(dists)

if counts[1] == 2 and N == 2:
    print "Possible"
elif counts[1] >= 2:
    print "Impossible"
else:
    m = max(dists)
    good = True
    if counts[m] < 2:
        good = False
    if m % 2 == 0 and counts[m//2] != 1:
        good = False
    if m % 2 == 1 and counts[m//2 + 1] != 2:
        good = False
    for i in range(m//2 + 1, m):
        if counts[i] < 2:
            good = False
    if good:
        print "Possible"
    else:
        print "Impossible"

Submission status: Runtime Error

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 = 0
    for i in range(x[0],m[-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,m[-1]+1):
      if a.count(i) < 2: m = 1
    if m:
      print("Impossible")
    else:
      print("Possible")
else:
  print("Impossible")

Submission status: Runtime Error

Solution code:

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

num = Zeros(n,-1)

for i in range(n):
    num[a[i]] += 1

mx = max(a)
    
#print(num)
ans = "Possible"
if(mx%2==0):
    num[mx//2] -= 1
    if(num[mx//2]<0): ans="Impossible"

now = mx//2 + 1


for i in range(mx-now+1):
    num[now+i]-=2
    if(num[now+i]<0): ans="Impossible"
#print(num)

if(sum(num[0:now])>=1):
    ans = "Impossible"

print(ans)

Submission status: Runtime Error

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()
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: Runtime Error

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]>1:
            flag = False
    else:
        if c[i]<2:
        flag = False
        break
if m%2==0 and c[m//2]!=1:
    flag = False
print('Possible' if flag else 'Impossible')

Submission status: Runtime Error

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 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: Runtime Error

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 s==a[1]==a[2]: print("Impossible")
else: print("Possible")

Submission status: Runtime Error

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

sorteda = sorted(a)

maxlen = sorteda[-1]
numpathsoflen = {}
if(sorteda[0] < (maxlen+1)/2):
    print 'Impossible'
elif(maxlen % 2 == 0 
     and sorteda[0] == maxlen/2 
     and sorteda[0] == sorteda[1]):
    print 'Impossible'
else:
    numnodes = maxlen + 1
    for i in range(N):
        if a[i] in numpathsoflen.keys():
            if numpathsoflen[a[i]] >= 2:
                numnodes += 1
            numpathsoflen[a[i]] += 1            
        else:
            numpathsoflen[a[i]] = 1
    if(numnodes != N):
        print 'Impossible'
    else:
        out= 'Possible'
        starti = (maxlen+1)/2) 
        if maxlen % 2 == 0:
            starti++
        for i in range(starti, maxlen)
            if(not i in numpathsoflen.keys() or numpathsoflen[i] < 2):
                out = 'Impossible'                
        print out