我目前正在谷歌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
。请注意,如果
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