13012. Розселення по квартирах


Відправити розв'язок

Бали: 100
Time limit: 1.0s
Memory limit: 250M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

Є \(n\) бажаючих і \(m\) вільних квартир. Ваше завдання - розподілити квартири так, щоб якомога більше бажаючих отримали квартиру.

У кожного заявника є бажаний розмір квартири, і вони приймуть будь-яку квартиру, розмір якої достатньо близький до бажаного.

Обмеження

  • \(1 ≤ 𝑛 , 𝑚 ≤ 2 ⋅ 10^5\)
  • \(0≤k≤10^9\)
  • \(1≤a_i ​,b_i ​ ≤10^9\)

Формат вхідних даних

У першому рядку вхідних даних є три цілі числа \(n\), \(m\) і \(k\): кількість претендентів, кількість квартир і максимально допустима різниця.

Наступний рядок містить \(n\) цілих чисел \(a_1 ​ , a_2 ​ ,…, a_n\) ​ : бажаний розмір квартири кожного претендента. Якщо бажаний розмір заявника \(x\), він або вона прийме будь-яку квартиру розміром від \(x−k\) до \(x+k\).

Останній рядок містить \(m\) цілих чисел \(b_1 ​ , b_2 ​ ,…,b_m\) ​ : розміри кожної квартири.

Формат вихідних даних

Виведіть одне ціле число: кількість претендентів, які отримають квартиру.

Приклад вхідних даних

4 3 5
60 45 80 60
30 60 75

Приклад вихідних даних

2

Коментарі

Ще немає коментарів.