JEDNAKOS - JEDNAKOST

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int L = 1000 + 10, S = 5000 + 10;
int f[L][S], s, p10[] = {1, 10, 100, 1000};
char a[L];

void enter() {
	scanf("%s", a+1);
	char * buf = strchr(a+1, '=');
	s = atoi(buf+1);
	*buf = 0;
}

void solve() {
	memset(f, 0x3f, sizeof f); f[0][0] = -1;
	int l = strlen(a+1);
	for(int i = 1; i <= l; ++i)
		for(int j = 0; j <= s; ++j) {
			if(a[i] == 0x30) f[i][j] = f[i-1][j] + (i == l);
			int tmp = 0;
			for(int k = 0; k < 4 && k < i; ++k) {
				tmp += p10[k] * (a[i-k] - 0x30);
				if(tmp <= j) f[i][j] = min(f[i][j], f[i-k-1][j-tmp] + 1);
				else break;
			}
		}
	printf("%d\n", f[l][s]);
}

int main() {
	enter();
	solve();
}

Download