Xin ý tưởng thuật toán cho bài tập

#1

Đề bài như sau ạ :

Hôm nay là ngày đầu tiên JK đi học. JK được giao một bài tập về nhà như sau:

Thầy giáo có một mảng n số nguyên không âm. Thầy muốn tìm 1 số nguyên x, sau đó cộng thêm x vào một số phần tử của mảng (không quá 1 lần với mỗi phần tử), và trừ đi x vào một số phần tử của mảng (không quá 1 lần với mỗi phần tử), sao cho sau đó tất cả các phần tử của mảng đều bằng nhau.

Với mảng n số nguyên ban đầu thầy cho, JK phải trả lời thầy rằng có tồn tại số nguyên x thỏa mãn hay không?

Hãy giúp JK ghi điểm ngay buổi đầu đi học nhé!

Input
Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 105) - số lượng phần tử trong mảng Dòng thứ hai chứa n số nguyên a1 , a2 , … , an (0 ≤ ai ≤ 109) - các phần tử của mảng.

Output
Nếu không tồn tại số nguyên x làm cho tất cả các phần tử của mảng bằng nhau, in "NO, ngược lại in " YES ".

Example
Input:
5
1 3 3 2 1

Output:
YES
Input:
5
1 2 3 4 5

Output:
NO

Mình mong được mọi người giúp đỡ ạ =))

#2

Giả sử có một số nguyên X
Các giá trị trong mảng có thể có các giá trị:
a0 + X
a1
a2 - X

Sao cho a0 + X == a1 == a2 - X
một mảng thoả mãn điều kiện trên cần có

  1. Max là a2
  2. Min là a0
  3. Trong mảng chỉ tồn tại a0, a1, a2 với a1 = (a0 + a2) / 2 khi a0 và a2 cùng tính chẵn lẻ
2 Likes
#3

Tức là trong mảng chỉ có các số nguyên a, a + x, a - x (a là 1 số bất kì).

Ta chỉ cần sort lại mảng, kiểm tra xem:

  • Có tối đa 3 số khác nhau hay không (nếu ít hơn 3 thì càng tốt, ta chỉ cần cộng/trừ 1 lần), ví dụ như 1 3 2 2 1 có 3 số khác nhau (1, 2, 3). Nếu có thì YES, nếu không thì NO.

  • Nếu có 3 số khác nhau, kiểm tra xem (số lớn nhất + số nhỏ nhất) / 2 (chia hết) có nằm trong dãy không. Nếu có thì YES, nếu không thì NO.

3 Likes
#4

Do ta chỉ cần nhận diện 3 số nên việc sort có thể tránh được, tức chỉ cần đọc 3n lần.

1 Like
#5

Bài này for 1 n cũng được, nhưng mà nhiều if else quá.

#6

for j:=1 to flag_counter do :smiley: mấy số cũng được, chốt bằng một câu if.

1 Like
#7

Với test 1 2 2 3 4 thì sao ạ .Nó là 4 số khác nhau. Nhưng vẫn đúng chứ

#8

Đúng gì mà đúng. Bạn chọn x bằng bao nhiêu đây? Mảng sau cùng là như thế nào?

2 Likes
#9

À ừ mình nhầm. @@ Mình cảm ơn :v

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?