Написать программу определения количества шестизначных «счастливых» билетов, у которых сумма первых 3 десятичных цифр
Вопрос посетителя
Написать программу определения количества шестизначных «счастливых» билетов, у которых сумма первых 3 десятичных цифр равна сумме 3 последних десятичных цифр.
Описание входных данных
Входные данные отсутствуют.
Описание выходных данных
Одно число – результат решения задачи.
Ответ эксперта
Решение принималось к рассмотрению, если программа выдавала правильный ответ — 55252.
1) Самое простое — это перебрать все возможные комбинации шести цифр и подсчитать число «счастливых» билетов.
Count:=0; {количество «счастливых» билетов}
for a1:=0 to 9 do
for a2:=0 to 9 do
for a3:=0 to 9 do
for a4:=0 to 9 do
for a5:=0 to 9 do
for a6:=0 to 9 do
if a1+a2+a3=a4+a5+a6
then Count:=Count+1;
или следующий вариант:
Count:=0;
for t:=0 to 999999 do begin
a1:=t div 100000;
a2:=t div 10000 mod 10;
a3:=t div 1000 mod 10;
a4:=t div 100 mod 10;
a5:=t div 10 mod 10;
a6:=t mod 10;
if a1+a2+a3=a4+a5+a6 then count:=count+1;
end;
Условие if во вложенных циклах будет проверяться 10^6 раз, поэтому будем говорить, что сложность этих алгоритмов 10^6.
2) Обратим внимание на то, что в «счастливом» билете последняя цифра a6 однозначно определяется первыми пятью:
a6=(a1+a2+a3)-(a4+a5).
Если 0<=a6<=9, то билет "счастливый", иначе - нет. Таким образом, мы можем убрать шестой вложенный цикл:
Count:=0;
for a1:=0 to 9 do
for a2:=0 to 9 do
for a3:=0 to 9 do
for a4:=0 to 9 do
for a5:=0 to 9 do
begin
a6:=(a1+a2+a3)-(a4+a5);
if (a6>=0) and (a6<=9)
then Count:=Count+1;
end;
Сложность алгоритма 10^5.
3) Если комбинаций a1 a2 a3 первых трех цифр с суммой T=a1+a2+a3 насчитывается C[T], то всего «счастливых» билетов с суммой половины T=a1+a2+a3=a4+a5+a6 будет C[T]*C[T]. Всех возможных сумм T-28 (от 0=0+0+0 до 27=9+9+9). Подсчитаем C[i], i=0, …, 28, затем найдем интересующее нас количество «счастливых» билетов
C[0]2 + C[1]2 + … + C[27]^2.
Заметим, что «счастливых» билетов с суммой T столько же, сколько и с суммой 27-T. Действительно, если билет a1 a2 a3 a4 a5 a6 с суммой T — «счастливый», то таковым же является и билет (999999 — a1 a2 a3 a4 a5 a6) с суммой 27-T. Поэтому число билетов можно вычислять и по формуле
2*(C[0]2+ … +C[13]2),
т.е.рассматривать только суммы T от 0 до 13.
Count:=0;
for T:=0 to 13 do C[T]:=0;
for a1:=0 to 9 do {перебираем все}
for a2:=0 to 9 do {возможные a1 a2 a3}
for a3:=0 to 9 do
begin
T:=a1+a2+a3;
C[T]:=C[T]+1 {нашли еще один билет}
end; {с суммой T}
for T:=0 to 13 do {считаем число билетов} Count:=Count+C[T]*C[T];
Count:=Count*2; {удваиваем сумму}
или следующий вариант
count:=0;
for t:=0 to 27 do c[t]:=0;
for t:=0 to 999 do begin
a1:=t div 100;
a2:=t div 10 mod 10;
a3:=t mod 10;
c[a1+a2+a3]:=c[a1+a2+a3]+1;
end;
for t:=0 to 27 do count:=count+c[t]*c[t];
Сложность этих алгоритмов 10^3.
