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