【ABC175 B】「Making Triangle」を解く【Python3】

コンテスト一覧へ

 

1,⋯,N の番号がついたN本の棒から3本選び、3辺の長さが異なる三角形を作ることのできるパターンがいくつあるのか求める問題です。

提出
n = int(input())
li = list(map(int, input().split()))

li.sort()
ans = 0

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if li[i] != li[j] and li[j] != li[k] and li[k] != li[i] and li[i]+li[j] > li[k]:
                ans += 1
print(ans)

棒の長さをリストにし、その中から3つを選んで、条件に合うかを判定します。

棒の長さが同じでないこと、選んだ2辺を足し合わせたものが、残りの辺より長いことが条件になります。

全パターンを調べるのですが、その前にソートをしておくと、「li[i]+li[j] > li[k]」のみを判定するだけで済みます。

【ABC175】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。