Kolikot

 
 
 
 
 
 
import itertools
import math
 
raw_input()
coins = sorted([int(x) for x in raw_input().split(" ")])
 
#def viableFor(money, coinsData):
#    result = []
#    for coin in coinsData:
#        if coin < money:
#            result.append(coin)
#        elif coin == money:
#            return [coin]
#        else:
#            return result
#    return result
 
def bsearch(a, b, v, orig=False):
    if coins[a] == v:
        return a
    elif coins[b] == v:
        return b
    elif coins[b] < v and orig:
        return b
    elif b - a == 1:
        if coins[a] < v and coins[b] > v:
            return a
    else:
        middle = a + (b-a)//2
        if coins[middle] > v:
            return bsearch(a, middle, v)
        elif coins[middle] < v:
            return bsearch(middle, b, v)
        else:
            return middle
 
def findSum(money):
    s = 0
    previousIndex = len(coins)-1
    while previousIndex > -1:
        index = bsearch(0, previousIndex, money-s, True)
        if index != None:
            s = s + coins[index]
            if s == money:
                return True
            previousIndex = index - 1
        else:
            return False
 
def binarize(combinations):
    x = 1
    while 2**x in combinations:
        x = x + 1
    return 2**x
 
if coins[0] > 1:
    print("1")
else:
    i = binarize(coins)
    #maxval = sum(coins)
 
    while True:
        #print(i)
        if not findSum(i):
            break
        i = i + 1
 
    print(i)

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED