CF::GYM 100379I / Move the queen to the corner!

Posted on By 二价氢

题目:CF::GYM 100379I

给你两个数,每次可以选择:

  1. 将第一个数减去
  2. 将第二个数减去
  3. 将第两个数均减去

现在求是否必胜,和若必胜,第一步的策略

Wythoff’s Game

首先,我们可以发现,这个游戏中,a和b是完全等价的,即状态和状态没有什么不同,为了方便起见,接下来将只讨论的情况

我们可以手算出最开始的几组必败态,它们是

经过一番维基之后,知道了对于均大于3的状态,就是Wythoff游戏

对于所有的必败态,它的有

其中,为黄金分割数

于是,通过二分的方法,找到对应的,可以知道一个状态是否为必败态

接着,对于必胜态,我们可以二分必败态,找到可以转移过去的必败态,这里也可以通过二分来实现

至于为什么是二分而不是直接求得,这里是考虑到了精度问题

因为输入高达,所以C++中doublelong double都存在精度不够的问题,需要使用Java的BigDecimal类来保证精度

最后说一下,这次比赛居然没有英文题解,全靠机译俄文才得以弄清楚

AC-Code

import java.io.*;
import java.math.*;
import java.util.*;
import java.text.*;
import java.lang.*;
public class Main {
    static BigDecimal sqrt5p1 = new BigDecimal("3.23606797749978969640917366873127623544061835961152572427089");
    static BigDecimal r2 = new BigDecimal("2.0");
    static BigDecimal phi = sqrt5p1.divide(r2);
    static Scanner cin = new Scanner(new BufferedInputStream(System.in));
    public static long get_a(long tk) {
        return phi.multiply(new BigDecimal(tk)).longValue();
    }
    public static long get_b(long tk) {
        return phi.multiply(new BigDecimal(tk)).longValue() + tk;
    }
    public static void work() {
        boolean flg = false;
        long a , b , swp;
        a = cin.nextLong();
        b = cin.nextLong();
        if (b < a) {
            swp = b;
            b = a;
            a = swp;
            flg = true;
        }
        if (a <= 3) {
            if (a == 3) {
                if (b == 3) {
                    System.out.printf("2\n");
                } else {
                    if (flg) {
                        System.out.printf("1 %d 0\n" , b - 3);
                    } else {
                        System.out.printf("1 0 %d\n" , b - 3);
                    }
                }
            }
            if (a == 2) {
                if (flg) {
                    System.out.printf("1 %d 0\n" , b - 1);
                } else {
                    System.out.printf("1 0 %d\n" , b - 1);
                }
            }
            return;
        }
        if (a == b) {
            System.out.printf("1 %d %d\n" , a - 3 , a - 3);
            return;
        }
        if (b == a + 1) {
            System.out.printf("1 %d %d\n" , a - 1 , a - 1);
            return;
        }
        a--;
        b--;
        long k0 = 0;
        for (long i = 1l << 40 ; i > 0 ; i >>= 1) {
            long rb = get_b(k0 + i);
            if (rb <= a) {
                k0 += i;
            }
        }
        if (get_b(k0) == a) {
            if (get_a(k0) == b) {
                System.out.printf("2\n");
                return;
            }
            long ansa = 0;
            long ansb = b - get_a(k0);
            if (flg) {
                swp = ansa;
                ansa = ansb;
                ansb = swp;
            }
            System.out.printf("1 %d %d\n" , ansa , ansb);
            return;
        }
        //--
        k0 = 0;
        for (long i = 1l << 40 ; i > 0 ; i >>= 1) {
            long ra = get_a(k0 + i);
            if (ra <= a) {
                k0 += i;
            }
        }
        if (get_a(k0) == a) {
            if (get_b(k0) == b) {
                System.out.printf("2\n");
                return;
            }
            if (get_b(k0) < b) {
                long ansa = 0;
                long ansb = b - get_b(k0);
                if (flg) {
                    swp = ansa;
                    ansa = ansb;
                    ansb = swp;
                }
                System.out.printf("1 %d %d\n" , ansa , ansb);
                return;
            }
        }
        k0 = a;
        for (long i = 1l << 40 ; i > 0 ; i>>= 1) {
            if (k0 - i <= 0)
                continue;
            long ra = get_a(k0 - i);
            long rb = get_b(k0 - i);
            long delta = a - ra;
            if (b - delta <= rb)
                k0 -= i;
        }
        /*
        if (get_a(k0) == a && get_b(k0) == b) {
            System.out.printf("2\n");
            return;
        }*/
        long ansa = a - get_a(k0);
        System.out.printf("1 %d %d\n" , ansa , ansa);
    }
    public static void main(String[] args) {
        //for (int i = 0 ; i < 10 ; i++)
        //    System.out.printf("(%d %d)\n" , get_a(i) , get_b(i));
        phi.setScale(60 , BigDecimal.ROUND_FLOOR);
        int t;
        t = cin.nextInt();
        for (int i = 0 ; i < t ; i++) {
            work();
        }
    }
}