Каосар та Гра (Розбір)

Рішення

Розглядайте фальшивий стрибок як особистий пропуск: він споживає $1$ з вашого бюджету (у вас $p$, у Каосара $q$) і залишає робота на тій же сходинці, просто передаючи хід супернику. Перший пропуск проходить, і згадайте базовий факт для гри "взяти $\mathrm{1..}k$": гравець, який робить хід, програє точно на сходинках, які є кратними (k+1), а в іншому випадку виграє, переміщуючись до найближчого нижнього кратного (k+1).

Тепер знову введіть пропуски. Пропускати має сенс лише тоді, коли ви стикаєтеся з програшною базовою позицією (кратне (k+1)): якщо ви на виграшній базовій позиції, ви повинні негайно перейти до програшної для вашого суперника; віддаючи хід, ви нічого не виграєте. Отже, щоразу, коли виникає програшна базова позиція, обидва гравці хочуть пропустити; ці пропуски споживають два бюджети симетрично, поки одна сторона не закінчиться першою. Якщо p=q, щоразу, коли з'являється програшна базова позиція, два пропуски нейтралізують один одного парами, і ми повертаємося до базової гри: гравець, який робить хід з цієї позиції, є таким же, як без пропусків, тому загальний результат є точною базовою правилом, а саме ви програєте, якщо n \bmod (k+1)=0.

Якщо p\neq q, сторона з більшим бюджетом завжди може забезпечити, щоб інший гравець був першим, хто повинен фактично зробити хід з програшної базової позиції: щоразу, коли така позиція з'являється, обидва намагаються пропустити; після \min(p,q) таких протистоянь менший бюджет вичерпується на один крок раніше, і на наступній програшній базовій позиції цей гравець змушений зробити хід. Як тільки суперник є тим, хто повинен зробити хід з програшної базової позиції, ви відновлюєте базову виграшну стратегію (завжди переходьте до найближчого нижнього кратного (k+1) на своїх ходах), і подальші пропуски не потрібні. Отже, якщо p>q, ви виграєте для всіх $n,k$; якщо p<q, ви програєте для всіх $n,k$; а якщо p=q, гра зводиться до базового випадку з звичайною умовою на n \bmod (k+1).

Складність $\mathcal{O}(1)$

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