Cod sursa(job #183466)

Utilizator nighttraxNiGhTCrAwLeR nighttrax Data 22 aprilie 2008 10:54:11
Problema Diamant Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
 #include <fstream>
 #include <iostream>
 using namespace std;

 unsigned N,M;	// dimensiunea diamantului
 long X;		// calitatea diamantului
 long S;
 long rezultat;


 ofstream fout("diamant.out");


 void citire() {
	 ifstream fin("diamant.in");
	 fin>>N>>M>>X;
	 fin.close();
 }
 
 void afis(int *B, int n) {
	 cout<<"B= ";
	 for (int i=0; i<=n; i++) cout<<i-S<<":"<<B[i]<<"  ";
	 cout<<"\n";
 }

 void clear(int *B, int n) {
	 for (int i=0; i<=n; i++)
		 B[i] = 0;
	 B[S] = 1;
 }

 void vcopy(int *A, int* B, int n) {
	 for (int i=0; i<=n; i++)
		 A[i] += B[i];
 }

 int* sume(int* A, unsigned nr) {
	 int* B;
	 int* C;
	 int i,j;
 	 long S1=0,S2=0;
	 for (i=1; i<=nr; i++) {
		 S1 += A[i]>0?A[i]:0;
		 S2 -= A[i]<0?A[i]:0;
	 }

	 S = S1>S2?S1:S2;
	 if (X>S) {fout<<"0\n"; exit(0);}
	 B = new int[S1+S2+1];
	 C = new int[S1+S2+1];
	 for (i=0; i<=S+S; i++) B[i] = C[i] = 0;
	 //for (i=1; i<=nr; i++) B[A[i]+S]++;
	 //B[A[1]+S] = 1;
	 C[S] = 1;
	 C[0] = 0;
	 //cout<<"S este "<<S<<"\n";
	 
	 for (i=1; i<=nr; i++) {
		 //if (A[i] == A[i-1]) continue;
		 //cout<<"Adun "<<A[i]<<"\n";
		 //B[A[i]+S]++;
		 
		 //cout<<"\n--------------------\n";
		 //afis(C,S+S);
			 for (j=S+S; j>=0; j--)
			 	if (C[j] > 0) {
					 //afis(C,S+S);
					 //cout<<"Adun la "<<j<<" adica la "<<j-S<<"\n";
					//cout<<"--- ["<<j+A[i]-S<<"]  "<<C[j+A[i]]<<" + 1]<<" ---    ";
					 /*if (B[j+A[i]]>0)*/ B[j+A[i]] = 1;//+= B[j];
					 if (j+A[i]-S==X) rezultat+=B[j+A[i]];
					/* else B[j+A[i]] += B[j];*/
					 //cout<<j-S<<" + "<<A[i]<<" = "<<j-S+A[i]<<" \n";
					 //afis(C,S+S);
					 //cout<<"In "<<j-S+A[i]<<" ajung in "<<B[j+A[i]]<<" feluri\n";

				}
		      //B[A[i]+S]++;
		 	
			 A[i] = -A[i];
		
			 for (j=0; j<=S+S; j++)
			 	if (C[j] > 0) {
					 //afis(C,S+S);
					 //cout<<"Adun la "<<j<<" adica "<<j-S<<"\n";
					 //cout<<"--- ["<<j+A[i]-S<<"]  "<<B[j+A[i]]<<" += "<<B[j]<<" ---    ";
					 /*if (B[j+A[i]]>0)*/ B[j+A[i]] = 1;//+= B[j];
					 /*else B[j+A[i]] += B[j];*/
					 if (j+A[i]-S==X) rezultat+=B[j+A[i]];
					 //cout<<j-S<<" + "<<A[i]<<" = "<<j-S+A[i]<<" \n";
					 //cout<<"In "<<j-S+A[i]<<" ajung in "<<B[j+A[i]]<<" feluri\n";
				}
		      //B[A[i]+S]++;
		 
		 B[S] = 0;
		 //afis(B,S+S);
		 vcopy(C,B,S+S);
		 //afis(C,S+S);
		 clear(B,S+S);
		 C[S] = 1;
		 B[S] = 1;
		 //B[A[i]+S] ++;
		 //for (j=0; j<=S+S; j++)
			// if (B[j] && !C[j]) C[j]=B[j], B[j]=0;
	 }
	 
	 
	 return C;
 }
 
 void rezolva() {
	 int i,j;
	 int nr=0;
	 int *A = new int[100];
	 int *B = new int[100];
	 for (i=1; i<=N; i++)
		 for (j=1; j<=M; j++) {
			 A[++nr] = i*j;
			 ///A[++nr] = -i*j;
		 }
	 /*for (i=1; i<=N; i++)
		 for (j=1; j<=M; j++)
			 A[++nr] = -i*j;*/
	 B = sume(A,nr);
	 //for (i=-S; i<=S; i++)
	 //	 cout<<i<<":"<<B[i+S]<<"   ";
	 fout<<rezultat;
	 fout<<"\n";
	 fout.close();
 }
 
 int main(void) {
	 citire();
	 rezolva();
	 return 0;
 }