10541 - Stripe

[Lijiganjun]

Why Wa?
#include<stdlib.h>
#include<string.h>
#include<iostream.h>

int t,n,k,f[2][201][51];

void add(int *a,int *b,int *c)
{
int i,g;

memset(c,0,sizeof(c[0])*51);
if (a[0]>b[0]) c[0]=a[0]; else c[0]=b[0];
g=0;
for (i=1;i<=c[0];i++)
{
c=a+b+g;
g=c/10;
c%=10;
}
if (g>0) c[++c[0]]=g;
}

void print(int *a)
{
int i;

for (i=a[0];i>0;i--) cout<<a;
cout<<endl;
}

void main()
{
int i,j,l;

cin>>t;
for (i=0;i<t;i++)
{
cin>>n>>k;
for (j=0;j<k;j++) {cin>>l;n-=l;}
n-=k-1;
if (n<0) {cout<<0<<endl;exit(0);}
for (j=0;j<=n;j++)
{
memset(f[0][j],0,sizeof(f[0][j]));
f[0][j][0]=f[0][j][1]=1;


}
for (j=1;j<=k;j++)
{
memcpy(f[j&1][0],f[(j-1)&1][0],sizeof(f[(j-1)&1][0]));
for (l=1;l<=n;l++) add(f[j&1][l-1],f[(j-1)&1][l],f[j&1][l]);
}
print(f[k&1][n]);
}
}

[Dmytro Chernysh]

Finally! Somebody does have troubles with it

[Lijiganjun]

Please give me some inputs and outputs,3x!!!!!!!!!!

[Dmytro Chernysh]

Sure!
Just mail me. You see, I don't want everyone just coping the results...

[Eduard]

I find a formula for it please tell me if i'm wrong.
Perhaps number of bleack square groups is N and number of white squars is K than answer is.
........ n
....C
........n+k-1

[LPH]

let's see...

assume here we have W white square, and there are G groups of black square. we have to put at most one white between two group of black square, we should at least have G-1 white square. if there is not, the result will be 0.

the remaining W-(G-1) white square are put into G+1 position(and not necessary put only one in), so we have

......G+1
H...................ways.
......W-(G-1)

(Dont know what H is? the way of putting r same objects in n different places, each one of which contains any number of objects are
......n............n+r-1
H........=..C....................)
......r.............r

the value of W and G will given (maybe indirectly) in the input, so you can use the formula to calculate.

hope this can help

[schindlersp]

please, help-me!!!!!

my program calc:

// input

5
200 50 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 2 1 2
4 0
4 2 2 2
200 25 1 2 3 1 2 5 6 4 8 2 1 4 2 1 4 2 1 4 2 1 5 2 1 3 2

// output

39334452841116697329459321983432455140
3
1
0
587793425317796785282960

thanxs

ps: i wish input with answer

[cpp][/cpp][cpp][/cpp]

[schindlersp]

I get AC

if help, my input and output ac program.

// input

6
200 50 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
5 2 1 2
4 0
4 2 2 2
200 25 1 2 3 1 2 5 6 4 8 2 1 4 2 1 4 2 1 4 2 1 5 2 1 3 2
25 5 2 3 2 8 1

// output


30093344528411106697329459321983432455140
3
1
0
587784321942209843029001280
252

[Solaris]

It seems that there might be some problem regarding your printing the big number. Your code have omitted all intermediate zeros from the actual output. I believe you should check your big number handling functions.

[Piotr42]

can you pls give me som input+output?
or at least some hint how to solve it
i think, the best way is to use combinations, but not pure combinations (because the order of black groups is important)
thanks for any help

[Jehad Uddin]

@ Piotr42
you can solve it using dp
dimension is [n][k];