zoj 3336 Friend Number II

zoj 3336 Friend Number II

#include<stdio.h>#include<algorithm>#include<string.h>#include<vector>using namespace std;#define N 1100char str[N];vector<int> ans;bool dfs(int p, int s, int n, bool f) {if (f && p == n && s == 0)return true;if (p == n)return false;if (s < 0)return false;if (f) {int t = 0;while ((n - 1 - p) * 9 < s - t) {t++;}if (t > 9)return false;do {ans.push_back(t);if (dfs(p + 1, s - t, n, 1))return true;ans.pop_back();t++;} while (t <= 9);} else {int t = str[p];while ((n - 1 - p) * 9 < s - t) {t++;}if (t > 9)return false;if (t == str[p]) {ans.push_back(t);if (dfs(p + 1, s - t, n, 0))return true;ans.pop_back();}if (t == str[p])t++;while (t <= 9) {ans.push_back(t);if (dfs(p + 1, s - t, n, 1))return true;ans.pop_back();t++;}}return false;}int main() {int n;scanf(" %d", &n);while (n--) {memset(str, 0, sizeof(str));scanf(" %s", str);int s = 0;int len = strlen(str);for (int i = 0; str[i]; i++) {s += str[i] - '0';str[i] -= '0';}ans.clear();if (!dfs(0, s, len, 0)) {ans.clear();ans.push_back(1);if (!dfs(0, s - 1, len, 1))while (1);}for (int i = 0; i < (int) ans.size(); i++) {printf("%d", ans[i]);}puts("");}return 0;}