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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

# 下がtrue, falseになる最小値を返す
def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n = I()
    a = LI()

    def f(i):
        for c in a:
            i -= i%c
        return i < 2

    def g(i):
        for c in a:
            i -= i%c
        return i <= 2

    mi = bs(f,0,sum(a)+3)
    ma = bs(g,0,sum(a)+3) - 1
    if mi <= ma:
        return '{} {}'.format(mi,ma)
    return -1




print(main())

Submission status: Accepted

Solution code:
from math import ceil
K = int(input())
A = list(map(int, input().split()))
L, R = 2, 2

for n in A[::-1]:
    L = ceil(L / n) * n
    R = (R // n) * n + n - 1
    if L > R:
        print(-1)
        exit()

print(L, R)

Submission status: Accepted

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

#
if A[-1]!=2:
    print(-1)
    exit()
if K>1 and A[-2]!=2 and A[-2]!=3:
    print(-1)
    exit()

#
min_n = 2
max_n = 3
for i in A[::-1][1:]:
    a = (min_n - 1)//i
    b = max_n//i
    if a==b:
        print(-1)
        exit()

    if min_n%i==0:
        pass
    else:
        min_n = min_n + (i - min_n%i)
    max_n = max_n - max_n%i + i - 1
    #print(min_n, max_n)

#
print(min_n, max_n)

Submission status: Accepted

Solution code:
K=int(input())
s=input().split(' ')
a=[int(s[i]) for i in range(len(s))]
n=len(s)

def solve():
	x,y=2,2
	for i in range(n-1,-1,-1):
		u=(x+a[i]-1)//a[i]
		v=y//a[i]
		if (a[i]*v<x): return -1,-1
		x=a[i]*u
		y=a[i]*(v+1)-1
	return x,y

x,y=solve()
if (x==-1): print(-1)
else: print('%d %d'%(x,y))

Submission status: Accepted

Solution code:
import pdb
#pdb.set_trace()
K=int(input())
s=input().split(' ')
a=[int(s[i]) for i in range(len(s))]
n=len(s)

def solve():
	x,y=2,2
	for i in range(n-1,-1,-1):
		u=(x+a[i]-1)//a[i]
		v=y//a[i]
		if (a[i]*v<x): return -1,-1
		x=a[i]*u
		y=a[i]*(v+1)-1
	return x,y

x,y=solve()
if (x==-1): print(-1)
else: print('%d %d'%(x,y))

Submission status: Accepted

Solution code:
import sys
import math
readline = sys.stdin.readline

K = int(readline())
A = reversed(list(map(int, readline().split())))

a_min = 2
a_max = 2
for a in A:
    a_min = math.ceil(a_min / a) * a
    a_max = a * (a_max // a) + a - 1
    if a_min > a_max:
        print(-1)
        exit()
print('{} {}'.format(str(a_min), str(a_max)))

Submission status: Accepted

Solution code:
import sys
k = int(raw_input())
a = map(int,raw_input().split())
l = 2; r = 2;
for i in range(k-1,-1,-1) :
    tl = (l-1)/a[i] + 1; tr = r/a[i];
    if tl > tr :
        print "-1"; sys.exit(0);
    l = tl * a[i]; r = tr * a[i] + a[i]-1;
print l,r

Submission status: Accepted

Solution code:
k = int(input())
ai = reversed([int(x) for x in input().split()])
b = 2; t = 2
f = False
for a in ai:
    b = (((b-1)//a)+1)*a
    t = ((t//a)+1)*a-1
    if b > t:
        f = True
        break
if f:
    print(-1)
else:
    print(b,t)

Submission status: Accepted

Solution code:
import sys

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


x, y = 2, 2

for i in range(k-1, -1, -1):
    minx = x + (a[i] - x % a[i]) % a[i]
    maxx = y - y % a[i]
    if minx > maxx:
        print(-1)
        sys.exit(0)
    else:
        x, y = minx, maxx + a[i] - 1


print(x, y)

Submission status: Accepted

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

s, t = 2, 2
for i in P:
    p = max((s + i - 1) // i, 1)
    q = t // i
    if q < p:
        print(-1)
        quit(0)
    s, t = p * i, q * i + i - 1

print(s, t)

Submission status: Accepted

Solution code:
from math import ceil, floor
k, a, l, r = input(), map(float, raw_input().split()), 2., 2.
for v in a[::-1]:
    l = ceil(l / v) * v
    r = floor(r / v) * v + v - 1
print '%d %d' % (l, r) if l < r else -1

Submission status: Accepted

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

min_A=2
max_A=3
cnt=True
if A[0]!=2:
  print(-1)
  cnt=False
for i in range(1,K):
  a=(min_A+A[i]-1)//A[i]*A[i]
  b=max_A//A[i]*A[i]
  if a>b and cnt:
    print(-1)
    cnt=False
    break
  else:
    min_A=a
    max_A=b+A[i]-1

if cnt:
  print(min_A,max_A)

Submission status: Accepted

Solution code:
import copy
import math


def main():
    n=int(input())
    temp=input().split(" ")
    nums=list(map(int,temp))
    nums.reverse()
    l=2 # min 
    r=2 # max
    for num in nums:
       # if num<=l and num>=r:
        r=(int(r/num)+1)*(num)-1
        l= math.ceil(l/num)*num
        
        if l>r:
             print("-1")
             return 0
    print(str(l)+" "+str(r))      
    



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import floor,ceil
K = int(input())
A = [int(x) for x in input().split()]
A.reverse()
jmax, jmin = 2,2

for i in range(0,K):
    if jmin % A[i] != 0:
        if (jmin + (A[i] - (jmin % A[i]))) > jmax:
            print(-1)
            exit()

    jmin = ceil(jmin / A[i]) * A[i]
    jmax = floor(jmax / A[i]) * A[i] + A[i] -1
    
print(jmin, jmax)


    #計算量はO(3K)すなわちO(K)

Submission status: Accepted

Solution code:
from math import floor,ceil
K = int(input())
A = [int(x) for x in input().split()]
A.reverse()
jmax, jmin = 2,2

for i in range(0,K):
    mmax,mmin = jmax,jmin
    if mmin % A[i] != 0:
        if (mmin + (A[i] - (mmin % A[i]))) > mmax:
            print(-1)
            exit()

    jmin = ceil(jmin / A[i]) * A[i]
    jmax = floor(jmax / A[i]) * A[i] + A[i] -1

print(jmin, jmax)

#計算量はO(3K)すなわちO(K)

Submission status: Accepted

Solution code:
from math import ceil, floor

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

L = 2
R = 2
for A in reversed(As):
    if R // A * A < L:
        print('-1')
        exit()
    L = ceil(L / A) * A
    R = floor(R / A) * A + A - 1

print(L, R)

Submission status: Accepted

Solution code:
mn = 2
mx = 2
n = int(input())
k = [int(i) for i in input().split()]
k.reverse()
for i in range(n):
  t1 = (mn + k[i] - 1) // k[i] * k[i]
  t2 = (mx) // k[i] * k[i]
  if t1 > mx:
    print(-1)
    exit()
  mn = t1
  mx = t2 + k[i] - 1
print(mn, mx)

Submission status: Accepted

Solution code:
from math import floor, ceil
k = int(input())
a = [int(i) for i in input().split()]
l,r = 2,2
for ai in a[::-1]:
    xi = ceil(l/ai)
    yi = floor(r/ai)
    if xi > yi:
        print(-1)
        exit()
    l = xi * ai
    r = yi * ai + ai - 1
print(l, r)

Submission status: Accepted

Solution code:
import math
K = int(input())
A = list(map(int,input().split()))
a = 1
L,S = 2,2 

while a <= K:
    if math.ceil(S/A[-a])*A[-a] < S or L < math.ceil(S/A[-a])*A[-a]:
        print('-1')
        exit()
    S = math.ceil(S/A[-a])*A[-a]
    L = math.floor(L/A[-a])*A[-a] + A[-a] -1
    a += 1
print(S,L)

Submission status: Accepted

Solution code:
import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [k] = [int(input_raw[0])]
    input_raw = read_func().strip().split()
    num_list = []
    for i in range(k):
        num_list.append(long(input_raw[i]))

    max_num = long(2)
    min_num = long(2)
    is_exist = True
    if num_list[k-1] != 2:
        is_exist = False
    for i in range(k-1, -1, -1):
        if is_exist == False:
            break;
        min_min_num = min_num;
        #min_max_num = min_num + num_list[i] - 1
        #max_min_num = max_num;
        max_max_num = max_num + num_list[i] - 1
        if i > 0:
            min_min_num = num_list[i - 1] * (min_min_num / num_list[i - 1] + (0 if (min_min_num % num_list[i - 1] == 0)  else 1) )
            #min_max_num = num_list[i - 1] * long(min_max_num / num_list[i - 1] )
            #max_min_num = num_list[i - 1] * (max_min_num / num_list[i - 1] + (0 if (max_min_num % num_list[i - 1] == 0)  else 1) )
            max_max_num = num_list[i - 1] * long(max_max_num / num_list[i - 1] )

        min_num = min_min_num
        max_num = max_max_num

##        if(min_min_num > min_max_num and max_min_num > max_max_num):
##            is_exist = False
##            break;
##        elif(min_min_num > min_max_num and max_min_num <= max_max_num):
##            min_num = max_min_num
##            max_num = max_max_num
##        elif(min_min_num <= min_max_num and max_min_num > max_max_num):
##            min_num = min_min_num
##            max_num = min_max_num
##        else:
##            min_num = min(min_min_num, max_min_num)
##            max_num = max(min_max_num, max_max_num)
        if min_num > max_num:
            is_exist = False
            break;

    if is_exist == True:
        print min_num, max_num
    else:
        print -1


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    mi = 2
    mx = 2

    for i in range(k):
        j = k-i-1

        mx = mx + a[j] - 1

        if j == 0:
            pass
        else:
            na = a[j-1]
            
            if mx % na != 0 and mi % na != 0 and ((mx % na) - (mi % na)) == (mx - mi):
                print(-1)
                return

            if mi%na != 0:
                mi = mi + (na - mi%na)

            if mx%na != 0:
                mx = mx - (mx % na)

    print(mi, mx)
solve()

Submission status: Accepted

Solution code:
input()
L=R=2
for A in list(map(int,input().split()))[::-1]:
    L=(L-1)//A*A+A
    R=R//A*A+A-1
    if L>R:
        print(-1)
        exit()
print(L,R)

Submission status: Accepted

Solution code:
import numpy as np
import math

n = int(input())
a = list(map(int, input().split(" ")))

min = 2
max = 2

for i in reversed(a):
    min = math.ceil(min / i) * i
    max = math.floor(max / i) * i + i - 1
    if(min > max):
        print(-1)
        exit()

print("%d %d" %(min, max))

Submission status: Accepted

Solution code:
input()
L=R=2
for A in list(map(int,input().split()))[::-1]:
    L=((L-1)//A+1)*A
    R=(R//A+1)*A-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]
l, r = 2, 2
for i in range(k):
    l = ((l-1)//a[i] + 1) * a[i]
    r = (r//a[i] + 1) * a[i] - 1
    if l > r:
        print(-1)
        exit()
print(l, r)

Submission status: Accepted

Solution code:
k = int(raw_input())
a = map(int,raw_input().split(" "))

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

r = [2,3]
ainv = a[::-1]

for now in ainv[1:]:
  lower = (r[0]/now)*now
  if lower < r[0]:
    lower += now
  upper = (r[1]/now)*now

  q = [lower,upper]

  if q[0] > r[1]:
    print "-1"
    exit(0)
  #print r,q
  q[1] = q[1] + now - 1
  r = q

print "%d %d" % (r[0],r[1])

Submission status: Accepted

Solution code:
import math

K = int(input())

A = input().split()

for i in range(K):
    A[i] = int(A[i])

maxlst = [0 for i in range(K)]
minlst = [0 for i in range(K)]

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

maxlst[K-1] = 3
minlst[K-1] = 2

for i in reversed(range(K-1)):
    if maxlst[i+1] < A[i] or (maxlst[i+1] % A[i] != 0 and minlst[i+1] % A[i] != 0 and int(maxlst[i+1]/A[i]) == int(minlst[i+1]/A[i])):
        print(-1)
        quit()
    maxlst[i] = int(A[i] - 1 + A[i] * math.floor(maxlst[i+1] / A[i]))
    minlst[i] = int(math.ceil(minlst[i+1] / A[i]) * A[i])

print(minlst[0], maxlst[0])

Submission status: Accepted

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

minn = 2
maxn = 3
if A[-1] != 2:
	minn = -1

if minn != -1:
	for i in range(K-2,-1,-1):
		m = A[i]
		a = (minn + m - 1) // m * m
		b = maxn // m * m
		if b < a:
			minn = -1
			break
		minn = a
		maxn = b + m - 1

if minn == -1:
	print(minn)
else:
	print(minn,maxn)

Submission status: Accepted

Solution code:
K=int(input())
A=input().split(' ')
min=2
max=2
flag=0
while K>0:
  K=K-1
  i=int(A[K])
  if max<i:
    print('-1')
    flag=1
    break
  elif i<min:
    if min%i!=0:min=min+i-(min%i)
    else:min=min+(min%i)
    max=max+i-(max%i)-1
    if min>max:
      print('-1')
      flag=1
      break
  else:
    min=i
    max=max+i-(max%i)-1
if flag==0:
  print('{0} {1}'.format(min,max))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter
import numpy as np
import sys

def IMPOSSIBLE():
    print(-1)
    sys.exit()
    

k = int(input())
a = list(map(int,input().split()))[::-1]
min_num = 2
max_num = 3

if(a[0]!=2):IMPOSSIBLE()

for i in range(len(a)-1):
    if(a[i+1] > max_num):IMPOSSIBLE()
    else:
        min_num = a[i+1]*(min_num//a[i+1] if min_num%a[i+1]==0 else min_num//a[i+1]+1)
        max_num = a[i+1]*((max_num//a[i+1])+1)-1
        

tmpmin = min_num
tmpmax = max_num
for i in range(len(a)):
    tmpmin -= tmpmin%a[len(a)-i-1]
    tmpmax -= tmpmax%a[len(a)-i-1]
if(tmpmin != 2 or tmpmax != 2):IMPOSSIBLE()
    
print(str(min_num)+' '+str(max_num))

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(lambda x:int(x), input().split(" ")))
A.reverse()

n = [2,2]

for a in A:

    n1 = (n[0]//a+(1 if n[0]%a>0 else 0))*a
    n2 = (n[1]//a)*a
    # print([n,n1,n2,a])
    if n1>n2:
        print("-1")
        exit()
    n[0] = n1
    n[1] = n2+a-1

if len(n)>0:
    print(min(n),max(n))
else:
    print("-1")

Submission status: Accepted

Solution code:
from pprint import pprint as pp
import collections
import math
import itertools

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

old_a = A[-1]
x_max = 2 // A[-1]
x_min = 2 // A[-1]
for a in reversed(A):
  #pp((a, old_a, x_min, x_max))
  if a >= (old_a * (x_max +1)):
    x_max = -1
    break
  x_max = (old_a * (x_max+1)-1) // a
  x_min = math.ceil(old_a * x_min / a)
  if x_max < x_min:
    x_max = -1
    break
  old_a = a
#pp((old_a, x_min, x_max))
if x_max == -1:
  print(-1)
else:
  print(old_a * x_min, (old_a * (x_max+1))-1)

Submission status: Accepted

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

def solve():
    if A[K - 1] != 2:
        print(-1)
        return;
    M = 2
    m = 2
    for i in range(K - 1, 0, -1):
        nM = (M + A[i] - 1) - (M + A[i] - 1) % A[i - 1]
        if m % A[i - 1] == 0:
            nm = m
        else:
            nm = m + A[i - 1] - m % A[i - 1]
        #print("nM =", nM, "nm =", nm)
        if nM < m or nm >= M + A[i]:
            print(-1)
            return;
        #print("nM =", nM, "nm =", nm)
        M, m = nM, nm
    M = M + A[0] - 1
    # m = m
    print(m, M)
solve()

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int, input().split()))
A.reverse()
A.append(1)
ansmin = 2
ansmax = 2
for a in A:
  tmin = ((ansmin+a-1)//a)*a
  tmax = (ansmax//a)*a
  if tmin > tmax:
    print('-1')
    exit()
  ansmin = tmin
  ansmax = tmax + a - 1
print(ansmin, ansmax)

Submission status: Accepted

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

A=reversed(AT)
s = 2;b = 1;lis=[]
for i in A:
    ns = i
    if s > ns:
        ns +=(((s-ns)//i)*i)
        if s > ns:
            ns+=i
    s = ns
sn = s
for i in AT:
    sn = sn-sn%i

if sn!=2:
    print(-1)
    exit()
b = 1
AT.reverse()
for i in AT:
    b=b-b%i
    nb = i
    if b > nb:
        nb +=(((b-nb)//i)*i)
        if b > nb:
            nb+=i
    b= (nb+i-1)
print(s,b)

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    A = [int(a) for a in input().split()]

    if not A[K - 1] == 2:
        print(-1)
        return

    nmin, nmax = 2, 2
    ii = list(range(K))
    ii.reverse()
    for i in ii:
        Ai = A[i]
        if Ai > nmax:
            print(-1)
            return
        if Ai < nmin and Ai * 2 > nmax:
            print(-1)
            return
        if Ai < nmin:
            if nmin % Ai == 0:
                pass
            else:
                nmin = Ai * (nmin // Ai + 1)
        else:
            nmin = Ai

        if nmax > Ai:
            # if nmax % Ai == 0:
            #     pass
            # else:
            #     pass
            nmax = Ai * (nmax // Ai + 1) - 1
        else:
            nmax = Ai * 2 - 1
        # print(Ai, nmin, nmax)
        if nmin > nmax:
            print(-1)
            return
    print(nmin, nmax)


main()

Submission status: Accepted

Solution code:
# D
K = int(input())
A_list = list(map(int, input().split()))

res_min = [2]*(K+1)
res_max = [2]*(K+1)
possible = True
A_list.append(2)

for i in range(K-1, -1, -1):
    # minimum
    if res_min[i+1] % A_list[i] == 0:
        res_min[i] = res_min[i+1]
    else:
        res_min[i] = res_min[i+1] + A_list[i] - res_min[i+1] % A_list[i]
        
    # minimum over
    if (res_min[i] // A_list[i+1]) * A_list[i+1] > res_max[i+1]:
        possible = False
    
    # maximum
    if (res_max[i+1] + A_list[i+1]) % A_list[i] == 0:
        res_max[i] = res_max[i+1] + A_list[i+1] - A_list[i]
    else:
        res_max[i] = ((res_max[i+1] + A_list[i+1]) // A_list[i]) * A_list[i]
        
    # maximum over
    if (res_max[i] // A_list[i+1]) * A_list[i+1] < res_min[i+1]:
        possible = False

        
if A_list[K-1] != 2:
    possible = False
if possible:
    print(res_min[0], res_max[0]+A_list[0]-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from bisect import bisect, bisect_left, insort
from itertools import accumulate
def inpl(): return tuple(map(int, input().split()))

K = int(input())
A = inpl()
if A[-1] != 2:
    print(-1)
    exit()

l, r = 2, 3
for a in A[:-1][::-1]:
    l = (l//a)*a + int(l%a!=0)*a
    r = (r//a)*a + (a-1)
    if r < l:
        print(-1)
        break
else:
    print(l, r)

Submission status: Accepted

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

N = int(input())
As = list(map(int, input().split()))

if As[-1] != 2:
    print(-1)
    exit()
if N == 1:
    print(2, 3)
    exit()

p_min = As[-1]
p_max = As[-1] + 1

for i in range(N-2,-1,-1):
    p_min = As[i] * math.ceil(p_min/As[i])
    p_max = As[i] * math.floor(p_max/As[i])
    if p_min > p_max:
        print(-1)
        exit()

    p_max = p_max + As[i] - 1


print(p_min, p_max)

Submission status: Accepted

Solution code:
import sys

K = int(raw_input())
A = [int(val) for val in raw_input().split(" ")]

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

MIN, MAX = 2, 2
for k in range(1, K)[::-1]:
    if MIN%A[k-1]==0:
        pass
    else:
        MIN = (MIN/A[k-1]+1)*A[k-1]
    MAX_ = MAX + A[k] - 1
    if MAX_%A[k-1]==0:
        MAX = MAX_
    else:
        MAX = (MAX_/A[k-1])*A[k-1]
    if MIN > MAX:
        print "-1"
        sys.exit()
MAX = MAX + A[0] - 1

print "%d %d"%(MIN, MAX)

Submission status: Accepted

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

if A[-1] != 2:
    result = -1
else:
    result = 0
    cand_max = 2
    cand_min = 2
    for i in range(len(A))[::-1]:
        comp = int(cand_min / A[i]) * A[i]
        if cand_min <= comp <= cand_max:
            pass
        elif cand_min <= comp + A[i] <= cand_max:
            comp += A[i]
        else:
            result = -1
            break
        cand_max = int(cand_max / A[i] + 1) * A[i] - 1
        cand_min = comp

if result == -1:
    print(-1)
else:
    print(cand_min, cand_max)

Submission status: Accepted

Solution code:
k = int(input())
A = list(map(int, input().split()))
l, r = 2, 2
for a in reversed(A):
    l += (a - l%a) % a
    r -= r % a
    r += a - 1
    if l > r:
        print(-1)
        break
else:
    print("{} {}".format(l, r))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
K = int(input())
A = list(map(int, input().split()))

A.reverse()
mn, mx = 2, 2
for i in range(K):
    mn += (A[i] - mn % A[i]) % A[i]
    mx -= mx % A[i]
    mx += A[i] - 1
    if mn > mx:
        print(-1)
        break
else:
    print(mn, mx)

Submission status: Accepted

Solution code:
n=int(input())
a=list(reversed(list(map(int,input().split()))))
if a[0]>2:
	print("-1")
	exit()
a1,a2=2,2
for i in range(1,n):
	a1+=(a[i]-a1%a[i])%a[i]
	pre=a2
	a2+=a[i-1]-1
	a2-=a2%a[i]
	if a1>a2:
		print("-1")
		exit()	
print(a1,a2+a[n-1]-1)

Submission status: Accepted

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

mn = 2
mx = 3
for a in reversed(src[:-1]):
    mn2 = mn + ((a - mn%a) % a)
    mx2 = mx - (mx%a)
    if mn2 > mx2:
        print(-1)
        exit()
    mn = mn2
    mx = mx2 + a - 1
print(str(mn) + ' ' + str(mx))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
from heapq import heappush, heappop
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy4, dx4 = [0, -1, 0, 1], [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W
def ceil(a, b):return (a + b - 1) // b


def up(a, b):
    s = ceil(a, b)
    for i in range(s - 1, s + 3):
        if i * b > a:
            return i * b


def check(n, A):
    for a in A:
        n = (n // a) * a
    return n == 2


def solve(A):


    if A[-1] != 2:
        return [-1]

    min_a, max_a = 2, 3
    for a in A[::-1][1:]:
        if a > max_a:
            return [-1]
        else:
            max_a = up(max_a, a) - 1

        if a >= min_a:
            min_a = a
        else:
            min_a = ceil(min_a, a) * a

    if min_a > max_a:
        return [-1]
    return min_a, max_a

def solve2(A):
    min_a = INF
    max_a = 0
    for i in range(0, 100):
        if check(i, A):
            min_a = min(min_a, i)
            max_a = max(max_a, i)

    if min_a == INF or max_a == 0:
        return [-1]
    return min_a, max_a

def solve3(A):
    # [low, high)
    min_a = INF
    max_a = 0

    low, high = 0, int(1e14) - 1
    while high - low > 1:
        middle = (low + high) // 2
        if check(middle, A):
            min_a = middle
            low = middle
        else:
            high = middle

    low, high = 0, int(1e14) - 1
    while high - low > 1:
        middle = (low + high) // 2
        if check(middle, A):
            max_a = middle
            high = middle
        else:
            low = middle

    if min_a == INF or max_a == 0:
        return [-1]
    return min_a, max_a

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

    print(*solve(A))



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(0)

minval = 2
maxval = 3
for i in range(K-1,-1,-1):
	if maxval < A[i] or (minval > A[i] and ((maxval - (maxval % A[i]) < minval))):
		print(-1)
		exit(0)

	if minval > A[i]:
		if minval % A[i] != 0:
			minval = minval + (A[i] - (minval % A[i]))

		maxval = (maxval - (maxval % A[i]) + A[i] - 1)

	else:
		maxval = A[i] + (A[i] - 1)
		minval = A[i]
		

print(str(minval) + " " + str(maxval))

Submission status: Accepted

Solution code:


def main():
    k = int(input())
    aa = list(map(int, input().split()))[::-1] + [1]
    if aa[0] != 2:
        print(-1)
        return
    min_n, max_n = 2, 2
    for i in range(k):
        a = aa[i]
        b = aa[i + 1]
        if min_n % a:
            min_n = (min_n // a + 1) * a
        else:
            min_n = min_n // a * a
        m = max_n + a - 1
        m -= m % b
        if min_n > m:
            print(-1)
            return
        else:
            max_n = m
    print(min_n, max_n)


main()

Submission status: Accepted

Solution code:
import math
K=int(input())
A_lst=[int(_) for _ in input().split() ]

failed=False
if A_lst[-1]!=2:
    failed=True
else:
    stt, end=2,4
    for a in A_lst[-2::-1]:
        #print(stt, end, a)
        stt=a*math.ceil(stt/a)
        if stt>= end:
            failed=True
            break
        end=a*math.ceil(end/a)

if failed:
    print(-1)
else:
    print(stt, end-1)

Submission status: Accepted

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

def main():
    mi = ma = 2
    for a in A[::-1]:
        if mi % a:
            mi += a - (mi % a)
        ma += (a - 1) - (ma % a)
        if ma < mi:
            print(-1)
            return
    print(mi, ma)

main()

Submission status: Accepted

Solution code:
import sys

K = int(input())
A = [int(x) for x in input().split()]

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

minn = 2
maxn = 3

for i in range(len(A) - 2, -1, -1):
    m = A[i]
    a = (minn + m - 1) // m * m
    b = maxn // m * m
    if b < a:
        print(-1)
        sys.exit()
    minn = a
    maxn = b + m - 1

print(minn, maxn)

Submission status: Accepted

Solution code:
n=int(raw_input())
A=map(int,raw_input().split())
A.reverse()
[p,q]=[2,2]
for a in A:
    if p%a==0:
        p=p
    else:
        p=a*(p/a+1)
        if p>q:
            print -1
            break
    q=a*(max(q/a,p/a)+1)-1
else:
    print p,q

Submission status: Accepted

Solution code:
import sys

sys.stdin.readline()
As = list(map(int, sys.stdin.readline().split()))
As.reverse()

min = 2
max = 2

for a in As:
    min = ((min-1)//a+1)*a
    max = (max//a+1)*a-1
    #print(min, max)
    if min > max:
        print(-1)
        sys.exit()
print(min, max)

Submission status: Accepted

Solution code:
from math import ceil


def solve(rounds):
    mx, mn = 3, 2
    if rounds[-1] != 2:
        return (-1,)
    for r in reversed(rounds[:-1]):
        if mx < r:
            return (-1,)
        mn = ceil(mn / r) * r
        mx = mx // r * r + r - 1
    if mn > mx:
        return (-1,)
    return mn, mx


k = int(input())
rounds = list(map(int, input().split()))
print(*solve(rounds))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
K = int(input())
A=[int(i) for i in input().split()]
L = 2
R = 2
flag = 0

#(a + (b - 1)) / b
for i in range(K):
    LL = A[K-1-i]*((L+A[K-1-i]-1)//A[K-1-i])
    RR = A[K-1-i]*(R//A[K-1-i])
    if LL > R:
        flag = -1
        L = 2
        R = 1
    else:
        L = LL
        R = RR+A[K-1-i]-1
        
if flag == -1:
    print(-1)
else:
    print(L,R)

Submission status: Accepted

Solution code:
def main():
    n = int(raw_input())
    a = map(int, raw_input().split())
    if a[-1] > 2:
        print -1
        return
    lo = hi = 2
    for x in reversed(a):
        if hi < x:
            print -1
            return
        nlo = (lo + x - 1) / x * x
        nhi = hi / x * x + x - 1
        if nlo > nhi:
            print -1
            return
        lo = nlo
        hi = nhi
    print lo, hi
main()

Submission status: Accepted

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

l, r = 2, 2
for x in a:
    lb = max((l + x - 1) // x, 1)
    rb = r // x
    if rb < lb:
        print(-1)
        quit(0)
    l, r = lb * x, rb * x + x - 1

print(l, r)

Submission status: Accepted

Solution code:
K = input()
A = map(int, raw_input().split())
if A[-1]!=2:
  print -1
  exit(0)
mn = 2
mx = 3
for a in A[-2::-1]:
  mn = (mn+a-1)/a*a
  mx = mx/a*a+a-1
if mn<=mx:
  print mn, mx
else:
  print -1

Submission status: Accepted

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

l = 2
r = 2

def ng():
  print "-1"
  exit()

for a in A:
  l = l / a * a + (l % a != 0) * a
  r = r / a * a
  if r < l:ng()
  r += a-1

print l, r

Submission status: Runtime Error

Solution code:
import math
K = int(input())
A = list(map(int,input().split()))
if A[N-1]!=2:
    print(-1)
elif K==1:
    print(2,3)
else:
    nmin = 2
    nmax = 2+A[K-1]-1
    flag = 0
    for i in range(K-2,-1,-1):
        b = A[i]
        nmin = math.ceil(nmin/b)*b
        nmax = math.floor(nmax/b)*b
        if nmin>nmax:
            flag = 1
            break
        nmax += b-1
    if flag==1:
        print(-1)
    else:
        print(nmin,nmax)

Submission status: Runtime Error

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

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

ans =2
for i in range(1,K):
    if A[i] >= A[i-1]*2:
        print(-1)
        exit()
    elif A[i-1]<=A[i]<A[i-1]*2:
        ans = A[i]
    elif A[i-1]>A[i]:
        ans = math.ceil(A[i-1]/A[i])*A[i]

print(ans,ans+A[i]-1)

Submission status: Runtime Error

Solution code:
n = int(input())
As = list(map(int, input().split()))
    
def f(m):
    debug = m
    for a in As:
        i = m // a
        m = i * a
    return m

# 二部探索?
l = 1
r = 10**5+1
while r-l > 1:
    m = (r+l)//2
    if f(m) <= 1: l = m
    else: r = m
ans1 = r
l = 1
r = 10**5 + 1
while r-l > 1:
    m = (r+l)//2
    if f(m) <= 2: l= m
    else: r = m
ans2 = l

if ans1 >= ans2:
    print(-1)
else:
    print(ans1[1],ans2[0])