Suvenirlər
Siz yalnız iki növ sikkənin istifadə edildiyi bir ölkədə məzuniyyətdəsiniz: gümüş və qızıl. Qızıl sikkənin dəyəri gümüş sikkələrə nisbətən daha yüksəkdir, çünki yalnız bu iki növ sikkə mövcuddur. Bu, tacirlər üçün əlverişsiz olsa da, onlar üçüncü növ sikkə ilə məşğul olmaq istəmirlər.
Tacirlərin ideyası budur ki, gümüş sikkələrin dəyəri elə dəyişdirilsin ki, qızıl sikkə daha az gümüş sikkəyə başa gəlsin. Onlar gümüş sikkələri paketlərə bağlayır və yalnız qızıl və paketlənmiş gümüş sikkələrlə qaytarırlar, lakin ayrı-ayrı gümüş sikkələrlə yox. Lakin onlar gümüş paketinin dəyərinə bölünən qiymətlərini dəyişmirlər.
Beləliklə, tacirlər qaytarılmanı yuvarlaqlaşdırmalıdırlar. Müxtəlif satıcılar müxtəlif yuvarlaqlaşdırma üsullarından istifadə edirlər. Dürüst tacirlər ən yaxın dəyərə və bərabərlik halında yuxarıya doğru yuvarlaqlaşdırırlar. Acgöz tacirlər həmişə aşağıya yuvarlaqlaşdırırlar. Səxavətli tacirlər həmişə yuxarıya yuvarlaqlaşdırırlar. Satıcılar paketlərin ölçüsü barədə də razılaşmayıblar, buna görə də onların hamısı fərqli ola bilər. Lakin onlar həmişə qızıl sikkənin cari dəyərinin gümüş sikkələrdəki tam bölünən faktorudur.
Sizin bir neçə qızıl sikkəniz qalıb və mümkün qədər çox suvenir almaq istəyirsiniz. Siz artıq bazardakı bütün tacirlərin fərqli qiymətlərini (qiymət bir qızıl sikkənin dəyərindən aşağıdır) və hansı tacirin acgöz, səxavətli və dürüst olduğunu, həmçinin onların gümüş sikkə paketlərinin ölçülərini bilirsiniz. Siz bazarı yalnız bir dəfə gəzməyə vaxtınız var, buna görə də tacirləri göstərilən ardıcıllıqla ziyarət etməlisiniz. Bundan əlavə, siz səxavətli tacirlərdən istifadə etmək istəmirsiniz. Beləliklə, əgər dəqiq qiymət ödəyə bilsəniz, bunu edəcəksiniz; əks halda, dəqiq bir qızıl sikkə ödəyəcəksiniz. Siz digər tacirlərə ya dəqiq qiymət, ya da bir qızıl sikkə ödəyirsiniz. Hər satıcıdan yalnız bir suvenir alırsınız. Sonra qaytarılan gümüş sikkə paketlərini açırsınız ki, sikkələri ayrı-ayrılıqda istifadə edə biləsiniz.
Məsələn, üçüncü testdə siz ilk satıcını ötürür və ikinci satıcıdan qızıl sikkə ilə alırsınız. Üçüncü satıcıya dəqiq ödəyə bilmədiyiniz üçün yenidən qızıl sikkə istifadə edirsiniz. İki alış-verişdə (altı və səkkiz gümüş sikkə) qaytarılanları dəyişdirərək qalan üç tacirdən suvenirlər ala bilərsiniz.
Giriş məlumatları
Birinci sətir üç tam ədəd g, c və n ehtiva edir, burada g bir qızıl sikkənin gümüş sikkələrdəki dəyərini, c sizin malik olduğunuz qızıl sikkələrin sayını və n bazardakı tacirlərin sayını göstərir (1 < g ≤ 100, 1 ≤ c, n ≤ 100).
Növbəti n sətirin hər biri bir taciri təsvir edir. Bu sətirlərin hər biri tacirin yuvarlaqlaşdırma vərdişini təsvir edən “greedy”, “honest” və ya “generous” sətiri ilə başlayır. Bu sətirdən sonra p[i] və s[i] iki tam ədəd gəlir, burada p[i] tacirin istifadə etdiyi gümüş sikkə paketinin ölçüsünü, s[i] isə bu tacirdəki suvenirin gümüş sikkələrdəki qiymətini göstərir (1 ≤ p[i] ≤ g, 1 ≤ s[i] < g).
Çıxış məlumatları
Maksimum ala biləcəyiniz suvenirlərin sayını ehtiva edən bir sətir.