原题传送门: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; }
相关推荐
VISIBILITY属性详解 在 Android 开发中,控件的可见性是非常重要的,VISIBILITY 属性就是控制控件的显示和隐藏的。通过设置 VISIBILITY 属性,我们可以控制控件的可见性,达到不同的显示效果。 VISIBLE、INVISIBLE...
`BoolToVisibilityConverter` 是一个内置的数据转换器,它用于将布尔值(`bool`)转换为 `Visibility`枚举类型,这对于根据逻辑状态控制UI元素的可见性非常有用。在本教程中,我们将深入探讨如何使用`...
在Android开发中,`visibility`属性是控制UI组件可见性的重要元素,广泛应用于各种视图控件,如TextView、ImageView、Button等。该属性决定了一个控件是否在屏幕上显示,以及如何显示。`visibility`属性有三个可能的...
### Display与Visibility的区别 在网页布局与样式设计中,`display`与`visibility`属性是控制元素显示状态的两种常用方式。尽管它们都能达到隐藏或显示元素的目的,但两者之间存在本质的区别。本文将深入探讨这两种...
《前端项目中的Page Visibility API与visibility.js库》 在当今的Web开发中,前端性能优化是不可或缺的一部分。其中,理解用户与页面的交互状态对于提升用户体验至关重要。这就是Page Visibility API和`visibility....
return (value is Visibility visibility) && visibility == Visibility.Visible; } } ``` 接下来,你需要在你的XAML资源字典中声明这个转换器: ```xml ``` 这里的`local`是命名空间前缀,需要根据实际...
JS 中 style.display 和 style.visibility 的区别实例说明 在 JavaScript 中,style.display 和 style.visibility 是两种常用的控制元素显隐的方法,但是它们之间有着根本的区别。 style.display style.display ...
在网页设计和开发中,`display` 和 `visibility` 是两个非常重要的CSS属性,它们用于控制元素在页面上的可见性和布局。这篇博客文章通过代码示例深入探讨了这两个属性的区别和用法。 首先,`display` 属性主要用于...
Modeling Mutual Visibility Relationship in Pedestrian Detection Modeling Mutual Visibility Relationship in Pedestrian Detection Modeling Mutual Visibility Relationship in Pedestrian Detection
在CSS中,隐藏元素的方法主要有三种:`display:none`、`visibility:hidden`和`opacity:0`,它们各自有不同的特点和适用场景。 1. `display:none`:此属性会使元素完全从页面布局中消失,不占据任何空间。元素及其...
"satellite visibility_satellite_卫星轨道计算"这个标题暗示我们要讨论的是如何预测和计算卫星在特定地点的可见性,这对于地面站接收信号或者规划卫星任务来说是极其关键的。 首先,卫星的轨道是由它的六根数(也...
Flutter Offstage、Visibility隐藏/可见。
标题“virtual_visibility”和描述“virtual netflow visibility,my test”提及的核心概念是虚拟网络的NetFlow可视性。NetFlow是一种由Cisco系统开发的技术,用于收集、分析和记录网络流量数据,以帮助网络管理员...
keyboard_visibility 通知服务,用于软键盘可见性 用法 将依赖项添加到项目的根文件夹中的pubspec.yaml文件中。 查找“ dependencies:”行,并在此行之后添加以下行: keyboard_visibility: any 或者 keyboard_...
在数学建模领域,"visibility_2020建模_2020数学建模_参数估计_数学建模_Visibility_"这个标题暗示了我们正在探讨2020年数学建模竞赛中的一项任务,特别关注的是“Visibility”问题,这可能涉及对某个系统或现象的...
【content-visibility】属性是CSS中的一个新特性,它允许开发者控制元素是否渲染其内容,以及何时渲染。这个属性能够显著提升网页的初始加载速度,因为它让浏览器可以在内容需要显示之前跳过大量的布局和渲染工作。 ...
在Android开发中,`visibility`属性是控制UI组件(如按钮、文本视图等)是否在屏幕上显示的关键属性。它提供了三个可能的值,每个值都有特定的效果: 1. **可见(Visible)**:当`visibility`设置为`visible`时,...
`visibility`属性有四个可选值:`visible`(默认值,元素可见)、`hidden`(元素不可见但保留空间)、`collapse`(仅对表格元素有效,移除元素但不影响布局)和`inherit`(继承父元素的`visibility`值)。...
在网页布局和样式设计中,`display` 和 `visibility` 是两个非常重要的CSS属性,它们都能用来控制元素的可见性,但实现方式和效果大不相同。本篇文章将深入探讨两者之间的区别,并通过示例来具体说明。 首先,`...