The Balance
2024-10-13 06:24:03
The Balance |
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
Total Submission(s): 135 Accepted Submission(s): 88 |
Problem Description
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.
|
Input
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.
|
Output
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.
|
Sample Input
3 |
Sample Output
0 |
Source
HDU 2007-Spring Programming Contest
|
Recommend
lcy
|
/*
题意:给出n个砝码的质量,让你求出在[1,s]范围内不能组成的质量,s是质量总和,这个题不一样的地方是天平两边都可以放砝码 初步思路:可以看成一个背包问题,每个取或不取,但是这个题有一个新的状态,就是
*/
#include<bits/stdc++.h>
using namespace std;
int v[];
int dp[];//dp[i]表示i金额能组成或不能组成
int vis[];//记录一下能组成的金额
int n;
int s=;
void init(){
memset(vis,,sizeof vis);
memset(dp,,sizeof dp);
s=;
}
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
init();
for(int i=;i<=n;i++){
scanf("%d",&v[i]);
s+=v[i];
}
vis[]=;
for(int i=;i<=n;i++){
memset(dp,,sizeof dp);
for(int j=;j<=s;j++){
if(vis[j]){//j金额能组成
dp[j+v[i]]=;//加上当前金额那么也是可以的
dp[abs(j-v[i])]=;//减去这个金额的也是可以的
}
}
for(int j=;j<=s;j++){
if(dp[j]) vis[j]=;
}
}
int res=;
for(int i=;i<=s;i++)
if(!vis[i])
res++;
printf("%d\n",res);
if(res==) continue;
int f=;
for(int i=;i<=s;i++){
if(!vis[i]){
if(f==){
printf("%d",i);
f=;
}else{
printf(" %d",i);
}
}
}
printf("\n");
}
return ; }
最新文章
- 求n!最后一位非零数
- UISearchController使用
- Python3基础 reverse 将列表倒序排列
- sql datetime操作
- MVC 登录认证与授权及读取登录错误码
- archlinux安装输入法需要的包及archlinux无法使用输入法的解决
- cf(#div1 B. Dreamoon and Sets)(数论)
- BZOJ2721 [Violet 5]樱花
- LeetCode Path Sum II (DFS)
- fastjson生成和解析json数据
- CSS3几个速记标签2
- OC - 14.NSOperation与NSOperationQueue
- 解压版本 Tomcat配置--转
- Java多线程:CopyOnWrite容器
- CRM 员工创建并分配用户
- JavaScript动态加载CSS和JS文件
- 2016年蓝桥杯省赛A组c++第8题(暴力求解)
- bzoj 1093 最大半连通子图 - Tarjan - 拓扑排序 - 动态规划
- Intellij 部署项目java.lang.ClassNotFoundException: org.springframework.web.context.ContextLoaderListener
- L3-009 长城 (30 分)