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: Runtime Error

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 = (b+t) - (b%t)
        else:
            b = t
        if c % t == 0:
            pass
        elif c > t:
            c = (c+t) - (c%t)
        else:
            return -1
    bb = b
    cc = c-1
    for i in range(n):
        bb -= bb%a[i]
        cc -= cc%a[i]
    if bb != 2:
        return 1 / 0
    if cc != 2:
        while 1:
            cc += 1

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

print(main())

Submission status: Runtime Error

Solution code:
import math
K=input()
A=[]
A=map(int, raw_input().split())
max_N =2 
N_min = 2
N_max = 2
min_frag=0
del_count =0 
for i in range(K-1):
          if A[K-i-1] == A[K-i-2]:
                del A[K-i-1]
                del_count += 1
for  i in range(K-del_count):
     max_N = max_N+A[K -del_count-i-1]-1 

for i in range(max_N):
       number = i+1
       for j in range(K-del_count):
              loss =  number % A[j]
              number = number - loss      
       if number == 2:
              if min_frag == 0:
                   N_min = i+1 
                   min_frag = 1
              N_max = i+1
if min_frag == 0:
       print -1
else:
       print N_min,N_max

Submission status: Runtime Error

Solution code:
# cook your dish here
from math import * 
#for _ in range(int(input().strip())):

def isvalid(l):
    n=len(l)
    if l[-1]!=2:
        return 0
    for i in range(n-2,-1,-1):
        if l[i]>=2*l[i+1]:
            return 0
    return 1

n=int(input())
l=[int(x) for x in input().split()]
if n>2:
    l2=l[:2]+l[2:]
f=isvalid(l)
if f==0:
    print("-1")
else:
    if n==1:
        print(l[0],l[0]*2-1)
        exit(0)
    if n==2:
        print(l[0],l[0]*2-1)
        exit(0)
    for i in range(n-2,-1,-1):
        ans=l[i]*ceil(l[i+1]/l[i])
        l[i]=ans
    #for ele in l:
     #   print(ele,end=" ")
    var2=l[n-3]
    for i in range(n-2,0,-1):
        var1=l2[i]*((var2//l2[i])+1) - 1 
        var2=l2[i-1]*(var1//l2[i-1])
    var2 = l2[0]*((var2//l2[0])+1)  - 1  
    #print(var2)
print(ans,var2)

Submission status: Runtime Error

Solution code:
# -- coding: utf-8 --
from math import ceil
round_no = int(input())
args = list(map(int, input().split(' ')))[::-1]
cand_min = 3
if args[0] == 2 and args[1] <= 3:
    for i in range(2, len(args)):
        if args[i] >= 0b10 | 0b1 << i:
            cand_min = -1
            break

        if args[i-1] <= args[i]:
            cand_min = args[i]
        else:
            cand_min = ceil(cand_min/args[i]) * args[i]
else:
    cand_min = -1


if cand_min == -1:
    print(cand_min)
else:
    cand_max = cand_min + args[-1] - 1
    print(str(cand_min) + ' ' + str(cand_max))

Submission status: Runtime Error

Solution code:
# cook your dish here
from math import * 
#for _ in range(int(input().strip())):

def isvalid(l):
    n=len(l)
    if l[-1]!=2:
        return 0
    for i in range(n-2,-1,-1):
        if l[i]>=2*l[i+1]:
            return 0
    return 1

n=int(input())
l=[int(x) for x in input().split()]
l2=l[:2]+l[2:]
f=isvalid(l)
if f==0:
    print("-1")
else:
    if n==1:
        print(l[0],l[0]*2-1)
        exit(0)
    if n==2:
        print(l[0],l[0]*2-1)
        exit(0)
    for i in range(n-2,-1,-1):
        ans=l[i]*ceil(l[i+1]/l[i])
        l[i]=ans
    #for ele in l:
     #   print(ele,end=" ")
    var2=l[n-3]
    for i in range(n-2,0,-1):
        var1=l2[i]*((var2//l2[i])+1) - 1 
        var2=l2[i-1]*(var1//l2[i-1])
    var2 = l2[0]*((var2//l2[0])+1)  - 1  
    #print(var2)
print(ans,var2)

Submission status: Runtime Error

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

if k == 1:
  if a[0] == 2:
    print(2, 3)
  else:
    print(-1)
  exit(1)

temp = a[-1]
for i in reversed(range(k-1)):
  if a[i] >= temp:
    temp = a[i]
  else:
    temp = (temp//a[i] + (temp%a[i] != 0))*a[i]

ans = temp

for data in a:
  temp -= temp%data

if temp == 2:
  s = int(ans/a[1]+1)*a[1]
  if s%a[0] != a[0]-1:
    s -= s%a[0] + 1
  print(ans, s)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
# -- coding: utf-8 --
from math import ceil
round_no = int(input())
args = list(map(int, input().split(' ')))[::-1]
cand_min = 3
if args[0] == 2 and args[1] == 3:
    for i in range(2, len(args)):
        if args[i] >= 0b10 | 0b1 << i:
            cand_min = -1
            break

        if args[i-1] <= args[i]:
            cand_min = args[i]
        else:
            cand_min = ceil(cand_min/args[i]) * args[i]
else:
    cand_min = -1


if cand_min == -1:
    print(cand_min)
else:
    cand_max = cand_min + args[-1] - 1
    print(str(cand_min) + ' ' + str(cand_max))

Submission status: Runtime Error

Solution code:
# cook your dish here
from math import * 
#for _ in range(int(input().strip())):

def isvalid(l):
    n=len(l)
    if l[-1]!=2:
        return 0
    for i in range(n-2,-1,-1):
        if l[i]>=2*l[i+1]:
            return 0
    return 1

n=int(input())
l=[int(x) for x in input().split()]
l2=l[:2]+l[2:]
f=isvalid(l)
if f==0:
    print("-1")
else:
    if n==2:
        print(l[0],l[0]*2-1)
        exit(0)
    for i in range(n-2,-1,-1):
        ans=l[i]*ceil(l[i+1]/l[i])
        l[i]=ans
    #for ele in l:
     #   print(ele,end=" ")
    var2=l[n-3]
    for i in range(n-2,0,-1):
        var1=l2[i]*((var2//l2[i])+1) - 1 
        var2=l2[i-1]*(var1//l2[i-1])
    var2 = l2[0]*((var2//l2[0])+1)  - 1  
    #print(var2)
print(ans,var2)

Submission status: Runtime Error

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

if l == 1:
  if a[0] == 2:
    print(2, 3)
  else:
    print(-1)
  exit(1)

temp = a[-1]
for i in reversed(range(l)):
  if a[i] >= temp:
    temp = a[i]
  else:
    temp = (temp//a[i] + (temp%a[i] != 0))*a[i]

ans = temp

for data in a:
  temp -= temp%data

if temp == 2:
  s = int(ans/a[1]+1)*a[1]
  if s%a[0] != a[0]-1:
    s -= s%a[0] + 1
  print(ans, s)
else:
  print(-1)

Submission status: Runtime Error

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

temp = a[-1]
for i in reversed(range(l-1)):
  if a[i] >= temp:
    temp = a[i]
  else:
    temp = (temp//a[i] + (temp%a[i] != 0))*a[i]

ans = temp

for data in a:
  temp -= temp%data

if temp == 2:
  s = int(ans/a[1]+1)*a[1]
  if s%a[0] != a[0]-1:
    s -= s%a[0] + 1
  print(ans, s)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import math
K=input()
A=[]
A=map(int, raw_input().split())
max_N =2 
N_min = 2
N_max = 2
min_frag=0
del_count =0 
for i in range(K-2):
          if A[K-i-1] == A[K-i-2]:
                del A[K-i-2]
                del_count += 1
for  i in range(K-del_count):
     max_N = max_N+A[K -del_count-i-1]-1 

for i in range(max_N):
       number = i+1
       for j in range(K-del_count):
             if number >A[j]:
              loss =  number % A[j]
              number = number - loss      
             else:
              number = 0    
       if number == 2:
              if min_frag == 0:
                   N_min = i+1 
                   min_frag = 1
              N_max = i +1
if min_frag == 0:
       print -1
else:
       print N_min,N_max

Submission status: Runtime Error

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

def solve():

    if k == 1:
        if a[0] == 2:
            print(2, 3)
            return
        else:
            print(-1)
            return

    can = []

    for i in range(k):

        if i==0:
            can = [2]
        elif i > 1 and i != k-1:
            if a[k-i-1] == a[k-(i-1)-1]:
                continue

        oldcan = can[:]
        can = []

        if i == k-1:
            can = list(range(min(oldcan), max(oldcan) + a[k-i-1]))
        else:
            j = i+1
            mi = min(oldcan)
            mx = max(oldcan) + a[k-i-1] -1
            if mx < a[k-j-1]:
                print(-1)
                return
            #print(mi, mx)
            if mi%a[k-j-1] != 0:
                mi = mi + (a[k-j-1] - mi%a[k-j-1])
            if mx%a[k-j-1] != 0:
                mx = mx - mx % a[k-j-1]
            can = [mi, mx]

        # if len(can) == 0:
        #     print(-1)
        #     return
            #print(i, can, oldcan)
        # for c in oldcan:
        #     for a__ in range(c,c+a[k-i-1]):
        #         if i == k-1:
        #             if a__ not in can:
        #                 can.append(a__)
        #         else:
        #             if a__ not in can and a__ % a[k-(i+1)-1] == 0:
        #                 can.append(a__)

    print(min(can), max(can))
solve()

Submission status: Runtime Error

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

after_nparticipant = [2, 3]
before_nparticipant = []
for i in reversed(range(K)):
  if A[i] > max(after_nparticipant):
    is_possible = False
    break

  for n in after_nparticipant:
    if max(n, A[i]) % min(n, A[i]) == 0:
      if n > A[i]:
        for j in range(A[i]):
          before_nparticipant.append(n + j)
      else:
        for j in range(A[i]):
          before_nparticipant.append(A[i] + j)
      break
  
  after_nparticipant = before_nparticipant
  before_nparticipant = []

if is_possible:
  print (str(min(after_nparticipant)) + " " + str(max(after_nparticipant)))
else:
  print (-1)

Submission status: Runtime Error

Solution code:
import math
K=input()
A=[]
A=map(int, raw_input().split())
max_N =2 
N_min = 2
N_max = 2
min_frag=0
del_count =0 
for i in range(K-2):
          if A[K-i-1] == A[K-i-2]:
                del A[K-i-2]
                del_count += 1
for  i in range(K-del_count):
     max_N = max_N+A[K -del_count-i-1]-1 

for i in range(max_N):
       number = i+1
       for j in range(K-del_count):
             loss =  number % A[j]
             number = number - loss          
       if number == 2:
              if min_frag == 0:
                   N_min = i+1 
                   min_frag = 1
              N_max = i +1
if min_frag == 0:
       print -1
else:
       print N_min,N_max

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# coding: utf-8

import numpy as np

def slove(k, a):
    a = np.array(a, dtype=np.uint32)

    if a[-1] > 3 or a[-2] > 3:
        return -1

    b = a[1:]
    b = np.append(b, 0)
    b *= 2
    diff = a - b

    if (diff[:-1] > 0).any():
        return -1

    minNum = a[0]
    while (minNum < a.max()):
        minNum *= 2

    maxNum = minNum + a[0] - 1

    return ("{0} {1}".format(minNum, maxNum))


if __name__ == "__main__":
    k = int(input())
    a = input().split(" ")

    print(slove(k, a))

Submission status: Runtime Error

Solution code:
import math
K=input()
A=[]
A=map(int, raw_input().split())
max_N =2 
N_min = 2
N_max = 2
min_frag=0
del_count =0 
if K > 1:
    for i in range(K-2):
          if A[K-i-1] == A[K-i-2]:
                del A[K-i-1]
                del_count += 1
for  i in range(K-del_count):
     max_N = max_N+A[K -del_count-i-1]-1 

for i in range(max_N):
       number = i+1
       for j in range(K-del_count):
             loss =  number % A[j]
             number = number - loss          
       if number == 2:
              if min_frag == 0:
                   N_min = i+1 
                   min_frag = 1
              N_max = i +1
if min_frag == 0:
       print -1
else:
       print N_min,N_max

Submission status: Runtime Error

Solution code:
import math
K=input()
A=[]
A=map(int, raw_input().split())
max_N =2 
N_min = 2
N_max = 2
min_frag=0
del_count =0 
if K > 1:
    for i in range(K-2):
          if A[K-i-1] == A[K-i-2]:
                del A[K-i-1]
                del_count += 1
for  i in range(K-del_count):
     max_N = max_N+A[K -del_count-i-1]-1 

for i in range(max_N):
       number = i+1
       for j in range(K-del_count):
             loss =  number % A[j]
             number = number - loss          
       if number == 2:
              if min_frag == 0:
                   N_min = i+1 
                   min_frag = 1
              N_max = i +1
print A
if min_frag == 0:
       print -1
else:
       print N_min,N_max

Submission status: Runtime Error

Solution code:
import math
K=input()
A=[]
A=map(int, raw_input().split())
max_N =2 
N_min = 2
N_max = 2
min_frag=0
del_count =0 
if K > 1:
    for i in range(K-1):
          if A[K-i-1] == A[K-i-2]:
                del A[K-i-1]
                del_count += 1
for  i in range(K-del_count):
     max_N = max_N+A[K -del_count-i-1]-1 
if max_N >2:
   for i in range(max_N):
       number = i+1
       for j in range(K-del_count):
             loss =  number % A[j]
             number = number - loss
           
       if number == 2:
              if min_frag == 0:
                   N_min = i +1 
                   min_frag = 1
              N_max = i +1
if min_frag == 0:
       print -1
else:
       print N_min,N_max

Submission status: Runtime Error

Solution code:
import math
K=input()
A=[]
A=map(int, raw_input().split())
max_N =2 
N_min = 2
N_max = 2
min_frag=0
del_count =0 
if K > 1:
    for i in range(K-1):
          if A[K-i-1] == A[K-i-2]:
                del A[K-i-1]
                del_count += 1
for  i in range(K-del_count):
     max_N = max_N+A[K -del_count-i-1]-1 
for i in range(max_N):
     number = i
     for j in range(K-del_count):
            number = number - number % A[j]
           
     if number == 2:
            if min_frag == 0:
                   N_min = i
                   min_frag = 1
            N_max = i
if min_frag == 0:
       print -1
else:
       print N_min,N_max

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# coding: utf-8

def slove(k, a):
    if int(a[-1]) > 3 or int(a[-2]) > 3:
        return -1

    for i in range(k-1):
        left = int(a[i])
        right = int(a[i+1])
        if left >= 2*right:
            return -1

    minNum = int(a[0])
    while (minNum < int(a[1])):
        minNum *= 2

    maxNum = minNum + int(a[0]) - 1

    return ("{0} {1}".format(minNum, maxNum))


if __name__ == "__main__":
    k = int(input())
    a = input().split(" ")

    print(slove(k, a))

Submission status: Runtime Error

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

    # min
    min_target_nums = [2]
    max_target_nums = [2]
    for a in reversed(A):
        min_targets = [_ for _ in min_target_nums if _ % a == 0]
        max_targets = [_ for _ in max_target_nums if _ % a == 0]
        if len(min_targets) == 0:
            print(-1)
            exit()
        min_target = min(min_targets)
        max_target = max(max_targets)

        target_nums = [_ for _ in range(a)]
        min_target_nums = list(map(lambda x: x + min_target, target_nums))
        max_target_nums = list(map(lambda x: x + max_target, target_nums))

    print(str(min(min_target_nums)) + " " + str(max(max_target_nums)))

Submission status: Runtime Error

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

    

temp = a[-1]
for i in reversed(range(l-1)):
  if a[i] >= temp:
    temp = a[i]
  else:
    temp = (temp//a[i] + (temp%a[i] != 0))*a[i]

print(temp, temp+a[0]-1)

Submission status: Runtime Error

Solution code:
import math
K=input()
A=[]
A=map(int, raw_input().split())
max_N =2 
N_min = 2
N_max = 2
min_frag=0
for  i in range(K):
     max_N = max_N+A[K-i-1]-1 
for i in range(max_N):
     number = i
     for j in range(K):
            number = number /A[j]
     if number == 2:
            if min_frag == 0:
                   N_min = i
                   min_frag = 1
            N_max = i
if min_frag == 0:
       print -1
else:
       print N_min,N_max

Submission status: Runtime Error

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: Runtime Error

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

def solve():
    can = []
    res = []

    for i in range(k):
        a_ = a[k-i-1]

        if i==0:
            res = [2]
        else:
            res = []
            for c in can:
                if c % a_ == 0:
                    res.append(c)
            if len(res) == 0:
                print(-1)
                return

        can = []
        for r in res:
            can = can + list(range(r, r+a_))
            can = list(set(can))

        #print(i, res, a_, can)
    print(min(can), max(can))
solve()

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# coding: utf-8


def slove(k, a):
    if int(a[-1]) > 3 or int(a[-2]) > 3:
        return -1

    num = 0
    index = -2
    for i in range(k-1):
        if i != k-2:
            if 2*int(a[index]) < int(a[index-1]):
                return -1
        if int(a[index]) > 2:
            tmp = int(a[index])
            if tmp > num:
                num = tmp
            else:
                while (tmp < num):
                    tmp *= 2
                num = tmp
        index -= 1

    if num == 0:
        minNum = 2
        maxNum = 3
    else:
        minNum = num
        maxNum = num + int(a[0]) - 1

    return ("{0} {1}".format(minNum, maxNum))




if __name__ == "__main__":
    k = int(input())
    a = input().split(" ")

    print(slove(k, a))

Submission status: Runtime Error

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

assert A_lst[-1]==2
stt, end=2,4
failed=False
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: Runtime Error

Solution code:
K = int(input())
A = list(map(int,input().split()))
a = K-1
p = 2
while 0 <= a:
    if A[a-1] > A[a]*2:
        print('-1')
        exit()
    num = 1
    if A[a] < p:
        while A[a]*num < p:
            num += 1
    p = num*A[a]
    a -= 1
pmax = p
while pmax < A[1]*2:
    pmax += A[0]
pmax -= A[0]
print(p,pmax)

Submission status: Runtime Error

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

if a[-1] != 2:
    print(-1)
else:
    n = 2
    flag = 0
    for i in range(k-2, -1, -1):
        if a[i+1] <= a[i]:
            if n <= a[i] <= n*2-1:
                n = a[i]
            else:
                flag = 1
                break
        else:
            n = a[i] * (int(a[i+1] / a[i])+1)

if flag == 0:
    print(n, n+a[0]-1)
else:
    print(-1)

Submission status: Runtime Error

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

can = []
res = []

def solve():

    for i in range(k):
        a_ = a[k-i-1]

        if i==0:
            res = [2]
        else:
            res = []
            for c in can:
                if c % a_ == 0:
                    res.append(c)
            if len(res) == 0:
                print(-1)
                return

        can = []
        for r in res:
            can = can + list(range(r, r+a[k-i-1]))

        #print(i, res, a_, can)
    print(min(can), max(can))
solve()

Submission status: Runtime Error

Solution code:
#include <cstdio>
#include <vector>   
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <iomanip>
#include <deque>
#include <cstring>

using namespace std;

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int k;
    scanf("%d", &k);
    vector<long long> a(k);
    for (int i = 0; i < k; i++)
        scanf("%lld", &a[i]);
    long long mn = 2, mx = 2;
    for (int i = k - 1; i >= 0; i--) {
        mx -= mx % a[i];
        mn += (a[i] - mn % a[i]) % a[i];
        if (mn > mx) {
            printf("-1");
            return 0;
        }
        mx += a[i] - 1;
    }
    printf("%lld %lld\n", mn, mx);
}