# Cod sursa(job #1604222)

Utilizator Data 18 februarie 2016 07:30:29 Pascal 0 cpp done Arhiva de probleme 1.69 kb
``````#include <iostream>
#include <fstream>
#include <string.h>
#include <math.h>
/*
a) cate numere exista cu cel mult P cifre 0 (zero) consecutive.
b) cate numere exista cu cel putin Q cifre 0 (zero) consecutive.

b ahol van benne egy olyan ahol q zero koveti egymast
*/

using namespace std;
const int nmax = 50;
int v[23];
int nrCifre, baza, p, q;
long long int rp = 0;

bool valid_p(int k) {
if (v[k] > 1) return false;
// -- meg kell szamoljam a nullasokat
if (v[k] == 1) return true;
else {
int i = k;
for (; v[i] == 0 && i > 0; i--);
return (k - i) <= p;
}
}

void afisare() {
int temp = 1;
for (int i = 1; i <= nrCifre - 1; i++) {
if (v[i] == 1) temp++;
cout << v[i] << " ";
}
cout << endl;
rp += pow(baza - 1, temp);
}

void bk_max(int k) {
int i;
for (i = 0; i <= 1; i++) {
v[k] = i;
if (valid_p(k)) {
if (k == nrCifre - 1)
afisare();
else
bk_max(k + 1);
};
}
}

bool solutie(int k) {
if (k < nrCifre - 1) return false;
// ha megvan az osszes szam akkor megnezzuk nva e eleg nullas
int maxim = 0, next = 0;
for (int i = 1; i <= nrCifre - 1; i++)
if (v[i] == 0){
next++;
if (maxim < next) maxim = next;
}
else next = 0;
return maxim >= q;
}
void bk_min(int k) {
int i;
for (i = 0; i <= 1; i++) {
v[k] = i;
if (k < nrCifre) {
if (solutie(k))
afisare();
else
bk_min(k + 1);
}
};
}

int main(){
freopen("zero.in", "r", stdin);
freopen("zero.out", "w", stdout);
cin >> nrCifre >> baza >> p >> q;

bk_max(1);
printf("%lld\n", rp);

rp = 0;

bk_min(1);
printf("%lld\n", rp);

fclose(stdin);
fclose(stdout);
return 0;
}``````