Problem:


Score : 700 points

Problem Statement

There are N cats.
We number them from 1 through N.

Each of the cats wears a hat.
Cat i says: "there are exactly a_i different colors among the N - 1 hats worn by the cats except me."

Determine whether there exists a sequence of colors of the hats that is consistent with the remarks of the cats.

Constraints

2 ≤ N ≤ 10^5

1 ≤ a_i ≤ N-1

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print Yes if there exists a sequence of colors of the hats that is consistent with the remarks of the cats; print No otherwise.

Sample Input 1

3
1 2 2

Sample Output 1

Yes

For example, if cat 1, 2 and 3 wears red, blue and blue hats, respectively, it is consistent with the remarks of the cats.

Sample Input 2

3
1 1 2

Sample Output 2

No

From the remark of cat 1, we can see that cat 2 and 3 wear hats of the same color.
Also, from the remark of cat 2, we can see that cat 1 and 3 wear hats of the same color.
Therefore, cat 1 and 2 wear hats of the same color, which contradicts the remark of cat 3.

Sample Input 3

5
4 3 4 3 4

Sample Output 3

No

Sample Input 4

3
2 2 2

Sample Output 4

Yes

Sample Input 5

4
2 2 2 2

Sample Output 5

Yes

Sample Input 6

5
3 3 3 3 3

Sample Output 6

No



Sample input:
3
1 2 2


Sample output:
Yes

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
D={}
for a in A:
  if(a in D):
    D[a]+=1
  else:
    D[a]=1
    
if(len(D)>2):
  print("No")
  exit()
  
if(len(D)==2):
  B=max(D)
  if(B-D[B-1]>0 and D[B]>=2*(B-D[B-1])):
    print("Yes")
  else:
    print("No")
  
else:
  B=max(D) # 常に同じ色の人がいる
  if(N>=2*B):
    print("Yes")
    exit()
  
  B=max(D)+1 # 全員違う色
  if(B==N):
    print("Yes")
    exit()
  print("No")

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
import collections
l1 = collections.Counter(a).most_common()
l1.sort()
if len(l1) > 2　or l1[1][0] - l1[0][0] > 1:
    print("No")
elif len(l1) == 1:#発言が１種類の場合
    if l1[0][0] * 2 <= n or l1[0][0] == n - 1:
        print("Yes")
    else:
        print("No")
else:
    if l1[1][1] >= (l1[1][0] - l1[0][1]) * 2 and l1[1][0] > l1[0][1]:
        print("Yes")#多い発言の人数が残りの色数かけ２より多い、全体色数が少ない発言の人数より多い
    else:
        print("No")

Submission status: Runtime Error

Solution code:
import sys
def printans(t):
    print(t)
    sys.exit()

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

if all([a==A[0] for a in A]):#全部同じ
    shurui=A[0]
    if shurui==N-1 or shurui*2<=N:
        printans("Yes")
    else:printans("No")
else:#少ないやつは自分だけの色、そいつら以外で上と同じ処理
    maxshurui = max(A)
    if all([a in (maxshurui,maxshurui-1)]):
        unique = A.count(maxshurui-1)
        shurui = maxshurui-unique
        if shurui<=0:
            printans("No")
        if shurui*2<=N-unique:
            printans("Yes")
        else:printans("No")

Submission status: Runtime Error

Solution code:
def printans(t):
    print(t)
    sys.exit()

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

if all([a==A[0] for a in A]):#全部同じ
    shurui=A[0]
    if shurui==N-1 or shurui*2<=N:
        printans("Yes")
    else:printans("No")
else:#少ないやつは自分だけの色、そいつら以外で上と同じ処理
    maxshurui = max(A)
    if all([a in (maxshurui,maxshurui-1)]):
        unique = A.count(maxshurui-1)
        shurui = maxshurui-unique
        if shurui<=0:
            printans("No")
        if shurui*2<=N-unique:
            printans("Yes")
        else:printans("No")

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
min_,max_=min(A),max(A)
ans=None

if max_-min_ > 1:
    ans=False
elif max_-min_ == 1:
    A=max_
    y=len([a for a in A if a==max_])
    x=N-y
    nc=A-x
    ans=(A-x)>0 and y >=2*(A-x)
else:
    ans=N>=2*min_ or min_+1==N

print("Yes" if ans else "No")

Submission status: Runtime Error

Solution code:
n = int(input())

a = list(map(int,int(input())))
a_max = max(a)
a_min = min(a)
if a_max > a_min+1:
    print('No')
    exit()
k = a_max
if a_max == a_min:
    if k == n-1 or 2*k <= n:
        print('Yes')
    else:
        print('No')
else:
    uni = a.count(k-1)
    if k >= uni + 1 and k <= uni + (n-uni)//2:
        print('Yes')
    else:
        print('No')

Submission status: Runtime Error

Solution code:
n=int(input())
s=input().split()
l=[int(s[i]) for i in range(n)]
l.sort()
if l[0]==l[-1]:
    if 1<=l[0]<=n//2:
        print("Yes")
    else:
        print("No")
elif l[-1]-l[0]>1:
    l[10000000]-=1
    print("No")
else:
    l[10000000]-=1
    a=l.count(l[0])
    b=l.count(l[-1])
    if a+1<=l[-1]<=a+b//2:
        print("Yes")
    else:
        print("No")

Submission status: Runtime Error

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

import sys, math, copy
import numba
# import fractions, itertools
import numpy as np
# import scipy

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

@numba.jit("b1(i8, i8[:])", nopython=True)
def main(n, ai):
    ma = np.max(ai)
    k = 0
    for a in ai:
        if a < ma - 1:
            return False
        if a == ma:
            k += 1

    if k == n:
        if ma + 1 == n:
            return True
        elif 1 <= ma <= n // 2:
            return True
        else:
            return False

    if k >= 2 and 1 <= ma - n + k <= k // 2:
        return True
    return False

n = int(input())
ai = np.array(list(map(int, input().split())))
print("Yes" if main(n, ai) else "No")

Submission status: Runtime Error

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

amax = max(a)
aelse = list(set(a))
aelse.remove(amax)
if len(aelse) == 0:
    if max == N | max == N-1:
        print('No')
    else:
        print('Yes')
    exit()
if len(aelse) != 1:
    print('No')
    exit()
if aelse[0] != amax - 1:
    print('No')
    exit()
print('Yes')

Submission status: Runtime Error

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

amax = max(a)
aelse = list(set(a)) - [amax]
if len(aelse) != 0:
    print('No')
    exit()
if aelse[0] != amax - 1:
    print('No')
    exit()
print('Yes')

Submission status: Runtime Error

Solution code:
import sys
if __name__ == "__main__":
    N = int(input())
    evidences = list(map(int, input().split()))
    evidences = list(sorted(evidences))
    unique_evidence = set(evidences)
    if (evidences[-1] - evidences[0] > 1):
        print ("No")
        sys.exit()
    if (len(unique_evidence) == 1):
        group = evidences[0];
        # all unique
        if (group == N - 1):
            print ("Yes")
            sys.exit()
        if (N - 2 * group < 0):
            print ("No")
            sys.exit()
        print ("Yes")
        sys.exit()
    # evidences[-1] - evidences[0] > 1
    min_val = min(evidences)
    max_val = max(evidences)

    min_val_cnt = 0
    max_val_cnt = 0
    for val in evidences:
        if (val == min_val):
            min_val_cnt += 1
        else:
            max_val_cnt += 1
    # violate not unique
    if (max_val_cnt <= 1):
        print ("No")
        sys.exit()
    #rest cat
    rest = N
    rest -= min_val_cnt

    min_group = min_val_cnt + 1
    max_group = min_val_cnt + (max_val_cnt // 2)
    if min_group <= evidences[-1] and evidences <= max_group:
        print ("Yes")
        sys.exit()
    print ("No")

Submission status: Runtime Error

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    d = collections.defaultdict(int)
    for c in a:
        d[c] += 1
    t = sorted(list(d.keys()))
    if t[-1] - t[0] > 1:
        return 'No'
    if len(t) == 1:
        if t[0] == n - 1:
            return 'Yes'
        if t[0] > n / 2.0:
            return 'No'
        return 'Yes'
    b = t[1] - d[t[0]]
    n2 = d[t[1]]
    if n2 == 2 and b == n2 - 1:
        return 'Yes'
    if b < 1:
        return 'No'
    return 1/0
    if b >= n2 - 2:
        return 'No'

    return 'Yes'


print(main())

Submission status: Runtime Error

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    d = collections.defaultdict(int)
    for c in a:
        d[c] += 1
    t = sorted(list(d.keys()))
    if t[-1] - t[0] > 1:
        return 'No'
    if len(t) == 1:
        if t[0] == n - 1:
            return 'Yes'
        if t[0] > n / 2.0:
            return 'No'
        return 'Yes'
    b = t[1] - d[t[0]]
    n2 = d[t[1]]
    if n2 == 2 and b == n2 - 1:
        return 'Yes'
    if b < 1:
        print(1/0)
        return 'No'
    if b >= n2 - 2:
        return 'No'

    return 'Yes'


print(main())

Submission status: Runtime Error

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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    d = collections.defaultdict(int)
    for c in a:
        d[c] += 1
    t = sorted(list(d.keys()))
    if t[-1] - t[0] > 1:
        return 'No'
    if len(t) == 1:
        if t[0] == n - 1:
            return 'Yes'
        if t[0] > n / 2.0:
            return 'No'
        return 'Yes'
    b = t[1] - d[t[0]]
    n2 = d[t[1]]
    print(1/0)
    if n2 == 2 and b == n2 - 1:
        return 'Yes'
    if b < 1:
        return 'No'
    if b >= n2 - 2:
        return 'No'

    return 'Yes'


print(main())

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
from queue import Queue

N = int(input())
a = sorted([int(n) for n in input().split()], reverse=True)

alone = a.count(max(a) - 1)

if alone:
    a = [a_ - alone for a_ in a][alone:]
    if len(a) == 2 and a[0] == 1:
        print("Yes")
    elif 2*a[0] <= len(a) and a[0] <= len(a)//a[0]:
        print("Yes")
    else:
        print("No")

else:
    if a[0] == N - 1:
        print("Yes")
    elif 2*a[0] <= len(a) and a[0] <= len(a)//a[0]:
        print("Yes")
    else:
        print("No")

Submission status: Runtime Error

Solution code:
import sys
N=int(input())
a=[int(i) for i in input().split()]
a.sort()

if a[N-1]-a[0]>1:
  print("No")
  sys.exit()
if a[0]==N-1:
  print("Yes")
  sys.exit()
if a[N-1]==1:
  print("Yes")
  sys.exit()
if a[0]==a[N-1]:
  if 2*a[0]<=N:
    print("Yes")
  else:
    print("No")
  sys.exit()
print(a[N])

Submission status: Runtime Error

Solution code:
import sys
from collections import Counter

sys.stdin = open('b1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


yes, no = 'Yes', 'No'


def solve(n, a):
    s = set(a)
    c = Counter(a)
    if len(s) == 1:
        a = list(s)[0]
        n_colors = a + 1
        if n_colors == n:
            return yes
        n_colors = a
        if 2 * n_colors <= n:
            return yes
    if len(s) == 2:
        a, b = sorted(s)
        if a + 1 == b:
            n_colors = b
            appear_once = c[a]
            appear_twice_or_more = n_colors - appear_once
            if appear_once < n_colors:
                if c[b] >= 2 * appear_twice_or_more:
                    return yes
    return no

n = read_int()
a = read_int_list()
res = solve(n, a)
print(res)

Submission status: Runtime Error

Solution code:
import sys
N=int(input())
a=[int(i) for i in input().split()]
a.sort()

if a[N-1]-a[0]>1:
  print("No")
  sys.exit()
if a[0]==N-1:
  print("Yes")
  sys.exit()
print(a[N])

Submission status: Runtime Error

Solution code:
import sys
N=int(input())
a=[int(i) for i in input().split()]
a.sort()

if a[N-1]-a[0]>1:
  print("NO")
  sys.exit()
if a[N-1]>N-1:
  print("NO")
  sys.exit()
if a[0]==N-1:
  print("YES")
  sys.exit()
if a[0]==a[N-1]:
  print("YES")
  sys.exit()
print(a[N])

Submission status: Runtime Error

Solution code:
import numpy as np

H,W,h,w = map(int,input().split())
# H,W,h,w = (3,4,2,3)

hrep = H//h +1
wrep = W//w +1

elem = np.ones((h,w),dtype=np.int)
elem[-1,-1] = -h*w

mat = np.tile(elem, (hrep,wrep))
mat = mat[:H,:W]

if mat.sum() > 0:
	print("Yes")
	for i in mat:
		print(" ".join(map(str,i)))
else:
	print("No")

Submission status: Runtime Error

Solution code:
import numpy as np

H,W,h,w = map(int,input().split())
# H,W,h,w = (3,4,2,3)

hrep = H//h +1
wrep = W//w +1

elem = np.ones((h,w),dtype=int)
elem[-1,-1] = -h*w

mat = np.tile(elem, (hrep,wrep))
mat = mat[:H,:W]

if mat.sum() > 0:
	print("Yes")
	for i in mat:
		print(" ".join(map(str,i)))
else:
	print("No")

Submission status: Runtime Error

Solution code:
nwin@linux-lqq3:~/atcoder/g16> cat b.py
n = int(raw_input())
a = map(int, raw_input().split())
b = max(a)
c = min(a)
if b - c > 1:
    print "No"
elif b == c:
    print "Yes" if b == n - 1 or 2 * b <= n else "No"
else:
    t = sum(c == x for x in a)
    if t >= b:
        print "No"
    else:
        print "Yes" if (b - t) * 2 <= t else "No"

Submission status: Runtime Error

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

result = False

if len(set(a)) > 1:
    set_min = list(set(a)[0])
    set_max = list(set(a)[1])

    if len(set(a)) > 2:
        result = False
    elif (set_max - set_min) != 1:
        result = False
    else:
        result = (a.count(set_min) == 1)
else:
    result = (list(set(a))[0] <= N/2 or list(set(a))[0] == 2)



if result:
    print("Yes")
else:
    print("No")

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<algorithm>

using namespace std;

void ng(){
  cout << "No" << endl;
  exit(0);
}

void ok(){
  cout << "Yes" << endl;
  exit(0);
}
int a[108000], n;
int main(){
  cin >> n;
  int mn = n + 1;
  int mx = 0;
  int mxcnt = 0;
  int mncnt = 0;
  for(int i = 0;i < n;i++){
    cin >> a[i];
    mn = min(mn, a[i]);
    mx = max(mx, a[i]);
  }

  if(mx == mn){
    if(2 * mx <= n || mx == n-1)ok();
    else ng();
  }
  if(mx - mn > 1)ng();
  
  for(int i = 0;i < n;i++){
    mncnt += a[i] == mn;
    mxcnt += a[i] == mx;
  }
  if(mx < mncnt + 1)ng();
  if((mx - mncnt) * 2 <= mxcnt)ok();
  else ng();
}