AtCoder Beginner Contest 176 B Problème Explication "Multiple of 9" (Python3, C ++, Java)

C'est Rute. Cet article est la suite du commentaire précédent Un problème </ b>!

Liens vers chaque problème / explication

A B C
ABC176 A Cetarticle!!! ABC176C

Maintenant, je vais vous expliquer le problème B </ b>.

Résumé du problème

Déterminez si $ N $ est un multiple de 9 $ $.

Contrainte

・ $ 0 \ leq N \ leq 10 ^ {200000} $ ・ $ N $ est un entier

Veuillez noter que cette fois, la méthode de solution est différente entre Python3, C ++ et Java.

Commentaire

Solution 1 (pour Python 3)

  • Vous pouvez également le résoudre avec la Solution 2, qui sera expliquée plus tard. Dans le cas de Python3, il n'y a pas de limite au nombre d'entiers qui peuvent être représentés par type ʻint` </ b>, donc vous pouvez AC en écrivant la branche conditionnelle suivante! (Strictement parlant, il peut gérer plusieurs entiers de longueur) </ font>

{ABC176B.py}


print("Yes") if int(input())%9 == 0 else print("No")
  • Le code a été raccourci ici, mais il n'y a pas de problème si vous le résolvez sans le raccourcir.

Solution 2 (pour C ++ et Java)

Faisons attention à cette limitation. ・ $ 0 \ leq N \ leq 10 ^ {200000} $ </ font>

Oui, la plage de $ N $ va jusqu'à 10 $ ^ {200000} $. Puisque $ 10 ^ {64} $ est 1 nombre infini </ b>, $ 10 ^ {200000} $ est un entier extrêmement grand </ b>.

Un tel entier ne peut pas être représenté en C ++ par le type long long int, sans parler du type ʻint. </ font> (En Java, c'est le type long`)

Alors tout le monde, vérifions la nature des multiples de 9 $. Tout d'abord, regardez cette vidéo.

La nature des multiples de 9 (source: Trivia Fountain)




La réponse à la multiplication de 9 est toujours 9 lorsque vous additionnez les nombres ensemble </ font>

Cela équivaut à la somme des chiffres est divisible par 9 $ </ b> si elle est un multiple de 9 $. (similaire à cela est indiqué dans l'énoncé du problème) </ font> En d'autres termes, j'ai pu le remplacer par le simple problème de déterminer si la somme des chiffres est divisible par 9 $ </ b>. Il faut temps linéaire pour la longueur de la chaîne </ b> pour trouver la somme des chiffres, mais dans les limites des contraintes, il est temps pour la limite de temps d'exécution.

Voici un exemple de la solution de la solution 2 en 3 langages: Python3, C ++ et Java.

Exemple de réponse pour chaque langue (Solution 2)

Exemple de solution en Python3

{ABC176B2.py}


N = input()
ans = 0
for i in range(len(N)):
  ans += N[i]
print("Yes") if ans%9 == 0 else print("No")
Exemple de solution en C ++

{ABC176B2.cpp}


#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int ans = 0;
  for (int i = 0; i < s.size(); i++){
    ans = ans +  int(s.at(i))-48;
  }
  if (ans%9==0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}
  • La somme des chiffres a été calculée en utilisant la nature du code ASCII. Dans le code ASCII, «0» est «48» et «9» est «57», vous pouvez donc convertir la chaîne de caractères en un entier en soustrayant 48 du code ASCII.
Exemple de solution en Java

{ABC176B2.java}


import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    String S = scan.next();
    int ans = 0;
    for (int i = S.length(); i > 0 ; i--){
      ans = ans + Integer.parseInt(S.substring(i-1,i));
    }
    if (ans % 9 == 0){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}

Recommended Posts