Pagini recente » Cod sursa (job #487214) | Cod sursa (job #1272352) | Cod sursa (job #1594881) | Cod sursa (job #2114990) | Cod sursa (job #183466)
Cod sursa(job #183466)
#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;
}