问下ZJU2042|新手社区 - OI爱好者（OIFans.cn）

只看楼主正序阅读 0 发表于: 2006-07-28

Divisibility

--------------------------------------------------------------------------------

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 832 Accepted Submit: 223

--------------------------------------------------------------------------------

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

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input

2

4 7
17 5 -21 15

4 5
17 5 -21 15

Sample Output

Divisible

Not divisible

分享到 淘江湖新浪 QQ微博 QQ空间开心人人豆瓣网易微博百度鲜果白社会飞信

离线勇气les

OIFans复赛选手

只看该作者 13 发表于: 2006-07-31

谢谢————

离线r134a

OIFans全国铜奖

只看该作者 12 发表于: 2006-07-30

一个字，强！！！~~~~我对大牛的敬仰犹如滔滔江水连绵不绝~~~~

.

祝大家明年NOIP大获全盛!

.

离线stevenjl

管理员

只看该作者 11 发表于: 2006-07-30

别的大牛写的～

复制代码

const maxk=100;
var old,newone:array[-maxk..maxk] of boolean;
kase,num,n,k,i,j,temp:integer;
begin
readln(kase);readln;
for num:=1 to kase do begin
if num>=2 then begin writeln;readln;end;
readln(n,k);
fillchar(old,sizeof(old),0);old[0]:=true;
for i:=1 to n do begin
fillchar(newone,sizeof(newone),0);
read(temp);
for j:=-k to k do
if old[j] then begin
newone[(j+temp)mod k]:=true;
newone[(j-temp)mod k]:=true;
end;
old:=newone;
end;
if newone[0] then writeln(\'Divisible\')
else writeln(\'Not divisible\');
end;
end.

Dream Walker...

离线eagleoi

OIFans初赛选手

只看该作者 10 发表于: 2006-07-30

说了枚举不行吗...

离线stevenjl

管理员

只看该作者 9 发表于: 2006-07-30

枚举的确超时，下面是我悲哀的超时程序

复制代码

program usacozju2042;
var sj: array[1..10000] of integer;
opr: array[1..9999] of integer;
m,n,k:integer;
procedure duru;
var i,j:integer;
ch:char;
function opradd :boolean;
var i:integer;
begin
inc(opr[n-1]);
if opr[n-1] = 2 then
begin
for i:= n-1 downto 2 do
begin
if opr[i]>1 then begin opr[i]:=0; inc(opr[i-1]); if opr[i-1] <> 2 then break; end;
end;
end;
if opr[1]=2 then exit(false);
exit(true);
end;
function yz : boolean;
var i:integer;
sum:longint;
begin
sum:=sj[1];
for i:= 1 to n-1 do
begin
if opr[i]=0 then sum:=sum+sj[i+1]
else sum:=sum-sj[i+1];
end;
if sum mod k = 0 then exit(true);
exit(false);
end;
procedure main;
var i,total: integer;
begin
total:=0;
for i:= 1 to n-2 do opr[i]:=0;
opr[n-1]:=-1;
while opradd do
if yz then begin writeln('Divisible'); exit; end;
writeln('Not divisible');
end;
begin
read(m);
read(ch);
if ch<>' ' then
begin
for j:= 1 to m do
begin
read(n,k);
for i:= 1 to n do read(sj[i]);
for i:= n+1 to 10000 do sj[i]:=0;
main();
if j<>m then writeln;
end;
end
else
begin
n:=m;
read(k);
for i:= 1 to n do read(sj[i]);
main();
end;
end;
begin
duru();
end.