我目前正在谷歌kickstart竞赛中练习,目前正在进行Even Digits problem from Round A of 2018的训练。
我已经创建了以下算法,当我测试它时,它工作得非常好。但问题是,当我提交到平台并按下“尝试”按钮时,它表明我的输出不正确。
我试着用更大更复杂的数字测试它,但我就是找不到是什么情况。
问题描述:
Supervin有一个独特的计算器。这个计算器只有一个显示器,一个加号按钮和一个减号按钮。当前,整数n显示在计算器显示屏上。
按加号按钮可将计算器显示屏上显示的当前数字增加1。类似地,按减号按钮将计算器显示的当前数字减少1。计算器不显示任何前导零。例如,如果计算器显示屏上显示100,按一次减号按钮将使计算器显示99。
 Supervin不喜欢奇数,因为他认为它们是“奇数”因此,他希望仅使用计算器按钮显示十进制表示中只有偶数位数的整数。由于计算器有点旧,按键也很难按下,他想用最少的按键次数。
请帮助Supervin确定使计算器显示不带奇数的整数的最小按钮按下次数。
输入
输入的第一行给出了测试用例的数量,然后是T.T测试用例。
每一行以一个整数N开头:
最初显示在Supervin计算器上的整数。
这是我的代码:

public static void Main(string[] args)
{
  var SCount = Console.ReadLine();
  long Count = Convert.ToInt64(SCount);

  for (long i = 0; i < Count; i++)
  {
    var val = Console.ReadLine();
    long l = Convert.ToInt64(val);

    Console.WriteLine("Case #{0}: {1}", i + 1, Slover4(l));
  }
}

public static long Slover4(double N)
{
  char[] odds = { '1', '3', '5', '7', '9' };

  double presses_p = 0;
  double PN = N;
  double presses_n = 0;
  double NN = N;

  double pdegits = -1;
  for (int i = PN.ToString().Length - 1; i >= 0; i--)
  {
    pdegits += 1;

    //2110
    //2018 EVEN EVEN (ODD EVEN)  ---->
    //11   ODD OOD               <----
    //1    ODD                   ---->
    //42   EVEN EVEN             XXXXX 6969 1 | 6970 30 | 7000 -200 | 6800

    #region Positives
    if (i > 0 && odds.Contains(PN.ToString()[i]) &&
        odds.Contains(PN.ToString()[i - 1])) // ODD - ODD
    {
      var val = int.Parse(string.Concat(PN.ToString()[i - 1], PN.ToString()[i]));
      var lv = int.Parse(PN.ToString()[i].ToString());
      //15 17  19
      //5  3   1
      presses_p += (5 - (lv - 5)) * Math.Pow(10, pdegits);
      PN += (5 - (lv - 5)) * Math.Pow(10, pdegits);
    }
    else if (i != 0 &&
             !odds.Contains(PN.ToString()[i - 1]) &&
             odds.Contains(PN.ToString()[i])) // EVEN - ODD
    {
      presses_p += Math.Pow(10, pdegits);
      PN += Math.Pow(10, pdegits);
    }
    else if (i != 0 &&
             odds.Contains(PN.ToString()[i - 1])) // ODD - EVEN
    {
      var val = int.Parse(string.Concat(PN.ToString()[i - 1], PN.ToString()[i]));
      var lv = int.Parse(PN.ToString()[i].ToString());

      //10 12 14 16 18
      //10  8  6  4  2  ->

      //10 12 14|
      //2 4  6 |
      presses_p += (10 - lv) * Math.Pow(10, pdegits);
      PN += (10 - lv) * Math.Pow(10, pdegits);
    }
    else if (i == 0 &&
             odds.Contains(PN.ToString()[i])) // ODD Only
    {
      presses_p += Math.Pow(10, pdegits);
      PN += Math.Pow(10, pdegits);
    }
    #endregion

    #region Negatives

    if (i > 0 &&
        odds.Contains(NN.ToString()[i]) &&
        odds.Contains(NN.ToString()[i - 1])) // ODD - ODD
    {
      var val = int.Parse(string.Concat(NN.ToString()[i - 1], NN.ToString()[i]));
      var lv = int.Parse(NN.ToString()[i].ToString());
      //11 13 15 17 19
      //3  5  7  9  11
      presses_n += (3 + (lv - 1)) * Math.Pow(10, pdegits);
      NN -= (3 + (lv - 1)) * Math.Pow(10, pdegits);
    }
    else if (i != 0 &&
             !odds.Contains(NN.ToString()[i - 1]) &&
             odds.Contains(NN.ToString()[i])) // EVEN - ODD
    {
      presses_n += Math.Pow(10, pdegits);
      NN -= Math.Pow(10, pdegits);
    }
    else if (i != 0 &&
             odds.Contains(NN.ToString()[i - 1])) // ODD - EVEN
    {
      var val = int.Parse(string.Concat(NN.ToString()[i - 1], NN.ToString()[i]));
      var lv = int.Parse(NN.ToString()[i].ToString());

      //10 12 14 16 18
      //2  4  6  8  10  <-

      presses_n += (2 + lv) * Math.Pow(10, pdegits);
      NN -= (2 + lv) * Math.Pow(10, pdegits);
    }
    else if (i == 0 &&
             odds.Contains(NN.ToString()[i])) // ODD Only
    {
      presses_n += Math.Pow(10, pdegits);
      NN -= Math.Pow(10, pdegits);
    }
    #endregion
  }

  //$"P:{presses_p} - N - {presses_n}";
  return presses_p < presses_n ? (long)presses_p : (long)presses_n;
}

最佳答案

好吧,那么,让我们从退化的情况开始:
如果给我们所有偶数位数(例如2048),我们返回0
如果最后一个数字是奇数(例如64087),则返回1
现在让left成为最左边奇数(leftDigit)的索引,例如。

 2480032581
      ^
      left = 5 (since 2, 4, 8, 0, 0 are even)
      leftDigit = 3

我们可以把初始号码转换成(按-键)
 2480028888

或(按+键)进入
 2480040000

最后,我们可以比较这两种可能性,并采取一个需要较少的压力:
 "-"  wants 2480032581 - 2480028888 == 3693 presses
 "+"  wants 2480040000 - 2480032581 == 7419 presses

对于给定的数字,按-是一个更好的策略,因此我们返回3693
请注意,如果leftDigit9我们将坚持按"-"键(忽略+策略)。
C代码:
private static long Solution(string value) {
  int left = -1;

  for (int i = 0; i < value.Length; ++i) {
    if ((value[i] - '0') % 2 != 0) {
      left = i;

      break;
    }
  }

  if (left < 0)
    return 0;                 // All even digits number
  else if (left == value.Length - 1)
    return 1;                 // The very last digit is the only odd one

  long initial = long.Parse(value.Substring(left));
  int leftDigit = value[left] - '0';

  if (leftDigit == 9)
    return initial - long.Parse(new string('8', value.Length - left));

  long plus =
    long.Parse((leftDigit + 1).ToString() + new string('0', value.Length - left - 1)) -
    initial;

  long minus = initial -
    long.Parse((leftDigit - 1).ToString() + new string('8', value.Length - left - 1));

  return plus < minus ? plus : minus;
}

演示:
  string[] tests = new[] {
    "42",
    "11",
    "1",
    "2018"
  };

  string report = string.Join(Environment.NewLine, tests
    .Select(test => $"{test,6} -> {Solution(test),3}"));

结果:
    42 ->   0
    11 ->   3
     1 ->   1
  2018 ->   2

10-06 01:57