English

Logic of the solution

To solve this problem we need to use 2 states. A winning state and a losing state. We know that "0 0" is a F losing state and every point that is reachable from "0 0" in one move is T a winning point. which means that all of below points are T winning states:

• 0 X
• X 0
• X X

Now we need to find the lowest pair that is closest to "0 0" which does not adhere to above conditions. This new pair will become the next F losing state. It is also inherently visible that "1 2", "2 1" pairs are the closest pairs which we are looking for, so now every point that is reachable from "1 2" will also become winning points which are:

• 1 X
• X 1
• 2 X
• X 2
• X X+1
• X+1 X

As you can see at every step we find the next F losing state from the previous losing state by increasing the difference between marble heaps by 1("X X+diff", "Y Y+(diff+1)", "Z Z+(diff+2)").

Solution

To solve this problem we save every solution to save complexity(because we can save previous solutions and continue from them to find next solutions). Since at every step we find the next F losing step, we start our algorithm by adding one initial losing step "0 0". Now we have to find either the given point is a losing step or not. Since there can be only be one pair of F losing pair for any given number, (e.g. "1 2" there are no "1 X","X 1","2 X","X 2" excluding "1 2" and "2 1" that are losing steps) we look if the current point's corresponding losing point is already found or not and if it is not found than its corresponding step should be the current different ("X X+diff"), we apply the above steps and continue until we reach the desirable F losing pair. For example:

If the question asks us to find "5 25" we find all losing pairs until a losing pair containing 5(since 5 is lower than 25) is found:"0 0"->"1 2"->"3 5". Since 5's corresponding losing pair is 3 and not 25 we say that "5 25" must be a winning pair and stop the algorithm.

Note: Since 2 consecutive F losing states will have counterparts of increasing differences there cant be 2 consecutive corresponding points(["0 0"(+0), "1 2"(+1), "3 5"(+2), "4 7"(+3),"6 10"(+4) ...]). lets assume 2 consecutive F losing states are found:

• X X+diff
• Y Y+(diff+1)

Since Y can be at least X+1, Y+(diff+1) can at least be(X+diff+2) which is 2 more than X+diff so 2 pairs of consecutive losing states will at least have 2 difference for their bigger number. So after finding a losing step either the next point or the second next point will not be found(if "X Y" is a losing step either X+1 or X+2's corresponding losing point would not have been found so we will check those points and continue from 1 of them in next step).

Complexity

The complexity of the problem is O(max((from 1 to testNum)min(\(X_i,Y_i\)))+testNum). Because finding either a pair is a winning pair or a losing pair will take O(min(X,Y)) time. But since there are t tests we can use the previous solutions and continue from them which lowers the needed computation count.

Türkçe

Çözümün mantığı

Bu soruyu çözmek için 2 state kullanmamız gerekiyor. Kazanan ve kaybeden stateler. "0 0"ın bir kaybetme state'i F olduğunu ve "0 0"dan tek hamlede ulaşılabilen her bilye çiftinin bir kazanma state'i T oluşturacağını biliyoruz. Bu bilgi, aşağıdaki bilye çiftlerinin hepsinin kazanan stateler T olduğu anlamına gelir:

• 0 X
• X 0
• X X

Şimdi yukarıdaki koşullara uymayan "0 0" çiftine en yakın çifti bulmamız gerekiyor. Bu yeni çift, bir sonraki kaybetme state'i 'F' olacak. "1 2", "2 1" çiftlerinin aradığımıza en yakın çiftler olduğu da kolayca görülebilir, yani artık "1 2" den ulaşılabilen aşağıdaki her nokta da kazanan state T olacaktır:

• 1 X
• X 1
• 2 X
• 2 X
• X X+1
• X+1 X

Fark ettiğiniz gibi her adımda, bilye grupları arasındaki farkı 1 artırarak sonraki F kaybetme state'ini buluyoruz ("X X+fark", "Y Y+(fark+1)", "Z Z+(fark+2)").

Çözüm

Bu soruyu çözerken complexity'yi düşürmek adına her kaybetme state'ini F kaydediyoruz (çünkü önceki çözümlerden sonraki çözümleri bulmak için onlardan devam edebiliriz). Her adımda bir sonraki F kaybetme state'ini bulduğumuz için, algoritmayı yazarken ilk kaybetme state'i olan "0 0"'ı ekleyerek başlıyoruz. Şimdi verilen noktanın kaybedilen bir adım olup olmadığını bulmamız gerekiyor. Herhangi bir sayı için yalnızca bir çift F kaybeden state olabileceğinden (örneğin, "1 2" F kaybeden state olduğundan dolayı başka bir "1 X","X 1", "2 X","X 2" F kaybeden state yoktur, "1 2" ve "2 1" hariç) geçerli noktaya karşılık gelen kaybetme state'inin bulunup bulunmadığına bakarız. Eğer elimizdeki sayının dahil olduğu F kaybeden state bulunmadıysa bu noktaya karşılık gelen kaybetme noktası şu anki fark kadar olmalı ("X X+diff"), Bu adımı istediğimiz sayıyı içeren bir F kaybeden state bulana kadar devam ederiz. Örneğin:

Soru "5 25" durumunu bulmamızı isterse, 5 içeren bir kaybeden çift (5'ten küçük olduğu için) bulana kadar tüm kaybeden çiftleri buluruz:"0 0"->" 1 2"->"3 5". 5'e karşılık gelen kaybeden çiftinde 5'in karşılığı 25 değil 3 olduğundan "5 25"'in kazanan bir çift olacağını söyleyip algoritmayı durdurmalıyız.

Since 2 consecutive F losing states will have counterparts of increasing differences there cant be 2 consecutive corresponding points Not: Ardarda gelen 2 F kaybetme state'inin büyük kısımları artan farklarda olacağı için 2 F kaybetme state'in büyük kısımları ardışık sayıları olamaz (["0 0"(+0), "1 2"(+1) ), "3 5"(+2), "4 7"(+3),"6 10"( +4) ...]). Örneğin 2 ardışık F kaybetme state'inin bulunduğunu varsayalım:

• X X+fark
• Y Y+(fark+1)

Y en az X+1 olabileceğinden, Y+(fark+1) en az (X+fark+2) olabilir, ki bu X+fark'tan 2 fazladır yani 2 çift ardışık kaybeden durumun büyük sayıları arasında en az 2 fark olacaktır. Bu nedenle, bir kaybedilen state F bulunduktan sonra("X X+fark"), sonraki iki noktadan birinin kaybeden state'inin daha bulunmamış olmak zorundadır ("X X+fark" F kaybeden state'se, X+1 veya X+2'den en az birinin karşılığı olan kaybetme noktası bulunmamış olmalı, bu yüzden bu noktaları kontrol edeceğiz ve sonraki adımda en küçük noktadan devam edeceğiz).

Complexity

Sorunun complexity'si O(max((1'den testNum'a)min(\(X_i,Y_i\)))+testNum). Çünkü bir çiftin kazandığını veya kaybettiğini bulmak O(min(X,Y)) zaman alacaktır. Ancak t sayıda test olduğu için önceki çözümleri kullanabilir ve onlardan devam ederek gerekli hesaplama sayısını bu şekilde azaltabiliriz.

Code-C++

#include <bits/stdc++.h>

using namespace std;

int res[3000005]={0,2,1};            //<million
int FNfound=3;      //first not found
int Cdiff=2;      //current max diff


bool solve(){
    int a,b,x,y;
    cin>>a>>b;
    if(a<b)x=a,y=b;
    else x=b,y=a;
        //x  <=  y

    //-------------base cases-------------
    if(x==0){
        if(y==0)return false;
        return true;
    }
    if(x==1){
        if(y!=2)return true;
        return false;
    }
    //------------------------------------

    //---------if already found-----------
    if(res[x]!=0){
        if(y==res[x])return false;
        return true;
    }
    //------------------------------------



    //-----------iterative step-----------
    int correspongind;
    for(int i=FNfound;i<=x;i++){
        if(res[i]!=0)continue;
        correspongind=i+Cdiff;
        res[i]=correspongind;
        res[correspongind]=i;
        Cdiff++;
        if(correspongind==x){
            if(res[i+1]==0)FNfound=i+1;
            else FNfound=i+2;   //because there can't be two consecutive founds after the initial consecutive section
            return true;
        }
    }
    //------------------------------------

    if(res[x+1]==0)FNfound=x+1;
    else FNfound=x+2;
    if(y==res[x])return false;
    return true;

}

int main(){
    int t;
    cin>>t;
    while(t--)
        switch(solve()){
            case 0:cout<<'F'<<endl;break;
            case 1:cout<<'T'<<endl;break;
        }
}

Code-Python

#Python 2.7.17
res=[0 for i in range(3000005)]
res[1]=2
res[2]=1
FNfound=3
Cdiff=2

def solve(a,b):
    global FNfound
    global Cdiff
    x=min(a,b)
    y=max(a,b)

    if(x==0):
        if(y==0):
            return False
        return True
    if(x==1):
        if(y!=2):
            return True
        return False
    if(res[x]!=0):
        if(y==res[x]):
            return False
        return True

    for i in range(FNfound,x+1):
        if(res[i]!=0):
            continue
        correspongind=i+Cdiff
        res[i]=correspongind
        res[correspongind]=i
        Cdiff=Cdiff+1
        if(correspongind==x):
            if(res[i+1]==0):
                FNfound=i+1
            else:
                FNfound=i+2
            return True

    if(res[x+1]==0):
        FNfound=x+1
    else:
        FNfound=x+2
    if(y==res[x]):
        return False
    return True







t=int(input())
for i in range(t):
   a,b=[int(x) for x in input().split()]
   if(solve(a,b)==True):
       print("T")
   else:
       print("F")
#print "Hello, world!"