B. Хулгана

хугацааны хязгаарлалт 0.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Одоогийн судлаачид олон өлсгөлөн хулгана хэрчим бяслаг хайхдаа дараах маягаар хайдагийг үзүүлсэн: хэрвээ хэд хэдэн хэрчим бяслаг байвал хулгана бүр өөрт хамгийн ойр байгаагаа сонгоно. Үүний дараа бүх хулгана сонгосон хэрчим бяслагруугаа чиглэн хөдлөнө. Нэг эсвэл хэд хэдэн хулгана төгсгөлийн цэг дээр очсон үед тэнд нэг л хэрчим бяслаг байх ба тэд түүнийг идэж сайн хооллоно. Үүний дараа уг цэг дээр очсон хулгана бүр өлсгөлөн хэвээрээ үлдэнэ. Бүх хулганы хөдлөх хурд адилхан.

Хэрвээ хамгийн ойрхон хэрчмийг сонгох хэд хэдэн зам байвал хулгана хамгийн цөөн өлсгөлөн хулганатайг нь сонгоно. Энэ теоремийг шалгахын тулд эрдэмтэд туршилт явуулахаар болсон. Тэд Декартын координатын систем дээр $N$ хулгана болон $M$ хэрчим бяслаг байрлуулсан ба энд бүх хулганууд $y = Y_{0}$ шулуун дээр харин бүх бяслагнууд өөр $y = Y_{1}$ шулуун дээр байна. Туршилтын үр дүнг шалгахын тулд эрдэмтдэд олон өлсгөлөн хулганы зан төлөвийг дууриалгадаг програм хэрэгтэй байна.

Өлсгөлөн үлдэх буюу өөрөөр бяслаггүй үлдэх хулганы хамгийн бага тоог тооцоолдог програм бич.

Оролт

Оролтын эхний мөрөнд дөрвөн бүхэл тоон утга $N$ ($1 ≤ N ≤ 10^{5}$), $M$ ($0 ≤ M ≤ 10^{5}$), $Y_{0}$ ($0 ≤ Y_{0} ≤ 10^{7}$), $Y_{1}$ ($0 ≤ Y_{1} ≤ 10^{7}$, $Y_{0} ≠ Y_{1}$) байна. Хоёр дахь мөрөнд $N$ тооны илэрхий өссөн дараалал $x$ байх ба хулгануудын координатууд юм. Гуравдугаар мөрөнд $M$ тооны илэрхий өссөн дараалал $x$ байх ба бяслагнуудын координатууд юм. Бүх координатууд бүхэл тоо байх ба үнэмлэхүй утгаараа $10^{7}$-с ихгүй байна.

Гаралт

Гаралтын нэг мөрөнд бяслаггүй үлдэх хулгануудын хамгийн бага тоо байна.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3 2 0 2
0 1 3
2 5
Гаралт
1

Тэмдэглэл

Гурван хулгана бүгдээрээ эхний хэрчим бяслагыг сонгоно. Хоёр болон гурав дахь хулгана уг хэрчмийг иднэ. Эхний хулгана өлсгөлөн үлдэнэ учир нь тэр ижил хэрчимрүү гүйж байсан боловч хоцорно. Хоёр дахь хэрчим бяслагийг идэхгүй үлдээнэ.

Сэтгэгдлүүдийг ачааллаж байна...