eolymp
bolt
Try our new interface for solving problems
Məsələlər

Sehrbaz və Canavarlar

Sehrbaz və Canavarlar

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Siz gəzməyə gedərkən birdən n canavarla rastlaşdınız. Hər bir canavarın, onun gücünü göstərən bir parametri - canı var. i-ci canavarın rastlaşma anındakı canını hi ilə işarə edək. Hər hansı bir canavarın canı 0-a və ya daha aşağı düşdükdə o yoxa çıxır.

Xoşbəxtlikdən, siz partlayış yarada bilən bacarıqlı bir sehrbazsınız. Bu partlayışlarla siz canavarların canını azalda bilərsiniz. Bir partlayışda canavarların canını aşağıdakı kimi azaltmaq olar:

Hələ də sağ olan hər hansı bir canavarı seçib, partlayışı onun yanında edirsiniz. Bu zaman həmin canavarın canı a qədər, digər bütün canavarların canı isə b qədər azalır. Burada ab öncədən verilmiş parametrlərdir və a > b.

Bütün canavarları yox etmək üçün minimum neçə partlayışa ehtiyac var?

Giriş verilənləri

İlk sətirdə üç tam ədəd: n, ab verilir. Daha sonra n sətrin hər birində bir ədəd h[i]i-ci canavarın rastlaşma anındakı canı verilir (1n10^5, 1b < a10^9, 1h[i]10^9).

Çıxış verilənləri

Bütün canavarları yox etmək üçün lazım olan minimum partlayışların sayını çıxışa verin.

İzah

Test 1.

  • Birinci partlayışı canı 8 olan canavarın yanında edin, bundan sonra canavarların canları müvafiq olaraq 3, 4, 1-1 olacaqdır.

  • İkinci partlayışı birinci partlayışdan sonra 4 canı qalan canavarın yanında edin. Bundan sonra bütün canavarlar yox olacaq.

Test 2.

  • Hər iki canavarı öldürmək üçün hər birinin yanında 2 partlayış, toplamda 4 partlayış etmək kifayətdir. Bundan az sayda partlayışla hər iki canavarı yox etmək mümkün deyil.

Nümunə

Giriş verilənləri #1
4 5 3
8
7
4
2
Çıxış verilənləri #1
2
Giriş verilənləri #2
2 10 4
20
20
Çıxış verilənləri #2
4
Giriş verilənləri #3
5 2 1
900000000
900000000
1000000000
1000000000
1000000000
Çıxış verilənləri #3
800000000
Müəllif Rashad Mammadov, Abutalib Namazov
Mənbə Azərbaycan 2019: Yuxarı yaş olimpiada hazırlığı qrupuna seçim turu