Wow. This problem is really cool. Try using the naive method and you're sure to get TLE#26.
Well, my solution(AC 0.234) goes this way:

if the first term is not 1 then the ans is 1.
if the first i terms are 1<<0, 1<<1, 1<<2, ... 1<<(i-1) then all numbers from 1 to (1<<i) - 1 can be expressed as a sum of some of the above terms. Thus if a number k is present all numbers from k to k+((1<<i) - 1) can be skipped. Proceed using this approach.

By the way 1<<i represents pow(2, i).

7
1 2 3 4 5 6 22

answer is 44


2
1 3
answer is 2

Try tist test:
5
1 2 4 8 16

Right answer is 32 ))))

i've got test for this program

3
3 5 9

if answer of my program is "4" site accept my program.
But the right answer is "1"!!! is it right?

Edited by moderator 03.04.2013 12:40

My first program gives right answers for all the extremal tests, that I think out for my AC program, but it can not pass this test with diagnosis "Crash (access violation)". Why? What checks this test?

Edited by author 30.01.2013 01:45

I have AC

Edited by author 10.11.2007 01:29

# include <iostream>
using namespace std;
main()
{
    int n,b[100];
    int i,max=0;
    cin>>n;
    for(i=0;i<n;i++) cin>>b[i];
    for(i=0;i<n;i++)
    {
        if(b[i]>max+1)
        {cout<<max+1;return 0;}
        else
            max+=b[i];
    }
    cout<<max+1;
    return 0;
}

Edited by author 22.10.2008 22:13

http://timus.h17.ru/

Edited by author 06.02.2007 03:15

Can any one tell me how to solve this problem using greedy approach pls..?

I have TLE test16. Why?

56
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 100000 131072 200000 262144 300000 400000 500000 524288 600000 700000 800000 900000 900001 900002 900003 900004 900005 900006 900007 900008 900009 900010 900011 900012 900013 900014 900015 900016 999000 999001 999002 999003 999004 999005 999006 999007 999008 999009  1000000

admin please add this test case. many programs (for example mine) can't paass it.

Does it means that first bancknot must be 1?
or if doesn't is 1 correct answer when first(d[1]) isn't 1?

Does that mean I cann't use same banknote more than once (ie. to make 2 I can/cann't use twice banknote 1?)?