原题传送门:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=977
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 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 分析: DP
#include<cstdio> #include<cstring> int t,n,k,num,cur; bool dp[2][100]; int main(){ scanf("%d",&t); while(t--){ cur = 0; memset(dp,false,sizeof(dp)); dp[0][0] = true; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ cur ^= 1; memset(dp[cur],false,sizeof(dp[cur])); scanf("%d",&num); if(i>1 && num<0) num = -num; num %= k; for(int j=0;j<k;j++){ if(dp[cur^1][j]){ dp[cur][(j+num+k)%k] = true; if(i>1)dp[cur][(j-num+k)%k] = true; } } } printf("%s\n",dp[cur][0]?"Divisible":"Not divisible"); } return 0; }
相关推荐
1.1 Notion of Visibility 1 1.2 Polygon 2 1.3 Asymptotic Complexity 5 1.4 Triangulation 6 1.5 The Art Gallery Problem 8 1.6 Special Types of Visibility 11 2 Point Visibility 13 2.1 Problems and Results...
WPF的bool2Visibility转换器使用
VISIBILITY属性的详解包括VISIBLE、INVISIBLE及GONE区别
Android开发中,大部分控件都有visibility这个属性,其属性有3个分别为“visible ”、“invisible”、“gone”。主要用来设置控制控件的显示和隐藏。
display与visibility的区别
前端项目-visibility.js,Wrapper for the Page Visibility API
Modeling Mutual Visibility Relationship in Pedestrian Detection Modeling Mutual Visibility Relationship in Pedestrian Detection Modeling Mutual Visibility Relationship in Pedestrian Detection
通过绑定修改DataGridColumns的Visibility
CSS隐藏元素 display visibility opacity的区别 display:none和visibility:hidden的区别 对比总结: height:0和overflow:hidden的组合
virtual netflow visibility,my test
Flutter Offstage、Visibility隐藏/可见。
去雾 灰度图 Fast Visibility Restoration from a Single Color or Gray Level Image
JS中style.display和style.visibility的区别实例说明.docx
keyboard_visibility 通知服务,用于软键盘可见性 用法 将依赖项添加到项目的根文件夹中的pubspec.yaml文件中。 查找“ dependencies:”行,并在此行之后添加以下行: keyboard_visibility: any 或者 keyboard_...
Android开发中,大部分控件都有visibility这个属性,其属性有3个分别为“visible ”、“invisible”、“gone”。主要用来设置控制控件的显示和隐藏。1) 可见(visible)XML文件:android:visibility=”visible”Java...
display通常可以设置为none、inline、block visibility通常可以设置为hidden、visible 当display为none,visibility为hidden时,元素都会不见。不过其还有不同之处。 display会将元素隐藏掉,并且位置不再被占据,而...
npm install --save vue-observe-visibility :warning: 该插件使用了并非在所有浏览器中都支持的 (当前在Edge,Firefox和Chrome中受支持)。 您需要包括一个才能使其在不兼容的浏览器上运行。 进口 import Vue ...
大多数人很容易将CSS属性display和visibility混淆,它们看似没有什么不同,其实它们的差别却是很大的。 visibility属性用来确定元素是显示还是隐藏的,这用visibility="visible|hidden"来表示(visible表示显示,...
该方法为在有雾天气下去雾的一种方法,有很高的参考价值
A Survey of Visibility for Walkthrough Applications