Счастливый билет

Задача «Счастливый билет»

Вот как представлена эта задача на сайте acmp.ru:

Счастливые билеты

(Время: 1 сек. Память: 16 Мб Сложность: 68%)

Требуется вычислить количество N-значных счастливых билетов. Напомним, что билет называется счастливым, если сумма первой половины его цифр равна сумме другой его половины. Например, билет 564159 счастливый, т.к. 5+6+4=1+5+9.

Входные данные

В единственной строке входного файла INPUT.TXT записано натуральное четное число N (N ≤ 100) – количество цифр в билете.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – количество N-значных счастливых билетов.

Примеры

INPUT.TXT

OUTPUT.TXT

1

  4 670

2

6 55252

3

12 39581170420

 

Идея решения

Как всегда начнем с простого решения. Оно может быть неэффективным, но его можно быстро реализовать. Организуем перебор всех N-значных чисел. Если очередное число «счастливое», увеличим счетчик на единицу.

Вот программа, реализующая переборный алгоритм:

/// <summary>

/// Счастливые билеты

/// Переборный алгоритм

/// </summary>

/// <param name=»N»>разрядность билета</param>

/// <returns>число счастливых билетов</returns>

ulong Perebor(int N)

{

ulong M;

ulong NP = Convert.ToUInt64(Math.Pow(10, N));

M = 0;

for (ulong i = 0; i < NP; i++)

{

if (IsHappy(i, N)) M++;

}

return M;

}

Метод IsHappy проверяет билет на «счастье»:

bool IsHappy(ulong x, int N)

{

string sN = x.ToString();

sN = sN.PadLeft(N,’0′);

string s1, s2;

int len = N / 2;

s1 = sN.Substring(N/2, len);

s2 = sN.Substring(0, len);

int sum1 = 0, sum2 = 0;

for (int i = 0; i < len; i++ )

{

sum1 += Convert.ToInt32(s1[i].ToString());

sum2 += Convert.ToInt32(s2[i].ToString());

}

return sum1 == sum2;

}

Для небольших значений N метод работает в приемлемое время. Но уже при N, равном шести, чувствуются задержки, которые становятся практически неприемлемыми с ростом N.

Эффективный алгоритм

Билет счастливый, если сумма цифр левой и правой половины номера совпадает. Зададимся вопросом, каковы могут быть значения суммы? Поскольку разрядность числа N – число четное, то сумма цифр варьируется в интервале [0, 9N/2]. Вместо того, чтобы перебирать все возможные номера, в цикле по всем возможным значениям суммы будем считать сколько номеров дают соответствует данной сумме. Если в одной половинке таких номеров K, то и во второй половинке их столько же, так что общее число счастливых билетов с данной суммой равно K*K.

Идея хорошая, но как посчитать, сколько номеров дают сумму S? От перебора номеров по понятным причинам следует отказаться. Вместо этого следует, зная S, генерировать последовательность номеров, дающих сумму S. Генерацию номеров можно осуществлять последовательно, начиная с максимального номера, двигаясь, пока не будет достигнут минимальный номер.

Для пояснения алгоритма приведу пример. Пусть N = 8, то есть рассматриваются номера из восьми цифр. Половину номера составляют четыре цифры и максимально возможная сумма S равна 36. Рассмотрим одно из возможных значений суммы, например S = 15. Максимальный номер из четырех цифр, дающий эту сумму равен 9600, минимальный – 0069. Номер, следующий по порядку за номером 9600 и дающий ту же сумму, равен 9510. Таким образом задача сводится к задаче вычисления следующего по порядку номера с заданной суммой, если известно предыдущее значение номера. Интуитивный алгоритм понятен, его формализация требует аккуратных рассуждений. Приводить их не буду, понять их можно будет, анализируя программу, реализующую данный алгоритм.

Еще одно важное усовершенствование алгоритма состоит в учете того факта, что число номеров, дающих сумму M, равно числу номеров, дающих сумму Smax – M. Так номеров из четырех цифр с суммой 0000 ровно столько же как и номеров 9999 ( для этих сумм существует ровно один номер. Этот факт позволяет практически вдвое сократить объем вычислений.

Основные идеи пояснены, остальное можно понять, анализируя программу:

/// <summary>

/// Счастливые билеты

/// </summary>

/// <param name=»N»>разрядность числа</param>

/// <returns>число счастливых билетов</returns>

ulong Parser(int N)

{

ulong M = 0, K = 0;

int len = N / 2;

int[] digits = new int[len];    //цифры числа

int[] digits_final = new int[len];

int Smax = (9 * len + 1)/2;

for (int S = 0; S < Smax ; S++ )

{//цикл по возможным значениям суммы чисел

//генерация первого числа

FirstNumber(S, digits, digits_final);

K = 1;

//цикл получения следующих чисел с той же суммой

while (ExistNextNumber(digits, digits_final))

K++;

M += K * K;

}

//Четно или нечетно N/2

if(len % 2 != 0)

return  2 * M;

else

{

FirstNumber(Smax , digits, digits_final);

K = 1;

//цикл получения следующих чисел с той же суммой

while (ExistNextNumber(digits, digits_final))

K++;

return 2 * M + K * K;

}

}

Генерация первого и последнего номера  выполняется в методе FirstNumber:

/// <summary>

/// Генерация первого (максимального) номера

/// и последнего (минимального) номера,

/// цифры которых дают сумму S

/// </summary>

/// <param name=»S»>заданная сумма</param>

/// <param name=»digits»>цифры первого номера</param>

/// <param name=»digits_final»>цифры последнего номера</param>

void FirstNumber (int S, int[] digits, int[] digits_final)

{

//формируем первое число и последнее число с суммой цифр S

int d = S;

int len = digits.Length;

for (int i = 0; i < len; i++)

{

if (d > 9)

{

digits[i] = 9;

d = d — 9;

}

else

{

digits[i] = d;

d = 0;

}

}

 

for (int i = 0; i < len; i++)

digits_final[i] = digits[len - 1 - i];

}

Основу алгоритма составляет метод ExistNextNumber, позволяющий генерировать следующее число с заданной суммой:

/// <summary>

/// Генерация очередного числа

/// </summary>

/// <param name=»digits»>текущее и следующее число</param>

/// <param name=»digits_final»>последнее число</param>

/// <returns>true, если текущее число не последнее</returns>

bool ExistNextNumber(int[] digits, int[] digits_final)

{

if (final(digits, digits_final)) return false;

int n = digits.Length;

int i = n — 1;

int j = n — 1;

//разбор случаев

//Последнюю цифру можно увеличить,

//предпоследнюю уменьшить

if (digits[n - 1] != 9 && digits[n - 2] != 0)

{

digits[n - 1]++; digits[n - 2]—;

}

else

//Число заканчивается 9-кой

if (digits[i] == 9)

{

int n9 = 1;

while (digits[i - 1] == 9) { i—; n9++; }

int item = digits[i - 1] + 1;

i—;

int i0 = 0;

while (digits[i - 1] == 0) { i—; i0++; }

digits[i - 1]—;

for (int k = 0; k < n9; k++ )

digits[i + k] = 9;

i += n9;

digits[i] = item;

i++;

while (i < n)

{ digits[i] = 0; i++; }

}

else

//Число заканчивается нулем

{

while (digits[i - 2] == 0) i—;

{

digits[i - 2]—;

digits[i - 1] = digi/tdppts[n - 1] + 1;

digits[n - 1] = 0;

}

}

return true;

}

Простой метод final завершает программу определения количества «счастья»:

/// <summary>

/// Проверка завершения

/// </summary>

/// <param name=»d»>первое число</param>

/// <param name=»f»>последнее число</param>

/// <returns>true, если числа совпадают</returns>

bool final(int[] d, int[] f)

{

int n = d.Length;

bool res = true;

int i = 0;

while (i < n && d[i] == f[i]) i++;

res = (i == n);

return res;

}

gt;lt;returns

4void FirstNumber (int S, int[] digits, int[] digits_final)/p