Rezumat problemă

zid1

#4663

Fascinată de cultura chineză și Marele Zid Chinezesc, Andra s-a hotărât să își construiască propriul zid în miniatură, de înălțime N și lățime M, din piese roșii și galbene pe care le deține. Ea are la dispoziție un număr nelimitat de piese cu lățimea de o unitate și toate înălțimile posibile. Piesele roșii (hóng) au înălțimea impară (1, 3, 5, ...), pe când piesele galbene (huáng) au înălțimea pară (2, 4, 6, ...). Piesele nu pot fi rotite și pot fi plasate doar pe verticală. Deoarece culoarea galbenă este considerată cea mai prestigioasă în cultura chineză, Andra vrea ca suma lungimilor tuturor pieselor galbene ce alcătuiesc zidul să fie egală cu un număr K, special ales astfel încât să aducă noroc. Mai mult de atât, ea se întreabă în câte moduri poate construi zidul astfel încât această condiție să fie respectată. Date fiind N, M și K, determinați numărul de moduri de a construi zidul în condițiile date.

ONI 2024, clasele 11-12

Fișiere Pracsiu Dan (dnprx) Liviu Silion concurs

Clasa 11 Programare dinamică Probleme diverse de programare dinamică

Rezolvă

Detalii

Problema	zid1	Operații I/O	zid.in/zid.out
Limita timp	1 secunde	Limita memorie	Total: 128 MB / Stivă 8 MB
Id soluție	#63640756	Utilizator	Aaaa Bbbb (mariodario890)
Fișier	zid1.c	Dimensiune	763 B
Data încărcării	12 Martie 2026, 11:44	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

zid1.c: In function 'main':
zid1.c:5:1: warning: implicit declaration of function 'freopen' [-Wimplicit-function-declaration]
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
 ^
zid1.c:5:240: error: 'stdin' undeclared (first use in this function)
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
                                                                                                                                                                                                                                                ^
zid1.c:5:240: note: each undeclared identifier is reported only once for each function it appears in
zid1.c:5:269: error: 'stdout' undeclared (first use in this function)
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
                                                                                                                                                                                                                                                                             ^
zid1.c:5:1: warning: implicit declaration of function 'scanf' [-Wimplicit-function-declaration]
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
 ^
zid1.c:5:298: warning: incompatible implicit declaration of built-in function 'scanf' [enabled by default]
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
                                                                                                                                                                                                                                                                                                          ^
zid1.c:5:1: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
 ^
zid1.c:5:337: warning: incompatible implicit declaration of built-in function 'printf' [enabled by default]
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
                                                                                                                                                                                                                                                                                                                                                 ^
zid1.c:5:1: warning: implicit declaration of function 'memcpy' [-Wimplicit-function-declaration]
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
 ^
zid1.c:4:15: warning: incompatible implicit declaration of built-in function 'memcpy' [enabled by default]
 #define D(x,y)memcpy(x[q],y,(T+1)*4);

               ^
zid1.c:5:516: note: in expansion of macro 'D'
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    ^
zid1.c:3:15: warning: incompatible implicit declaration of built-in function 'memcpy' [enabled by default]
 #define C(x,y)memcpy(x,y,(T+1)*4);

               ^
zid1.c:5:599: note: in expansion of macro 'C'
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       ^
zid1.c:3:15: warning: incompatible implicit declaration of built-in function 'memcpy' [enabled by default]
 #define C(x,y)memcpy(x,y,(T+1)*4);

               ^
zid1.c:5:623: note: in expansion of macro 'C'
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               ^
zid1.c:5:630: warning: incompatible implicit declaration of built-in function 'printf' [enabled by default]
 int f[2][X],p[2][X],d[2][X],F[X],P[X],D[X],a[X],r[X],t[X];void m(int*x,int*y,int*z,int n){int i,j;for(i=0;i<=n;i++)z[i]=0;for(i=0;i<=n;i++)if(x[i])for(j=0;i+j<=n;j++)if(y[j])z[i+j]=(z[i+j]+1LL*x[i]*y[j])%O;}int main(){freopen("zid.in","r",stdin);freopen("zid.out","w",stdout);int N,M,K,T,n,i,q;if(scanf("%d%d%d",&N,&M,&K)-3||K%2)return!printf("0\n");T=K/2;f[0][0]=p[0][0]=d[0][0]=r[0]=1;for(n=1;n<=N;n++){q=n&1;for(i=0;i<=T;i++)F[i]=(p[q^1][i]+(i?d[q][i-1]:0))%O,P[i]=(F[i]+p[q][i])%O,D[i]=(F[i]+(i?d[q][i-1]:0))%O;D(f,F)D(p,P)D(d,D)}for(i=0;i<=T;i++)a[i]=f[N&1][i];for(;M;M>>=1){if(M&1)m(r,a,t,T),C(r,t)if(M>1)m(a,a,t,T),C(a,t)}printf("%d\n",r[T]);}
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      ^

Cum funcționează evaluarea?