Problem:


Score : 500 points

Problem Statement

An adult game master and N children are playing a game on an ice rink.
The game consists of K rounds.
In the i-th round, the game master announces:

Form groups consisting of A_i children each!

Then the children who are still in the game form as many groups of A_i children as possible.
One child may belong to at most one group.
Those who are left without a group leave the game. The others proceed to the next round.
Note that it's possible that nobody leaves the game in some round.

In the end, after the K-th round, there are exactly two children left, and they are declared the winners.

You have heard the values of A_1, A_2, ..., A_K. You don't know N, but you want to estimate it.

Find the smallest and the largest possible number of children in the game before the start, or determine that no valid values of N exist.

Constraints

1 \leq K \leq 10^5

2 \leq A_i \leq 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

K
A_1 A_2 ... A_K

Output

Print two integers representing the smallest and the largest possible value of N, respectively,
or a single integer -1 if the described situation is impossible.

Sample Input 1

4
3 4 3 2

Sample Output 1

6 8

For example, if the game starts with 6 children, then it proceeds as follows:

In the first round, 6 children form 2 groups of 3 children, and nobody leaves the game.

In the second round, 6 children form 1 group of 4 children, and 2 children leave the game.

In the third round, 4 children form 1 group of 3 children, and 1 child leaves the game.

In the fourth round, 3 children form 1 group of 2 children, and 1 child leaves the game.

The last 2 children are declared the winners.

Sample Input 2

5
3 4 100 3 2

Sample Output 2

-1

This situation is impossible.
In particular, if the game starts with less than 100 children, everyone leaves after the third round.

Sample Input 3

10
2 2 2 2 2 2 2 2 2 2

Sample Output 3

2 3



Sample input:
4
3 4 3 2


Sample output:
6 8

Submission status: Accepted

Solution code:
k = int(input())
ai = [int(i) for i in input().split()]

low = 2
high = 2*10**15
ans = []

while low+1 < high:
    tmp = 0
    mid = (low + high) //2
    #print(mid)
    tmp = mid
    
    for i in range(k):
        tmp = tmp // ai[i]
        tmp = tmp*ai[i]
    #print(tmp,mid,low)
    
    if tmp > 2:
        high = mid
    else:
        low = mid

tmp = low

for i in range(k):
    tmp = tmp // ai[i]
    tmp = tmp*ai[i]

if tmp != 2:
    print(-1)
    exit()
        
ans.append(low)

low = 2
high = 2*10**15

flag = True

while low+1 < high:
    tmp = 0
    mid = (low + high) //2
    if flag == True:
        flag = False
        mid = 2
    #print(mid)
    tmp = mid
    
    for i in range(k):
        tmp = tmp // ai[i]
        tmp = tmp*ai[i]
    #print(tmp)
    
    if tmp > 1:
        high = mid
    else:
        low = mid
    #print(mid)
ans.append(high)
tmp = high
for i in range(k):
    tmp = tmp // ai[i]
    tmp = tmp*ai[i]

if tmp != 2:
    print(-1)
    exit()
print(ans[1],ans[0])

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int, input().split()))[::-1]
if A[0] != 2:
  print(-1)
  quit()

left = 2; right = 3
for a in A[1:]:
  ra = right - right%a
  if ra < left:
    print(-1)
    quit()
  l1 = ra; r1 = ra + a - 1
  la = left + (a - (left%a))%a
  l2 = la; r2 = la + a - 1
  left = min(l1, l2)
  right = max(r1, r2)

print(left, right)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
low, high = 2, 2

for a in A[::-1]:
    low += (-low) % a
    high -= high % a
    high += (a-1)

if low > high:
    print(-1)
else:
    print(low, high)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

min = 2
max = 2
for i in reversed(a):
    max = max // i * i + i - 1
    min = (min + i - 1) // i * i

if min >= max:
    print("-1")
else:
    print(min, max)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

k = int(input())
a = list( map(int, input().split()))

if a[-1]!=2:
    print(-1)
    exit()

ma = 2

for i in reversed(range(k)):
    ma = ma//a[i]*a[i] + (a[i]-1)

    if a[i] > ma:
        print(-1)
        exit()

mi = 2

for i in reversed(range(k)):

    mi = -(-mi//a[i])*a[i]

if mi > ma:
    print(-1)
    exit()

print(mi,ma)

Submission status: Accepted

Solution code:
K=int(input())
A=list(map(int,input().split()))
mb=Mb=2
t=1
for i in A[::-1]:
    if Mb//i*i>=mb:
        Ma=(Mb//i+1)*i-1
    else:
        t=0
        break
    if mb%i==0:
        ma=mb
    elif (mb//i+1)*i<=Mb:
        ma=(mb//i+1)*i
    else:
        t=0
        break
    mb=ma
    Mb=Ma
if t:
    print(ma,Ma)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

K = INT()
A = LIST()
if A[-1] != 2:
	print(-1)
	exit()

ma = 3
mi = 2

for x in A[::-1]:
	if x > ma:
		print(-1)
		exit()
	elif mi <= x <= ma:
		mi = x
		ma = 2*x-1
	else:
		tmp_mi = -(-mi//x)*x
		tmp_ma = ma//x*x
		if tmp_mi > tmp_ma:
			print(-1)
			exit()
		ma = tmp_ma+x-1
		mi = tmp_mi

print(mi, ma)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))

if A[-1] > 2:
    print(-1)
    exit()

"""
愚直解
初めの人数を2から増やしていって確認。範囲が分からないので、間に合わないのは分かるが計算量は分からん。

問題的にも最後から最初に戻るのがよさそう。
問題的に、Aiの処理を受けたすぐの人数をCiとする。また、ラウンドiの後にとりうる最大の人数をHIi,最小をLOiとする
考えるうえでややこしいのだが、

HIi-1                 HIi
 Ci-1   ->  {Ai} ->    Ci
LOi-1                 LOi

の形になっていて、
「LOi-1~HIi-1 の範囲の値が、  Aiの処理を受けたときに、HIiやLOiの範囲に収まらなければならない」
であるので、HIi-1,LOi-1 が Ai,HIi,LOiに依存している。
（HIi,LOiがAiで決まるのではないのに気を付けたい）

最後の状態（HIi = LOi = Ci = 2）が決まっているので、後ろから先頭に戻る形で、HIi-1, LOi-1を決めていく。

LOi-1を　Aiに通した後の値が LOi であるのは自明で、「LOi-1はAiの定数倍かつ、LOi以上」であるから
LOi-1 = (Loi // Ai) * Ai
といえる

HIi-1 を Ai に通した後に、HIi以下に収まらなければならないので、
HIi-1 = (HIi // Ai) * Ai + (Ai - 1)
となる。ここちょっと発想しにくい感じある。
(HIi // Ai + 1) * Ai が、Aiを通すと、HIiを上回るので、これより小さい物の中で最も大きいものを選びたいから。


"""


HI = 2
LO = 2
for i in range(N):
    
    if LO // A[N-i-1] > 0:
        if LO % A[N-i-1] > 0:
            nxt_LO = (LO // A[N-i-1] + 1) * A[N-i-1]
        else:
            nxt_LO = LO
    else:
        nxt_LO = A[N-i-1]

    
    
    nxt_HI = (HI // A[N-i-1]) * A[N-i-1] + (A[N-i-1] - 1)

    if HI > nxt_HI or LO > nxt_LO  or nxt_HI < nxt_LO:
        print(-1)
        exit()

    LO = nxt_LO
    HI = nxt_HI

print(LO, HI)

Submission status: Accepted

Solution code:
def calc(n, N, x):
    m, M = -1, -1
    L, R = 0, 10**13
    while L+1 < R:
        P = (L+R)//2
        if n <= x*P:
            R = P
        else:
            L = P
    if n <= x*R <= N:
        m = x*R
    L, R = 0, 10**13
    while L+1 < R:
        P = (L+R)//2
        if N < x*P:
            R = P
        else:
            L = P
    if n <= x*L <= N:
        M = x*L + (x-1)
    return m, M

def main():
    k = int(input())
    a = list(map(int, input().split()))
    f = True
    m, M = 2, 2
    for i in reversed(range(k)):
        m, M = calc(m, M, a[i])
        if m == -1 or M == -1:
            f = False
            break
    if f:
        print(m, M)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import ceil as c
input()
m=M=2
for b in map(int,input().split()[::-1]):
  m = c(m/b)*b
  M = c((M+1)/b)*b-1
  if m > M:
    print(-1)
    exit()
print(m,M)

Submission status: Accepted

Solution code:
import math
n = int(input())
a = [int(i) for i in input().split()]
mi = 2
ma = 2
for b in a[::-1]:
  mi = math.ceil(mi/b)*b
  ma = math.ceil((ma+1)/b)*b-1
  if ma < b or mi > ma:
    print(-1)
    exit()
print(mi,ma)

Submission status: Accepted

Solution code:
k = int(input())
a = list(map(int, input().split()))

def sim(num):
    for g in a:
        num = g * (num//g)
    return num

l=0
r=100+k*max(a)
while r-l>1:
    mid=(l+r)//2

    if sim(mid) > 2:
        r=mid
    else:
        l=mid
ans_max=l

l=0
r=100+k*max(a)
while r-l>1:
    mid=(l+r)//2

    if sim(mid) < 2:
        l=mid
    else:
        r=mid
ans_min=r

if ans_min > ans_max:
    print(-1)
else:
    print(ans_min,ans_max)

Submission status: Accepted

Solution code:
k = int(input())
a = list(map(int, input().split()))
a.reverse()

mn,mx = 2,2
for g in a:
    mn = g * (((mn - 1) // g) + 1)
    mx = g * (mx//g) + g - 1

    if mn > mx:
        print(-1)
        exit()

print(mn,mx)

Submission status: Accepted

Solution code:
k,*a = map(int,open(0).read().split())
a = a[::-1]
nmax = 2
nmin = 2
for i in range(k):
  if nmax//a[i]-(nmin-1)//a[i]<=0:
    print(-1)
    exit()
  nmin = ((nmin-1)//a[i]+1)*a[i]
  nmax = (nmax//a[i])*a[i]+a[i]-1
print(nmin,nmax)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b, a%b)

def lcm(a,b):
    return a // gcd * b

def main():
    K = int(input())
    A = [int(_n) for _n in input().split()]
    maxnum = 2
    minnum = 2
    for i in reversed(range(0,K)):
        mi = (minnum + A[i] - 1)//A[i] * A[i]
        ma = maxnum // A[i] * A[i]
        # print(mi,ma)
        if mi < minnum or mi > maxnum or ma < minnum or ma > maxnum:
            print(-1)
            return
        minnum = mi
        maxnum = ma+A[i]-1
    print(minnum,maxnum)
main()

Submission status: Accepted

Solution code:
# 現在の数curに対して直前の数としてあり得る範囲は、cur ~ cur + A[i] - 1の範囲内
# さらにA[i-1]の倍数である必要があるため、上記範囲内のA[i-1]の倍数の最大最小値を設定する
# 直前の数がない場合(最後)はcur, cur + A[i]をそのまま出力
import sys
readline = sys.stdin.readline

K = int(readline())
A = list(map(int,readline().split()))[::-1] # ややこしいので逆順で見ていく

mincur = 2
maxcur = 2

def get_min_val(c,a): # c以上のaの倍数の最小値を求める
  return ((c - 1)//a + 1) * a

def get_max_val(c,a): # c以下のaの倍数の最大値を求める
  return (c // a) * a

if A[0] != 2:
  print(-1)
  exit(0)
  
for i in range(len(A)):
  mincur = mincur
  maxcur = maxcur + A[i] - 1
  if i + 1 < len(A):
    mincur = get_min_val(mincur,A[i + 1])
    maxcur = get_max_val(maxcur,A[i + 1])
    if mincur > maxcur:
      print(-1)
      exit(0)
print(mincur,maxcur)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import math

k = ni()
a = na()

r,l = 2,2

for i in a[::-1]:
    if r < i:
        print(-1)
        exit()
    l = math.ceil(l/i)*i
    r = (r//i)*i+i-1
    if l > r:
        print(-1)
        exit()

print(l,r)

Submission status: Accepted

Solution code:
k = int(input())
A = list(map(int,input().split()))[::-1]

dp = [[0,0] for _ in range(k+1)]
dp[0] = [2,2]

for i in range(k):
    dp[i+1][0] = ((dp[i][0]-1)//A[i] + 1)*A[i]
    dp[i+1][1] = (dp[i][1]//A[i])*A[i] + A[i] -1
    if dp[i+1][0] > dp[i+1][1]:
        print(-1)
        exit(0)
print(' '.join(str(i) for i in dp[k]))

Submission status: Accepted

Solution code:
MOD = 10 **9 + 7
INF = 10 ** 10

def main():
    K = int(input())
    A = list(map(int,input().split()))
    m = 2
    M = 2
    flag = True
    for i in range(K - 1,-1,-1):
        x = (m + A[i] - 1)//A[i]
        y = M//A[i]
        if x > y:
            flag = False
            break
        M = y*A[i] + A[i] - 1
        m = x*A[i]
    if flag:
        print(m,M)
    else:
        print(-1)         
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:




K = int(input())
A = list(map(int, input().split()))

if A[-1] > 2:
    print(-1)
    exit()



hi = 2
lo = 2

for i in reversed(range(K)):



    new_hi = hi // A[i] * A[i] + (A[i] - 1)

    if lo // A[i] > 0 and lo % A[i] > 0:
        new_lo = (lo // A[i] + 1) * A[i]
    elif lo // A[i] > 0 and lo % A[i] == 0:
        new_lo = lo
    elif lo // A[i] == 0:
        new_lo = A[i]

    if new_hi < hi or new_lo < lo or new_hi < new_lo:
        print(-1)
        exit()


    

    hi = new_hi
    lo = new_lo


print(lo, hi)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
A=A[::-1]
dpmax=[0 for i in range(0,N)]
dpmin=[0 for i in range(0,N)]

for i in range(0,N):
    if i==0:
        if A[0]!=2:
            print(-1)
            break
        else:
            dpmax[0]=3
            dpmin[0]=2
    else:
        testmax=dpmax[i-1]-dpmax[i-1]%A[i]
        if dpmin[i-1]%A[i]!=0:
            testmin=dpmin[i-1]-dpmin[i-1]%A[i]+A[i]
        else:
            testmin=dpmin[i-1]
        if testmax>=dpmin[i-1]:
            dpmax[i]=testmax+A[i]-1
        else:
            print(-1)
            break
        if dpmax[i-1]>=testmin:
            dpmin[i]=testmin
        else:
            print(-1)
            break
else:
    print(dpmin[-1],dpmax[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    k = II()
    a = LI()
    if a[-1] == 2:
        tmp = [2, 3]
        for ai in a[::-1]:
            tmp0, tmp1 = tmp
            if tmp1 // ai > (tmp0 - 1) // ai:
                tmp = [((tmp0 - 1) // ai + 1) * ai, (tmp1 // ai+1) * ai  - 1]
            else:
                print(-1)
                return
        print(*tmp)
    else:
        print(-1)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
x=2
y=2
A=A[::-1]
for i in range(N):
  if y<A[i]:
    print(-1)
    exit()
  else:
    if x<A[i]:
      x=A[i]
    if x%A[i]!=0:
      x+=A[i]-x%A[i]
    if y%A[i]!=0:
      y-=y%A[i]
    y+=A[i]-1
    if x>y:
      print(-1)
      exit()
print(x,y)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
x=2
y=2
A=A[::-1]
for i in range(N):
  nmin=((x+A[i]-1)//A[i])*A[i]
  nmax=y-y%A[i]
  if nmin>nmax:
    print(-1)
    exit()
  x=nmin
  y=nmax+A[i]-1
print(x,y)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    low = 2
    high = 2
    for a in A[::-1]:
        if(high < a):
            print(-1)
            return
        high = a * (high//a)
        low = a * ceil(low,a)
        if(high<low):
            print(-1)
            return
        high += a-1
    print(low,high)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

from math import ceil, floor

def main():
  k = int(input())
  la = list(map(int, input().split()))[::-1]
  l = 2
  r = 2
  for a in la:
    if ceil(l/a) > floor(r/a):
      print(-1)
      return
    l = ceil(l/a) * a
    r = floor(r/a) * a + a - 1
  print(l, r)
      

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

k = INT()
a = LIST()
mn = 2
mx = 2
for i in reversed(range(k)):
    mn = (mn + a[i] - 1) // a[i] * a[i]
    mx = mx // a[i] * a[i] + a[i] - 1
    if mn > mx:
        print(-1)
        exit()
print(mn, mx)

Submission status: Accepted

Solution code:
k=int(input())
a=list(map(int,input().split()))
a.reverse()
ans1=2
ans2=2
for i in range(k):
	m,M=ans1,ans2
	ans1=((m-1)//a[i]+1)*a[i]
	ans2=M//a[i]*a[i]

	if ans1>ans2:
		print(-1)
		exit()

	ans1=ans1//a[i]*a[i]
	ans2=ans2//a[i]*a[i]+(a[i]-1)

if ans1>ans2:
	print(-1)
	exit()
else:
	print(ans1,ans2)

Submission status: Accepted

Solution code:
k = int(input())
a = list(map(int, input().split()))
#そのラウンドで落ちるマックスはa[i]-1人、残る人数は最小でa[i]
#a[i-1] <= 2 でなくてはいけない。
#そのラウンドが終わるごとに人数がa[i]の倍数になっていると考えると分かりやすい
#最大を考える場合は、そのラウンドで毎回毎回max人数落ちてると考えればいい
#最小を考える場合は、そのラウンドで毎回毎回min人数落ちていると考える

if a[-1] > 2:
    print(-1)
    exit()
ans_min = 2
ans_max = 2
a.reverse()
for i in range(k):
    if ans_max % a[i] != a[i] - 1:
        ans_max += (a[i] - 1) - (ans_max % a[i])
    if ans_min % a[i] != 0:
        ans_min += a[i] - ans_min % a[i]
a.reverse()
sim_max = ans_max
sim_min = ans_min
for i in range(k):
    sim_max = sim_max - sim_max % a[i]
    sim_min = sim_min - sim_min % a[i]
if sim_max == sim_min == 2:
    print("{} {}".format(ans_min, ans_max))
else:
    print(-1)

Submission status: Accepted

Solution code:
k = int(input())
A = list(map(int, input().split()))
A.reverse()

L = [-1]*(k+1)
R = [-1]*(k+1)

L[0] = 2
R[0] = 2
for i in range(1, k+1):
    if L[i-1]%A[i-1] == 0 or R[i-1]%A[i-1] == 0:
        pass
    else:
        if R[i-1] - L[i-1] >= A[i-1] or L[i-1]%A[i-1]>R[i-1]%A[i-1]:
            pass
        else:
            #print(i, A[i-1], L[i-1], R[i-1])
            print(-1)
            exit()
    if L[i-1]%A[i-1] == 0:
        L[i] = (L[i-1]//A[i-1])*A[i-1]
    else:
        L[i] = (L[i-1]//A[i-1]+1)*A[i-1]
    R[i] = (R[i-1]//A[i-1])*A[i-1]+A[i-1]-1
    #print(i, L[i], R[i])

#print(L)
#print(R)
print(L[k], R[k])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))[::-1]
if a[0]!=2:
    print(-1)
    exit()
import math
#print(a)
maxi=3
mini=2
for i in range(1,n):
    if mini<=a[i]:
        mini=a[i]
    else:
        times=math.ceil(mini/a[i])
        mini=a[i]*times
    if mini>maxi:
        print(-1)
        exit()
    #print("i={} mini={}".format(i,mini))
    if maxi<a[i]:
        print(-1)
        exit()
    else:
        times=int(maxi/a[i])
        maxi=a[i]*(times+1)-1
    #print("i={} maxi={}".format(i,maxi))
print(mini,maxi)

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int, input().split()))

def g(x):
    for a in A:
        x = (x // a) * a
    return x

overEq = 10**18
less = 0
while overEq - less > 1:
    mid = (overEq + less) // 2
    if g(mid) < 2:
        less = mid
    else:
        overEq = mid

over = 10**18
lessEq = 0
while over - lessEq > 1:
    mid = (over + lessEq) // 2
    if g(mid) <= 2:
        lessEq = mid
    else:
        over = mid

if g(overEq) == 2 and g(lessEq) == 2:
    print(overEq, lessEq)
else:
    print(-1)

Submission status: Accepted

Solution code:
K=int(input())
A=list(map(int, input().split()))

mx=2
mn=2
for i in range(K-1,-1,-1):
    a = A[i]
    a_mn = ((mn+a-1)//a)*a
    a_mx = mx - mx%a
    if a_mn > a_mx:
        print(-1)
        exit()
    mn=a_mn
    mx=a_mx+a-1
print("{} {}".format(mn,mx))

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int, input().split()))

mx = 2
mi = 2

for a in A[:: -1]:
    mx = (-(-(mx + 1) // a)) * a - 1
    mi = (-(-mi // a)) * a

def isOk(x):
    for a in A:
        x = (x // a) * a
    return x == 2

if isOk(mi) and isOk(mx):
    print(mi, mx)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

k = INT()
a = LIST()
l = 2
r = 2
for i in reversed(range(k)):
    l = (l + a[i] - 1) // a[i] * a[i]
    r = r // a[i] * a[i] + a[i] - 1
    if l > r:
        print(-1)
        exit()
print(l, r)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.append(2)
mi = 2
mx = 2
for i in range(N-1,-1,-1):
    # A[i]人に分けた結果 mi ~ mx人が残った
    mi = (mi + A[i] - 1) // A[i] * A[i]
    mx = mx // A[i] * A[i]
    if mi > mx:
        print(-1)
        exit(0)
    mx += A[i] - 1
print(mi,mx)

Submission status: Accepted

Solution code:
k = int(input())
a = list(map(int,input().split()))
def cal(x):
    for i in range(k):
        x -= (x%a[i])
    return x
top = 3+ k*max(a)
bot = 0
while top - bot > 1:
    mid = (top+bot)//2
    if cal(mid) >= 2:top = mid
    else:bot = mid
mini = top
top = 3+ k*max(a)
bot = 0
while top - bot > 1:
    mid = (top+bot)//2
    if cal(mid) > 2:top = mid
    else:bot = mid
maxi = bot
if mini > maxi:print(-1)
    
else:print(mini,maxi)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    K = int(input())
    A = [int(a) for a in input().split()]
    if A[K-1] != 2: print(-1)
    else:
        minK, maxK = 2, 3
        for i in reversed(range(K - 1)):
            mod = A[i]
            lb, hb = (minK - 1) // mod, maxK // mod
            if lb >= hb: 
                print(-1)
                break
            else:
                minK = mod * (lb + 1)
                maxK = mod * (hb + 1) - 1
        else: print(minK, maxK)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
k = int(input())
a = list(map(int, input().split()))

mx = 3
mn = 2
for i in range(k)[::-1]:
    mn = (mn + a[i] - 1) // a[i] * a[i]
    # print(mx + a[i] - 1)
    mx = (mx + a[i] - 1) // a[i] * a[i]
    # mx = min(2 * a[i] - 1, 2 * mx - 1)
    # print(mn, mx)
mx -= 1
# print()

ans = (mn,mx)
for i in range(k):
    mx = (mx // a[i]) * a[i]
    mn = (mn // a[i]) * a[i]
# print(mn, mx)

if mn == 2 and mx == 2:
    print(*ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
k = int(input())
A = list(map(int,input().split()))

ans = [2,2]
for a in A[::-1]:

  if a > ans[1]:
    print(-1)
    exit()
  ans[1] = (ans[1]//a) *a+ (a-1)
  if ans[0] <= a:
    ans[0] = a
  else:
    if ans[0]%a != 0:
      ans[0] = (ans[0]//a+1)*a
  if ans[0] >ans[1]:
    print(-1)
    exit()
print(*ans)

Submission status: Accepted

Solution code:
import math
K = int(input())
A = list(map(int,input().split()))
lo = 2
hi = 2
for e in A[::-1]:
    if hi//e == lo//e and (hi%e)*(lo%e) != 0:
        print(-1)
        exit(0)
    else:
        lo = e*math.ceil(lo/e)
        hi = e*((hi//e)+1)-1
print(lo,hi)

Submission status: Accepted

Solution code:
k = int(input())
a = [int(i) for i in input().split()]
l = r = 2
for i in reversed(a):
    if (l - 1) // i == r // i:
        print(-1)
        break
    l, r = (l + i - 1) // i * i, r // i * i + i - 1
else:
    print(l, r)

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    K = int(input())
    A = [int(a) for a in input().split()]
    if A[K-1] != 2: print(-1)
    else:
        minN, maxN = 2, 3
        for i in reversed(range(K - 1)):
            lb = (minN - 1) // A[i]
            hb = maxN // A[i]
            if lb == hb: 
                print(-1)
                break
            else:
                minN = A[i] * (lb + 1)
                maxN = A[i] * hb + A[i] - 1
        else: print(minN, maxN)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    K = int(input())
    A = [int(a) for a in input().split()]
    if A[K-1] != 2: print(-1)
    else:
        minN, maxN = 2, 3
        for i in reversed(range(K - 1)):
            if maxN < A[i]: 
                print(-1)
                break
            else:
                lb = (minN - 1) // A[i]
                hb = maxN // A[i]
                if lb == hb: 
                    print(-1)
                    break
                else:
                    minN = A[i] * (lb + 1)
                    maxN = A[i] * hb + A[i] - 1
        else: print(minN, maxN)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def examA():
    N = I()
    A = LI()
    if A[-1]!=2:
        print(-1)
        return
    l = 2; r = 2
    for a in A[::-1]:
        ner = (r//a+1)*a-1
        nel = ((l-1)//a+1)*a
        r = ner; l = nel
        if r<l:
            print(-1)
            return
    print(l,r)
    return

def examB():
    N, M = LI()

    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examA()

"""

"""

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int, input().split()))
def ceiling(x, mod):
  if x % mod == 0:
    return x // mod
  else:
    return x // mod + 1

m, M = 2, 2
p = 0
for i in range(K-1, -1, -1):
  m, M = A[i] * ceiling(m, A[i]), A[i] * (M // A[i]) + A[i] - 1
chk1, chk2 = m, M
for i in range(K):
  chk1, chk2 = A[i] * (chk1 // A[i]), A[i] * (chk2 // A[i])
if chk1 == 2 and chk2 == 2:
  print(m, M)
else:
  print(-1)

Submission status: Accepted

Solution code:
def calc_n_range(a):
    min_n = max_n = 2

    for curr_a in reversed(a):
        min_n = ((min_n + curr_a - 1) // curr_a) * curr_a
        if min_n > max_n:
            return None
        max_n = max_n - max_n % curr_a + curr_a - 1

    return min_n, max_n


def main():
    input()
    a = list(map(int, input().split()))

    n_range = calc_n_range(a)
    if n_range:
        print(*n_range)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K = int(input())
A = [int(i) for i in input().split()]
A.reverse()

# L: 最小の生存人数
# H: 最大の生存人数
L, H = 2, 2
for i in range(K):
    # [L,H]で最小のA[i]の倍数
    MIN = (L + A[i] - 1) // A[i] * A[i]
    # [L,H]で最大のA[i]の倍数
    MAX = H // A[i] * A[i]

    if L <= MIN <= H:
        L = MIN
        H = MAX + A[i] - 1
    else:
        print(-1)
        exit()

print(L,H)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int,input().split()))
A.reverse()

M = m = 2
for i,ai in enumerate(A):
  # print(m , (m-1+ai)//ai*ai , M//ai*ai + ai-1 , M)
  if not (m <= (m-1+ai)//ai*ai<= M):
    print(-1);exit()
  M = M//ai*ai + ai-1
  m = (m-1+ai)//ai*ai
  # print(m,M,i)
print(m,M)

# # 最大ケースを求める
# M = 2
# for i,ai in enumerate(A):
#   if M < ai:
#     print(-1);exit()
#   M = M//ai*ai + ai-1
#   print(M,i)
# print(M)

# # 最小ケースを求める
# m = 2
# for i,ai in enumerate(A):
#   m = (m-1+ai)//ai*ai

# print(m,M)

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int,input().split()))

if A[-1] != 2:
    print(-1)
    exit()

A.reverse()
mn = mx = 2
for a,b in zip(A,A[1:]):
    mn += (b - mn%b)%b
    mx += a-1
    mx -= mx%b
    if mn > mx:
        print(-1)
        exit()

mx += A[-1]-1
print(mn,mx)