AtCoder Beginner Contest 169 B Je vais vous expliquer le problème "Multiplication 2".
URL du problème: https://atcoder.jp/contests/abc169/tasks/abc169_b
Une suite de nombres ($ A_1, ..., A_N $) constituée de $ N $ entiers est donnée. $ A_1 × ... × A_N $, soit
\prod_{i=1}^{N} A_i
Demander. Cependant, si cette valeur dépasse 10 $ ^ {18} $, affichez «-1».
・ $ 2 \ leq N \ leq 10 ^ 5 $ ・ $ 0 \ leq A_i \ leq 10 ^ {18} $ ・ Toutes les entrées sont des entiers
Ce problème nécessitait la connaissance de entiers multiples </ b>. Si vous entrez les valeurs de ces nombres dans un type ʻintet que vous les multipliez, un débordement <b> se produira. </ b> De plus, comme la contrainte est jusqu'à 10 $ ^ {18} $, un dépassement <b> se produira même si vous entrez et multipliez avec le typelong int`. </ b>
Par conséquent, nous devons prendre des mesures.
Le tri par ordre décroissant vous permet de trier les nombres par ordre décroissant. C'est une bonne décision, car trier un certain nombre de colonnes aboutira au même produit total </ b>. Après cela, multipliez les valeurs dans plusieurs colonnes et affichez «-1» lorsqu'il dépasse </ b> 10 $ ^ {18} $ pour terminer le processus. Le montant du calcul est $ O (logN) $ pour le tri et $ O (N) $ pour la multiplication, donc c'est $ O (NlogN) $.
De plus, si vous ne terminez pas le processus, ce sera TLE </ font> dans certaines langues. La raison est simple: il faut beaucoup de temps pour multiplier plusieurs entiers.
Par exemple, en Python3, C ++, Java, exécutez respectivement 100 $ × 100 $, 10 $ ^ 5 × 10 ^ 5 $, 10 $ ^ 9 × 10 ^ 9 $ et 10 $ ^ {18} $ plusieurs fois. Comparons le temps de calcul
(J'ai utilisé le test de code d'AtCoder)
(En Python3, j'ai entré la valeur comme ʻint, en C ++ comme long long int, et en Java comme double`, et je l'ai exécutée.)
( Le calcul est basé sur l'hypothèse d'un dépassement de capacité </ b>)
| Calcul | Python3 | C++ | Java |
|---|---|---|---|
| 18ms | 6ms | 122ms | |
| 21ms | 10ms | 106ms | |
| 18ms | 7ms | 122ms | |
| 19ms | 8ms | 122ms | |
| 18ms | 6ms | 118ms | |
| 585ms | 8ms | 113ms | |
| 10500ms | 9ms | 118ms |
Comme vous pouvez le voir, il n'y a pas beaucoup de différence de temps de calcul entre C ++ et Java, mais avec Python3, le temps d'exécution est limité en raison du grand nombre de calculs 2sec (2000ms) </ font> Vous pouvez voir que la police> prend plus de temps de calcul.
S'il y a même un $ 0 $ dans la colonne numérique, le produit total sera naturellement $ 0 $, mais si vous faites la même chose que la contre-mesure 1, en fait, -1 sera affiché même dans la séquence de nombres contenant $ 0 $. Sera fait.
La raison est simple. Parce qu'il est jugé que le produit total dépasse 10 $ ^ {18} $ en raison du terme avec une valeur élevée qui n'est pas 0 $ par tri, et il est affiché sous la forme «-1» </ b>.
Cela fait apparaître le jugement WA </ font> dans la casse du coin telle que zero_01.txt.
Ainsi, lors de la lecture d'une séquence de nombres, créons une fonction indicateur qui définit $ 0 $ à 1 s'il existe </ b>. Ensuite, vous pouvez déterminer si le produit total est de 0 $ avant de multiplier! </ B>
En Python3, vous pouvez vérifier si le terme $ 0 $ existe dans ʻA.count (0) `.
En d'autres termes, les points de chaque langue pour ce problème sont les suivants.
・ Python3 La multiplication de plusieurs entiers </ b> prend beaucoup de temps de calcul et doit être évitée. ・ C ++, Java Il vaut mieux éviter les erreurs de calcul dues au débordement </ b>
Vous trouverez ci-dessous des exemples de réponses en Python3, C ++ et Java.
{ABC169.py}
N = int(input())
A = list(map(int,input().split()))
A.sort()
A.reverse()
if A.count(0) > 0:
print(0)
else:
f = 0
ans = 1
for i in range(N):
ans *= A[i]
if ans > 10**18:
f += 1
print(-1)
break
if f == 0:
print(ans)
{ABC169.cpp}
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<long int> vec(n);
for (int i = 0; i < n; i++){
long int a;
cin >> a;
vec.at(i) = a;
if(vec.at(i) == 0){
cout << 0 << endl;
return 0;
}
}
sort(vec.begin(),vec.end());
reverse(vec.begin(),vec.end());
long int ans = 1;
for (int i = 0; i < n; i++){
if (vec.at(i) > 1000000000000000000/ans){
cout << -1 << endl;
return 0;
}else{
ans *= vec.at(i);
}
}
cout << ans << endl;
}
{ABC169.java}
import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long [] a = new long[n];
for (int i = 0; i < n; i++){
a[i] = scan.nextLong();
if (a[i] == 0){
System.out.println(0);
return;
}
}
Arrays.sort(a);
long ans = 1;
for (int i = n-1; i >= 0; i--){
if (a[i] > 1000000000000000000L/ans){
System.out.println(-1);
return;
}else{
ans *= a[i];
}
}
System.out.println(ans);
}
}
Recommended Posts