Pagini recente » Welcome @ Alex's profile | Rating Cojocaru Paul (paulELectronistul) | Welcome @ Alex's profile | Istoria paginii utilizator/iiiiiiiiiii | Cod sursa (job #1330882)
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#define Nmax 105
using namespace std;
int N,A,B;
char kk[105];
///long long DPA[Nmax][Nmax],DPN[Nmax][Nmax];
/// DPA[i][j] in cate feluri putem pava i pietre primele j fiind albe
/// DPN[i][j] in cate feluri putem pava i pietre primele j fiind negre
vector<int> sol;
class nr_mare{
public:
int nc,cif[Nmax];
nr_mare()
{
nc = 0;
memset(cif,0,sizeof(cif));
}
nr_mare(char c[105])
{
int x = strlen(c);
nc = x;
for(int i = 0; i < x; ++i)
this->cif[x-i - 1] = c[i] - 48;
}
nr_mare operator =(int b){
nc = 0;
while(b)
{
cif[nc++] = b % 10;
b/=10;
}
return *this;
}
friend nr_mare operator + (nr_mare a,nr_mare b)
{
nr_mare c;
c.nc = a.nc;
if(b.nc > c.nc)
c.nc = b.nc;
int t = 0;
for(int i = 0; i < c.nc; ++i)
{
c.cif[i] = (a.cif[i] + b.cif[i] + t)%10;
t = (a.cif[i] + b.cif[i] + t) / 10;
}
if(t)
c.cif[c.nc++] = 1;
return c;
}
friend nr_mare operator - (nr_mare a, nr_mare b)
{
nr_mare c;
c.nc = a.nc;
for(int i = 0; i < c.nc; ++i)
{
c.cif[i] = a.cif[i] - b.cif[i];
if(c.cif[i] < 0)
{
c.cif[i] += 10;
--a.cif[i+1];
}
}
while(c.cif[c.nc - 1] == 0)
--c.nc;
return c;
}
friend ostream &operator << ( ostream &out, nr_mare &n)
{
int i = n.nc;
while(i--)
out << n.cif[i];
return out;
}
};
nr_mare DPA[Nmax][Nmax],DPN[Nmax][Nmax],K;
bool mai_mare(nr_mare a,nr_mare b)
{
if(a.nc > b.nc)
return 1;
if(a.nc < b.nc)
return 0;
for(int i = a.nc - 1; i >= 0; --i)
{
if(a.cif[i] > b.cif[i])
return 1;
if(a.cif[i] < b.cif[i])
return 0;
}
return 0;
}
void Read(){
scanf("%d%d%d\n",&N,&A,&B);
scanf("%s",kk);
K = nr_mare(kk);
}
void Solve(){
DPA[1][1] = 1;
DPN[1][1] = 1;
for(int i = 2; i <= N; ++i)
{
for(int k = 1; k <= B && k < i; ++k)
DPA[i][1] = DPA[i][1] + DPN[i-1][k]; /// schimb culoarea
for(int k = 1; k <= A && k < i; ++k)
DPN[i][1] = DPN[i][1] + DPA[i-1][k]; /// schimb culoarea
for(int j = 2; j <= A && j <= i; ++j)
DPA[i][j] = DPA[i-1][j-1]; /// prelungire
for(int j = 2; j <= B && j <= i; ++j)
DPN[i][j] = DPN[i-1][j-1]; /// prelungire
}
nr_mare ans;
for(int i = 1; i <= A; ++i)
ans = ans + DPA[N][i];
for(int i = 1; i <= B; ++i)
ans = ans + DPN[N][i];
cout << ans << "\n";
}
void Print( long long a[Nmax][Nmax] )
{
for(int i = 1; i <= N; ++i)
{
for(int j = 1; j <= N; ++j)
printf("%d ",a[i][j]);
printf("\n");
}
printf("\n-------------------------\n");
}
/**void Debug()
{
Print(DPA);
Print(DPN);
}**/
void Reconst()
{
int lastA = 0,lastB = 0;
long long crt = 0,gata;
int tip = 0;
for(int pz = N; pz >= 1; --pz)
{
gata = 0;
if(tip == 0)
{
for(int j = A; j >= 1; --j) /// incerc sa pun cati mai multi de 0
if(mai_mare(K ,DPA[pz][j]))
K = K - DPA[pz][j];
else
{
for(int k = 1; k <= j; ++k)
sol.push_back(0);
gata = 1;
pz -= (j - 1);
tip = 1;
break;
}
}
if(tip == 1 || !gata)
{
if(gata)
continue;
for(int j = 1; j <= B; ++j)
if(mai_mare( K,DPN[pz][j]))
K = K - DPN[pz][j];
else
{
for(int k = 1; k <= j; ++k)
sol.push_back(1);
pz -= (j - 1);
tip = 0;
break;
}
}
}
for(int i = 0; i < N; ++i)
printf("%d",sol[i]);
printf("\n");
}
int main()
{
freopen("pavare2.in","r",stdin);
freopen("pavare2.out","w",stdout);
Read();
Solve();
///Debug();
Reconst();
return 0;
}