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: Time Limit Exceeded

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

res = 0
if A[N - 1] != 2:
    res = -1
else:
    N_possible = [2,3]
    i = N - 2
    while i >= 0:
        #print(i,N_possible)
        N_new = []
        for n in N_possible:
            if n % A[i] == 0:
                temp = n / A[i]
                x = 0
                while x < A[i]:
                    N_new.append(temp * A[i] + x)
                    x += 1
        if N_new == []:
            res = - 1
            i = - 1
        else:
            N_possible = N_new
        i -= 1
if res == - 1:
    print(res)
else:
    a = int(min(N_possible))
    b = int(max(N_possible))
    print(a," ",b)

Submission status: Time Limit Exceeded

Solution code:
def main():
    K = int(input())
    A = list(map(int, input().split()))
    candidate = set([2])
    for Ai in reversed(A):
        next_candidate = set()
        for j in candidate:
            if j % Ai == 0:
                next_candidate |= set(range(j, j+Ai))
        candidate = next_candidate
    if candidate:
        print(min(candidate), max(candidate))
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def game(A,N):
    for A_i in A:
        N-=N%A_i
    if N==2:
        return True
    else:
        return False

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

minimum=-1
maximum=-1
for i in range(max(A),sum(A)-K+3):
    if game(A,i):
        maximum=i
        if minimum==-1:
            minimum=i

if minimum!=-1:
    print("{0} {1}".format(minimum,maximum))
else:
    print("-1")

Submission status: Time Limit Exceeded

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

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

for i in range(0,K):  # 0<=i<=K-2 A[K-2]は2ラウンドの組．Kラウンドから2ラウンドまで
    Round = list(range(jmin,jmax+1))
    decide = [Round[h] % A[i] for h in range(len(Round))]
    if not(0 in decide):
        print(-1)
        sys.exit()
    jmin = (math.ceil(jmin / A[i])) * A[i]
    jmax = (math.floor(jmax / A[i])) * A[i] + A[i] -1

print(jmin, jmax)

Submission status: Time Limit Exceeded

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:
            #     print(-1)
            #     return
            chk = False
            for c in range(mi, mx+1):
                if c % na == 0:
                    chk = True
                    break
            if chk == False:
                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: Time Limit Exceeded

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:
            #     print(-1)
            #     return
            chk = False
            for c in range(mi, mx+1):
                if c % na == 0:
                    chk = True
            if chk == False:
                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: Time Limit Exceeded

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):
    k = i
    while(min > k):
        k += i
    if(k <= max):
        min = math.ceil(min / i) * i
        max = math.floor(max / i) * i + i - 1
    else:
        print(-1)
        exit()

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

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
a = [int(i) for i in input().split()]
m = sum([i for i in a]) - k + 2
l = []
for n in range(max(a), m+1):
    c = n
    q = 0
    for i in a:
        c -= c % i
        q += c // i
    if c == 2: l.append(n)
    if q > m + 1: break
    if c > 2: break
if len(l) == 0: print(-1)
else: print(l[0], l[-1])

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
a = list(map(int, input().split()))
n_min = 2
n_max = 2
for i in range(k):
    n_min = n_min
    n_max = n_max + a[-i] - 1
while True:
    x = n_min
    for i in range(k):
        x = x - x % a[i]
    if x == 2 or n_min == n_max + 1:
        break
    else:
        n_min = n_min + 1
while True:
    if n_min == n_max + 1:
        break
    y = n_max
    for i in range(k):
        y = y - y % a[i]
    if y == 2:
        break
    else:
        n_max = n_max - 1
if n_min > n_max:
    print(-1)
else:
    print(n_min, n_max)

Submission status: Time Limit Exceeded

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[1]+1
    n2 = n[0]
    for i in range(n[0], n[1]+1):
        if i%a!=0:
            continue
        if i<n1:
            n1 = i
        if i>n2:
            n2 = i
    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: Time Limit Exceeded

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
  q = [lower,lower + now - 1]

  upper = lower + now - 1
  while (upper / now) * now <= r[1]:
    upper += 1
  upper -= 1

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

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

Submission status: Time Limit Exceeded

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)


def main():
    n = I()
    a = LI()
    if a[-1] != 2:
        return -1
    b = 2
    c = 4
    for i in range(n-2,-1,-1):
        t = a[i]
        if b * 2 <= t:
            return -1
        if b % t == 0:
            pass
        elif b > t:
            b += t-b%t
        else:
            b = t
        if c % t == 0:
            pass
        elif c > t:
            c += t-c%t
        else:
            return -1
    bb = b
    cc = c-1
    while True:
        bb = b
        for i in range(n):
            bb -= bb%a[i]
        if bb != 2:
            b += a[0]
        else:
            break
    for i in range(n):
        cc -= cc%a[i]
    if cc != 2:
        return 1/0

    return '{} {}'.format(b, c-1)

print(main())

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
a = [int(i) for i in input().split()]
m = sum([i-1 for i in a])
l = []
for n in range(max(a), m+3):
    c = n
    for i in a:
        c -= c % i
    if c == 2: l.append(n)
    if c > 2: break
if len(l) == 0: print(-1)
else: print(l[0], l[-1])

Submission status: Time Limit Exceeded

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)


def main():
    n = I()
    a = LI()
    if a[-1] != 2:
        return -1
    b = 2
    c = 4
    for i in range(n-2,-1,-1):
        t = a[i]
        if b * 2 <= t:
            return -1
        if b % t == 0:
            pass
        elif b > t:
            b += t-b%t
        else:
            b = t
        if c % t == 0:
            pass
        elif c > t:
            c += t-c%t
        else:
            return -1
    bb = b
    cc = c-1
    while True:
        bb = b
        for i in range(n):
            bb -= bb%a[i]
        if bb != 2:
            b += a[0]
        else:
            break
    for i in range(n):
        cc -= cc%a[i]
    if cc != 2:
        while 1:
            cc += 1

    return '{} {}'.format(b, c-1)

print(main())

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    K = int(input())
    A = list(map(int, input().split()))

    # min
    target_nums = [2]
    for a in reversed(A):
        targets = [_ for _ in target_nums if _ % a == 0]
        if len(targets) == 0:
            print(-1)
            exit()

        target_nums = []
        for target in targets:
            target_nums += [_ + target for _ in range(a)]

    print(str(min(target_nums)) + " " + str(max(target_nums)))

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
a = list(map(int, input().split()))
n_min = 2
n_max = 2
for i in range(k):
    n_min = n_min
    n_max = n_max + a[-i] - 1
ok = []
for i in range(n_min, n_max + 1):
    l = i
    for j in range(k):
        i = i - i % a[j]
    if i == 2:
        ok.append(l)
if ok == []:
    print(-1)
else:
    print(min(ok), max(ok))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    K = int(input())
    A = list(map(int, input().split()))

    # min
    target_nums = [2]
    for a in reversed(A):
        targets = [_ for _ in target_nums if _ % a == 0]
        if len(targets) == 0:
            print(-1)
            exit()

        tmp_target_nums = [_ for _ in range(a)]
        target_nums = []
        for target in targets:
            target_nums += list(map(lambda x: x + target, tmp_target_nums))

    print(str(min(target_nums)) + " " + str(max(target_nums)))

Submission status: Time Limit Exceeded

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:
        while 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:
        while b > nb:
            nb+= i
    b= (nb+i-1)
print(s,b)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
A = list(map(int, input().split()))
A.reverse()
A.append(1)
prev = set()
if A[0] == 2:
  prev.add(2)

for i in range(K):
  a = A[i]
  an = A[i+1]
  s = set()
  for n in prev:
    if n+a <= an:
      continue
    for x in range(((n+an-1)//an)*an, n+a, an):
      s.add(x)
  prev = s

if len(prev) > 0:
  print(min(prev), max(prev))
else:
  print('-1')

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    
    K = int(input())
    A = list(map(int, input().split()))

    minN = 0
    maxN = 0
    i = max(A) - 1
    while True:
        i += 1
        N = i
        for a in A:
            N -= N%a
            if N < 2:
                break
            
        else:
            if N == 2:
                if minN == 0:
                    minN = i
                    maxN = i
                else:
                    maxN = i
            elif N > 2:
                break

    if minN == 0:
        print(-1)
    else:
        print(minN, maxN)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    
    K = int(input())
    A = list(map(int, input().split()))

    minN = 0
    maxN = 0
    i = max(A) - 1
    while True:
        i += 1
        N = i
        for a in A:
            N -= N%a
            if N == 0:
                break
            
        else:
            if N == 2:
                if minN == 0:
                    minN = i
                    maxN = i
                else:
                    maxN = i
            elif N > 2:
                break

    if minN == 0:
        print(-1)
    else:
        print(minN, maxN)

Submission status: Time Limit Exceeded

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

A=reversed(AT)
s = 2;b = 1;lis=[]
for i in A:
    b=b-b%i
    ns = i
    if s > ns:
        while s > ns:
            ns += i
    s = ns
    nb = i
    if b > nb:
        while b > nb:
            nb+= i
    b= (nb+i-1)
sn = s
for i in AT:
    sn = sn-sn%i
if sn!=2:
    print(-1)
    exit()
print(s,b)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    
    K = int(input())
    A = list(map(int, input().split()))

    minN = 0
    maxN = 0
    i = 0
    # for i in range(100):
    while True:
        i += 1
        N = i
        for a in A:
            N -= N%a
            if N == 0:
                break
            
        else:
            if N == 2:
                if minN == 0:
                    minN = i
                    maxN = i
                else:
                    maxN = i
            elif N > 2:
                break

    if minN == 0:
        print(-1)
    else:
        print(minN, maxN)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

result = []
for i in itertools.count(1):
  now_i = i
  for a in A:
    now_i = (now_i // a) * a
  if now_i == 2:
    result.append(i)
  if now_i > 2:
    break

if result:
  print(result[0], result[-1])
else:
  print(-1)

Submission status: Time Limit Exceeded

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

n = [2]

for a in A:
    tmp = []
    for t in filter(lambda x:x%a==0, n):
        for i in range(t,t+a):
            tmp.append(i)
    n = list(set(tmp))

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

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
A = list(map(int, input().split()))
A.reverse()
prev = set([2])
for a in A:
  s = set()
  for n in prev:
    if n % a == 0: # そのラウンドでn人残るための条件
      for x in range(n, n+a):
        s.add(x)
  prev = s

if len(prev) > 0:
  print(min(prev), max(prev))
else:
  print('-1')

Submission status: Time Limit Exceeded

Solution code:
input()
l = list(map(int,input().split()))
R = {2}
for n in l[::-1]:
   R2 = set()
   for r in R:
      if r%n == 0:
         for i in range(n):
            R2.add(r+i)
   R = R2
if len(R):
   print(min(R),max(R))
else:
   print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

r = set([2, 3])

for i in range(len(A) - 2, -1, -1):
    m = A[i]
    nr = set([])
    for x in r:
        if x % m == 0:
            nr |= set(range(x, x + m))
    r = nr
    if len(r) == 0:
        print(-1)
        sys.exit()

print(min(r), max(r))

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, A):
    mx = 2
    mn = 2
    for a in reversed(A):
        mx = (mx // a + 1) * a - 1
        mn = (mn + a - 1) // a * a
        if mn > mx:
            print(-1)
            return
    print(mn, mx)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    main(N, A)

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int,input().split()))
I = [[-1,-1] for _ in range(K+1)]
I[K] = [2,2]
fg = True
for i in range(K-1,-1,-1):
    #consider range I[i]
    left = A[i]*((I[i+1][0]+A[i]-1)//A[i]) 
    I[i][0] = max(A[i],left)
    I[i][1] = A[i]*(I[i+1][1]//A[i] + 1) -1
    #print(i,*I[i])
    if(I[i][0] > I[i][1]):
        fg = False
        break
if(not fg):
    print(-1)
else:
    print(*I[0])

Submission status: Accepted

Solution code:
K = int(input())
A = list(map(int,input().split()))
I = [[-1,-1] for _ in range(K+1)]
I[K] = [2,2]
fg = True
for i in range(K-1,-1,-1):
    #consider range I[i]
    left = A[i]*((I[i+1][0]+A[i]-1)//A[i]) 
    I[i][0] = max(A[i],left)
    I[i][1] = A[i]*(I[i+1][1]//A[i] + 1) -1
    #print(i,*I[i])
    if(I[i][0] > I[i][1]):
        fg = False
        #break
if(not fg):
    print(-1)
else:
    print(*I[0])

Submission status: Accepted

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

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

A = A[::-1]
if A[0] != 2:
  ng()
mim = 2
mox = 3

for i in range(1, K):
  a = A[i]
  n = -(-mim // a) * a
  if n > mox:
    ng()
  mim = n
  mox = mox // a * a + a - 1

print(mim, mox)

Submission status: Accepted

Solution code:
k=int(input())
a=list(map(int,input().split()))
a.reverse()
d=[2,2]
f=True
for i in a:
  d[0]=((d[0]-1)//i+1)*i
  d[1]=d[1]//i*i+i-1
  if d[0]>d[1]:
    f=False
if f:
  print(d[0],d[1])
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
K = int(input())
A = list(map(int, input().split()))
minA = 2
maxA = 2
for ai in A[::-1]:
    if minA <= ai <= maxA:
        minA = ai
        maxA = maxA - maxA%ai + ai - 1
    elif ai < minA:
        minA = minA + ai * int(minA%ai>0) - minA%ai
        maxA = maxA - maxA%ai + ai - 1
    elif ai > maxA:
        print(-1)
        sys.exit()
if minA > maxA:
    print(-1)
else:
    print(minA, maxA)

Submission status: Accepted

Solution code:
import math
K = int(input())
A = list(map(int, input().split()))
mincnt = 2
for a in reversed(A):
    if a < mincnt:
        a = math.ceil(mincnt/a) * a
    mincnt = max(mincnt, a)

#print(mincnt)

maxcnt = 2
nowgropu = 1
for a in reversed(A):
    nowgropu = maxcnt // a
    maxcnt = a * (nowgropu + 1) - 1

#print(maxcnt)

def check(init, A):
    cnt = init
    for a in A:
        group = cnt // a
        cnt = group * a
    return cnt == 2

#print(check(mincnt, A))
if check(mincnt, A) and check(maxcnt, A):
    print(mincnt, maxcnt)
else:
    print(-1)

Submission status: Accepted

Solution code:
def solve(x):
    for i in a:
        x = i * (x // i)
    return x

def solve_min(c1, c2):
    m = (c1 + c2 + 1) // 2
    if abs(c1 - c2) <= 1:
        return m
    else:
        if solve(m) < 2:
            c1 = m
        else:
            c2 = m
        return solve_min(c1, c2)

def solve_max(c1, c2):
    m = (c1 + c2 + 1) // 2
    if abs(c1 - c2) <= 1:
        return m
    else:
        if solve(m) <= 2:
            c1 = m
        else:
            c2 = m
        return solve_max(c1, c2)

k = int(input())
a = list(map(int, input().split()))
maxa = max(a)
mi = solve_min(maxa - 1, pow(10, 18))
ma = solve_max(maxa - 1, pow(10, 18))
ans = [mi, ma - 1]
print(-1 if mi == ma else " ".join(map(str, ans)))

Submission status: Accepted

Solution code:
from math import ceil, floor

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


"""
- X人いてAi人グループをつくるとき，floor(X/Ai)個のグループになる
- floor(X/Ai) * Ai = X - X mod Ai 人が残る
- fp(X) = X - X mod pとする
"""

L, R = 2, 2

# L, Rから1つ前のL, R (最小，最大)を復元する

for k in range(K - 1, -1, -1):
    # print(k, A[k])
    L = ceil(L / A[k]) * A[k]
    R = floor(R / A[k]) * A[k] + A[k] - 1
    if L > R:
        print(-1)
        exit()

print(L, R)

Submission status: Accepted

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

l = 2
r = 2
for i in a[::-1]:
    if i > r:
        print(-1)
        exit()
    l = (l+i-1)//i*i
    r = r//i*i+i-1
    if r < l:
        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()

l = 2
r = 3
for i in a[::-1][1:]:
    if i > r:
        print(-1)
        exit()
    l = (l+i-1)//i*i
    r = r//i*i+i-1
    if r < l:
        print(-1)
        exit()
print(l,r)

Submission status: Accepted

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

def solve(num, checker):
    return checker*(num//checker)

max_A = max(a)

left, right = 0, k*max_A + 1
while left < right:
    middle = (left+right)//2
    num = middle
    for i in a:
        num = solve(num, i)
    if num >= 2:
        right = middle
    else:
        left = middle + 1
x = right

left, right = 0, k*max_A + 1
while left < right:
    middle = -((-left-right)//2)
    num = middle
    
    for i in a:
        num = solve(num, i)
    if num <= 2:
        left = middle
    else:
        right = middle - 1
        
y = right

if y < x:
    print(-1)
else:
    print(x, y)

Submission status: Accepted

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

def solve(num, checker):
    return checker*(num//checker)

max_A = max(a)

left, right = 0, k*max_A + 1
while left < right:
    middle = (left+right)//2
    num = middle
    for i in a:
        num = solve(num, i)
    if num >= 2:
        right = middle
    else:
        left = middle + 1
x = right

left, right = 0, k*max_A + 1
while left < right:
    middle = -((-left-right)//2)
    #print(left, right, middle, num)
    num = middle
    
    for i in a:
        num = solve(num, i)
    if num <= 2:
        left = middle
    else:
        right = middle - 1
        
y = right

if y < x:
    print(-1)
else:
    print(x, y)

Submission status: Accepted

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

def solve(num, checker):
    return checker*(num//checker)

left, right = 0, max(a)*k + 2
while left+1 < right:
    middle = (left+right)//2
    num = middle
    for i in a:
        num = solve(num, i)
    if num <= 2:
        left = middle
    else:
        right = middle
x = left

left, right = 0, max(a)*k + 2
while left+1 < right:
    middle = (left+right)//2
    num = middle
    for i in a:
        num = solve(num, i)
    if num < 2:
        left = middle
    else:
        right = middle
        
y = right
if x < y:
    print(-1)
else:
    print(y, x)

Submission status: Accepted

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

for i in range(K):
    if i == 0:
        if A[i] != 2:
            print(-1)
            exit()
        else:
            m,M = 2,3
    else:
        m0 = m//A[i]
        M0 = M//A[i]
        if m0*A[i] >= m:
            m = m0*A[i]
        else:
            m = (m0+1)*A[i]
        M = (M0+1)*A[i]-1
        if m > M:
            print(-1)
            exit()

print(m,M)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


K = I()
A = LI()
A.reverse()

m,M = 2,2  # 最小値、最大値
for i in range(K):
    a = A[i]
    if (m+(a-1))//a > M//a:
        print(-1)
        exit()
    else:
        m = a*((m+(a-1))//a)
        M = a*(M//a)+(a-1)

print(m,M)

Submission status: Accepted

Solution code:
import math
K = int(input())
A = list(map(int,input().split()))
if A[K-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: Accepted

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

low, high = 2, 3

for a in A:
    if high < a:
        print(-1)
        exit()
    elif a < low:
        low=(-((-low)//a))*a
        if low > high:
            print(-1)
            exit()
        high=max(low+a-1,high+a-1-high%a)
    else:
        low=a
        if low>high:
            print(-1)
            exit()
        high=low+a-1
print(low,high)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())

unko = 2
unti = 2
for i in reversed(a):
    unko = unko // i * i + i - 1
    unti = (unti + i - 1) // i * i
if unti >= unko:
    print(-1)
else:
    print(unti, unko)

Submission status: Accepted

Solution code:
k=int(input())
A=[int(i) for i in input().split()]
mi=2
ma=2

for i in range(k-1,-1,-1):
    mi=((mi+A[i]-1)//A[i])*A[i]
    if mi>ma:
        print(-1)
        break
    ma=(ma//A[i])*A[i]+(A[i]-1)
else:
    if A[-1]==2:
        print(mi,ma)
    else:
        print(-1)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


K = I()
A = LI()
A.reverse()

m,M = 2,2
for i in range(K):
    a = A[i]
    if (m+(a-1))//a > M//a:
        print(-1)
        exit()
    else:
        m = a*((m+(a-1))//a)
        M = a*(M//a)+(a-1)

print(m,M)

Submission status: Accepted

Solution code:
import sys
 
K = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
 
if A[-1] != 2:
    print(-1)
    sys.exit()
 
l = 2
r = 2
for i in range(K-2, -1, -1):
    l = ((l - 1) // A[i] + 1) * A[i]
    r = ((r + A[i+1] - 1) // A[i]) * A[i] 
 
    if r < l:
        print(-1)
        sys.exit()
 
print(l, r + A[0] - 1)

Submission status: Accepted

Solution code:
from math import ceil, floor

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

l,r = -1,-1
if al[0] != 2:
    print(-1)
    exit()

l = 2
r = 3
for a in al[1:]:
    min_l = ceil(l/a)*a
    max_r = floor(r/a)*a
    if min_l > r:
        print(-1)
        exit()
    if max_r < l:
        print(-1)
        exit()
    l = min_l
    r = max_r + (a-1)

print(l,r)

Submission status: Accepted

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

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

min_child = 2
max_child = 2

for i in range(K-1,-1,-1):
    if math.ceil(min_child/A[i])>0 and math.floor(max_child/A[i])>0 and math.floor(max_child/A[i])-math.ceil(min_child/A[i])>=0:
        min_child = math.ceil(min_child/A[i])*A[i]
        max_child =math.floor(max_child/A[i])*A[i]+A[i]-1
    else:
        print(-1)
        exit()
print(min_child,max_child)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd
#input=sys.stdin.readline
#import bisect
k=int(input())
a=list(map(int,input().split()))
ml=mr=2
l=r=2
for i in range(k):
    ai=a[k-1-i]
    mr=(r//ai)*ai
    ml=(1+(l//ai))*ai if l%ai!=0 else l
    if ml>mr:
      print(-1)
      exit()
    if mr==0:
        print(-1)
        exit()
    elif ml==0:
        ml=mr
    l=ml
    r=mr+ai-1
print(l,r)

Submission status: Accepted

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**20
while r-l > 1:
    m = (r+l)//2
    if f(m) <= 1: l = m
    else: r = m
ans1 = r
l = 1
r = 10**20
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,ans2)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))[::-1]
if a[0]!=2:
  print(-1)
  exit()
mn,mx=2,2
for j in a:
  if (mn+j-1)//j>mx//j:
    print(-1)
    exit()
  mn=(mn+j-1)//j*j
  mx=mx//j*j+j-1
print(mn,mx)

Submission status: Accepted

Solution code:
import sys
import math

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

if a[-1] != 2:
    print(-1)
    sys.exit()
else:
    mi,ma = 2,2
    for i in range(k-1,-1,-1):
        if mi == ma and mi%a[i] != 0 :
            print(-1)
            sys.exit()
        elif mi != ma and math.floor(ma/a[i]) - math.floor((mi-1)/a[i]) == 0:
            print(-1)
            sys.exit()
        else:
            mi = math.ceil(mi / a[i]) * a[i]
            ma = math.floor(ma / a[i]) * a[i] + a[i] - 1
            
    print(mi,ma)

Submission status: Accepted

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

# answer will be "{lo} {hi}"
lo = 2
hi = 2
for A in reversed(As):
    if (hi // A) - ((lo - 1) // A) == 0:
        print(-1)
        exit()
    lo = (lo + A - 1) // A * A
    hi = (hi // A + 1) * A - 1 

print(lo, hi)

Submission status: Accepted

Solution code:
k = int(input())
alst = list(map(int, input().split()))[::-1]
l = 2
r = 2

def check(l, r, a):
    if l % a == 0:
        return True
    elif r // a == l // a:
        return False
    else:
        return True

for a in alst:
    if not check(l, r, a):
        print(-1)
        exit()
    l = (l + a - 1) // a * a
    r = r // a * a + (a - 1)
print(l, r)