結果

問題 No.3633 Rabbit and turtle
コンテスト
ユーザー 👑 ssmbc2929_bartok
提出日時 2026-06-12 16:54:13
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 2,244 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 223 ms
コンパイル使用メモリ 96,232 KB
実行使用メモリ 118,304 KB
最終ジャッジ日時 2026-08-21 20:53:35
合計ジャッジ時間 4,498 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 1
other RE * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from math import gcd

def floor_sum(n, m, a, b):
    # sum_{i=0}^{n-1} floor((a*i + b)/m)   (ACL版, m>=1, n>=0, a,b負も可)
    ans = 0
    if a < 0:
        a2 = a % m
        ans -= n * (n - 1) // 2 * ((a2 - a) // m)
        a = a2
    if b < 0:
        b2 = b % m
        ans -= n * ((b2 - b) // m)
        b = b2
    while True:
        if a >= m:
            ans += n * (n - 1) // 2 * (a // m)
            a %= m
        if b >= m:
            ans += n * (b // m)
            b %= m
        ymax = a * n + b
        if ymax < m:
            break
        n, b, m, a = ymax // m, ymax % m, a, m
    return ans

def solve(A, B, D, R):
    # 疲労度の漸化式は f -> D - ((-f) mod R)。f_n ≡ (n+1)D (mod R) より
    # 超周期は P = R/gcd(D,R) 回の移動。閉じた式で超周期の総ターン数を出す。
    g = gcd(D, R)
    P = R // g                  # 超周期に含まれる移動回数
    Q, S = divmod(D, R)         # Q = floor(D/R), S = D mod R
    Tsuper = P * (Q + 1) + S // g   # 超周期の総ターン数

    # うさぎ P*A 進む / かめ B*Tsuper 進む を比較（10^100 は十分大きく漸近が支配）
    lhs, rhs = P * A, B * Tsuper
    if lhs > rhs:
        return "rabbit"
    if lhs < rhs:
        return "turtle"

    # 平均同速：終了位置（10^100 mod Tsuper）で勝敗が決まる
    rem = (10 ** 100) % Tsuper
    if rem == 0:
        return "tie"

    # C_i = i 回移動した時点までの累積ターン数 = i*(Q+1) + Long(i)
    #   Long(i) = #{k in [1,i] : (kD mod R) in [1,S]} = N_i(S+1) - floor(i/P)
    def C(i):
        c = S + 1
        Ni = floor_sum(i + 1, R, D, 0) - floor_sum(i + 1, R, D, -c) - 1
        Long = Ni - i // P
        return i * (Q + 1) + Long

    # rem ターン目までに行われた移動回数 = 最小の i で C_i >= rem
    lo, hi = 0, P
    while lo < hi:
        mid = (lo + hi) // 2
        if C(mid) >= rem:
            hi = mid
        else:
            lo = mid + 1
    moves = lo

    rl, rr = moves * A, B * rem
    if rl > rr:
        return "rabbit"
    if rl < rr:
        return "turtle"
    return "tie"

def main():
    A, B, D, R = map(int, sys.stdin.read().split())
    print(solve(A, B, D, R))

main()
0