AtCoder Beginner Contest 175 B Problem "Making Triangle" Explanation (C ++, Python3, Java)

This is Rute.

AtCoder Beginner Contest 175 B I will explain the problem "Making Triangle".

Problem URL: https://atcoder.jp/contests/abc175/tasks/abc175_b

Problem summary

Find out how many $ N $ sticks you can choose from different lengths </ b> $ 3 $ sticks that can make a triangle.

Constraint

・ $ 1 \ leq N \ leq 100 $ ・ $ 1 \ leq L_i \ leq 10 ^ 9 $ ・ All inputs are integers

solution

Initialize with ans = 0. You can implement the following iterative processing. -Perform the following iterative processing in the range of $ (0, n) $ (counter variable is $ i $) -Perform the following iterative processing in the range of $ (i + 1, n) $ (counter variable is $ j $) -Perform the following iterative processing in the range of $ (j + 1, n) $ (counter variable is $ k $) Determine if L [i] == L [j] or L [i] == L [k] or L [j] == L [k] is satisfied. To do. ・ If not satisfied ( length is different </ b> condition is satisfied) Determine if the following equation holds, and if so, add 1 to ans.

L[i]+L[j] > L[k] \space and \space L[j]+L[k] > L[i] \space and \space L[i]+L[k] > L[j]

Since it is the number of combinations required by ans, you can output this.

The amount of calculation is $ O (N ^ 3) $, which is in time for constraints. Below are examples of solutions in Python3, C ++, and Java.

Example of answer for each language

Example solution in Python3

{ABC175B.py}


N = int(input())
L = list(map(int,input().split()))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            if L[i] == L[j] or L[j] == L[k] or L[i] == L[k]:
                continue
            else:
                if L[i]+L[j] > L[k] and L[j]+L[k] > L[i] and L[k]+L[i] > L[j]:
                    ans += 1
print(ans)
Example solution in C ++

{ABC175B.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<long long> L(n);
  for (int i = 0; i < n; i++){
    int l;
    cin >> l;
    L.at(i) = l;
  int ans = 0;
  for (int i = 0; i < n; i++){
    for (int j = i+1; j < n; j++){
      for (int k = j+1; k < n; k++){
        if (L.at(i) == L.at(j) || L.at(i) == L.at(k) || L.at(j) == L.at(k)){
          continue;
        }else{
          if (L.at(i)+L.at(j) > L.at(k) && L.at(j)+L.at(k) > L.at(i) && L.at(i)+L.at(k) > L.at(j){
            ans++;
          }
        }
      }
    }
  }
  cout << ans << endl;
}
Java answer example

{ABC175B.cpp}


import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int n = scan.nextInt();
    long L[]; L = new long[n];
    for (int i = 0; i < n; i++){
      long l = scan.nextLong();
      L[i] = l;
    }
    int ans = 0;
    for (int i = 0; i < n; i++){
      for (int j = i+1; j < n; j++){
        for (int k = j+1; k < n; k++){
          if (L[i] == L[j] || L[i] == L[k] || L[j] == L[k]){
            continue;
          }else{
            if (L[i]+L[j] > L[k] && L[i]+L[k] > L[j] && L[j]+L[k] > L[i]){
              ans++;
            }
          }
        }
      }
    }
    System.out.println(ans);
  }
}

Recommended Posts