Pertimbangkan sebuah segitiga ABC di mana setiap sisi memiliki panjang bilangan bulat ( segitiga integral ). Tentukan median dari ABC menjadi segmen garis dari titik ke titik tengah sisi lawan. Pada gambar di bawah, segmen garis merah mewakili median. Perhatikan bahwa setiap segitiga yang diberikan memiliki tiga median.
Biarkan n menjadi bilangan bulat positif. Berapa banyak segitiga integral non-degenerasi dengan masing-masing panjang sisi kurang dari atau sama dengan n memiliki setidaknya satu median integral?
Tantangan
Tulis program untuk menghitung jumlah segitiga integral dengan setidaknya satu median integral untuk panjang sisi maksimum yang diberikan n . Urutan panjang sisi tidak masalah, yaitu <6,6,5> mewakili segitiga yang sama dengan <5,6,6> dan harus dihitung hanya sekali. Singkirkan segitiga yang merosot seperti <1,2,3>.
Mencetak gol
N terbesar yang program Anda dapat menghasilkan jumlah segitiga dalam 60 detik pada mesin saya adalah skor Anda. Program dengan skor tertinggi menang. Mesin saya adalah Sony Vaio SVF14A16CLB, Intel Core i5, 8GB RAM.
Contohnya
Biarkan T ( N ) menjadi program dengan masukan N .
T(1) = 0
T(6) = 1
T(20) = 27
T(22) = 34
Perhatikan bahwa T (1) = T (2) = T (3) = T (4) = T (5) = 0 karena tidak ada kombinasi sisi integral yang akan menghasilkan median integral. Namun, begitu kita mencapai 6, kita dapat melihat bahwa salah satu median dari segitiga <5,5,6> adalah 4, jadi T (6) = 1.
Perhatikan juga bahwa T (22) adalah nilai pertama di mana penghitungan ganda menjadi masalah: segitiga <16,18,22> memiliki median 13 dan 17 (dan 2sqrt (85)).
Menghitung median
Median segitiga dapat dihitung dengan rumus berikut:
Current top score: Sp3000 - 7000 points - C
sumber
Jawaban:
C, brute force - n = 6080
Ini lebih merupakan baseline daripada pesaing yang serius, tetapi setidaknya harus memulai.
n = 6080 setinggi yang saya dapatkan dalam satu menit runtime pada mesin saya sendiri, yang merupakan MacBook Pro dengan Intel Core i5. Hasil yang saya dapatkan untuk nilai ini adalah:
Kode ini murni kekuatan kasar. Ini menyebutkan semua segitiga dalam batas ukuran, dan menguji kondisi:
sumber
lrintf()
atau(int)roundf()
bukannya menambahkan 0,5f dan menggunakan pemotongan default. Namun, terkadang Anda perlu menggunakannya-ffast-math
untuk mengkompilasi ke satucvtss2si
instruksi. gcc inlinelrintf()
dansqrtf
hanya dengan-fno-math-errno
, sehingga Anda mendapatkan asm efisien: godbolt.org/g/E3hncQ . (Saya menggunakan-march=ivybridge
karena itu CPU OP). Dengan-ffast-math
, dentang mengubah sqrt menjadi iterasi rsqrt + Newton; IDK jika itu kemenangan.roundf
. Gunakan(int)nearbyintf()
jikalrintf()
tidak sebaris, karena menggunakan mode pembulatan saat ini dan bukan yang aneh. stackoverflow.com/questions/37620659/…C, sekitar
66506900Saya tidak terlalu sering menggunakan C, tetapi dengan jumlah aritmatika yang terjadi sepertinya pilihan bahasa yang baik. Algoritma inti adalah kekuatan kasar seperti jawaban @ RetoKoradi , tetapi dengan beberapa optimisasi sederhana. Saya tidak yakin nilai kami sebanding, karena komputer @ RetoKoradi tampaknya lebih cepat daripada milik saya.
Optimalisasi utama adalah melewati
% 4
pemeriksaan sepenuhnya. Kotak integern*n
adalah 0 atau 1 modulo 4, tergantung pada apakahn
itu sendiri 0 atau 1 modulo 2. Dengan demikian, kita dapat melihat semua kemungkinan untuk(x, y, z) % 2
:Mudahnya, hanya ada dua kasus untuk dipertimbangkan:
(0, 0, 0)
dan(1, 1, 0)
, yang, mengingat dua sisi pertamaa, b
, sama dengan pihak ketigac
memiliki kesamaana^b
:a^b
sama dengana-b
, jadi daripada mencari daric = a-b+1
dan naik 1s, ini memungkinkan kita mencari daric = a-b+2
dan naik 2s.Optimalisasi lain datang dari fakta bahwa, untuk
(1, 1, 0)
kasus ini, kita hanya perlu memanggil is_square sekali karena hanya satu permutasi yang berfungsi. Ini dikurung khusus dalam kode dengan membuka gulungan pencarian.Pengoptimalan lain yang disertakan hanyalah kegagalan cepat dalam
is_square
fungsi.Kompilasi dilakukan dengan
-std=c99 -O3
.(Terima kasih kepada @RetoKoradi untuk menunjukkan bahwa
0.5
is_square diperlukan0.5f
untuk menghindari konversi ganda yang terjadi.)sumber
0.5f
bukannya0.5
diis_square()
.0.5
adalah tipe konstandouble
, sehingga ekspresi akan menghasilkan nilai ganda saat Anda menambahkan0.5
, termasuk konversi tipe darifloat
menjadidouble
untuk istilah lainnya.f
, sebenarnya.Felix, tidak diketahui
Pada dasarnya port jawaban C, tetapi lebih cepat dari itu, diuji dengan
clang -O3
danicc -O3
. Felix dan Nim adalah dua bahasa yang saya tahu dapat mengalahkan C dan C ++. Saya sedang mengerjakan versi paralel, tetapi akan sedikit sampai selesai, jadi saya memutuskan untuk memposting ini di depan.Saya juga menaruh "tidak dikenal" karena komputer saya belum tentu yang tercepat di bumi ...
Perintah yang digunakan untuk membangun:
C ++ yang dihasilkan cukup menarik untuk dilihat:
sumber
C # (sekitar 11000?)
n
diambil sebagai argumen baris perintah.Penjelasan
PersamaannyaSebuah2+ b2= 2 ( m2+ C2) adalah dasar untuk algoritma meet-in-the-middle yang digunakan di sini.
JikaSebuah dan b aneh maka kita tidak memiliki risiko penghitungan ganda, karena hanya satu dari tiga median yang mungkin bisa integral. Jika ketiganya genap maka kita perlu waspada penghitungan ganda. Oleh karena itu saya menangani dua case secara terpisah sehingga case odd-odd-even dapat diproses lebih cepat daripada even-even-even.
sumber
n=5000
adalah 67 detik untuk jawaban Reto Koradi, 48 detik untuk jawaban Sp3000, dan 13 detik untuk jawaban saya.C, n = 3030 di sini
hasil:
kode di atas akan menjadi traslation dalam C dari jawaban Aksioma (jika kita tidak menghitung fungsi isq ()).
Kompiler saya tidak menautkan fungsi yang lain menggunakan sqrtf () ... di sini tidak ada fungsi sqrt untuk float ... Apakah mereka yakin bahwa sqrtf itu adalah fungsi standar C?
sumber
APL NARS, n =
239282 dalam 59 detik(saya traslate jawaban Axiom one, dalam APL):
sumber
Aksioma, n = 269 dalam 59 detik
Jika a, b, cx adalah panjang sisi satu segitiga dari sisi panjang max ...
Kita akan tahu bahwa m: = sqrt ((2 * (a ^ 2 + b ^ 2) -cx ^ 2) / 4)
Seperti yang dikatakan Peter Taylor, 4 | (2 * (a ^ 2 + b ^ 2) -cx ^ 2) dan karena 2 | 2 * (a ^ 2 + b ^ 2) dari 2 | cx ^ 2 => cx = 2 * c. Jadi mulai 1 akan
a, dan b harus memiliki paritas yang sama, sehingga kita dapat menulis b dalam fungsi a
daripada yang kita miliki
sehingga (1) dapat ditulis ulang lihat (2) (3) (4) sebagai:
dimana
hasil
sumber
VBA 15.000 dalam SEPULUH detik!
Saya berharap jauh lebih sedikit setelah posting-posting lain ini. Pada Intel 7 dengan RAM 16 GB saya mendapatkan 13-15.000 dalam SEPULUH detik. Pada Pentium dengan RAM 4 GB, saya mendapatkan 5-7.000 dalam SEPULUH detik. Kode di bawah. Ini adalah hasil terbaru tentang Pentium
Itu naik ke segitiga dengan sisi 240, 239, 31 dan media 121. Jumlah media adalah 7.371.
sumber