Biến đổi số


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

Cho mảng $a$ gồm $n$ số, số thứ $i$ là $a_i$. Bạn có một phép biến đổi như sau: Chọn hai số $a_i$ và $a_j \ (i \neq j)$, nếu $a_i \ge a_j$ thì xóa $a_j$ ra khỏi mảng và $a_i=a_i+1$.

Hãy biến đổi để số lượng số lớn hơn hoặc bằng một giá trị $k$ cho trước là nhiều nhất có thể.

Dữ liệu

  • Dòng đầu tiên là hai số nguyên $n$ và $q \ (1\le n,q\le 10^5)$ - số phần tử của mảng và số truy vấn;
  • Dòng thứ hai $N$ số nguyên dương $a_i \ (1\le a_i\le 10^9)$ là các phần tử của mảng $a$;
  • Dòng thứ $i$ trong $q$ dòng tiếp theo là các giá trị $k_i \ (1\le k_i\le 10^9)$.

Kết quả

  • In ra $q$ dòng, dòng thứ $i$ là số phần tử lớn hơn hoặc bằng giá trị $k_i$ nhiều nhất có thể thu được sau khi biến đổi.

Ví dụ

Ví dụ 1

input

5 2
21 9 5 8 10
10
15

output

3
1
Ví dụ 2

input

5 1
1 2 3 4 5
100

output

0

Giải thích

  • Test thứ nhất: - Truy vấn 1: Chọn phần tử thứ 2 (giá trị là 9) và thứ 4 (giá trị là 8), sau khi biến đổi ta thu được dãy $(21,10,5,10)$, đây là cách tối ưu.
  • Truy vấn 2: Dù làm cách nào thì cũng chỉ có một phần tử lớn hơn hoặc bằng 15.

  • Test thứ hai: - Truy vấn 1: Dù làm cách nào thì không thể tạo ra phần tử lớn hơn hoặc bằng 100.


Comments

There are no comments at the moment.