现在的位置: 首页 > 算法 > 正文

poj 1745

2019年02月28日 算法 ⁄ 共 1702字 ⁄ 字号 评论关闭
Divisibility
Time Limit:?1000MS ? Memory Limit:?10000K
Total Submissions:?9199 ? Accepted:?3197

秒速赛车公式 www.l19l7.cn Description

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 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

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

4 7
17 5 -21 15

Sample Output

Divisible

Source

给你n个数,第一个默认加,后面通过+或-计算问能否被k整除。
第一感觉想列出所有结果,一想复杂度O(2^n),果断放弃这想法。
然后就是dp啦,其实只要记录每次的余数,看最后一次余数为0是否可能,这样复杂度大大降低,O(n*k),最多1000000次计算嘛
然而这里记录余数要注意,要把负的改成正的,我就这里没注意wa了几次
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int z(int i)
{
    return i>0?i:-i;
}
int main()
{
    int n,k,a;
    bool f[10005][105];
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        memset(f,0,sizeof(f));
        scanf("%d",&a);
        f[1][z(a%k)]=1;
        for(int i=2; i<=n; i++)
        {
            scanf("%d",&a);
            for(int j=0; j<k; j++)
            {
                if(f[i-1][j])
                {
                    f[i][z((j+a)%k)]=1;
                    f[i][z((j-a)%k)]=1;
                }
            }
        }
        if(f[n][0])cout<<"Divisible"<<endl;
        else cout<<"Not divisible"<<endl;
    }
    return 0;
}
【上篇】
【下篇】

抱歉!评论已关闭.

  • 一以贯之推进党的建设新的伟大工程 2019-03-19
  • 回复@真理论者:你天天在强坛攻击爱因斯坦是不是劳动?创造价值么?负价值也! 2019-03-19
  • 北京天安门广场更换花卉 2019-03-18
  • 党的自我革命是伟大社会革命的强大动力(深入学习贯彻习近平新时代中国特色社会主义思想) 2019-03-18
  • 人民日报人民时评:让安全生产理念成为基本共识 2019-03-18
  • “人民体育 健康中国”马拉松系列赛北京站 2019-03-17
  • 识破“假大学”并没那么难 2019-03-17
  • 佛山:用公积金买装配式住房 贷款额度或可上浮20% ——凤凰网房产北京 2019-03-17
  • 奥运冠军寄语Running Together国际迷你马拉松—在线播放—《奥运冠军寄语Running Together国际迷你马拉松》—体育—优酷网,视频高清在线观看 2019-03-17
  • 【理上网来喜迎十九大】西班牙学者:大国外交令中国成为建立世界新秩序的中流砥柱 2019-03-16
  • 马上背!十九大报告中的四个“新” 2019-03-16
  • 呼市赛罕区南门外小学开展庆父亲节亲子趣味足球赛 2019-03-16
  • 2017大皖客户端徽派栏目全面回顾宣传片 2019-03-15
  • 回复@海之宁:你想自主劳动?全民所有的生产资料凭啥让你自主? 2019-03-15
  • 重庆市南岸区:探索建立“微益坊” 2019-03-15
  • 198| 479| 680| 952| 353| 929| 824| 557| 331| 627|