問題概要
問題ページ
-
-
B - Multiplication 2
問題ページへ移動する
問題文
\(N\) 個の整数 \(A_1,...,A_N\) が与えられます。
\(A_1 \times ... \times A_N\) を求めてください。
ただし、結果が \(10^{18}\) を超える場合は、代わりに -1 を出力してください。
制約
- \(2 \leq N \leq 10^5\)
- \(0 \leq A_i \leq 10^{18}\)
- 入力は全て整数である。
問題の考察
問題はシンプルで各\(A_i\)の総乗（全てを掛け算する）を求めれば良い。
「\(10^18\)を超える場合には-1を出力する」とあるが、掛け算の性質を忘れると間違ってしまう。
\(1 \times 2 \times ... \times 100 \times 0\)
のように最後が\(0\)の場合、全て計算すると答えは\(0\)になるが途中で\(10 ^ 18\)を超えてしまい-1を出力してしまう。
全て計算しようとしても\(10^18\)が\(10^5\)個だと計算が間に合わずにTLEしてしまう。
\(A_1,...,A_N\)をsort()で昇順に並び替えてから計算する必要がある。
\(0 \leq A_i \leq 10^{18}\)なので、負の値は存在しないので間に合う。
負の値がある場合でも\(0\)をカウントして処理すれば計算できる。
昇順に並び替える場合
sort()で昇順に並び替える- 総乗が\(0\)になったら
0を出力 - \(10^18\)を超えたら
-1を出力 - それ以外の場合には計算した総乗を出力
0をカウントする場合
- \(0\)をカウントして存在すれば\(0\)を出力
- 存在ければ順に計算し\(10^18\)を超えたら
-1を出力 - それ以外の場合には計算した総乗を出力
ACコードは昇順に並び替える方法で解答しています。
たびすけ
問題文は難しくないけど油断すると間違えてしまう問題！
ACコード
import sys
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
n = int(input().rstrip('\n'))
a = list(map(int, input().rstrip('\n').split()))
a.sort()
t = 1
limit = pow(10, 18)
for i in range(n):
t *= a[i]
if t > limit:
print(-1)
exit()
print(t)
if __name__ == '__main__':
solve()