Uva 10036 - Divisibility
Consider an arbitrary sequence of integers. One can place + or - operators between integers in the sequence, thus deriving different arithmetical expressions that evaluate to different values. Let us, for example, take the sequence: 17, 5, -21, 15. There are eight possible expressions:
17 + 5 + -21 + 15 = 16
17 + 5 + -21 - 15 = -14
17 + 5 - -21 + 15 = 58
17 + 5 - -21 - 15 = 28
17 - 5 + -21 + 15 = 6
17 - 5 + -21 - 15 = -24
17 - 5 - -21 + 15 = 48
17 - 5 - -21 - 15 = 18
We call the sequence of integers divisible by K if + or - operators can be placed between integers in the sequence in such way that resulting value is divisible by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14) but is not divisible by 5. You are to write a program that will determine divisibility of sequence of integers.
Input
The first line of the input file contains a integer M indicating the number of cases to be analyzed. Then M couples of lines follow. For each one of this couples, the first line of the input file contains two integers, N and K (1 ≤ N ≤ 10000, 2 ≤ K ≤ 100) separated by a space. The second line contains a sequence of N integers separated by spaces. Each integer is not greater than 10000 by it’s absolute value
Output
For each case in the input file, write to the output file the word ‘Divisible’ if given sequence of integers is divisible by K or ‘Not divisible’ if it’s not.
Sample Input
2
4 7
17 5 -21 15
4 5
17 5 -21 15
Sample
Output Divisible
Not divisible
题目大意:给n个数,在这n个中放上‘+’ ‘-’使得结果能被k整除。
dp[i][j]表示 前i个数余数j 是否可能
/* ***********************************************
Author :guanjun
Created Time :2016/9/6 15:25:54
File Name :uva10036.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 10010
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << ;
const double eps=1e-;
using namespace std;
priority_queue<int,vector<int>,greater<int> >pq;
struct Node{
int x,y;
};
struct cmp{
bool operator()(Node a,Node b){
if(a.x==b.x) return a.y> b.y;
return a.x>b.x;
}
}; bool cmp(int a,int b){
return a>b;
}
int dp[maxn][];
int a[maxn];
int main()
{
#ifndef ONLINE_JUDGE
//freopen("in.txt","r",stdin);
#endif
//freopen("out.txt","w",stdout);
int t,n,k;
cin>>t;
while(t--){
scanf("%i %i",&n,&k);
for(int i=;i<=n;i++)scanf("%i",&a[i]),a[i]=abs(a[i]%k);
cle(dp);
dp[][]=;
for(int i=;i<=n;i++){
for(int j=;j<k;j++){
if(dp[i][j]){
dp[i+][(j-a[i]+k)%k]=;
dp[i+][(j+a[i])%k]=;
}
}
}
if(dp[n+][])puts("Divisible");
else puts("Not divisible");
}
return ;
}
。
最新文章
- [Linux]使用PHP编写Gearman的Worker守护进程
- SSH框架整合项目(一)——搭建平台和引入依赖
- 企业架构(Enterprise Architecture)
- kindeditor用法
- HBase的完全分布式的搭建与部署,以及多master
- java将数组中的零放到末尾
- WPF--Calendar控件高级使用
- OS Kernel Parameter.semopm
- python实现的文本编辑器 - Skycrab - 博客频道 - CSDN.NET
- [Swust OJ 767]--将军回家(Dijkstra算法)
- (二十一)unity4.6学习Ugui中文文档-------交互-Supported Events &;amp; Raycasters
- Cocos2d-x实现Android的Toast特征
- MVC 5 + EF6 完整教程16 -- 控制器详解
- 不解释,分享这个base.css
- jquery实现上下滑动选择
- Session 与 Token 的区别
- ViewPager结合view无限滑动
- faster rcnn训练自己的数据集
- linux中时间命令详解
- 【Sql】经典sql语句
热门文章
- 【百度编辑器ueditor】工具,如何去掉百度编辑器 ueditor 元素路径、字数统计等
- LeetCode第63题--不同路径
- Spring Boot 创建hello world项目
- JPA @MappedSuperclass注解
- Android studio升级后原有项目无法正常编译运行问题
- 洛谷——P2054 [AHOI2005]洗牌(扩展欧几里得,逆元)
- BZOJ 3648 寝室管理
- 线程 synchronized锁机制
- 解决maven无法加载本地lib/下的jar包问题(程序包XXX不存在)
- Spring MVC学习总结(8)——Swagger入门详解