#c# #algorithm
#c# #алгоритм
Вопрос:
В настоящее время я участвую в конкурсе Google Kickstart, и в настоящее время я работаю над проблемой четных цифр из раунда A 2018 года.
Я создал следующий алгоритм, и когда я его тестирую, он работает просто великолепно. Но проблема в том, что когда я отправляю его на платформу и нажимаю кнопку «Попытка», это показывает, что мой вывод неверен.
Я повторил тестирование, используя более крупные и сложные числа, но я просто не могу найти, в чем дело.
Описание проблемы:
У Supervin есть уникальный калькулятор. У этого калькулятора есть только дисплей, кнопка «Плюс» и кнопка «минус». В настоящее время на дисплее калькулятора отображается целое число N.
Нажатие кнопки «Плюс» увеличивает текущее число, отображаемое на дисплее калькулятора, на 1. Аналогично, нажатие кнопки минус уменьшает текущее число, отображаемое на дисплее калькулятора, на 1. Калькулятор не отображает никаких начальных нулей. Например, если на дисплее калькулятора отображается 100, нажатие кнопки минус один раз приведет к отображению калькулятором 99.
Супервину не нравятся нечетные цифры, потому что он считает их «нечетными». Поэтому он хочет отобразить целое число только с четными цифрами в десятичном представлении, используя только кнопки калькулятора. Поскольку калькулятор немного устарел, а кнопки трудно нажимать, он хочет использовать минимальное количество нажатий кнопок.
Пожалуйста, помогите 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 amp;amp; odds.Contains(PN.ToString()[i]) amp;amp;
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 amp;amp;
!odds.Contains(PN.ToString()[i - 1]) amp;amp;
odds.Contains(PN.ToString()[i])) // EVEN - ODD
{
presses_p = Math.Pow(10, pdegits);
PN = Math.Pow(10, pdegits);
}
else if (i != 0 amp;amp;
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 amp;amp;
odds.Contains(PN.ToString()[i])) // ODD Only
{
presses_p = Math.Pow(10, pdegits);
PN = Math.Pow(10, pdegits);
}
#endregion
#region Negatives
if (i > 0 amp;amp;
odds.Contains(NN.ToString()[i]) amp;amp;
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 amp;amp;
!odds.Contains(NN.ToString()[i - 1]) amp;amp;
odds.Contains(NN.ToString()[i])) // EVEN - ODD
{
presses_n = Math.Pow(10, pdegits);
NN -= Math.Pow(10, pdegits);
}
else if (i != 0 amp;amp;
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 amp;amp;
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;
}
Комментарии:
1. Пожалуйста, предоставьте ссылку или, лучше, ссылку и описание проблемы
2. Это соревнования по кодированию. withgoogle.com/kickstart/round / … правильная ссылка?
3. Да, это правильная ссылка
4. Я добавил описание проблемы
5. Отладка чужого кода сложна , особенно такого загадочного кода, как этот, с редкими комментариями. Я не ожидаю, что кто-либо приложит усилия для поиска недостатков в вашем коде. Как правило, стоит объяснить свой алгоритм в комментариях вверху, а затем в коде указать, какой бит реализует какой бит алгоритма, как для таких людей, как мы, помогающих вам, для ваших коллег, так и для вас самих в будущем!
Ответ №1:
Хорошо, тогда давайте начнем с вырожденных случаев:
- Если нам даны все четные цифры номера (например
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
Комментарии:
1. Вы можете немного расширить свой второй вырожденный случай — если только конечная цифра многозначного числа нечетна (т. Е.
left == value.Length - 1), тогда результат равен 1. Не то, чтобы это имело какое-либо практическое влияние…2. @canton7: Вы совершенно правы, спасибо! Я отредактировал ответ
3. (Для справки, я запустил этот код и отправил результаты на страницу Google Kickstart, и он прошел)
4. @greybeard: как может самой левой нечетной цифре предшествовать нечетная цифра?
5. @DmitryBychenko: если строка содержит ‘9xxxx’, то вы вычитаете из ‘8xxxx’? Я не знаю c #, поэтому интересно, как это будет обрабатывать случай 2999 и случай 9888?