Cod sursa(job #183346)

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

 unsigned N,M;	// dimensiunea diamantului
 long X;		// calitatea diamantului
 long S;
 
 ofstream fout("diamant.out");


 void citire() {
	 ifstream fin("diamant.in");
	 fin>>N>>M>>X;
	 fin.close();
 }
 
 int* sume(int* A, unsigned nr) {
	 int* B;
	 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 = S>=0?S:-S;
	 S = S1>S2?S1:S2;
	 if (X>S) {fout<<"0\n"; exit(0);}
	 B = new int[S+S+1];
	 for (i=0; i<=S+S; i++) B[i] = 0;
	 for (i=1; i<=nr; i++) B[A[i]+S]++;
	 //B[A[1]+S] = 1;

	 //cout<<"S este "<<S<<"\n";
	
	 for (i=2; i<=nr; i++) {
		 //if (A[i] == A[i-1]) continue;
		 //cout<<"Adun "<<A[i]<<"\n";
		 //B[A[i]+S]++;
		 if (A[i]<0) {
			 for (j=1; j<=S+S; j++)
			 	if (B[j] > 0) {
					 if (B[j+A[i]]>0) B[j+A[i]]++;
					 else B[j+A[i]] ++;//= B[j];
					// 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]++;
		 }
		 else { 
			 for (j=S+S; j>=1; j--)
			 	if (B[j] > 0) {
					 if (B[j+A[i]]>0) B[j+A[i]]++;
					 else B[j+A[i]] ++;//= B[j];
					 //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]++;

		 }
	 }
	 
	 
	 return B;
 }
 
 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;
	 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<<B[X+S];
	 fout<<"\n";
	 fout.close();
 }
 
 int main(void) {
	 citire();
	 rezolva();
	 return 0;
 }