Code Viblo

Changing seats

Link

Đề bài

An có một mảng gồm n số nguyên. Mỗi giây An có thể đổi chỗ hai phần tử cạnh nhau trong mảng. Sau một hồi đổi chỗ giữa các phần tử trong mảng, An chợt nghĩ rằng, ko biết sau một số lần hữu hạn đổi chỗ sẽ thu được một mảng mà hai phần tử liền kề là khác nhau hay ko ?

Bạn hãy giúp anh ấy.

Input
Dòng đầu tiên là số nguyên n (1 ≤ n ≤ 100) — số lượng các phần tử trong mảng. Dòng thứ 2 là n số nguyên a_1,a_2,…,a_n,(1 ≤ a_i ≤ 1000) — các phần tử của mảng.

Output
in ra YES nếu có thể, in ra NO nếu ngược lại.

Resource limits
Execution time: 2 seconds

Memory: 256.00 MB

Đáp án

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

import sys
import math

input_str = ""
number_of_line = 0
for line in sys.stdin:
    number_of_line += 1
    if number_of_line == 2:
        arr = [int(i) for i in line.split()]
c = {}
max_high = math.ceil(len(arr)/2)
for i in arr:
    if i in c:
        c[i] += 1
    else:
        c[i] = 1
    if c[i] > max_high:
        print("NO")
        exit()
print("YES")