Masala #1176
Boltavoy va guruhlarga ajratish #2
Boltavoyni eslaysizmi? U bugun yana o'z o'quvchilarini guruhlarga ajratmoqchi. Uning o'quvchilari har xil davlatlardan kelgani uchun u guruhlarni quyidagicha ajratmoqchi.
- Hech qaysi o'quvchi guruhsiz qolib ketmaslik kerak
- Har bir guruhda 1 ta yoki 2 tadan o'quvchi bo'lishi kerak.
- Bitta davlatdan bo'lgan o'quvchilar bir xil guruhga tushib qolmasin.
Boltavoy guruhlar sonini minimallashtirmoqchi. Uning yaqin do'sti sifatida unga yordam bering
Kiruvchi ma'lumotlar:
Kirish faylining birinchi qatorida N (1≤N≤\(10^5\)) - o'quvchilar soni
Keyingi qatorda N ta sondan tashkil topgan massiv \(a_1\),\(a_2\),…,\(a_N\)(1≤\(a_i\)≤\(10^5\)) - har bir o'quvchining qaysi davlatdan ekanligi.
Chiquvchi ma'lumotlar:
Chiqish faylining yagona qatorida bitta son - minimal guruhlar sonini chop eting.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
6 3 1 1 1 1 1 |
5 |
| 2 |
2 1 2 |
1 |
Izoh:
Boltavoy guruhlarga ajirata olishi kafolatlanadi.
Telegram kanalimizga obuna bo'ling