Problemi 155

Kërkesa

Ari dhe Riku po luajnë një lojë me fije shkrepësesh. Në fillim janë dy grumbuj me fije shkrepësesh me N dhe M fije, dhe Ari luan gjithmonë i pari. Në çdo lëvizje, lojtari që ka radhën heq X fije nga njëri prej grumbujve, të tilla që X është shumëfish i numrit të fijeve në grumbullin tjetër. Fiton ai që boshatis njërin prej grumbujve (heq fijet e fundit).

Duke ditur numrin e fijeve në secilin pirg, si dhe që Ari luan i pari, dhe të dy luajnë në mënyrën më të mirë të mundshme (pa gabime), gjeni se kush e fiton lojën.

Referenca: https://www.codechef.com/problems/MATCHS

Shembull

$ cat input.txt
5
1 1
2 2
1 3
155 47
6 4

$ python3 prog.py < input.txt
Ari
Ari
Ari
Ari
Rich

Zgjidhja

for _ in range(int(input())):
    a, b = [int(i) for i in input().split()]
    a, b = max(a,b), min(a,b)
    turn = 'Ari'
    while True:
        if a % b == 0 or a // b > 1:
            print(turn)
            break
        a, b = b, a % b
        turn = 'Rich' if turn == 'Ari' else 'Ari'