eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Миші та сир

Миші та сир

Сучасні дослідження виявили, що зграя голодних мишей в пошуках сиру діє наступним чином: якщо поблизу є декілька шматків сиру, то кожна миша обирає собі найближчий, після чого всі миші одночасно починають рухатись в напрямку обраного шматку сиру. Як тільки миша, або декілька мишей, досягли точки призначення і там є сир, вони його з’їдають, а усі миші які прибігли пізніше залишаються голодними. Швидкість пересування всіх мишей однакова. Якщо існує декілька способів обрати найближчі шматки сиру, то миші оберуть такий спосіб, за яким мінімальна кількість мишей зграї залишиться голодною. Щоб перевірити цю теорію вчені вирішили провести експеримент. Вони розташували \textbf{N }мишей і \textbf{M} шматків сиру в прямокутній системі координат, таким чином, що всі миші знаходяться на деякій прямій \textbf{y = Y_0}, а всі шматки сиру - на інший прямій \textbf{y = Y_1}. Але щоб перевірити результати експерименту вченим потрібна програма яка відтворює поведінку зграї голодних мишей. Напишіть програму, яка знаходить кількість мишей які залишаться без сиру. \InputFile Перший рядок містить чотири цілих числа \textbf{N }(\textbf{1 }≤ \textbf{N }≤ \textbf{10^5}), \textbf{M }(\textbf{0 }≤ \textbf{M }≤ \textbf{10^5}), \textbf{Y_0} (\textbf{0 }≤ \textbf{Y}_0 ≤ \textbf{10^7}), \textbf{Y_1} (\textbf{0 }≤ \textbf{Y}_1 ≤ \textbf{10^7}). Другий рядок містить послідовність із \textbf{N} зростаючих чисел - абсциси мишей. Третій рядок містить \textbf{M} зростаючих чисел - абсциси шматків сиру. Всі абсциси цілі і не перевищують за модулем \textbf{10^7}. \OutputFile Вивести одне число - мінімальну кількість мишей, які залишаться без сиру.
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
3 2 0 2
0 1 3
2 5
Вихідні дані #1
1
Автор Роман Ризванов
Джерело 2011 XXIV Всеукраїнська олімпіада з інформатики, Черкаси, Березень 26 - 31, тур 2