2013
12-21

# The Balance

Now you are asked to measure a dose of medicine with a balance and a number of weights. Certainly it is not always achievable. So you should find out the qualities which cannot be measured from the range [1,S]. S is the total quality of all the weights.

The input consists of multiple test cases, and each case begins with a single positive integer N (1<=N<=100) on a line by itself indicating the number of weights you have. Followed by N integers Ai (1<=i<=N), indicating the quality of each weight where 1<=Ai<=100.

For each input set, you should first print a line specifying the number of qualities which cannot be measured. Then print another line which consists all the irrealizable qualities if the number is not zero.

3
1 2 4
3
9 2 1

0
2
4 5

#include <cstdio>
#include <cstring>
using namespace std;

int vis[10005];
int x[10005];
int dp[10005];
int abs(int x)
{
return x<0?-x:x;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(vis,0,sizeof(vis));
memset(dp,0,sizeof(dp));
int sum=0,cnt=0;
vis[0]=1;
for(int i=1;i<=n;i++)
{
scanf("%d",&x[i]);
sum+=x[i];
}
for(int i=1;i<=n;i++)
{
memset(dp,0,sizeof(dp));
for(int j=0;j<=sum;j++)
{
if(vis[j])
{
dp[j+x[i]]=1;
dp[abs(j-x[i])]=1;
}
}
for(int j=0;j<=sum;j++)
if(dp[j])vis[j]=1;
}

for(int i=1;i<=sum;i++)
{
if(!vis[i])cnt++;
}

bool first=false;

printf("%d\n",cnt);

for(int i=1;i<=sum;i++)
{
if(!vis[i])
{
if(!first)
{
printf("%d",i);
first=true;
}
else printf(" %d",i);
}
}

if(cnt)puts("");
}
}

1. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count