Muallif: __thecrash__
E. Park lampalari
Vaqt limiti: 1000 ms Xotira limiti: 256 mb
Sizga \(n \times m\) maydonning tomonlari beriladi. Maydonda uzunligi \(1\) teng yo'laklar hamda \(1 \times 1\) o'lchamdagi bo'g'lar mavjud bo'lib, ushbu maydonning barcha qismini lampalar orqali yoritish talab etiladi. Lampani faqat istalgan yo'lakning o'rtasiga joylashtirish mumkin. Lampa o'zi turgan ikkita qo'shni bo'g'larni yoritadi ( yoki agar maydon chegarasida bo'lsa, faqat bitta bo'g'ni yoritadi).
Misol: rasmda tasvirlangan \(4 \times 5\) maydonda \(1\) teng yo'laklar soni \(49\) ta, \(1 \times 1\) bo'g'lar soni \(20\) ta ga teng. Aylana shaklda sariq belgilar lampalar hisoblanadi. Yoritilgan joylar sariq bilan belgilangan joriy rasmda maydonning barcha qismi yoritilmagan.
Sizning vazifangiz \(n \times m\) maydonni barcha qismini yoritish uchun kerak bo'ladigan minimal lampalar sonini aniqlashdan iborat.
Kiruvchi ma'lumotlar
Kirish faylida ikkita natural son \(n, m\) (\(1 \le n, m \le 10^5\)) maydon o'lchami beriladi.
Chiquvchi ma'lumotlar
Chiqish faylida minimal kerak bo'ladigan lampalar sonini chop eting.
Misollar
| # | Input.txt | Output.txt |
|---|---|---|
1 |
1 1 |
1 |
2 |
1 3 |
2 |
Izoh
Ikkinchi test uchun lampalarning optimal joylashuvi rasmda tasvirlangan.
