AtCoder Grand Contest 009: A - Multiple Array

solution

典型ぽい貪欲。最後の項を変えるには最後のボタンを押すしかないので、後ろから順にそのようにする。$O(N)$。

implementation

必要になったから使ったのだけどzip(*[ ... ])は便利

#!/usr/bin/env python3
n = int(input())
a, b = zip(*[ map(int, input().split()) for _ in range(n) ])
c = 0
for i in reversed(range(n)):
    c += (- (a[i] + c)) % b[i]
print(c)