AtCoder Beginner Contest 169 B Ich werde das Problem "Multiplikation 2" erklären.
Problem-URL: https://atcoder.jp/contests/abc169/tasks/abc169_b
Es wird eine Zahlenfolge ($ A_1, ..., A_N $) angegeben, die aus $ N $ ganzen Zahlen besteht. Das heißt $ A_1 × ... × A_N $
\prod_{i=1}^{N} A_i
Nachfragen. Wenn dieser Wert jedoch $ 10 ^ {18} $ überschreitet, geben Sie -1 aus.
・ $ 2 \ leq N \ leq 10 ^ 5 $ ・ $ 0 \ leq A_i \ leq 10 ^ {18} $ ・ Alle Eingänge sind ganze Zahlen
Dieses Problem erforderte Kenntnisse über mehrere Ganzzahlen </ b>. Wenn Sie die Werte in diesen Zahlen in einem "int" -Typ eingeben und multiplizieren, tritt ein Überlauf auf. </ b> Da die Einschränkung bis zu $ 10 ^ {18} $ beträgt, tritt ein Überlauf auf, selbst wenn Sie den Typ "long int" eingeben und mit ihm multiplizieren. </ b>
Deshalb müssen wir einige Maßnahmen ergreifen.
Durch Sortieren in absteigender Reihenfolge können Sie die Zahlen in absteigender Reihenfolge sortieren. Dies ist ein guter Schritt, da das Sortieren einer Anzahl von Spalten zum gleichen Gesamtprodukt </ b> führt. Danach multiplizieren Sie die Werte in mehreren Spalten und geben "-1" aus, wenn </ b> $ 10 ^ {18} $ überschreitet, und beenden Sie den Vorgang. Der Berechnungsbetrag beträgt $ O (logN) $ für die Sortierung und $ O (N) $ für die Multiplikation, also $ O (NlogN) $.
Wenn Sie den Vorgang nicht abschließen, wird in einigen Sprachen TLE </ font> angezeigt. Der Grund ist einfach: Das Multiplizieren mehrerer Ganzzahlen dauert lange. Führen Sie beispielsweise in Python3, C ++, Java $ 100 × 100 $, $ 10 ^ 5 × 10 ^ 5 $, $ 10 ^ 9 × 10 ^ 9 $ Multiplikation bzw. $ 10 ^ {18} $ mehrmals aus. Vergleichen wir die Berechnungszeit (Ich habe den Code-Test von AtCoder verwendet) (Ich habe den Wert in Python3 als "int", in C ++ als "long long int" und in Java als "double" eingegeben und ausgeführt.) ( Die Berechnung basiert auf der Annahme, dass ein Überlauf auftritt </ b>)
| Berechnung | Python3 | C++ | Java |
|---|---|---|---|
| 18ms | 6ms | 122ms | |
| 21ms | 10ms | 106ms | |
| 18ms | 7ms | 122ms | |
| 19ms | 8ms | 122ms | |
| 18ms | 6ms | 118ms | |
| 585ms | 8ms | 113ms | |
| 10500ms | 9ms | 118ms |
Wie Sie sehen, gibt es keinen großen Unterschied in der Berechnungszeit zwischen C ++ und Java, aber mit Python3 ist die Ausführungszeit aufgrund der großen Anzahl von Berechnungen 2 Sekunden (2000 ms) </ font> begrenzt Sie können sehen, dass Schriftart> mehr Rechenzeit benötigt.
Wenn die Sequenz nur ein $ 0 $ enthält, beträgt das Gesamtprodukt natürlich $ 0 $. Wenn Sie jedoch dasselbe wie bei Gegenmaßnahme 1 tun, wird tatsächlich sogar in der Sequenz, die $ 0 $ enthält, "-1" ausgegeben. Getan werden.
Der Grund ist einfach. Weil beurteilt wird, dass das Gesamtprodukt aufgrund des Ausdrucks mit einem großen Wert, der nicht $ 0 $ ist, durch Sortieren $ 10 ^ {18} $ überschreitet und als -1 </ b> ausgegeben wird.
Dies führt dazu, dass das Urteil WA </ font> im Eckfall wie "zero_01.txt" angezeigt wird.
Wenn Sie also eine Folge von Zahlen lesen, erstellen wir eine Flag-Funktion, die $ 0 $ auf 1 setzt, falls vorhanden </ b>. Dann können Sie bestimmen, ob das Gesamtprodukt $ 0 $ ist, bevor Sie multiplizieren! </ B>
In Python3 können Sie überprüfen, ob der Begriff $ 0 $ in A.count (0) vorhanden ist.
Mit anderen Worten, die Punkte jeder Sprache für dieses Problem sind wie folgt.
・ Python3 Das Multiplizieren mehrerer Ganzzahlen </ b> nimmt viel Rechenzeit in Anspruch und sollte vermieden werden. ・ C ++, Java
Nachfolgend finden Sie Beispiele für Antworten in Python3, C ++ und 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);
}
}