黑客等级中的反游戏程序

Question

我用HackerRank解决了c#的问题。但是，在提交代码时，9的测试用例由于超时错误而被终止。

路易丝和理查德开发了一款数字游戏。他们选择一个数字并检查它是否是2的幂。如果是，他们将它除以2。如果不是，他们会将它减为下一个较低的数，即2的幂。谁把这个数字减到1，谁就赢了。露易丝总是开始。

给定初始值，确定谁赢了这场比赛。

示例

先轮到露易丝了。她确定132不是2的幂，下一个下一次方是128，所以她从132减去它，然后把4传给Richard。4是2的幂，所以理查德把它除以2，然后把2传给路易丝。同样，2是一种力量，所以她把它除以2，达到1。她赢得了比赛。

更新，如果他们最初设置计数器为1，理查德获胜。路易丝不能采取行动，所以她输了。

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

    /*
     * Complete the 'counterGame' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts LONG_INTEGER n as parameter.
     */

    public static string counterGame(long n)
    {
        // Write your code here
        int isWho = 0;
        
        while(n != 1)
        {
            int pow=0;
            long n_maximus = n;
            
            while(n_maximus > 1)
            {
                n_maximus >>= 1; 
                pow++; 
            }

            long minPow = 1 << pow; 
            if(n - minPow == 0)
            {
                n = n >> 1; 
            }
            else 
            {
                n -= minPow; 
            }
            
            isWho++; /
            
        }
        
        return (isWho & 1) != 0 ? "Louise" : "Richard";
    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine().Trim());

        for (int tItr = 0; tItr < t; tItr++)
        {
            long n = Convert.ToInt64(Console.ReadLine().Trim());

            string result = Result.counterGame(n);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

Answer 1

超时的原因是long minPow = 1 << pow;。如果使用一些较大的值调试代码，您将看到minPow甚至没有关闭您所期望的值。

例如，使用660570904136157尝试您的代码。pow将是49岁，而1 << pow将是131072，但您会期望达到562949953421312。

其原因是因为1是一个int，而不是long。您实际得到的是1 << 17，即1 << (49 - 32)。要获得正确的结果，您应该指定1是带有long的1L。当用long minPow = 1 << pow;更改long minPow = 1L << pow;时，代码将通过所有测试。