/*
小虎去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装包装不可拆分。
可是小虎现在只想购买恰好n个苹果，小虎想购买尽量少的袋数方便携带。
如果不能购买恰好n个苹果，小虎将不会购买。
输入一个整数n，表示小虎想购买的个苹果，返回最小使用多少袋子。
如果无论如何都不能正好装下，返回-1。
 */

/**
 * 解题思路：尽量使用8个苹果的袋子进行装配，剩余的苹果数量如果可以被6整除，则使用6个苹果的袋子进行装配。
 * 如果不能恰好装下，减少8个苹果袋子的数量，再次尝试。
 * 提前退出的情况：剩余苹果数量大于24个，因为6和8的最小公倍数是24。
 *
 * @param apple 小虎想购买的苹果数量
 * @return 最小使用的袋子数量，若不能正好装下返回-1
 */
public static int minBags(int apple) {
    if (apple < 0) {
        return -1;
    }
    int bag6 = -1;  // 使用6个苹果袋子的数量
    int bag8 = apple / 8;  // 使用8个苹果袋子的数量
    int rest = apple - 8 * bag8;  // 剩余的苹果数量
    while (bag8 >= 0 && rest < 24) {
        int restUse6 = minBagBase6(rest);
        if (restUse6 != -1) {
            bag6 = restUse6;
            break;
        }
        rest = apple - 8 * (--bag8);
    }
    return bag6 == -1 ? -1 : bag6 + bag8;
}

// 如果剩余苹果数量rest可以被6个苹果的袋子搞定，返回袋子数量；否则返回-1
public static int minBagBase6(int rest) {
    return rest % 6 == 0 ? (rest / 6) : -1;
}


/**
 * 打表法，特别适合输入输出都是简单类型，并且变量很少，可以枚举入参对应出参的情况。
 * 根据题意，枚举所有的返回情况。
 * @param apple 小虎想购买的苹果数量
 * @return 最小使用的袋子数量，若不能正好装下返回-1
 */
public static int minBagAwesome(int apple) {
    if ((apple & 1) != 0) {
        return -1;
    }
    if (apple < 18) {
        return apple == 0 ? 0 : (apple == 6 || apple ==

8) ? 1 : (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;
    }
    return (apple - 18) / 8 + 3;
}

/*
牛牛和羊羊都很喜欢青草。今天他们决定玩青草游戏。
最初有一个装有n份青草的箱子，牛牛和羊羊依次进行，牛牛先手，羊羊后手。
在每个回合中，每个玩家必须吃一些箱子中的青草，所吃的青草份数必须是4的x次幂，比如1、4、16、64等等。
不能在箱子中吃到有效份数青草的玩家落败。假定牛牛和羊羊都是按照最佳方法进行游戏，请输出胜利者的名字。
 */

/**
 * 解题思路：根据当前的青草份数，判断先手或后手的情况。
 * 当青草份数是0或2时，后手获胜，否则先手获胜。
 * 如果青草份数大于5，通过递归调用判断子过程的胜负情况。
 * 子过程中如果后手获胜，则表示先手获胜；如果后手获胜，则表示先手获胜。
 *
 * @param n 初始青草份数
 * @return 胜利者的名字，"先手"或"后手"
 */
public static String winner(int n) {
    if (n < 5) {
        return (n == 0 || n == 2) ? "后手" : "先手";
    }
    int base = 1;  // 先手决定吃的青草份数
    while (base <= n) {
        if (winner(n - base).equals("后手")) {
            return "先手";
        }
        if (base > n / 4) {
            break;
        }
        base *= 4;
    }
    return "后手";
}

/**
 * 打表法，根据青草份数直接判断胜利者。
 * 若青草份数是0或2的倍数，后手获胜，否则先手获胜。
 * @param n 初始青草份数
 * @return 胜利者的名字，"先手"或"后手"
 */
public static String winnerAwesome(int n) {
    if (n % 5 == 0 || n % 5 == 2) {
        return "后手";
    } else {
        return "先手";
    }
}

public static void main(String[] args) {
    int n = 587687687;

    for (int i = 1; i <= n; i++) {
        System.out.println(i + " : " + winner(i));
    }

    if ((n % 4) % 2 == 1) {
        System.out.println("后手");
    } else {


        System.out.println("先手");
    }

    System.out.println("========");

    printWinner(n);
}