Masala #SWMK5EYY1R
Ko'cha chiroqlari
To'g'ri ko'cha bo'ylab bir xil masofada \(N\) ta uy joylashgan. Uylar orasidagi masofani bir birlik uzunlik sifatida qabul qilamiz. Har bir uy yoniga birta chiroq o'rnatish mumkin. Jami \(A\) ta chiroq bor, ular \(X\) masofagacha yorita oladi, va \(B\) ta chiroq bor, ular \(Y\) masofagacha yorita oladi. Agar \(X=0\) yoki \(Y=0\) bo'lsa, bunday chiroq faqat o'z o'rnatilgan uyni yoritadi. Siz barcha uylar yoritilgan bo'lishi uchun chiroqlarning minimal sonini aniqlashingiz kerak. Bir uy bir nechta chiroq bilan yoritilishi mumkin. Ko'chaning uylar orasidagi hududlarni yoritish majburiy emas.
Dastur kiruvchi ma’lumot sifatida bitta \(N\) butun sonini oladi \((1 \leq N \leq 10^5)\). Keyingi satrda yana \(A, X, B\)va \(Y\) butun musbat sonlar kiritiladi, ularning qiymatlari \(10^5\) dan oshmasligi kerak.
Dastur qancha chiroq o'rnatish kerakligini aniqlashi kerak va har bir chiroq uchun ikki butun sonni chiqarishi kerak - chiroqning koordinatasi va u yoritadigan masofa (ya'ni, \(X\) yoki \(Y\) soni).
Koordinatalar \(1\) dan \(N\) gacha bo'lgan butun sonlar bo'lishi kerak, har bir uy yonida faqat bitta chiroq o'rnatish mumkin.
Agar bir nechta to'g'ri javoblar bo'lsa, dastur har qanday to'g'ri javobni chiqarishi mumkin.
Agar javob mavjud bo'lmasa, dastur -1 ni qaytarishi kerak.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
10 3 1 1 2 |
3 2 7 1 10 1 |
| 2 |
10 1 1 1 2 |
-1 |
| 3 |
5 8 1 4 8 |
5 8 |
Birinchi misolda javobda 2-uydagi chiroq 1 va 3-uylarni ham yoritadi, 5-uydagi chiroq esa 3, 4, 6 va 7-uylarni ham yoritadi, 9-uydagi chiroq esa 8 va 10-uylarni ham yoritadi. Natijada barcha uylar yoritiladi. Ikkinchi misolda esa chiroqlar yetarli emas.
Telegram kanalimizga obuna bo'ling