10541 - Stripe
Moderator: Board moderators
-
- New poster
- Posts: 5
- Joined: Tue Dec 16, 2003 4:10 pm
- Location: China
- Contact:
10541 - Stripe
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]);
}
}
#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]);
}
}
Hello ,everyone!
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
-
- New poster
- Posts: 5
- Joined: Tue Dec 16, 2003 4:10 pm
- Location: China
- Contact:
-
- Experienced poster
- Posts: 146
- Joined: Sat Apr 26, 2003 2:51 am
10541
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
Perhaps number of bleack square groups is N and number of white squars is K than answer is.
........ n
....C
........n+k-1
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650
Re: acm10541[WA]
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
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
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.
-
- New poster
- Posts: 28
- Joined: Tue Aug 03, 2004 8:11 pm
- Contact:
10541 (wa)
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]
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]
-
- New poster
- Posts: 28
- Joined: Tue Aug 03, 2004 8:11 pm
- Contact:
10541 AC
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
10541 Stripe
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
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
-
- Learning poster
- Posts: 74
- Joined: Fri May 08, 2009 5:16 pm
Re: 10541 - Stripe
@ Piotr42
you can solve it using dp
dimension is [n][k];
you can solve it using dp
dimension is [n][k];