AtCoder Beginner Contest 175 B Explication du problème "Making Triangle" (C ++, Python3, Java)

C'est Rute.

AtCoder Beginner Contest 175 B Je vais vous expliquer le problème "Making Triangle".

URL du problème: https://atcoder.jp/contests/abc175/tasks/abc175_b

Résumé du problème

Découvrez combien de tiges $ N $ vous pouvez choisir parmi différentes longueurs </ b> tiges $ 3 $ pouvant former un triangle.

Contrainte

・ $ 1 \ leq N \ leq 100 $ ・ $ 1 \ leq L_i \ leq 10 ^ 9 $ ・ Toutes les entrées sont des entiers

Solution

Initialisez avec ans = 0. Vous pouvez implémenter le traitement itératif suivant. -Effectuer le traitement itératif suivant dans la plage de $ (0, n) $ (la variable du compteur est $ i $) -Effectuer le traitement itératif suivant dans la plage de $ (i + 1, n) $ (la variable du compteur est $ j $) -Effectuer le traitement itératif suivant dans la plage de $ (j + 1, n) $ (la variable du compteur est $ k $) Déterminer si L [i] == L [j] ou L [i] == L [k] ou L [j] == L [k] est satisfait Faire. ・ Si non satisfait (la condition longueur est différente </ b> est satisfaite) Déterminez si l'équation suivante est vérifiée et, le cas échéant, ajoutez 1 à 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]

Puisqu'il s'agit du nombre de combinaisons requises par ans, vous pouvez le sortir.

Le montant du calcul est $ O (N ^ 3) $, ce qui correspond au temps pour les contraintes. Vous trouverez ci-dessous des exemples de réponses en Python3, C ++ et Java.

Exemple de réponse pour chaque langue

Exemple de solution en 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)
Exemple de solution en 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;
}
Exemple de solution en Java

{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