Tăng Giảm

Xem PDF

Điểm: 300 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

ami ?có một dãy số nguyên \(a\) gồm \(N\) phần tử và một số \(k\). Các bạn được làm thao tác sau không quá \(m\) lần:

  • Chọn một cặp số \((i , j)\) thoả điều kiện \(1 ≤ i, j ≤ N\)\(a[i] ≥ k\). Sau đó, gán \(a[i] = a[i] - k\)\(a[j] = a[j] + k\).

Hãy tìm cách tận dụng thao tác trên để sau khi chuyển đổi, giá trị \(max(a[1] , a[2] , ... , a[N]) - min(a[1] , a[2] , ... , a[N])\) là nhỏ nhất có thể.

Input

  • Dòng đầu tiên chứa một số nguyên dương \(k\).
  • Dòng thứ hai chứa một số nguyên dương \(m\).
  • Dòng tiếp theo chứa một số nguyên dương \(N\).
  • \(N\) dòng tiếp theo, mỗi dòng chứa một phần tử của \(a\).

Output

  • \(1\) số nguyên dương là kết quả bài toán. Giá trị nhỏ nhất của \(max(a[1] , a[2] , ... , a[N]) - min(a[1] , a[2] , ... , a[N])\).

Example

Test 1

Input
2
1
3
2
2
3
Output
1
Note
  • Ta không cần dùng thao tác nào. Sau đó, max(2 , 2 , 3) - min(2 , 2 , 3) = 1. Đây là giá trị nhỏ nhất có thể đạt được.

Test 2

Input
1
1
3
2
3
4
Output
0
Note
  • Ta sẽ áp dụng thao tác lên cặp (1, 3). Sau đó, dãy \(a\) trở thành [3 3 3]. Max(3 , 3 , 3) - min(3 , 3 , 3) = 0. Đây là giá trị nhỏ nhất có thể đạt được.

Scoring

  • Subtask \(1\): \(70\)% test có \(N\), \(m\) \(\leq 50\) và 1 ≤ \(k\) , \(a[i]\)\(10^9\).
  • Subtask \(2\): \(30\)% test có \(N\), \(m\) \(\leq 5 * 10^4\) và 1 ≤ \(k\) , \(a[i]\)\(10^9\).

Bình luận


  • -7
    xuanphuc165    10:47 a.m. 25 Tháng 9, 2021

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.