Pagini recente » Cod sursa (job #1897978) | Cod sursa (job #404670) | Cod sursa (job #840738) | Cod sursa (job #1240705) | Cod sursa (job #2630844)
#include <bits/stdc++.h>
#define maxn 1005
std::ifstream fin ("pavare2.in");
std::ofstream fout ("pavare2.out");
std::vector <int> dp[2][maxn];
void add (std::vector <int> &a, std::vector <int> &b){
int i, j, val=0;
for (i=0, j=0; i<a.size() or j<b.size()or val; i++, j++){
if (i < a.size()) val += a[i];
if (j < b.size()) val += b[j];
if (i < a.size())
a[i] = val % 10;
else a.push_back (val % 10);
val /= 10;
}
}
bool compare (std::vector <int> &a, std::vector <int> &b){
if (a.size() < b.size()) return 0;
if (a.size() > b.size()) return 1;
for (int i=a.size()-1; i>=0; i--){
if (a[i] > b[i])
return 1;
if (a[i] < b[i])
return 0;
}
return 0;
}
void reduce (std::vector <int> &a, std::vector <int> &b){
int last = 0;
for (int i=0; i<a.size(); i++){
if (i < b.size()) last -= b[i];
last += a[i];
if (last < 0){
a[i] = last + 10;
last = -1;
}
else{
a[i] = last;
last = 0;
}
}
if (a[a.size()-1] == 0)
a.pop_back();
}
void print (std::vector <int> &nr){
for (int i=nr.size()-1; i>=0; i--)
fout << nr[i];
fout << '\n';
}
int main()
{
int n, maxWhite, maxBlack, i, j, crt=0, last=-1;
std::vector <int> K;
std::string s;
fin >> n >> maxWhite >> maxBlack;
dp[0][0].push_back(1);
dp[1][0].push_back(1);
for (i=1; i<=n; i++){
for (j=1; j<=maxWhite and j<=i; j++)
add (dp[0][i], dp[1][i-j]);
// dp[0][i] += dp[1][i-j];
for (j=1; j<=maxBlack and j<=i; j++)
add (dp[1][i], dp[0][i-j]);
// dp[1][i] += dp[0][i-j];
}
std::vector <int> ans;
add (ans, dp[0][n]);
add (ans, dp[1][n]);
print(ans);
//fout << dp[0][n] + dp[1][n] << '\n';
fin >> s;
for (i=s.size()-1; i>=0; i--)
K.push_back (s[i]-'0');
//print(K);
while (crt < n){
if (last != 0)
for (j=std::min (maxWhite, n-crt); j>=1; j--){
if (compare (K, dp[1][n-crt-j]) == 0){
//if (K <= dp[1][n-crt-j]){
crt += j;
while (j--)
fout << 0;
last = 0;
break;
}
reduce (K, dp[1][n-crt-j]);
//print (K);
//K -= dp[1][n-crt-j];
}
if (last != 1)
for (j=1; j<=std::min (maxBlack, n-crt); j++){
if (compare (K, dp[0][n-crt-j]) == 0){
//if (K <= dp[0][n-crt-j]){
crt += j;
while (j--)
fout << 1;
last = 1;
break;
}
reduce (K, dp[0][n-crt-j]);
// print (K);
//K -= dp[0][n-crt-j];
}
}
return 0;
}