B - rng_10s

Quiz

https://atcoder.jp/contests/agc026/tasks/agc026_b

Submit

https://atcoder.jp/contests/agc026/submissions/4482224

基礎

  • A<BだとNo
  • D<BだとNo
  • よって、以降はA>=B, B>=D

分析

  • テストケース1の最初のを見てみると、6になった後にNo
  • これは、CとBの間であり、この区間に入ると補充できずにNo
  • 2, 4, 6と徐々に危険ゾーンに近づいていると分かる
  • この刻み幅はD-B
  • 始点2は、AからBを負にならない数だけ引いたもの
  • 2から刻みで6を踏んでしまうとNo
  • 刻みが大きくて危険ゾーンを越えれても安心できない。B消費で元に戻ったときも踏まない必要がある
  • 図より、gcd(刻み, B)のステップで危険ゾーンを踏まなければYes

f:id:peroon:20190306061700j:plain

テストケース

1
231493377467046671 167237005795662710 75743987639229921 371262972310963173
No

その他

  • タイトルは「リンゴジュース」と読むそう