Решение задачи 2.
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;
Условие if во вложенных циклах будет проверяться 106 раз, поэтому будем говорить, что сложность этого алгоритма 106.
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;
Сложность алгоритма 105.
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.
var C:array[0..13] of longint;
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; {удваиваем сумму}
Сложность этого алгоритма 103.
4) В пункте 3 мы перебирали комбинации цифр и искали количество комбинаций с суммами C[T]. Сейчас мы пойдем от суммы T, и по ней будем определять, какое количество комбинаций a1 a2 a3 ее имеет.
Итак T=a1+a2+a3.
Минимальное значение, которое может принимать a1, - это MAX{0,T-18}. Член T-18 появляется из следующих соображений: пусть a2=a3=9, тогда a1=T-18, но a1 не может быть меньше 0. Максимальное значение a1=MIN{9,T} (так как a2 и a3 неотрицательны, то a1<=T и одновременно a1<=9).
Для цифры a2 аналогично получаем, что она лежит в пределах от max{0,T-a1-9} до min{9,T-a1}.
Цифра a3 по T, a1 и a2 определяется однозначно.
Получаем, что комбинаций a1 a2 a3 с суммой T и с первой цифрой a1 столько же, сколько возможных цифр a2, а именно
min{9,T-a1}-max{0,T-a1-9}+1.
Как и в пункте 3 мы можем рассматривать диапазон сумм T от 0 до 13.
Count:=0;
for T:=0 to 13 do
begin
CT:=0;
for a1:=max(0,T-18) to min(9,T) do CT:=CT+min(9,T-a1)-max(0,T-a1-9)+1;
Count:=Count+CT*CT
end;
Count:=Count*2;
Сложность этого алгоритма (т.е. количество выполнений операций присваивания внутри двух вложенных циклов) не превышает 140.
|
