Pagini recente » Cod sursa (job #1321028) | Cod sursa (job #1659066) | Cod sursa (job #1115699) | Cod sursa (job #953934) | Cod sursa (job #795972)
Cod sursa(job #795972)
#include <iostream>
#include <fstream>
#define nmax 55
#define kmax 15
using namespace std;
int main() {
ifstream f("peisaj.in");
ofstream g("peisaj.out");
long long dp[nmax][nmax][2], posib; //dp[i][j] = nr de posib. de lungime i, care se termina cu nivelul j
long long ajung[nmax][nmax][2]; //ajung[i][j] = nr de posib. care au cel putin 1 varf la nivel >= k
long long a[nmax][kmax][2], b[nmax][kmax][2]; //configuratii de lungime i, care se termina la nivel j, formand k varfuri, coborand/urcand
int n, i, j, k, q; //dp[i][j][0] -> se termina coborand
//dp[i][j][1] -> se termina urcand*
//a ii penultima linie, b ii ultima linie
f>>n>>k;
for(i=0; i<=n+1; i++)
for(j=0; j<=n+1; j++) dp[i][j][0] = 0, dp[i][j][1] = 0, ajung[i][j][0] = 0, ajung[i][j][1] = 0;
for(j=0; j<=n+1; j++)
for(q=0; q<=k+1; q++) a[j][q][0]=0, a[j][q][1]=0, b[j][q][0]=0, b[j][q][1]=0;
dp[1][1][1] = 1;
a[1][1][1] = 1; //de lungime 1 care ajunge la nivel 1 formand 1 varf de forma "/"
for(i=2; i<=n; i++) {
for(j=1; j<=n; j++) { //pot continua nivelul j-1, j, sau j+1
//dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1]; //asta in caz ca nu se ia in considerare orientarea
dp[i][j][0] = dp[i-1][j][1] + dp[i-1][j+1][0];
dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j-1][1];
for(q=1; q<=k; q++) {
b[j][q][0] = a[j][q][1] + a[j+1][q][0];
b[j][q][1] = a[j][q-1][0] + a[j-1][q][1];
}
if(j>=k) {
ajung[i][j][0] = dp[i][j][0]; //ajung toate posibilitatile la nivelul k
ajung[i][j][1] = dp[i][j][1];
}
else {
ajung[i][j][0] = ajung[i-1][j][1] + ajung[i-1][j+1][0];
ajung[i][j][1] = ajung[i-1][j][0] + ajung[i-1][j-1][1];
}
//g<<ajung[i][j]<<" ";
}
for(j=1; j<=n; j++)
for(q=1; q<=k; q++) a[j][q][0]=b[j][q][0], a[j][q][1]=b[j][q][1];
//g<<"\n";
}
posib = dp[n][1][0]; //lungime n care se termina la nivelul 1, coborand
g<<posib<<" "<<ajung[n][1][0]<<" "<<b[1][k][0]<<"\n";
f.close();
g.close();
return 0;
}