Bài Đếm số - VNOI

Tiêu đề: Bài Đếm số - VNOI 29.11.08 18:40

Bài này lấy trên VNOI, do khuc_tuan tự nghĩ ra đề bài đó. Đây là một bài QHĐ và duyệt khá hay, các bạn có thể tham khảo thử.

http://vn.spoj.pl/problems/DEMSO/vn/

Với một số tự nhiên được viết trong hệ cơ số 10, ta định nghĩa
vị trí xấu là vị trí mà chữ số tại đó với chữ số kề sau nó có độ chênh
lệch không quá D. Nếu một số có không quá K vị trí xấu thì đó là số đẹp.
Hãy đếm số lượng số đẹp trong khoảng từ A đến B.

Dữ liệu

Gồm một dòng duy nhất là 4 số A, B, D, K.

Kết quả

Gồm một dòng duy nhất là số lượng số đếm được.

Giới hạn

1 ≤ A ≤ B ≤ 10¹⁵

Ví dụ

Dữ liệu
1 13 1 0

Kết quả
10

Dưới đây là code của Khúc Tuấn Very Happy

Code:: #include
using namespace std;

long long A, B;
long long F[22][22][2][22];
int D, K, c[22], nc;

long long go(int pos, int last, int less, int count) {
if(pos<0) return (count<=K) ? 1 : 0;
long long &ret = F[pos][last][less][count];
if(ret!=-1) return ret;
ret = 0;
for(int ad=0;ad<10;++ad) if(less || ad<=c[pos])
ret += go( pos-1, (last==10 && ad==0) ? 10 : ad,
less || ad
count + ((last!=10 && abs(last-ad)<=D) ? 1 : 0));
return ret;
}

long long process( long long x ) {
for(c[0]=nc=0;x>0;x/=10) c[nc++] = x%10;
if(nc==0) nc=1;
memset( F, -1, sizeof(F));
return go( nc-1, 10, 0, 0);
}

int main() {
cin >> A >> B >> D >> K;
cout << process(B) - process(A-1) << endl;
return 0;
}

» VNOI 2009 - Contest của vn.spoj.pl