AtCoder Anfängerwettbewerb 175 B Problem "Making Triangle" Erklärung (C ++, Python3, Java)

Das ist Rute.

AtCoder Beginner Contest 175 B Ich werde das Problem "Making Triangle" erklären.

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

Problemzusammenfassung

Finden Sie heraus, wie viele $ N $ -Sticks Sie aus verschiedenen Längen </ b> $ 3 $ -Sticks auswählen können, die ein Dreieck bilden können.

Zwang

・ $ 1 \ leq N \ leq 100 $ ・ $ 1 \ leq L_i \ leq 10 ^ 9 $ ・ Alle Eingänge sind ganze Zahlen

Lösung

Initialisieren Sie mit ans = 0. Sie können die folgende iterative Verarbeitung implementieren.

  • Führen Sie die folgende iterative Verarbeitung im Bereich von $ (0, n) $ durch (Zählervariable ist $ i $).
  • Führen Sie die folgende iterative Verarbeitung im Bereich von $ (i + 1, n) $ durch (Zählervariable ist $ j $)
  • Führen Sie die folgende iterative Verarbeitung im Bereich von $ (j + 1, n) $ durch (Zählervariable ist $ k $) Bestimmen Sie, ob "L [i] == L [j]" oder "L [i] == L [k]" oder "L [j] == L [k]" erfüllt ist. Machen. ・ Wenn nicht erfüllt ( Länge ist unterschiedlich </ b> Bedingung ist erfüllt) Bestimmen Sie, ob die folgende Gleichung gilt, und addieren Sie in diesem Fall 1 zu 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]

Da dies die Anzahl der von ans benötigten Kombinationen ist, können Sie diese ausgeben.

Der Berechnungsbetrag beträgt $ O (N ^ 3) $, was rechtzeitig für Einschränkungen ist. Nachfolgend finden Sie Beispiele für Antworten in Python3, C ++ und Java.

Beispiel für eine Antwort für jede Sprache

Beispiellösung 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)
Lösungsbeispiel 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-Antwortbeispiel

{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