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:
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:
K=int(input())
A=list(map(int,input().split()))

def func(num):
    for item in A:
        num=num//item*item
    return num

ok=10**20
ng=0

while ok-ng>1:
    mid=(ok+ng)//2
    if func(mid)>=2:
        ok=mid
    else:
        ng=mid

low=ok

ok=10**20
ng=0

while ok-ng>1:
    mid=(ok+ng)//2
    if func(mid)>=4:
        ok=mid
    else:
        ng=mid

high=ng

if func(low)==2 and func(high)==2:
    print(low,high)
else:
    print(-1)

Submission status: Accepted

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

max_ans = 2
for i in range(k)[::-1]:
    max_ans = (max_ans // a[i]) * a[i] + (a[i] - 1)
    
min_ans = 2
for i in range(k)[::-1]:
    min_ans = -((-min_ans) // a[i]) * a[i]

tmp = max_ans
for i in range(k):
    tmp = (tmp // a[i]) * a[i]
if tmp != 2:
    print(-1)
    exit()
    
tmp = min_ans
for i in range(k):
    tmp = (tmp // a[i]) * a[i]
if tmp != 2:
    print(-1)
    exit()

print(min_ans, max_ans)

Submission status: Accepted

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

def func(num):
    for item in A:
        num=num//item*item
    return num

ans=[]
ok=10**20
ng=0

while ok-ng>1:
    mid=(ok+ng)//2
    if func(mid)>=2:
        ok=mid
    else:
        ng=mid

ans=ok

ok=10**20
ng=0

while ok-ng>1:
    mid=(ok+ng)//2
    if func(mid)>=4:
        ok=mid
    else:
        ng=mid

if func(ans)==2 and func(ng)==2:
    print(ans,ng)
else:
    print(-1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
K=int(input())
A=list(map(int,input().split()))

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

low=2
high=3
for item in A[::-1]:
    #print(low,high)
    if high<item:
        print(-1)
        exit()
    elif item<low:
        low=(-((-low)//item))*item
        if low>high:
            print(-1)
            exit()
        high=max(low+item-1,high+item-1-high%item)
    else:
        low=item
        if low>high:
            print(-1)
            exit()
        high=low+item-1
print(low,high)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def main():
    K = int(input())
    A = read_list()[::-1]
    if A[0] != 2:
        print(-1)
        return

    minN = 2
    maxN = 2
    for a in A:
        minN = ((minN - 1) // a + 1) * a
        maxN = (maxN // a + 1) * a - 1
    if minN > maxN:
        print(-1)
    else:
        print(minN, maxN)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k = int(input())
l = list(map(int,input().split()))
for i in range(k-1,-1,-1):
    if i == k-1:
        if l[i] == 2:
            ans = [2,3]
        else:
            ans = [-1]
            break
    else:
        if l[i] > ans[1]:
            ans = [-1]
            break
        else:
            if l[i] >= ans[0]:
                ans[0] = l[i]
            else:
                b0 = ans[0]
                c = l[i]
                if b0%c == 0:
                    ans[0] = b0
                else:
                    if (b0//c+1)*c > ans[1]:
                        ans = [-1]
                        break
                    else:
                        ans[0] = (b0//c+1)*c
            b1 = ans[1]
            c = l[i]
            if b1%l[i] == 0:
                ans[1] = b1+l[i]-1
            else:
                ans[1] = (b1//c)*c+c-1
    
    #print(ans)
for i in ans:
    print(i,end=" ")

Submission status: Accepted

Solution code:

import sys
input = sys.stdin.readline

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

lb, ub = 1, 10**18
while ub - lb > 1:
    m = (lb + ub) // 2
    rem = m
    for a in A:
        rem = rem // a * a
    if rem < 2:
        lb = m
    else:
        ub = m

lb2, ub2 = 1, 10**18
while ub2 - lb2 > 1:
    m = (lb2 + ub2) // 2
    rem = m
    for a in A:
        rem = rem // a * a
    if rem <= 2:
        lb2 = m
    else:
        ub2 = m

if ub > lb2:
    print(-1)
else:
    print(ub, lb2)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline

K, *A = map(int, read().split())
maximum = 2
minimum = 2
for i in A[::-1]:
    if maximum // i - (minimum - 1) // i >= 1:
        maximum = maximum // i * i + i - 1
        minimum = (minimum + i - 1) // i * i
    else:
        print(-1)
        exit()

print(minimum, maximum)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline

K, *A = map(int, read().split())
maximum = 2
minimum = 2
for i in A[::-1]:
    if i > maximum:
        print(-1)
        exit()
    if i >= minimum:
        new_minimum = i
    else:
        new_minimum = (minimum + i - 1) // i * i
    new_maximum = maximum // i * i + i - 1
    if minimum <= new_minimum <= new_maximum and maximum <= new_maximum:
        minimum, maximum = new_minimum, new_maximum
    else:
        print(-1)
        exit()

print(minimum, maximum)

Submission status: Accepted

Solution code:
def div_ceil(x, y): return (x + y - 1) // y

N = int(input())
*A, = map(int, input().split())
cand_min, cand_max = 2, 2
for a in reversed(A):
    if div_ceil(cand_min, a) * a > cand_max: print(-1); break
    cand_min = div_ceil(cand_min, a) * a
    cand_max = (cand_max // a) * a + a - 1
else:
    print(cand_min, cand_max)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
l.reverse()
m=[2,3]
if l[0]!=2:
    print(-1)
    exit()
for i in range(1,n):
    p=l[i]
    s=-(-m[0]//p)*p
    e=(m[1]//p)*p+p-1
    if not m[0]<=s<=m[1]:
        print(-1)
        exit()
    m=[s,e]
print(*m)

Submission status: Accepted

Solution code:
#解説参照
k = int(input())
a = list(map(int, input().split( )))
l = 2
r = 2
for i in range(k-1,-1,-1):
    if (r//a[i])*a[i]<l:
        print(-1)
        exit()
    r2 = (r//a[i])*a[i]+a[i]-1
    l2 = ((l+a[i]-1)//a[i])*a[i]
    r = r2
    l = l2
print(l,r)

Submission status: Accepted

Solution code:
K,*A=map(int, open(0).read().split())
m=2
M=2
for a in A[::-1]:
    if (m+a-1)//a*a>M//a*a:
        print(-1)
        break
    m=(m+a-1)//a*a
    M=M//a*a+a-1
else:
    print(m,M)

Submission status: Accepted

Solution code:
#Ice link game
import math
k=int(input())
lists=list(map(int,input().split()))
lists=lists[::-1]
maxi=2
mini=2
flag=True
for i in range(k):
    #maxiとminiについて更新をしてゆく
    a=lists[i]
    upper_bound=math.floor(maxi/a)
    lower_bound=math.ceil(mini/a)
    new_maxi=(upper_bound+1)*a-1
    new_mini=lower_bound*a
    if new_maxi<new_mini:
        flag=False
        break
    else:
        maxi=new_maxi
        mini=new_mini
if flag:
    print(mini,maxi)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20
MOD = 10**9 + 7
# def combmod(n, k, mod=MOD):
#     if k == 0:
#         return 1
#     if k == 1:
#         return n
#     ret = 1
#     for i in range(n - k + 1, n + 1):
#         ret *= i
#         ret %= mod
#
#     for i in range(1, k + 1):
#         ret *= pow(i, mod - 2, mod)
#         ret %= mod
#
#     return ret
#
#
# class Segtree_op():
#     def __init__(self, n):
#         self.size = 1
#         while (n >= 1):
#             self.size = self.size << 1
#             n = n // 2
#
#         self.arr = [self.unit() for i in range(self.size * 2)]
#
#     def op(self, lch, rch):
#         # update min with holding index
#         return lch + rch
#
#     def unit(self):
#         return 0
#
#     def update(self, k, val):
#         k += self.size - 1
#         self.arr[k] = val
#         while (k):
#             k = (k - 1) // 2
#             self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])
#
#     def query(self, l, r):
#         L = l + self.size
#         R = r + self.size
#         s = self.unit()
#         while L < R:
#             if R & 1:
#                 R -= 1
#                 s = self.op(s, self.arr[R - 1])
#
#             if L & 1:
#                 s = self.op(s, self.arr[L - 1])
#                 L += 1
#             L >>= 1
#             R >>= 1
#         return s
#
# def update_daikou(st, k):
#     st.update(k, (st.query(0,k+1)) % MOD)
    # print(st.arr)
 
def main():
    k = getList()
    nums = getList()
    mn, mx = 2,2
    for num in nums[::-1]:
        mn = num * math.ceil(mn / num)
        mx = num * (mx// num) + num - 1
        tm = (mx // num) * num
        if tm < mn or tm > mx:
          print(-1)
          return
 
    print(mn, mx)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K, *A = map(int, open(0).read().split())
if A[-1]!=2:
  print(-1)
  import sys
  sys.exit()
S = 2
M = 2
for i in range(K-1,0,-1):
  c = A[i]
  p = A[i-1]
  ms = S
  mm = M+c-1
  ns = ms//p+1 if ms%p!=0 else ms//p
  nm = mm//p
  if ns*p>mm or nm*p<ms:
    print(-1)
    break
  M = nm*p
  S = ns*p
else:
  print(S,M+A[0]-1)

Submission status: Accepted

Solution code:
k = int(input())
A = list(map(int, input().split()))
m = M = 2
for a in A[::-1]:
  m += (-m)%a
  M += -(M%a) + a - 1
  if m > M:
    print(-1)
    break
else:
  print(m, M)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

k = inn()
a = inl()
l = r = 2
for i in range(k-1,-1,-1):
    nl = ((l+a[i]-1)//a[i])*a[i]
    nr = (r//a[i])*a[i] + a[i]-1
    #ddprint("l {} r {} nl {} nr {}".format(l,r,nl,nr))
    if r<nl or nr<l:
        print(-1)
        exit()
    l = nl
    r = nr
print("{} {}".format(l,r))

Submission status: Accepted

Solution code:
K = int(input())
A = [int(a) for a in input().split()]
    
if A[K-1] == 2:
    l = 2
    r = 2
    flag = True
    for i in range(K-2, -1, -1):
        r += A[i+1]-1
        if l%A[i] > 0:
            l += A[i]-(l%A[i])
        r -= r%A[i]
        if r < l:
            flag = False
            break
    if flag:
        r += A[0]-1
        ans = str(l) + " " + str(r)
    else:
        ans = -1
else:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
def main():
    K=int(input())
    A=list(map(int,input().split()))
    A.reverse()
    minres = 2
    maxres = 2
    for a in A:
        minres = ((minres+a-1)//a)*a
        if minres>maxres:return -1
        maxres = (maxres//a)*a+a-1
    return str(minres)+" "+str(maxres)

print(main())

Submission status: Accepted

Solution code:




K = int(input())

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


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

big = 2
small = 2
for i in reversed(range(K)):
    """
    smallのときにai人組つくると脱落者なし
    bigのときにai人組作るとai-1人脱落

    """


    # smallは元のsmall以上かつ、脱落者なし
    """
    ・smallはaiで割り切れる（脱落者なし）
    ・元のsmall以上の値
    """

    if small // A[i] > 0 and small % A[i] > 0:
        small = (small // A[i] + 1) * A[i]
    elif small // A[i] > 0 and small % A[i] == 0:
        pass
        #small = small
    elif small // A[i] == 0:
        small = A[i] 
        
    # bigは元のbig以上かつ、脱落者がai-1
    big = (big // A[i]) * A[i] + A[i] - 1

    if big < small:
        print(-1)
        exit()


print(small, big)

Submission status: Accepted

Solution code:




K = int(input())

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

# ここの上でK=1の場合を書いてしまったので無限にWAだした
if A[-1] != 2:
    print(-1)
    exit()

big = 2
small = 2
for i in reversed(range(K)):
    """
    smallのときにai人組つくると脱落者なし
    bigのときにai人組作るとai-1人脱落

    """


    # smallは元のsmall以上かつ、脱落者なし
    """
    ・smallはaiで割り切れる（脱落者なし）
    ・元のsmall以上の値
    """

    if small // A[i] > 0 and small % A[i] > 0:
        small = (small // A[i] + 1) * A[i]
    elif small // A[i] > 0 and small % A[i] == 0:
        small = small
    elif small // A[i] == 0:
        small = A[i] 
        
    # bigは元のbig以上かつ、脱落者がai-1
    big = (big // A[i]) * A[i] + A[i] - 1

    if big < small:
        print(-1)
        exit()


print(small, big)

Submission status: Accepted

Solution code:




K = int(input())

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


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

big = 2
small = 2
for i in reversed(range(K)):
    """
    smallのときにai人組つくると脱落者なし
    bigのときにai人組作るとai-1人脱落

    """


    # smallは元のsmall以上かつ、脱落者なし
    if small // A[i] > 0 and small % A[i] > 0:
        small = (small // A[i] + 1) * A[i]
    elif small // A[i] > 0 and small % A[i] == 0:
        small = small
    elif small // A[i] == 0:
        small = A[i] 
        
    # bigは元のbig以上かつ、脱落者がai-1
    big = (big // A[i]) * A[i] + A[i] - 1

    if big < small:
        print(-1)
        exit()


print(small, big)

Submission status: Accepted

Solution code:




K = int(input())

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


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

big = 2
small = 2
for i in reversed(range(K)):
    """
    smallのときにai人組つくると脱落者なし
    bigのときにai人組作るとai-1人脱落

    """


    # smallは元のsmall以上かつ、脱落者なし
    small = ((small - 1) // A[i] + 1) * A[i]
        
    # bigは元のbig以上かつ、脱落者がai-1
    big = (big // A[i]) * A[i] + A[i] - 1

    if big < small:
        print(-1)
        exit()


print(small, big)

Submission status: Accepted

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

def f(x):
    for i in range(K):
        x = x-x % A[i]
    return x

def bisect_search(f,val=0,l=0,r=10**6):

    #is_increase=(f(r)-f(l))>=0

    eps=10**(-5)
    while True:

        c=(l+r)//2
        print(l,c,r)
        input()
        if f(c)==val and f(c-1)!=val:
            return c
        #if f(c)-val < eps:
        #    return c

        if f(c)>val:
            r=c

        else:
            l=c
        
        if l==r:
            return False

def bisect_search_int(f,val=0,l=0,r=10**6,equal=False):
    #is_increase=(f(r)-f(l))>=0
    
    eps=10**(-5)
    if not equal:
        siki = "f(c) > val"
    else:
        siki = "f(c) >= val"

    while r-l>1:

        c=(l+r)//2
        
        if eval(siki,{"c":c,"f":f,"val":val}):
            r=c            
        else:
            l=c
        
        #if l==r:
        #    return False
    if f(l)!= f(c) and f(r)!=f(c):
        return False
    return l,r



K=int(input())
A=acinput()

R = 2+K*max(A)
#R=10**6

l,r=bisect_search_int(f, 2,0,R,equal=True)
if f(l)==2:
    resL=l
elif f(r)==2:
    resL=r
else:
    resL=-1

l, r = bisect_search_int(f, 2,0,R,equal=False)
#print(l,r,f(l),f(r))
if f(l) == 2:
    resR = l
elif f(r) == 2:
    resR = r
else:
    resR = -1

if resL>=0:
    print(resL,resR)
else:
    print(-1)


#for x in range(0,20):
#    print(x,f(x))

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import copy
K=int(input())
A=list(map(int,input().split()))
if A[-1]!=2:
    print(-1)
    exit()

maX=2
miN=2

for i in range(K-1,-1,-1):

    if A[i]//maX>=2:
        print(-1)
        exit()
    if A[i]//miN>=2:
        miN=A[i]
    else:
        if miN%A[i]==0:
            pass
        else:
            miN=(miN//A[i] +1) *A[i]
    maX=maX-maX%A[i] + A[i]-1

mmaX=maX
for i in range(K):
    mmaX-=mmaX%A[i]
if mmaX==2:
    print(miN,maX)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def f(n):
    sumation = 0
    while n > 0:
        sumation += n%10
        n //= 10
    return sumation

def main():
    k = inp()
    a = inpl()
    a.reverse()
    x,y = 2,2
    for i in range(k):
        pair = a[i]
        if y < pair:
            print(-1)
            return
        if (y//pair)*pair < x:
            print(-1)
            return
        if pair >= x:
            x = pair
        elif x%pair != 0:
            s = x//pair + 1
            x = s*pair
        y = (y//pair+1) * pair - 1
        if y < x:
            print(-1)
            return
    print(x,y)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

K = ir()
A = lr()[::-1]
left = 2
right = 2
for x in A:
    left += (-left) % x
    right -= right % x
    right += x - 1

if left > right:
    print(-1)
else:
    print(left, right)
# 05

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

K = ir()
A = lr()[::-1]
domain = [2, 2] #現在の最小と最大
for i in range(K):
    x = A[i]
    left = domain[0]; right = domain[1]
    if x > right * 2 - 1:
        print(-1)
        exit()
    left += (-left) % x
    right -= right % x
    right += x - 1
    if left > right:
        print(-1)
        exit()
    domain = [left, right]

print(*domain)
# 05

Submission status: Accepted

Solution code:
import sys
k=int(input())
a=list(map(int,input().split()))
min=2;max=2
min=((min+a[k-1]-1)//a[k-1])*a[k-1]
max=(max//a[k-1])*a[k-1]
if min>max:
  print(-1)
  sys.exit()
for i in range(k-1,0,-1):
  max=max+a[i]-1
  min=((min+a[i-1]-1)//a[i-1])*a[i-1]
  max=(max//a[i-1])*a[i-1]
  if min>max:
    print(-1)
    sys.exit()
max+=a[0]-1
print(min,max)

Submission status: Accepted

Solution code:
k = int(input())
l = reversed(list(map(int, input().split())))
lo,hi = 2,2
for a in l:
  nl = lo + (a - lo%a)%a
  nh = (hi//a)*a + a-1
  if nl > nh: print(-1); exit(0)
  lo,hi = nl,nh
print(lo,hi)

Submission status: Accepted

Solution code:
k = int(input())
A = list(map(int, input().split()))
UP = 2
DOWN = 2 
for a in A[::-1]:
  DOWN = ((DOWN - 1) // a + 1) * a
  UP = UP // a * a + a  - 1
  if UP < DOWN:
    print(-1)
    exit()
print(DOWN, UP)

Submission status: Accepted

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

mina = maxa = 2

for a in A[::-1]:
  mina = -(-mina // a) * a
  maxa = maxa // a * a + a - 1
  if mina > maxa:
    print(-1)
    break
else:
  print(mina, maxa)

Submission status: Accepted

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

lower = 2
upper = 2
flag = True
for i in range(k):
    lowm = lower//arr[i]
    upm = upper//arr[i]

    if upm == 0:
        flag = False
    if arr[i] * lowm < lower:
        lowm += 1
        if lowm > upm:
            flag = False
    lower = arr[i] * lowm
    upper = arr[i] * upm + arr[i]-1
    # print(lowm,upm)
    # print(lower,upper)
    # print("##########")



if flag:
    print(lower,upper)
else:
    print(-1)

Submission status: Accepted

Solution code:
from sys import stdout
import sys,resource
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

k = inn()
a = inl()
if k==1:
    if a[0]==2:
        print("2 3")
    else:
        print(-1)
    exit()
l = r = 2
for i in range(k-1,-1,-1):
    mn = ((l+a[i]-1)//a[i])*a[i]
    mx = (r//a[i])*a[i]+a[i]-1
    if mn>mx:
        print(-1)
        exit()
    l = mn
    r = mx
print("{} {}".format(l,r))

Submission status: Accepted

Solution code:
k = int(input())
a = list(map(int,input().split()))
a = a[::-1]
ansmin = 2
ansmax = 2
for x in a:
  ansmin = x*((ansmin+x-1)//x)
  ansmax = x*(ansmax//x)+x-1
  if ansmin>ansmax:
    print(-1)
    exit()
print(ansmin,ansmax)

Submission status: Accepted

Solution code:
k = int(input())
a = list(map(int,input().split()))
a = a[::-1]
ansmin = 2
ansmax = 2
for i in range(k):
  x = a[i]
  ansmin = x*((ansmin+x-1)//x)
  ansmax = x*(ansmax//x)+x-1
  if ansmin>ansmax:
    print(-1)
    exit()
print(ansmin,ansmax)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N = INT()
A = LIST()

def check1(m):
    sm = m
    for a in A:
        sm = (sm // a) * a
    return sm >= 2

def check2(m):
    sm = m
    for a in A:
        sm = (sm // a) * a
    return sm > 2

l = bisearch_min(0, 10**18, check1)
r = bisearch_min(0, 10**18, check2) - 1

# 2人にできない時はNG
if l > r:
    print(-1)
else:
    print(l, r)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

N = INT()
A = LIST()

def check1(m):
    sm = m
    for a in A:
        sm = (sm // a) * a
    return sm >= 2

def check2(m):
    sm = m
    for a in A:
        sm = (sm // a) * a
    return sm > 2

l = bisearch_min(0, 10**18, check1)
r = bisearch_min(0, 10**18, check2) - 1

if l > r:
    print(-1)
else:
    print(l, r)

Submission status: Accepted

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

B = [(0, 0)] * (N + 1)
B[N] = (2, 2)

for i in range(N - 1, -1, -1):
  min_next, max_next = B[i + 1]
  
  min_left = -1
  min_right = 10 ** 15
  
  while min_left + 1 < min_right:
    min_mid = (min_left + min_right) // 2
    mid_next = min_mid // A[i] * A[i]
    if mid_next >= min_next:
      min_right = min_mid
    else:
      min_left = min_mid
  
  max_left = 0
  max_right = 10 ** 15
  
  while max_left + 1 < max_right:
    max_mid = (max_left + max_right) // 2
    mid_next = max_mid // A[i] * A[i]
    if mid_next >= max_next + 1:
      max_right = max_mid
    else:
      max_left = max_mid
  
  if  min_right == 0 or max_left == 0 or max_left < min_right:
    print(-1)
    exit()
  else:
    B[i] = (min_right, max_left)

print(*B[0])

Submission status: Accepted

Solution code:
K = int(input())
A = [int(a) for a in input().split()]
ma = mi = 2
while A:
    a = A.pop()
    mi = (mi+a-1) // a * a
    ma = (ma) // a * a + (a-1)
    if mi > ma:
        print(-1)
        exit()

print(mi, ma)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline

def main():
    K = int(input())
    A = list(map(int,input().split()))
    
    L = [1]
    for i in range(K):
        if L[-1] != A[-i-1]:
            L.append(A[-i-1])
    
    L.pop(0)
    L_long = len(L)
    ans = [2,2]
    for i in range(L_long):
        s,t = ans[0],ans[1]
        ans[0] = -(-s//L[i])*L[i]
        ans[1] = (t//L[i] + 1)*L[i] - 1
        if ans[1] < ans[0]:
            print(-1)
            exit()
    
    print(ans[0],ans[1])
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int,input().split()))
B = [2,2]
for i in range(K-1,-1,-1):
    a = A[i]
    bmin = B[0]
    bmax = B[1]
    if bmin%a==0:
        bmin = bmin
    else:
        bmin = (bmin//a+1)*a
    if bmin>bmax:
        B = []
        break
    else:
        if bmax%a==0:
            bmax = bmax+a-1
        else:
            bmax = (bmax//a)*a+a-1
        B = [bmin,bmax]
if len(B)==0:
    print(-1)
else:
    print(B[0],B[1])

Submission status: Accepted

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

def g(n):
    for a in A:
        n=n-n%a
    return n

a_max=max(A)
l=1
r=2+K*a_max
while r-l>1:
    m=(l+r)//2
    if g(m)>=2:
        r=m
    else:
        l=m
l0=r

l=1
r=2+K*a_max
while r-l>1:
    m=(l+r)//2
    if g(m)<=2:
        l=m
    else:
        r=m
r0=l

if l0>r0:
    print(-1)
else:
    print(l0,r0)

Submission status: Accepted

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

n_min=2
n_max=2
for i in range(K-1,-1,-1):
    if (n_max//A[i])*A[i] < n_min or (n_min//A[i]+(1 if n_min%A[i]!=0 else 0))*A[i] > n_max:
        print(-1)
        exit()
    n_min=(n_min//A[i]+(1 if n_min%A[i]!=0 else 0))*A[i]
    n_max=(n_max//A[i])*A[i]+A[i]-1

print(n_min,n_max)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    k=int(input())
    A=list(map(int,input().split()))

    l=r=2
    for a in A[::-1]:
        l=a*((l-1)//a+1)
        r=a*(r//a)+(a-1)
        if(l>r):
            print(-1)
            return

    print(l,r)
resolve()