Pagini recente » Cod sursa (job #837960) | Cod sursa (job #1838190) | Cod sursa (job #664314) | Cod sursa (job #1269437) | Cod sursa (job #1044948)
#include <fstream>
#include <cstring>
using namespace std;
const int Base = 10;
const int Nmax = 105;
int N ,A ,B;
class Huge
{
public: int V[40];
Huge ()
{
memset(V, 0, sizeof(V));
}
Huge (int X)
{
*this = X;
}
Huge operator= (int X)
{
memset(V, 0, sizeof(V));
for(; X; X /= Base)
V[++V[0]] = X % Base;
return *this;
}
Huge operator= (Huge X)
{
memcpy(V, X.V, sizeof(X.V));
return *this;
}
Huge operator+ (Huge X) const
{
int i, T = 0;
Huge Now;
for(i = 1; i <= V[0] || i <= X.V[0] || T; i++, T /= Base)
Now.V[i] = (T += V[i] + X.V[i]) % Base;
Now.V[0] = i - 1;
return Now;
}
int operator== ( Huge X) const
{
int i,n = V[0];
for(i = 0; i <= n && V[i] == X.V[i]; ++i);
if(i==n+1)
return 0;
if(V[i] < X.V[i])
return -1;
return 1;
}
void Print() const
{
for(int i = V[0]; i >= 1; i--) printf("%d", V[i]);
printf("\n");
}
inline void ToHugeNumber(char *s)
{
V[0] = 0;
for(int i = strlen(s)-1;i >= 0; --i)
V[++V[0]] = s[i]-'0';
}
inline void sub(const Huge B)
{
int i, t = 0;
for (i = 1; i <= V[0]; i++)
{
V[i] -= ((i <= B.V[0]) ? B.V[i] : 0) + t;
V[i] += (t = V[i] < 0) * Base;
}
for (; V[0] > 1 && !V[V[0]]; V[0]--);
}
};
Huge dp[Nmax][2][Nmax], a , sol;
int main()
{
char s[Nmax];
int i, j;
ifstream f("pavare2.in");
freopen("pavare2.out","w",stdout);
f >> N >> A >> B >> (s+1);
f.close();
a.ToHugeNumber(s+1);
dp[N][0][1] = dp[N][1][1] = 1;
for(i = N-1;i ;--i)
{
for(j = 2;j <= A; ++j)
{
dp[i][0][j] = dp[i+1][0][j-1];
dp[i][1][1] = dp[i][1][1] + dp[i+1][0][j-1];
}
dp[i][1][1] = dp[i][1][1] + dp[i+1][0][A];
for(j = 2;j <= B; ++j)
{
dp[i][1][j] = dp[i+1][1][j-1];
dp[i][0][1] = dp[i][0][1] + dp[i+1][1][j-1];
}
dp[i][0][1] = dp[i][0][1] + dp[i+1][1][B];
}
for(i = 1; i <= A; ++i)
dp[0][0][0] = dp[0][0][0] + dp[1][0][i];
for(i = 1; i <= B; ++i)
dp[0][0][0] = dp[0][0][0] + dp[1][1][i];
dp[0][0][0].Print();
Huge sum;
int last = -1;
for( i = 1; i <= N ;)
{
if(last!=0)
{
if(i + A > N)
j = N - A;
else
j = A;
for( ;j ; --j)
if( (dp[i][0][j]== a) < 0)
a.sub(dp[i][0][j]);
else
{
i += j;
while(j)
{
printf("0");
--j;
}
last = 0;
break;
}
}
if(last != 1)
{
for(j = 1; j <= B && i + j<= N ;++j)
if( (dp[i][1][j]== a) < 0)
a.sub(dp[i][1][j]);
else
{
i += j;
while(j)
{
printf("1");
--j;
}
last = 1;
break;
}
}
}
printf("\n");
return 0;
}