Masala #1029
Crazy monster game #2
Azimjon crazy monster game o'yinini o'ynashni yoqtiradi. Ushbu o'ynda \(n\) ta monster ga qarshi jang olib borish kerak bo'ladi(monsterlar bitta chiziqda joylashgan).
Azimjon monsterlar ustidan g'alaba qozonishi uchun dastlab har bir monsterning umumiy kuchini aniqlab olishi kerak. \(i-\)monsterning kuchi \(s_i\) ga teng, umumiy kuchi esa \(i-\)monsterdan ko'pi bilan \(r\) masofadagi monsterlar kuchlari yig'indisiga teng.
Har bir monsterni umumiy kuchini aniqlab bo'lgach Azimjon jang qilishga hozirlanadi va Azimjonning dastlabki kuchi \(h\) ga teng. Agar \(i-\)monsterning umumiy kuchidan Azimjonning kuchi kam bo'lmasa \(i-\)monster ustidan g'alaba qozonadi(Azimjon istalgan monster bilan jangga kirishi mumkun deb qaralsin va u bir vaqtda bir nechta monsterlar bilan jang qilmaydi) va \(s_i\) bonusga ega bo'ladi, uning kuchi \(h=h+s_i\) ga ortadi. Aks holda mag'lubiyatga uchraydi.
Bu o'yinda Azimjon g'alaba qozonadimi buni aniqlashda unga yordam bering.
Kirish faylining dastlabkis satrida \(n, r, h(1\leq n\leq 10^6, 0\leq r\leq n,0\leq h\leq 10^9)\) butun sonlar. Kiyingi satrda \(n\) son \(s_i(1\leq s_i\leq 10^9)\) monsterlar kuchlari beriladi.
Agar o'yinda Azimjon g'alaba qozonsa "Next level" so'zini va jami to'plagan achkosini bitta satrda probil bilan ajratilgan holda chop eting. Aks holda "Game over" so'zini chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
3 1 99 1 0 100 |
Next level 200 |
2 |
3 1 99 1 1 100 |
Game over |
Birinchi testda monsterlar kuchlari \([1,0,100]\) ga teng bo'lsa umumiy kuchlari \([1,101,100]\) ga teng. Azimjon dastlab birinchi monster bilan janga kiradi\((1\leq99)\) va uni mag'lubiyatga uchratib 1 bonsuga ega bo'ladi \(99+1\). Endi u uchinchi monster bilan jang qiladi\((100\leq100)\) va 100 bonusga ega bo'ladi \(100+100\). Nihoyat oxirgi monsterni mag'lubiyatga \((101\leq200)\) uchratadi \(200+0\). Jami bonuslari \(200\).
Ikkinchi testda monsterlar kuchlari \([1,1,100]\) ga teng bo'lsa umumiy kuchlari \([2,102,101]\) ga teng. Azimjon birinchi monster bilan jang qiladi\((2\leq 99)\) va uni mag'lubiyatga uchratib 1 bonusga ega bp'ladi \(99+1\). Endi uning kuchi \(100\) ga teng ammo qolgan ikki monster umumiy kuchlaridan kichik bo'lganligi uchun o'yinda mag'lubiyatga uchraydi.