Форум: "Потрепаться";
Текущий архив: 2003.10.06;
Скачать: [xml.tar.bz2];
Вниз
Задача про количество Найти похожие ветки
← →
wl (2003-09-17 10:31) [0]Попросили сделать сабж оптимальным способом. А мне что-то ничего кроме тупого перебора
for d6:=0 to 9 do
for d5:=0 to 9 do
........
if (d6+d5+d4) = (d3+d2+d1) then Lucky:=Lucky+1;
в голову не приходит. Как сократить перебор?
Помниться это как-то можно сделать динамическим программированием, но для школы достаточно перебора...
← →
Думкин (2003-09-17 10:32) [1]Разводка?
← →
wl (2003-09-17 10:37) [2]
> Думкин © (17.09.03 10:32) [1]
в смысле?
← →
Думкин (2003-09-17 10:44) [3]Ну тот же перебор - на три порядка можно снизить.
← →
Sandman25 (2003-09-17 10:44) [4]Нужно не проверять равенство сумм, а рассчитывать последнюю цифру.
Типа такого
d6 := (d1 + d2 + d3) - (d4 + d5);
if d6 in [0,9] then ...
← →
MBo (2003-09-17 12:17) [5]тупой перебор ~10^6 операций
умный перебор, основанный на симметрии - ~10^3 операций
с привлечением комбинаторики - ~80 операций
← →
Sandman25 (2003-09-17 12:20) [6]Не заметил, что задача про количество. Тогда, конечно, числа можно не показывать и задачу надо решать комбинаторикой.
← →
Mystic (2003-09-17 12:46) [7]Взято с http://algolist.manual.ru/olimp/rec_sol.php#a2
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 во вложенных циклах будет проверяться 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.
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; {удваиваем сумму}
Сложность этого алгоритма 10^3.
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.
← →
wl (2003-09-17 13:03) [8]спасибо за ответы
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2003.10.06;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.007 c
