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

K = INT()
A = LIST()

def f(N):
	left = N
	for a in A:
		left = left//a*a
	return left

l_N_max = 0
r_N_max = K*max(A)+2
while l_N_max+1 < r_N_max:
	m = (l_N_max+r_N_max)//2
	if f(m) <= 2:
		l_N_max = m
	else:
		r_N_max = m

N_max = l_N_max

l_N_min = 0
r_N_min = K*max(A)+2
while l_N_min+1 < r_N_min:
	m = (l_N_min+r_N_min)//2
	if f(m) < 2:
		l_N_min = m
	else:
		r_N_min = m
N_min = r_N_min

if N_min > N_max:
	print(-1)
else:
	print(N_min, N_max)

Submission status: Accepted

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

K = INT()
A = LIST()

def f(N):
	left = N
	for a in A:
		left = left//a*a
	return left

l_N_max = 0
r_N_max = 10**14
while l_N_max+1 < r_N_max:
	m = (l_N_max+r_N_max)//2
	if f(m) <= 2:
		l_N_max = m
	else:
		r_N_max = m

N_max = l_N_max

l_N_min = 0
r_N_min = 10**14
while l_N_min+1 < r_N_min:
	m = (l_N_min+r_N_min)//2
	if f(m) < 2:
		l_N_min = m
	else:
		r_N_min = m
N_min = r_N_min

if N_min > N_max:
	print(-1)
else:
	print(N_min, N_max)

Submission status: Accepted

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

K = INT()
A = LIST()

def f(N):
	left = N
	for a in A:
		left = left//a*a
	return left

l_N_max = 0
r_N_max = sum(A)-K+3
while l_N_max+1 < r_N_max:
	m = (l_N_max+r_N_max)//2
	if f(m) <= 2:
		l_N_max = m
	else:
		r_N_max = m

N_max = l_N_max

l_N_min = 0
r_N_min = sum(A)-K+3
while l_N_min+1 < r_N_min:
	m = (l_N_min+r_N_min)//2
	if f(m) < 2:
		l_N_min = m
	else:
		r_N_min = m
N_min = r_N_min

if N_min > N_max:
	print(-1)
else:
	print(N_min, N_max)

Submission status: Accepted

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

K = INT()
A = LIST()[::-1]

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

N_min = 2
N_max = 3
for a in A[1:]:
	if ((N_min-1)//a) ==  N_max//a:
		print(-1)
		exit()

	N_min = -(-N_min//a)*a
	N_max = N_max//a*a + a - 1

print(N_min, N_max)

Submission status: Accepted

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

K = INT()
A = LIST()[::-1]

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

N_min = 2
N_max = 3
for a in A[1:]:
	if (N_min-1)//a ==  N_max//a:
		print(-1)
		exit()

	N_min = ((N_min-1)//a+1)*a
	N_max = N_max//a*a + a - 1

print(N_min, N_max)

Submission status: Accepted

Solution code:
from math import ceil
K = int(input())
A = list(map(int, input().split()))
A.reverse()
if A[0] != 2:
    print(-1)
    exit()
mi = 2
mx = 3
for a in A[1:]:
    if ceil(mi/a) > mx//a:
        print(-1)
        exit()
    mi = ceil(mi/a)*a
    mx = mx//a*a
    mx = mx + a - 1
print(mi, mx)

Submission status: Accepted

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


lo = 2
hi = 3
for a in reversed(A):

    nl = (lo-1)//a+1
    nh = (hi-1)//a+1

    lo,hi = nl*a,nh*a

if lo < hi:
    print(lo,hi-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    k = int(readline())
    a = list(map(int, readline().split()))
    a = a[::-1]

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

    l = 2
    r = 3

    for x in a[1:]:
        l = (x + l - 1) // x * x
        r = r // x * x + (x - 1)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    k = int(ipt())
    a = [int(i) for i in ipt().split()]
    mi = 2
    ma = 2
    for i in a[::-1]:
        mi = ((mi-1)//i+1)*i
        ma = (ma//i)*i
        if mi > ma:
            print(-1)
            exit()
        ma = ma+i-1
    print(mi,ma)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

ans = (2, 2)

for div in reversed(nums):
    lower = (ans[0] + div - 1) // div * div
    upper = ans[1] // div * div
    if not lower <= upper:
        print(-1)
        exit()
    
    ans = (lower, upper + div - 1)

print(f'{ans[0]} {ans[1]}')

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    k = ni()
    a = na()
    a.reverse()

    min_num = 2
    max_num = 2

    for ai in a:
        min_num = int(math.ceil(min_num / ai) * ai)
        max_num = int(math.floor(max_num / ai + 1) * ai) - 1

    if min_num <= max_num:
        print(min_num, max_num)
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cb, cu = 2, 2
for a in A:
    nb = ((cb+a-1)//a)*a
    nu = (cu//a+1)*a-1
    if nb > cu:
        print(-1)
        exit()
    cb, cu = nb, nu
print(nb, nu)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    K = in_n()
    A = in_nl()[::-1]

    min_n = 2
    max_n = 2

    for group in A:

        cnt = -(-min_n // group)
        next_min = group * cnt
        if not (min_n <= next_min <= max_n):
            print(-1)
            exit()

        cnt = max_n // group
        next_max = cnt * group + (group - 1)

        min_n, max_n = next_min, next_max

    print(min_n, max_n)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def is_ok(arg,flg):
  # 条件を満たすかどうか？問題ごとに定義
  N0 = arg
  for a in A:
    N0 -= N0 % a
  if flg:
    return  N0 >= 2
  else:
    return  N0 <= 2
    
def meguru_bisect(ng, ok, flg):
  '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
  '''
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid, flg):
      ok = mid
    else:
      ng = mid
    #print(ok,ng)
  return ok
      
ok,ng = K * max(A) + 100, -1
m = meguru_bisect(ok,ng,False)
#print()
ok,ng = 0, K * max(A) + 100
M = meguru_bisect(ok,ng,True)

if M <= m:
  print(M,m)
else:
  print(-1)

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    A = list(map(int, input().split()))
    A = A[::-1]
    if A[0] != 2:
        print(-1)
        return
    n = 2
    lower_n, upper_n = 2, 3
    for a in A:
        # [lower_n, upper_n]内にaの倍数が無ければNG
        if upper_n // a - (lower_n - 1) // a == 0:
            print(-1)
            return
        lower_n = (lower_n + a - 1) // a * a  # ceil(lower_n/a) * a
        upper_n = upper_n // a * a + a - 1  # # floor(upper_n/a) * a + a - 1
    print('{} {}'.format(lower_n, upper_n))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
  ans = 0
  K = int(input())
  A = list(map(int, input().split()))
  A = A[::-1]
  bottom = 2
  top = 2
  for a in A:
    bottom = -(-bottom//a)*a
    if bottom>top:
      return [-1]
    top = top//a*a+a-1
  return [bottom,top]
print(*solve())

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 l > r:
        print(-1)
        sys.exit()

# print(l, r)
print(l, r + A[0] - 1)

Submission status: Accepted

Solution code:
import sys

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

# うまい方法がない気がするため、二分探索で攻める
l = 0
r = 2 * 10**15
ans1 = -1
while l != r:
    n = (l + r) // 2
    res = n
    for a in A:
        res = res - res % a
    if res >= 2:
        r = n
        if res == 2:
            ans1 = n
    else:
        l = n + 1

l = 0
r = 2 * 10**15
ans2 = -1
while l != r:
    n = (l + r) // 2
    res = n
    for a in A:
        res = res - res % a
    if res <= 2:
        l = n + 1
        if res == 2:
            ans2 = n
    else:
        r = n

if ans1 != -1:
    print(ans1, ans2)
    # print(n - n % A[0], A[0] * ((n - 1) // A[0] + 1) - 1)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# Li-1 = [Li // A[i]] * A[i]
# Ri-1 = [Ri // A[i]] * A[i] + A[i] - 1

K = getN()
A = getList()
A = A[::-1]
if A[0] != 2:
    print(-1)
    exit()
mi = A[0]
mx = A[0] * 2 - 1
for i in range(1, K):
    ai = A[i]
    mi = (mi + ai - 1) // ai
    mx = mx // ai
    if mi > mx:
        print(-1)
        exit()
    else:
        mi = mi * ai
        mx = (mx + 1) * ai - 1
print(mi, mx)

Submission status: Accepted

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

k = int(input())
a = list(map(int, input().split()))
a= a[::-1]
if a[0]!=2:
    print(-1)
    exit()
mi = a[0]
mx = a[0]*2-1
for i in range(1,k):
    ai = a[i]
    mi = (mi+ai-1)//ai
    mx = mx//ai
    if mi>mx:
        print(-1)
        exit()
    else:
        mi = mi*ai
        mx = (mx+1)*ai-1
print(mi, mx)

Submission status: Accepted

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

for i in reversed(range(k)):
    if ansmax - ansmin < a[i] and (ansmin%a[i])*(ansmax%a[i]) != 0 and (ansmax%a[i]) >= (ansmin%a[i]):
        print(-1)
        exit()
    ansmin = -(-ansmin//a[i])*a[i]
    ansmax = (ansmax//a[i])*a[i] + a[i] - 1
print(str(ansmin) + " " + str(ansmax))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    if A[0] != 2:
        print(-1)
    else:
        prev_min, prev_max = 2, 3
        for i in range(1, k):
            a = A[i]
            if a > prev_max:
                print(-1)
                break
            else:
                if prev_min % a == 0:
                    now_min = prev_min
                else:
                    now_min = (prev_min // a + 1) * a
                if now_min > prev_max:
                    print(-1)
                    break
                diff = prev_max - now_min
                now_max = now_min + (diff // a + 1) * a - 1
                prev_min, prev_max = now_min, now_max
        else:
            print(prev_min, prev_max)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.reverse() #後ろから見る。

if A[0] != 2:
  print(-1)
  exit()
MIN = 2
MAX = 3
for i in range(1,N):
  nxt = A[i]
  if MAX < nxt:
    print(-1)
    exit() 
  #オッケーの最大値
  MAX = (MAX//nxt)*nxt #MAXは絶対前の数の倍数
  if MAX < MIN:
    print(-1)
    exit()
  #オッケーの最小値
  MIN = min(MAX,((MIN+nxt-1)//nxt)*nxt)

  #print(MIN,MAX)
 
  #最小値は変化なし。
  MAX = MAX+(nxt-1)
  #print(nxt,MIN,MAX)
print(MIN,MAX)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
K = I()
A = IL()

def is_ok(l,r,a):
  if r-l+1 >= a:
    return True
  else:
    if l%a == 0 or r%a == 0 or l%a > r%a:
      return True
    else:
      return False
now = (2,2)
for a in A[::-1]:
  l,r = now
  if is_ok(l,r,a):
    l = ((l-1)//a)*a+a
    r = (r//a)*a+a-1
    now = (l,r)
  else:
    print(-1)
    exit()
print(*now)

Submission status: Accepted

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

def f(n):
    for a in As:
        n = a * (n//a)
    return n

ng,ok = 1, 10**20
while ok-ng > 1:
    m = (ok+ng)//2
    if f(m) >= 2: #2以上ならTrue
        ok = m
    else:
        ng = m
mn = ok
# print(ng,ok)

ok,ng = 1, 10**20
while ng-ok > 1:
    m = (ok+ng)//2
    if f(m) <= 2: #2以下の範囲
        ok = m
    else:
        ng = m
mx = ok

# print(ok,ng)
if mn > mx:
    print(-1)
else:
    print(mn,mx)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


k = int(input())
a = list(map(int, input().split()))
v1 = 2
v2 = 2
ans = None
for num in a[::-1]:
#     print(v1,v2)
    # num人組を作って生き残れた人がv1~v2人
    if (v1-1)//num == (v2)//num:
        ans = -1
        break
    v1 = ((v1-1)//num+1) * num
    v2 = (v2)//num * num + (num-1)
if ans == -1:
    print(ans)
else:
    print(v1,v2)

Submission status: Accepted

Solution code:
k=int(input())
a=list(map(int,input().split()))
if a[-1]!=2:
  print(-1)
  exit()
l,r=2,2
for i in range(k):
  ai=a[-1-i]
  # l以上r以下のaiの倍数を探す。なければ-1
  if r<ai or (l//ai==r//ai and l%ai!=0):
    print(-1)
    exit()
  l=ai*((l+ai-1)//ai)
  r=ai*(r//ai)+(ai-1)
print(l,r)

Submission status: Accepted

Solution code:
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def nn(v, min_v, max_v):
	min_n = (min_v + v - 1) // v
	max_n = max_v // v
	#pa((min_n, max_n))
	if max_n < min_n:
		return -1, -1
	return v * min_n, v * max_n + v - 1

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	al = al[::-1]
	min_v, max_v = 2, 2
	for v in al:
		min_v, max_v = nn(v, min_v, max_v)
		if min_v == -1:
			return -1
	print(min_v, max_v)
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():

	n=II()
	A=LI()

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

	l=2
	r=2

	for i in range(n-2,-1,-1):
		l=((l-1)//A[i]+1)*A[i]
		r=((r+A[i+1]-1)//A[i])*A[i]
		if l>r:
			print(-1)
			exit()

	print(l,r+A[0]-1)
















if __name__ == "__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    # from collections import deque
    k = int(input())
    a = list(map(int, input().split()))
    rl = [2, 2]
    ra = a[::-1]

    for i in range(k):
        nxt = []
        nowa = ra[i]
        if (rl[-1] // nowa) - ((rl[0]-1)//nowa) > 0:
            nxt.append((((rl[0]-1)//nowa)+1)*nowa)
            nxt.append((rl[-1]//nowa)*nowa + nowa-1)
        if not nxt:
            print(-1)
            exit()
        rl = nxt

    print("{} {}".format(rl[0], rl[-1]))
resolve()

Submission status: Accepted

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

upper,lower = 2,2

for ai in a[::-1]:
    lower = (1+(lower-1)//ai)*ai
    upper = (1 + upper//ai)*ai -1
    if(upper < lower):
        print(-1)
        exit()
    # print(lower,upper)

print(' '.join(map(str,[lower,upper])))

Submission status: Accepted

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import math

k = readint()
a = readints()

flag = 0
if a[-1]!=2:
    flag = 1

b = 2
c = 2
for i in range(k-1,0,-1):
    b = math.ceil(b/a[i-1]) * a[i-1]
    c = ((c+a[i]-1)//a[i-1]) * a[i-1]
    if c == 0:
        flag = 1
        break
    if b>c:
        flag = 1
        break

c = c+a[0]-1

if flag:
    print(-1)
else:
    print(b,c)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, *A = map(int, read().split())

def f(A):
    low, high = 2, 2
    for x in A[::-1]:
        low += (-low) % x
        high -= (high) % x
        if low > high:
            print(-1)
            return
        low, high = low, high+(x-1)
    print(low, high)

f(A)

Submission status: Accepted

Solution code:
#AGC020-B Ice Rink Game
"""
逆操作を考える。
何人組を作るということは、modにおける最大値と最小値を求め続けるということ。
そのような組が作れないような場合(全員が脱落するような場合)は、-1を出力。
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

k = int(readline())
lst1 = list(map(int,readline().split()))
lst1.reverse()
if lst1[0] != 2:
    print(-1)
    exit()


def min_lot(value,unit):
    if value%unit == 0:
        return value//unit
    else:
        return value//unit + 1
mn = 2
mx = 3
for i in range(1,k):
    res = min_lot(mn,lst1[i])

    if not mn <= res*lst1[i] <= mx:
        print(-1)
        exit()

    mn = res*lst1[i]

    lim = (mx//lst1[i] + 1)*lst1[i] - 1
    mx = lim



print(mn,mx)

Submission status: Accepted

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

m = [0]*K
M = [0]*K
m[K-1] = 2
M[K-1] = 3
if S[K-1] != 2:
    print(-1)
else:
    for i in range(K-2, -1, -1):
        if m[i+1]%S[i] == 0:
            m[i] = m[i+1]
        else:
            m[i] = m[i+1]+S[i]-(m[i+1]%S[i])
        if M[i+1]%S[i] == 0:
            M[i] = M[i+1]+S[i]-1
        else:
            M[i] = (M[i+1]//S[i])*S[i]+S[i]-1
        if m[0] > M[0]:
            print(-1)
            break
    else:
        print(m[0], M[0])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

    # ラウンドiにおける通過者を保存
    m = 2
    M = 2
    for i in range(K - 1, -1, -1):
        n = (m + A[i] - 1) // A[i]
        tmp_m = n * A[i]
        tmp_M = (M // A[i]) * A[i] + A[i] - 1
        if tmp_m > M or tmp_M < m:
            print(-1)
            return
        m = tmp_m
        M = tmp_M

    print(m, M)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    K = int(input())
    A = list(map(int, input().split()))
    min_ch = 2
    max_ch = 3
    if A[-1] != 2:
        print(-1)
        return
    for i in range(K):
        n = K - i - 1
        if max_ch < A[n]:
            print(-1)
            return
        a = math.ceil(min_ch / A[n])
        b = math.floor(max_ch / A[n])
        min_ch = A[n] * a
        if min_ch > max_ch:
            print(-1)
            return
        max_ch = A[n] * (b + 1) - 1
    print(min_ch, max_ch)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import ceil
k = int(input())
A = list(map(int,input().split()))[::-1]
if A[0]!=2:
    print(-1)
    exit()
flg = True
ans = [2,3]
for i in range(1, k):
    a = A[i]
    m = a*ceil(ans[0]/a)
    if m>ans[1]:
        flg = False
        break
    else:
        ans = [m,a*(ans[1]//a+1)-1]
if flg:
    print(*ans)
else:
    print(-1)