Kaosar və Oyun (Həll təhlili)

Həll

Saxta tullanmanı şəxsi keçid kimi görün: bu, büdcənizdən $1$ istehlak edir (sizin $p$, Kaosar'ın $q$ var) və robotu eyni pillədə saxlayır, sadəcə növbəni rəqibə verir. İlk keçidlər keçir və "1..k" oyununa dair əsas faktı xatırlayın: hərəkət edən oyunçu, (k+1)-in tam bölünən pillə saylarında məğlub olur, əks halda (k+1)-in ən yaxın aşağı tam bölünəninə hərəkət edərək qalib gəlir.

İndi keçidləri yenidən təqdim edin. Keçid yalnız itirən əsas vəziyyətlə qarşılaşdığınızda (bir (k+1)-in tam bölünəni) məqbul olur: əgər qalib bir əsas vəziyyətdəysəniz, dərhal rəqibiniz üçün itirən birinə keçməlisiniz; hərəkəti vermək heç bir şey qazandırmır. Nəticədə, itirən əsas vəziyyət meydana gəldikdə, hər iki oyunçu keçmək istəyir; bu keçidlər iki büdcəni simmetrik olaraq istehlak edir, ta ki bir tərəf əvvəlcə tükənir. Əgər p=q isə, hər dəfə itirən əsas vəziyyət meydana gəldikdə, iki keçid bir-birini cütləşdirərək neytrallaşdırır və biz əsas oyuna qayıdırıq: o vəziyyətdən hərəkət edən oyunçu, keçidlər olmadan olduğu kimi, eyni olur, buna görə də ümumi nəticə tam olaraq əsas qaydadır, yəni siz uduzursunuz əgər n \bmod (k+1)=0.

Əgər p\neq q isə, daha böyük büdcəyə sahib olan tərəf həmişə itirən əsas vəziyyətdən ilk hərəkət etməli olan digər oyunçunu təmin edə bilər: belə bir vəziyyət meydana gəldikdə, hər iki tərəf keçməyə çalışır; \min(p,q) belə qarşıdurmalardan sonra, daha kiçik büdcə bir addım əvvəl tükənir və növbəti itirən əsas vəziyyətdə həmin oyunçu hərəkət etməyə məcbur olur. Bir dəfə rəqib itirən əsas vəziyyətdən hərəkət etməli olan şəxs olduqda, siz əsas qalib strategiyanı bərpa edirsiniz (hər dövrünüzdə (k+1)-in ən yaxın aşağı tam bölünəninə hərəkət edin) və daha çox keçidə ehtiyac yoxdur. Buna görə, əgər p>q isə, siz bütün $n,k$ üçün qalib gəlirsiniz; əgər p<q isə, siz bütün $n,k$ üçün uduzursunuz; və əgər p=q isə, oyun adi şərtlərlə əsas vəziyyətə endirilir n \bmod (k+1).

Komplekslik $\mathcal{O}(1)$

for _ in range(int(input())):
   n,k,p,q = map(int,input().split())
   if p>q:
      print("bəli")
   elif p == q:
      if n%(k+1)==0:
         print("xahiş")
      else:
         print("bəli")
   else:
      print("xahiş")