Cod sursa(job #795972)

Utilizator harababurelPuscas Sergiu harababurel Data 9 octombrie 2012 22:06:26
Problema Pairs Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#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;
}