c# - Google Kickstart 2018 年 A 轮的 "Even Digits"问题

Question

我目前正在 Google Kickstart 竞赛中练习，我目前正在研究 Even Digits problem from Round A of 2018 .

我创建了以下算法，当我对其进行测试时，它运行得非常好。但问题是，当我提交到平台并按下“尝试”按钮时，它显示我的输出不正确。

我尝试使用更大、更复杂的数字重新测试它，但我只是找不到问题所在。

Problem Description:

 Supervin has a unique calculator. This calculator only has a display, a plus button, and a minus button. Currently, the integer N is displayed on the calculator display.
 Pressing the plus button increases the current number displayed on the calculator display by 1. Similarly, pressing the minus button decreases the current number displayed on the calculator display by 1. The calculator does not display any leading zeros. For example, if 100 is displayed on the calculator display, pressing the minus button once will cause the calculator to display 99.
 Supervin does not like odd digits, because he thinks they are "odd". Therefore, he wants to display an integer with only even digits in its decimal representation, using only the calculator buttons. Since the calculator is a bit old and the buttons are hard to press, he wants to use a minimal number of button presses.
 Please help Supervin to determine the minimum number of button presses to make the calculator display an integer with no odd digits.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing an integer N: the integer initially displayed on Supervin's calculator.

这是我的代码:

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;
}

Answer 1

好吧，让我们从退化的情况开始:

1. 如果给定所有偶数数字(例如2048)，我们返回0
2. 如果只有最后一位是奇数(例如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。请注意，如果 leftDigit 是 9 我们将坚持 "-" 按下(并忽略 + 策略).

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