2005. Subtree Removal Game with Fibonacci Tree

Program.cs

using Spectre.Console;

for (var i = 10; i >= 1; i--)
{
    AnsiConsole.MarkupLine($"Dado que n é igual a [yellow]{i:00}[/] então [blue]Alice[/] {(FibonacciTree.DoAliceWins(i) ? "[green]vence[/]" : "[red]perde[/]")}");
}

public record Node(int Value, Node? Left = null, Node? Rigth = null)
{
    public static explicit operator int(Node node)
        => node.Value;

    public static Node operator +(Node a, Node b)
        => new(a.Value + b.Value, a.Value == b.Value ? null : b, a);
}

public class FibonacciTree
{
    public static bool DoAliceWins(int n)
        => Fibonacci(n).totalNodes % 2 == 0;

    public static (Node rootNode, int totalNodes) Fibonacci(int value)
    {
        var totalNodes = 1;
        Node a = new(1);
        var b = a;

        for (int i = 1; i < value; i++)
        {
            var newNode = a + b;
            totalNodes++;
            if (a.Left is not null)
                totalNodes++;
            if (a.Rigth is not null)
                totalNodes++;
            b = a;
            a = newNode;
        }

        return (a, totalNodes);
    }
}