Diberikan daftar bilangan bulat positif, temukan jumlah segitiga yang dapat kita bentuk sedemikian rupa sehingga panjang sisi mereka diwakili oleh tiga entri berbeda dari daftar input.

(Inspirasi berasal dari CR .)

Detail

• Segitiga dapat dibentuk jika semua permutasi dari panjang tiga sisi memenuhi ketimpangan segitiga ketat(Ini berarti , dan harus dimiliki semua.)$a,b,c$ $$a + b > c.$$ $a+b > c$$a+c>b$$b+c>a$
• Tiga panjang sisi harus muncul pada posisi yang berbeda dalam daftar, tetapi tidak harus berbeda secara berpasangan.$a,b,c$
• Urutan tiga angka dalam daftar input tidak masalah. Jika kita mempertimbangkan daftar adan tiga angka a[i], a[j], a[k](di mana i,j,kberpasangan berbeda), maka (a[i],a[j],a[k]), (a[i],a[k],a[j]), (a[j], a[i], a[k])dll. Semua dianggap sebagai segitiga yang sama .
• Daftar input dapat dianggap mengandung setidaknya 3 entri.
• Anda dapat mengasumsikan bahwa daftar input diurutkan dalam urutan menaik.

Contohnya

Program uji kecil dapat ditemukan di sini di Coba online!

Input, Output:
[1,2,3]  0
[1,1,1]  1
[1,1,1,1] 4
[1,2,3,4] 1
[3,4,5,7] 3
[1,42,69,666,1000000] 0
[12,23,34,45,56,67,78,89] 34
[1,2,3,4,5,6,7,8,9,10] 50

Untuk inputnya [1,2,3,...,n-1,n]adalah A002623 .

Untuk input [1,1,...,1](panjang n) ini adalah A000292 .

Untuk input nangka Fibonacci pertama ( A000045 ) ini adalah A000004 .

R , 62 52 40 34 byte

sum(c(1,1,-1)%*%combn(scan(),3)>0)

Cobalah online!

Solusi Octave Pelabuhan Luis Mendo

Karena a<=b<=c, kondisi segitiga sama dengan a+b-c>0. Secara a+b-cringkas ditangkap oleh produk matriks [1,1,-1] * X, di mana Xadalah 3-kombinasi dari array input.

Ada banyak saran untuk perbaikan yang dilakukan oleh 3 orang yang berbeda di komentar:

• Robert S. untuk memberi saranscan .

• Robin Ryder untuk menyarankan perbaikan pada ketimpangan segitiga dan yang aneh ini yang membutuhkan input dalam urutan menurun (yang hanya menunjukkan betapa pentingnya format input yang fleksibel).

• dan akhirnya Nick Kennedy untuk yang berikut:

R , 40 byte

y=combn(scan(),3);sum(y[3,]<y[1,]+y[2,])

Cobalah online!

Stax , 8 7 byte

Berkat rekursif untuk -1!

é═rê÷┐↨

Jalankan dan debug di staxlang.xyz!

Dibongkar (8 byte) dan penjelasan:

r3SFE+<+
r           Reverse
 3S         All length-3 combinations
   F        For each combination:
    E         Explode: [5,4,3] -> 3 4 5, with 3 atop the stack
     +        Add the two shorter sides
      <       Long side is shorter? 0 or 1
       +      Add result to total

Itu trik yang rapi. Jika Anda memiliki urutan instruksi yang akan selalu menghasilkan 0 atau 1 dan Anda perlu menghitung item dari array yang menghasilkan hasil yang benar pada akhir program Anda, F..+lebih pendek satu byte dari {..f%.

Mengasumsikan daftar awal diurutkan naik. Tanpa asumsi ini, tempelkan odi awal untuk 8 byte.

Haskell , 49 byte

([]%)
[c,b,a]%l|a+b>c=1
p%(h:l)=(h:p)%l+p%l
_%_=0

Cobalah online!

Secara rekursif menghasilkan semua urutan l(terbalik), dan memeriksa yang panjang-3 yang membentuk segitiga.

50 byte

f l=sum[1|[a,b,c]<-filter(>0)<$>mapM(:[0])l,a+b>c]

Cobalah online!

Gagasan yang sama, menghasilkan hasil dengan mapM, dengan memetakan setiap nilai lbaik untuk dirinya sendiri (termasuk) atau 0(mengecualikan).

50 byte

([]%)
p%(b:t)=sum[1|c<-t,a<-p,a+b>c]+(b:p)%t
_%_=0

Cobalah online!

Mencoba setiap titik partisi untuk mengambil elemen tengah b.

51 byte

f(a:t)=f t+sum[1|b:r<-scanr(:)[]t,c<-r,a+b>c]
f _=0

Cobalah online!

Fungsi q=scanr(:)[]menghasilkan daftar sufiks. Banyak masalah timbul karena harus mempertimbangkan memasukkan elemen yang sama beberapa kali.

52 byte

q=scanr(:)[]
f l=sum[1|a:r<-q l,b:s<-q r,c<-s,a+b>c]

Cobalah online!

Fungsi helper q=scanr(:)[]menghasilkan daftar sufiks.

57 byte

import Data.List
f l=sum[1|[a,b,c]<-subsequences l,a+b>c]

Cobalah online!

Brachylog , 11 byte

{⊇Ṫ.k+>~t}ᶜ

Cobalah online!

Saya mungkin lupa memanfaatkan input yang diurutkan dalam solusi lama saya:

Brachylog , 18 17 15 byte

{⊇Ṫ¬{p.k+≤~t}}ᶜ

Cobalah online!

{            }ᶜ    The output is the number of ways in which
 ⊇                 a sublist of the input can be selected
  Ṫ                with three elements
   ¬{       }      such that it is not possible to show that
     p             for some permutation of the sublist
       k+          the sum of the first two elements
         ≤         is less than or equal to
      .   ~t}      the third element.

Perl 6 , 35 byte

+*.combinations(3).flat.grep(*+*>*)

Cobalah online!

Penjelasan

Ini adalah kode Apapun, yaitu notasi ringkas untuk fungsi lambda (yang hanya berfungsi dalam kasus yang sangat sederhana). Masing *- masing adalah penampung untuk satu argumen. Jadi kita ambil daftar panjang (yang muncul di bagian pertama *), buat semua kombinasi dari 3 elemen (mereka selalu keluar dalam urutan yang sama seperti dalam daftar asli, sehingga itu berarti kombinasi diurutkan juga), ratakan daftar, dan kemudian ambil daftar 3-oleh-3, dan filter ( grep) hanya triplet yang memuaskan *+*>*, yaitu jumlah dari dua argumen pertama lebih besar dari yang ketiga. Itu memberi semua kembar tiga, dan kami akhirnya menghitungnya dengan memaksa konteks numerik dengan a +.

(Tentu saja kita perlu mengujinya hanya untuk kasus "jumlah dua lebih kecil> yang terbesar". Jika ini berlaku, yang lain berlaku sepele, jika tidak, triplet tidak menunjukkan panjang segitiga yang benar dan kami tidak perlu melihat lebih jauh.)

Retina , 55 byte

\d+
*
L$`_+
$<'
%L$w`(,_+)\b.*\1(_*)\b(?<=^_+\2,.*)
_
_

Cobalah online! Tautan termasuk kasus uji, tetapi dengan nilai dalam kasus ke 5 dikurangi untuk memungkinkannya selesai hari ini. Mengasumsikan input diurutkan. Penjelasan: Regex tidak terlalu suka mencocokkan lebih dari satu hal. Regex normal akan dapat menemukan semua nilai yang bisa menjadi kaki terpendek dari segitiga. Pilihan Retina vtidak membantu di sini, kecuali untuk menghindari pencarian. Namun wopsi Retina sedikit lebih membantu, karena akan dapat menemukan kaki terpendek dan terpanjang pada saat yang sama. Itu tidak cukup untuk tantangan ini, karena mungkin ada beberapa kaki tengah.

\d+
*

Konversikan input ke unary.

L$`_+

Untuk setiap nomor input ...

$<'

... buat garis yang array aslinya dipotong untuk memulai pada angka itu. $'biasanya berarti string setelah pertandingan, tetapi <memodifikasinya berarti string setelah pemisah sebelumnya, menghindari membuang 2 byte $&. Oleh karena itu setiap baris mewakili semua solusi potensial menggunakan nomor itu sebagai kaki terpendek.

%L$w`(,_+)\b.*\1(_*)\b(?<=^_+\2,.*)
_

Untuk masing-masing garis tersebut, temukan semua kemungkinan kaki tengah dan terpanjang, tetapi pastikan bahwa perbedaannya kurang dari kaki pertama. Keluarkan a _untuk setiap kombinasi kaki yang cocok.

_

Hitung jumlah total segitiga yang ditemukan.

Python 3 , 73 byte

lambda l:sum(a+b>c for a,b,c in combinations(l,3))
from itertools import*

Cobalah online!

$(a,b,c)$$a+b>c$

Python 2 , 72 byte

f=lambda l,p=[]:l>[]and(p==p[:2]<[sum(p)]>l)+f(l[1:],p)+f(l[1:],p+l[:1])

Cobalah online!

73 byte

lambda l:sum(a+b>c for j,b in enumerate(l)for a in l[:j]for c in l[j+1:])

Cobalah online!

05AB1E , 12 10 9 byte

Pertama kali saya menggunakan 05AB1E! Terima kasih kepada [Grimy] untuk -1!

3.Æʒ`α›}g

Cobalah online! atau test suite

Port langsung dari jawaban Stax saya. Dapatkan semua kombinasi dari tiga entri dan hitung yang mungkin membentuk segitiga. Bagian penghitungan itulah yang benar-benar membuat saya. Saya menghabiskan banyak byte di sana. Terikat menjadi kesalahan pemula di sana.

3.Æʒ`α›}g
3.Æ          List of length-3 combinations
   ʒ   }g    Count truthy results under operation:
    `          Push the two shorter sides, then the long one
     α         Absolute difference (negated subtraction in this case)
      ›        Remaining short side is longer?

JavaScript (ES6), 63 byte

f=([v,...a],p=[])=>v?(!p[2]&p[0]+p[1]>v)+f(a,p)+f(a,[...p,v]):0

Cobalah online!

Oktaf / MATLAB, 33 byte

@(x)sum(nchoosek(x,3)*[1;1;-1]>0)

Cobalah online!

Zsh , 66 byte

for a;z=$y&&for b (${@:2+y++})for c (${@:3+z++})((t+=c<a+b))
<<<$t

Cobalah online!

Relatif mudah, mengambil keuntungan dari input yang diurutkan, dan kenaikan di forheader (kenaikan terjadi sekali per loop orangtua ).

for a;{
  z=$y
  for b (${@:2+y++});{   # subarray starting at element after $a
    for c (${@:3+z++})   # subarray starting at element after $b
      ((t+=c<a+b))
  }
}

Excel VBA, 171 164 152 byte

^{-26 byte berkat TaylorScott}

Sub z
t=[A:A]
u=UBound(t)
For i=1To u-2
For j=i+1To u-1
For k=j+1To u
a=t(i,1):b=t(j,1):c=t(k,1)
r=r-(a+b>c)*(b+c>a)*(c+a>b)
Next k,j,i
Debug.?r
End Sub

Input ada dalam rentang A:Alembar aktif. Output ke jendela langsung.

Karena ini terlihat pada setiap kombinasi setiap sel dalam kolom yang tingginya 2 ²⁰ sel (yang hampir ²⁶⁰ kombinasi), kode ini ... tidak cepat. Anda bisa membuatnya lebih cepat tetapi dengan mengorbankan byte.

Arang , 17 byte

ＩΣ⭆θ⭆…θκ⭆…θμ›⁺νλι

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Mengasumsikan input diurutkan. Penjelasan:

   θ                Input array
  ⭆                 Map over elements and join
      θ             Input array
     …              Truncated to length
       κ            Outer index
    ⭆               Map over elements and join
          θ         Input array
         …          Truncated to length
           μ        Inner index
        ⭆           Map over elements and join
              ν     Innermost value
             ⁺      Plus
               λ    Inner value
            ›       Is greater than
                ι   Outer value
 Σ                  Take the digital sum
Ｉ                   Cast to string for implicit print

Japt -x , 9 byte

à3 ËÌÑ<Dx

Cobalah

à3 ®o <Zx

Cobalah

Bahasa Wolfram (Mathematica) , 37 35 byte

Tr@Boole[2#3<+##&@@@#~Subsets~{3}]&

Cobalah online!

Ruby , 41 byte

->l{l.combination(3).count{|a,b,c|c<a+b}}

Cobalah online!

Pyth , 14 byte

*1sm>sPded.cQ3

Cobalah online!

          .cQ3  # All combinations of length 3 from Q (input), sorted in ascending order
   m            # map over that lambda d:
     sPd        #   sum(d[:-1])
    >   ed      #     > d[-1]
  s             # sum all of those (uses the fact that True = 1)
*1              # multiply by 1 so it doesn't output True if there's only one triangle

Alternatif (juga 14 byte):

lfTm>sPded.cQ3

Perl 5 ( -p), 55 52 byte

menggunakan regex backtracking, -3 bytes berkat @Cows quack menggunakan ^alih-alih (?!)gagal dan mundur.

$d='(\d++)';$_=/$d.* $d.* $d(?{$n++if$1+$2>$3})^/+$n

atau

$_=/(\d++).* (\d++).* (\d++)(?{$n++if$1+$2>$3})^/+$n

TIO

Jelly , 9 byte

œc3+>ƭ/€S

Cobalah online!

Tautan monadik dengan mengambil daftar bilangan bulat yang disortir sebagai argumennya dan mengembalikan jumlah segitiga.

Penjelasan

œc3       | Combinations of length 3
     ƭ/€  | Reduce each using each of the following in turn:
   +      | - Add
    >     | - Greater than
        S | Sum (counts the 1s)

Alternatif 9s:

œc3Ṫ€<§ƊS
œc3Ṫ<SƊ€S

J , 40 byte

1#.](+/*/@(->])])@#~2(#~3=1&#.)@#:@i.@^#

Cobalah online!

Bash , 123 byte

for a;do for((i=2;i<=$#;i++)){ b=${!i};for((j=$[i+1];j<=$#;j++)){ c=${!j};T=$[T+(a<b+c&b<a+c&c<a+b)];};};shift;done;echo $T

Cobalah online!

Yang menyenangkan.

SNOBOL4 (CSNOBOL4) , 181 byte

	S =TABLE()
R	X =X + 1
	S<X> =INPUT	:S(R)
I	I =J =K =I + 1	LT(I,X)	:F(O)
J	J =K =J + 1	LT(J,X)	:F(I)
K	K =K + 1	LT(K,X - 1)	:F(J)
	T =T + 1 GT(S<I> + S<J>,S<K>)	:(K)
O	OUTPUT =T
END

Cobalah online!

$O(n^3)$00

C (dentang) , 83 byte

x,y,q;f(*a,z){for(x=y=q=0;z;q+=z>1&a[x-=x?1:2-y--]+a[y]>a[z])y=y>1?y:--z;return q;}

Cobalah online!

Disimpan 1 berkat @ceilingcat