Задача вычисления количества счастливых билетов известна давно. Ее задавали практически любому школьнику, обучающемуся программированию. В интернете можно найти множество ее решений на разных языках программирования. Все эти варианты сводятся к перебору всех существующих билетов и проверке их на «счастливость». Получается миллион вариантов.
Но данную задачу можно решить и другим способом, перебрав всего тысячу вариантов.
Напомню, что счастливыми являются билеты, сумма первых трёх цифр номера которых равна сумме последних трёх цифр номера. Например, билет с номером «546780» является счастливым, так как сумма первых трёх цифр (5+4+6) равна сумме последних трёх цифр (7+8+0). Задача состоит в определении того, сколько всего существует счастливых билетов.
Во всех примерах она решается в лоб, но что если пойти иным путем? Вначале ответим на другой вопрос. Сколько существует различных комбинаций трех цифр (троек), которые в сумме дают n? Для ответа на этот вопрос нужно перебрать все возможные тройки (тысяча вариантов).
Сумма любых троек находится между нулем (0+0+0) и 27 (9+9+9). Поэтому можно подготовить массив сумм:
{n_0, n_1, n_2, n_3, …., n_25, n_26, n_27}
где n_i – количество троек, дающих в сумме i. При этом сумма цифр равна индексу этого элемента в массиве.
Хорошо, мы подготовим такой массив, но как это связано с билетами? Рассмотрим частный случай. Всего существует n_25 троек, дающих в сумме 25. Для каждой такой тройки существует n_25 троек, при объединении с каждой из которых будет получаться счастливый номер. Поэтому существует n_25*n_25 счастливых билетов, сумма первых трёх цифр которых равна 25. Аналогично и для других сумм. Таким образом, общее количество счастливых билетов равно:
n_0*n_0 + n_1*n_1 + …. + n_26*n_26 + n_27*n_27
Ниже приводится полный исходный код приложения, реализующего данный алгоритм.
#include <cassert> #include <stdio.h> //Количество различных вариантов сумм трех цифр #define COUNT_SUMS 28 //Суммы трех цифр unsigned char sums[COUNT_SUMS]; /****************************/ /*Инициализирует массив сумм*/ /****************************/ void InitSums(void) { unsigned char i; for (i = 0; i < COUNT_SUMS; i++) sums[i] = 0; } /********************************/ /*Обрабатывает трехзначное число*/ /********************************/ void PerformNumber(unsigned short number) { unsigned short sum = 0; unsigned short val = number; unsigned char digit; //Добавляем количество сотен digit = (unsigned char)(val / 100); sum += digit; //Добавляем количество десятков val %= 100; digit = (unsigned char)(val / 10); sum += digit; //Добавляем количество единиц val %= 10; sum += val; //Учитываем в массиве сумм assert(sum < COUNT_SUMS); sums[sum]++; } /***********************************************/ /*Вычисляет общее количество счастливых билетов*/ /***********************************************/ unsigned long GetFullCount(void) { unsigned long count = 0; unsigned char i; for (i = 0; i < COUNT_SUMS; i++) count += sums[i] * sums[i]; return count; } /***********************************************/ /***********Главная процедура*******************/ /***********************************************/ int main() { //Инициализируем массив сумм InitSums(); //Обрабатываем все трехзначные числа unsigned short number; for (number = 0; number < 1000; number++) PerformNumber(number); //Вычисляем количество счастливых билетов и выводим его на экран printf("%d\\r\\n", GetFullCount()); return 0; }
Код хорошо прокомментирован, поэтому вопросы возникнуть не должны.
Если посмотреть на массив сумм, то можно сделать два наблюдения.
1. Он симметричен:
n_13 = n_14,
n_12 = n_15,
n_11 = n_16,
n_10 = n_17,
………………
n_1 = n_26,
n_0 = n_27.
2. Больше всего существует билетов, сумма первых трёх цифр которых равна 13 и 14 (их по 75).
Массив сумм из 28 элементов подготавливается за один проход перебора троек. Поэтому для подсчета количества счастливых билетов достаточно перебрать 1000 вариантов.