Rozważ trójkąt ABC, w którym każdy bok ma długość całkowitą ( integralny trójkąt ). Zdefiniuj medianę z ABC być odcinek od wierzchołka do punktu środkowego przeciwnej stronie. Na poniższym rysunku segmenty czerwonej linii przedstawiają mediany. Zauważ, że każdy trójkąt ma trzy mediany.
Niech n będzie dodatnią liczbą całkowitą. Ile nieodegenerowanych trójkątów całkowitych o każdej długości boku mniejszej lub równej n ma co najmniej jedną integralną medianę?
Wyzwanie
Napisz program do obliczania liczby integralnych trójkątów z co najmniej jedną integralną medianą dla danej maksymalnej długości boku n . Kolejność długości boków nie ma znaczenia, tzn. <6,6,5> reprezentuje ten sam trójkąt co <5,6,6> i należy go policzyć tylko raz. Wyklucz zdegenerowane trójkąty, takie jak <1,2,3>.
Punktacja
Największy n, dla którego Twój program może wygenerować liczbę trójkątów w ciągu 60 sekund na mojej maszynie, to Twój wynik. Program z najwyższym wynikiem wygrywa. Moje urządzenie to Sony Vaio SVF14A16CLB, Intel Core i5, 8 GB pamięci RAM.
Przykłady
Niech T ( N ) będzie program z wejściem N .
T(1) = 0
T(6) = 1
T(20) = 27
T(22) = 34
Zauważ, że T (1) = T (2) = T (3) = T (4) = T (5) = 0, ponieważ żadna kombinacja całek boków nie da integralnej mediany. Gdy jednak dojdziemy do 6, widzimy, że jedna z median trójkąta <5,5,6> wynosi 4, więc T (6) = 1.
Zauważ również, że T (22) jest pierwszą wartością, przy której podwójne liczenie staje się problemem: trójkąt <16,18,22> ma mediany 13 i 17 (i 2sqrt (85)).
Obliczanie median
Mediany trójkąta można obliczyć za pomocą następujących wzorów:
Current top score: Sp3000 - 7000 points - C
źródło
Odpowiedzi:
C, brutalna siła - n = 6080
Jest to bardziej punkt odniesienia niż poważny pretendent, ale przynajmniej powinien zacząć wszystko.
n = 6080 jest tak wysoki, jak w minutę w czasie wykonywania na własnym komputerze, jakim jest MacBook Pro z procesorem Intel Core i5. Wynik dla tej wartości to:
Kod jest czysto brutalną siłą. Wymienia wszystkie trójkąty w ramach limitu wielkości i testuje warunek:
źródło
lrintf()
lub(int)roundf()
zamiast dodawania 0,5f i przy użyciu domyślnego obcięcia. Czasami jednak trzeba go użyć-ffast-math
, aby skompilować go do pojedynczejcvtss2si
instrukcji. gcc inlineslrintf()
isqrtf
only with-fno-math-errno
, dzięki czemu zyskujesz wydajność asm: godbolt.org/g/E3hncQ . (Użyłem,-march=ivybridge
ponieważ to jest procesor OP). Z-ffast-math
, clang zamienia sqrt w rsqrt + iteracja Newtona; IDK, jeśli to wygrana.roundf
. Użyj(int)nearbyintf()
iflrintf()
nie inline, ponieważ używa bieżącego trybu zaokrąglania zamiast określonego dziwnego. stackoverflow.com/questions/37620659/…C, około
66506900Tak naprawdę nie używam często C, ale przy dużej ilości arytmetyki wydawało się, że to dobry wybór języka. Podstawowym algorytmem jest brutalna siła jak odpowiedź @ RetoKoradi , ale z kilkoma prostymi optymalizacjami. Nie jestem jednak pewien, czy nasze wartości są porównywalne, ponieważ komputer @ RetoKoradi wydaje się być szybszy niż mój.
Główną optymalizacją jest
% 4
całkowite ominięcie kontroli. Kwadratem całkowitymn*n
jest albo 0, albo 1 modulo 4, w zależności od tegon
, czy sam jest 0, czy 1 modulo 2. Zatem możemy przyjrzeć się wszystkim możliwościom(x, y, z) % 2
:Dogodnie są tylko dwa przypadki do rozważenia:
(0, 0, 0)
i(1, 1, 0)
które, biorąc pod uwagę dwie pierwsze stronya, b
, równa sięc
parzystości trzeciej stronya^b
:a^b
ma taką samą parzystość jaka-b
, więc zamiast przeszukiwaćc = a-b+1
i zwiększać się o 1s, pozwala nam to przeszukiwaćc = a-b+2
i zwiększać się o 1s .Kolejna optymalizacja wynika z faktu, że w tym
(1, 1, 0)
przypadku wystarczy wywołać is_square tylko raz, ponieważ działa tylko jedna permutacja. Jest to szczególnie uwypuklone w kodzie przez rozwinięcie wyszukiwania.Inna zawarta w tym optymalizacja to po prostu szybka
is_square
funkcja.Kompilacja została zakończona
-std=c99 -O3
.(Podziękowania dla @RetoKoradi za wskazanie, że
0.5
in is_square musiało być,0.5f
aby uniknąć podwójnej konwersji).źródło
0.5f
zamiast0.5
wis_square()
.0.5
jest stałą typudouble
, więc wyrażenie doda podwójną wartość po dodaniu0.5
, w tym konwersję typu odfloat
dodouble
dla drugiego terminu.f
naprawdę zaskakująco mało znaczący .Felix, nieznany
Zasadniczo port odpowiedzi C, ale jest szybszy od niego, przetestowany z
clang -O3
iicc -O3
. Felix i Nim są dosłownie jedynymi dwoma znanymi mi językami, które mogą pokonać C i C ++ w testach porównawczych. Pracuję nad wersją równoległą, ale trochę potrwa, dopóki się nie skończy, więc postanowiłem opublikować to wcześniej.Umieściłem również „nieznane”, ponieważ mój komputer niekoniecznie jest najszybszy na świecie ...
Polecenie użyte do zbudowania:
Wygenerowane C ++ jest dość interesujące:
źródło
C # (około 11000?)
n
jest traktowany jako argument wiersza poleceń.Wyjaśnienie
źródło
n=5000
to 67 sekund na odpowiedź Reto Koradi, 48 sekund na odpowiedź Sp3000 i 13 sekund na moją odpowiedź.C, n = 3030 tutaj
wyniki:
powyższy kod byłby tłumaczeniem w C odpowiedzi Axiom (jeśli nie policzymy funkcji isq ()).
Mój kompilator nie łączy funkcji, której inni używają sqrtf () ... tutaj nie ma funkcji sqrt dla float ... Czy są pewni, że sqrtf jest funkcją standardową w C?
źródło
APL NARS, n =
239282 w 59 sekund(tłumaczę odpowiedź Axiom 1, w APL) test:
źródło
Aksjomat, n = 269 w 59 sek
Jeśli a, b, cx mają długość boków jednego trójkąta o maksymalnej długości boku n ...
Wiedzielibyśmy, że m: = sqrt ((2 * (a ^ 2 + b ^ 2) -cx ^ 2) / 4)
Jak powiedział Peter Taylor, 4 | (2 * (a ^ 2 + b ^ 2) -cx ^ 2) i ponieważ 2 | 2 * (a ^ 2 + b ^ 2) niż 2 | cx ^ 2 => cx = 2 * c. Więc od 1 będzie
a ib muszą mieć tę samą parzystość, abyśmy mogli napisać b w funkcji a
niż my to mamy
więc (1) można przepisać patrz (2) (3) (4) jako:
gdzie
wyniki
źródło
15 000 VBA w ciągu dziesięciu sekund!
Spodziewałem się znacznie mniej po tych innych postach. Na procesorze Intel 7 z 16 GB RAM dostaję 13–15 000 w ciągu dziesięciu sekund. Na Pentium z 4 GB pamięci RAM dostaję 5-7 000 w ciągu dziesięciu sekund. Kod znajduje się poniżej. Oto najnowszy wynik Pentium
Dostał się do trójkąta o bokach 240, 239, 31 i medium 121. Liczba mediów to 7371.
źródło