Комментарии 57
У меня получилось за 0.7 секунды на P4 3Ггц на языке TCL.
clipie.org/view.php? key=5ZPF4SCV7Q1M32UJ6GE8
clipie.org/view.php? key=5ZPF4SCV7Q1M32UJ6GE8
+6
Вот. Быдлокодинг, конечно, но все таки.
Ответ:
28 * 157 = 4396
18 * 297 = 5346
12 * 483 = 5796
4 * 1738 = 6952
39 * 186 = 7254
48 * 159 = 7632
4 * 1963 = 7852
45228
Правильно?
<? set_time_limit(0); $n = 0; for ($i = 999; $i < 9999; $i++) { for ($a = 1; $a <= $i; $a++) { $good = false; $b = $i / $a; if (round($b) == $b) { $s = "$a$b$i"; if (strlen($s) == 9) { $good = true; for ($x = 1; $x < 10; $x++) { if (strpos($s, "$x") === false) { $good = false; break; } } if ($good) { $n += $i; print "$a * $b = $i "; break; } } } } } print $n; ?>
Ответ:
28 * 157 = 4396
18 * 297 = 5346
12 * 483 = 5796
4 * 1738 = 6952
39 * 186 = 7254
48 * 159 = 7632
4 * 1963 = 7852
45228
Правильно?
+2
30424
0
<? $found = array(); for($i=11; $i<=99; $i++){ if($i{1} != '0'){ for($j=111; $j<=999; $j++){ if(($j{1} != '0') && ($j{2} != '0')){ $n = $i*$j; if($n <= 9999){ $cnt = count(array_flip(preg_split('//', "0".$n.$i.$j, -1, PREG_SPLIT_NO_EMPTY))); if($cnt == 10){ $found[$n]++; } } } } } } echo array_sum(array_keys($found)); ?>
0.2c на P4 core2Duo 2.4GHz
+1
Банальное решение с банальным отсечением занимает 0.4 с на AMD Turion 64 X2 2.0 GHz.
s = {} check = lambda i, j: i*j < 10000 and i*j > 1000 and \ "".join(sorted(str(i)+str(j)+str(i*j))) == "123456789" for i in xrange(1, 9): for j in xrange(1, 9999): if check(i, j): s[i*j] = i, j for i in xrange(11, 99): for j in xrange(11, 999): if check(i, j): s[i*j] = i, j print "\n".join(["%i x %i = %i" % (s[a][0], s[a][1], a) for a in s]) print "Total:", sum(s.keys())
27 x 198 = 5346 42 x 138 = 5796 4 x 1738 = 6952 28 x 157 = 4396 4 x 1963 = 7852 48 x 159 = 7632 39 x 186 = 7254 Total: 45228
0
14.8 за 100 итераций на Intel E6550. Расход памяти только для хранения суммы. =)
from math import sqrt base, summ = set("123456789"), 0 for i in xrange(1234, 9877): if len( set( str(i) ) ) == 4: for j in xrange(2, int(sqrt( i ))): if i % j == 0 and set("%s%s%s" % (i ,j, i/j)) == base: summ += i break print summ
+4
Если считать простом, как доска, перебором, то получается вот так:
4*1738=6952
4*1963=7852
12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632
summ: 56370
53844 ms
4*1738=6952
4*1963=7852
12*483=5796
18*297=5346
27*198=5346
28*157=4396
39*186=7254
42*138=5796
48*159=7632
summ: 56370
53844 ms
0
>>> def do(): prods = [] for n in range(1, 10000): if len(str(n))==len(set(str(n))): for k in range(2, n**.5+1): if len(str(k))==len(set(str(k))) and n%k==0 and len(set(''.join(map(str,(n,k,n/k))).replace('0','')))==9: print k,'*',n/k,'=',n prods.append(n) print sum(set(prods)) >>> do() 28 * 157 = 4396 18 * 297 = 5346 27 * 198 = 5346 12 * 483 = 5796 42 * 138 = 5796 4 * 1738 = 6952 39 * 186 = 7254 48 * 159 = 7632 4 * 1963 = 7852 45228
+2
Ну, разбавлю поток скриптовых решений :) Вот, немного хакерское решение (на CeleronM 540@1.8ГГц с 512DDR@266МГц работает за 0,013 секунд. Работает быстро, потому как использует битовые маски для определения «правильности» числа + небольшой отсев.
#include <stdio.h>Как видно, numtomask тоже можно ускорить.
#include <math.h>
#include <time.h>
int numtomask(int n)
{
int ans=0;
{
while(n)
{
ans+=1<<(n%10);
n/=10;
}
}
return ans;
}
int bitcount(int n) {
/* MIT HAKMEM Count
works for 32-bit numbers only
fix last line for 64-bit numbers */
int tmp;
tmp = n — ((n >> 1) & 033333333333)
— ((n >> 2) & 011111111111);
return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}
int main ()
{
int magic_number=0;
clock_t start, finish;
start=clock();
for (int a=1234; a<=9876; a++)
{
bool find=false;
int i=(int)sqrt(float(a)), d1=numtomask(a);
if (bitcount(d1) != 4)
continue; // coz it isn't abcd-number
for (; i>=1 &&! find; i--)
if (a%i==0)
{
int d4 = d1 ^ numtomask(a/i) ^ numtomask(i);
if (1022 == d4) // ..1111111110 in bin
{
magic_number+=a;
find=true;
}
}
}
finish=clock();
printf(«%i\n», magic_number);
printf( «%2.7f seconds\n», (double)(finish — start) / CLOCKS_PER_SEC);
return 0;
}
+13
для пятизначного результата
0
Ну наконец то! Давно жду, когда же появится решение на статическом, компилируемом языке. Да, конечно по скорости нам не тягаться, оптимизация моего решения при помощи ваших масок дала прирост всего в 1-2 секунды на 100 итераций, тут уж се ля ви даже не в масках дело. =)
Кстати, на мой взгляд, вычислять корень стоит после проверки числа на уникальность его цифр.
Кстати, на мой взгляд, вычислять корень стоит после проверки числа на уникальность его цифр.
0
> Кстати, на мой взгляд, вычислять корень стоит после проверки числа на уникальность его цифр.
Верно. Еще можно перебирать в [2, sq) а не в [sq,1].
Верно. Еще можно перебирать в [2, sq) а не в [sq,1].
int sq, i, d1=numtomask(a); if (bitcount(d1) != 4) continue; // coz it isn't abcd-number sq=(int)sqrt(float(a)); for (i=2; i<sq && !find; i++)
0
Незначительное ускорение даст тот факт, что a не оканчивается на 5.
0
НЛО прилетело и опубликовало эту надпись здесь
Думаю, что нет. По сути, все алгоритмы, которые здесь представленны — брут форс. Если замутить генерацию перестановок, то можно выиграть на проверках, но это тоже перебор и не учитывает специфику задачи. Это задание, как школьные задания вида: ABC+ZA=SDF, где все разные буквы это разные цифры, а от сюда следует, что (C+A)%10 == F и область перебора сужается:)
+2
Я начал от перестановок, но полез явно не в ту сторону, верное решение я нашёл сразу (и оно было гарантировано верным, т.к. перебирал я там вообще все варианты перестановок от этих 9-ти цифр =)), но вот со скоростью и расходом памяти там был полный швах, по-этому я отбросил эту идею и написал то, что написал выше. Надо будет ещё покусать…
А вообще там, да, явно нужно больше математики, верно выбранное математическое обоснование даст огромный прирост по скорости.
А вообще там, да, явно нужно больше математики, верно выбранное математическое обоснование даст огромный прирост по скорости.
0
Я тоже вначале думал о перестановках и математике, но быстро понял, что генерация подходящих вариантов будет занимать значительно больше времени чем простой перебор. Имхо лучше одно умножение чем одно условие (ошибка предсказателя переходов при ветвлении в процессоре сбрасывает весь конвеер, что замедляет работу).
P.S.
Код на Java. 0.156 сек. E8400 3ГГц.
P.S.
Код на Java. 0.156 сек. E8400 3ГГц.
0
Отталкивался от следующего:
abc*de=khgf равноценно
(a*100+b*10+c)*(d*10+e)=k*1000+h*100+g*10+f, то есть
1000*a*d+100*(a*e+d*b)+(e*b+c*d)*10+c*e=k*1000+h*100+g*10+f
а далее смотрю на остатки при делении и того 0.03 на TCL, почти догнал брут форс на C=)
clipie.org/view.php? key=B9K47FLMVSP03EDUJIX5
abc*de=khgf равноценно
(a*100+b*10+c)*(d*10+e)=k*1000+h*100+g*10+f, то есть
1000*a*d+100*(a*e+d*b)+(e*b+c*d)*10+c*e=k*1000+h*100+g*10+f
а далее смотрю на остатки при делении и того 0.03 на TCL, почти догнал брут форс на C=)
clipie.org/view.php? key=B9K47FLMVSP03EDUJIX5
+3
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
msec можно трактовать по разному милли и микро, в данном случае милли.
0
НЛО прилетело и опубликовало эту надпись здесь
if (a * b == c) { nums[c] = true; // имеет смысл заменить на sum += n; } else { a = n1*10 + n2; b = n3*100 + n4*10 + n5; if (a*b==c) { nums[c] = true; // sum += n; } }
Этот цикл дальше по коду, ого-го время кушает (и массив булей убрать, он не нужен):
for (int n = 1000; n < 10000; n++) { if (nums[n]) { sum += n; } }
Еще можно сузить перебор переменных n1, n2, n3… Интересный вариант ;)
0
НЛО прилетело и опубликовало эту надпись здесь
А сейчас я покажу вам немного магии, кодерской магии:
Так и быть, раскажу «секрет» фокуса :) Фишка в том, что с теми переменными вы саначала перебирали («странным») образом «делители» и только потом само число. Если число перебирать на внешмен уровне рекурсии, то перейти к следующему, пропустив остальные делители не составляет труда. Такие дела :)
bool flags[10], magic=false; memset(flags,false,sizeof(flags)); int sum=0; //дальше без изменений for (int n1 = 1; n1 < 10; n1++) { flags[n1] = true; //...первые три без изменений for (int n4 = 1; n4 < 10; n4++) if (!flags[n4]) { for (int n5 = 1; n5 < 10 && !magic; n5++) //... с n5 до n9 добавляется новое уловие for (int n9 = 1; n9 < 10 && !magic; n9++){ //.. int c = n1 * 1000 + n2 * 100 + n3 * 10 + n4; // особая магия int a = n5; // у-у-у int b = n7 * 1000 + n8 * 100 + n9 * 10 + n6; // бу-у-у if (a * b == c) { sum+=c; magic=true; } else { a = n5*10 + n7; // ву-у-у b = n8*100 + n9*10 + n6; // а-а-а if (a*b==c) { sum+=c; magic=true; } } } //тут закрываются циклы с n9 по n5 magic=false; } //end for n4
Так и быть, раскажу «секрет» фокуса :) Фишка в том, что с теми переменными вы саначала перебирали («странным») образом «делители» и только потом само число. Если число перебирать на внешмен уровне рекурсии, то перейти к следующему, пропустив остальные делители не составляет труда. Такие дела :)
+1
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
А ещё можно математичненько так (и читаемо, заодно):
На моей машине выдаёт «Done 10 times in 2.11714696884 sec.», т.е. считает за 0.2 секунды. Похоже, неплохо, учитывая рекурсивный генератор, сортировку и set.
# Python import timeit def gen_positional_combinations(seq, n): # Генерируем сочетания по n элементов, только позиционные. # Не помню, как это называется в комбинаторике. if n==1: for e in seq: yield e else: for i in range(len(seq)): for tail in gen_positional_combinations(seq[:i]+seq[i+1:], n-1): yield seq[i]+tail def work(): result_set=set() for perm in gen_positional_combinations('123456789', 5): for i in (1,2): x, y = int(perm[:i]), int(perm[i:]) xy = x*y if ''.join(sorted(perm+str(xy)))=='123456789': print x, y, x*y result_set.add(x*y) return sum(list(result_set)) t = timeit.Timer('print euler32.work()', 'import euler32') print "Done 10 times in %s sec."%t.timeit(10)
На моей машине выдаёт «Done 10 times in 2.11714696884 sec.», т.е. считает за 0.2 секунды. Похоже, неплохо, учитывая рекурсивный генератор, сортировку и set.
+1
Haskell:
import Data.List (sort, nub) main = print $ sum $ nub [i | i <- [1234..9876], j <- [2..iSqrt i], let (d,m) = i `divMod` j, m == 0, allDigits i j d] where iSqrt = round . sqrt . fromIntegral allDigits x y z = sort (show x ++ show y ++ show z) == ['1'..'9']
+2
Python, Haskell, TCL, C, PHP, C# — круто, чувствую скоро рабисты подтянуться=)
+1
Скучная задача, раз простым перебором решается)
Тем не менее, код на С++: clipie.org/view.php? key=E1ZLSOPRG7M4UCK30FIT
Тем не менее, код на С++: clipie.org/view.php? key=E1ZLSOPRG7M4UCK30FIT
0
ну вот вам и самый простой брут на руби (диапазоны в уме подбирал)
c=[]
for a in 2..98
for b in 123..4897
s=a.to_s+b.to_s+(a*b).to_s
c.push a*b if s.size==9 &&! s['0'] && s.split(//).uniq.size==9
end
end
p c.uniq.inject{|s, i|s+i}
3.7сек на AM2 4200+
c=[]
for a in 2..98
for b in 123..4897
s=a.to_s+b.to_s+(a*b).to_s
c.push a*b if s.size==9 &&! s['0'] && s.split(//).uniq.size==9
end
end
p c.uniq.inject{|s, i|s+i}
3.7сек на AM2 4200+
+1
Java
3.6 секунд на Intel Q6600
3.6 секунд на Intel Q6600
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача №32