/*DFS

2012亚洲区域赛长春赛区现场赛C题

Date: 2012/10/14

题目链接地址：

一开始因为题目理解错误（以为是题目错了）导致wa了n次，后来在看了n遍题目之后

恍然大悟，输入的是Alice已经去过的山和摘的蘑菇数，没有去过的山Alice可能去摘

也可能不去摘，去摘的话，摘的数量是在[0,2012]之间的

这样让你求Alice回家能带的最大蘑菇数量

思路：

1.当n = 0,1,2,3时，最大值应该是1024,比如n = 3,假设摘的数分别为a,b,c;

那么任选其中两个数比如a,b再加上[0,2012]之间的数肯定能把这三个数之和凑成1024的倍数，

就把装这三个数的袋子给three mischievous fairies，然后还剩下c，c加上[0,2012]之间

一个数肯定能把这两个数凑成1024的倍数，多的给Marisa偷去了，所以能剩下1024

2.当n = 4时，有两种情况 (1),若其中三个数之和是1024的倍数，则同上

                                  (2),若不能，则可以选其中两个加上[0,2012]之间

                                      的数凑成1024的倍数给three mischievous fairies，剩下的两个数

                                      之和如果小于1024的话，就是要求的答案，若大于则减去1024 直到

                                     小于1024

所以当n = 4的时候枚举一下上述情况就好，具体见代码

3.当n = 5时，其实也是枚举，用dfs枚举任意其中任意三个（如果是1024倍数的话），那就剩下两数

之和去掉多余1024的部分，求其中的最大值

还剩一个数再加上

*/

#include
     
      using namespace std;#define INF 0x3f3f3f3f#define maxn 10int sum,count,flag,n,arr[maxn];bool visited[maxn];void dfs(int i,int s,int num){    int t;    if(num == 3 && s%1024 == 0)    {        flag = 1;        t = sum-s;        while(t > 1024)            t -= 1024;        if(count < t)            count = t;        return;    }    if(flag && sum - s <= count)  return;    visited[i] = true;    for(int j = 1; j <= 5; j++)        if(!visited[j])        {            dfs(j,s+arr[j],num+1);        }        visited[i] = false;}int main(){    //freopen("1003.txt","r",stdin);    while(cin >> n)    {        int i,j,k,m;        count = sum = 0;        for(i = 1; i <= n; i++)        {            cin >> arr[i];            sum += arr[i];        }        if(n == 0 || n == 1 || n == 2 || n == 3)          {            cout << 1024 << endl;        }        else if(n == 4)        {            int num;            flag = 1;            for(i = 1; i <= 4 && flag; i++)                for(j = 1; j <= 4 && flag; j++)                    for(k = 1; k <= 4 && flag; k++)                        if((k!=i) && (k!=j) && (j!=i))                        {                            num = arr[i]+arr[j] +arr[k];                            if(num % 1024 == 0)                            {                                flag = 0;                                count = 1024;                                break;                            }                        }            if(!flag)            {                cout << count << endl;                continue;            }            for(i = 1; i <= 4; i++)                for(j = 1; j <= 4; j++)                {                    if(i != j)                    {                        num = arr[i]+arr[j];                        while(num > 1024) num -= 1024;                        if(num > count)                         {                            count = num;                        }                    }                }                cout << count << endl;        }        else         {            for(i = 1; i <= 5; i++)            {                for(j = 1; j <= 5; j++)  visited[j] = false;                flag = 0;                dfs(i,arr[i],1);            }            cout << count << endl;        }        }    return 0;}