Page 1 of 1
10541 - Stripe
Posted: Wed Dec 17, 2003 4:53 pm
by 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]);
}
}
Posted: Wed Dec 17, 2003 11:10 pm
by Dmytro Chernysh
Finally!
Somebody does have troubles with it
Posted: Fri Dec 19, 2003 3:20 pm
by Lijiganjun
Please give me some inputs and outputs,3x!!!!!!!!!!
Posted: Sat Dec 20, 2003 7:15 pm
by Dmytro Chernysh
Sure!
Just mail me. You see, I don't want everyone just coping the results...
10541
Posted: Sat Mar 13, 2004 1:58 pm
by 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
Re: acm10541[WA]
Posted: Mon Mar 15, 2004 5:29 am
by 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
10541 (wa)
Posted: Mon Aug 09, 2004 9:10 pm
by 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]
10541 AC
Posted: Tue Aug 10, 2004 6:24 am
by 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
Posted: Sat Jan 29, 2005 9:36 pm
by 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.
10541 Stripe
Posted: Sun Dec 16, 2007 6:20 pm
by 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
Re: 10541 - Stripe
Posted: Tue Sep 14, 2010 7:03 am
by Jehad Uddin
@ Piotr42
you can solve it using dp
dimension is [n][k];