CodeForces 625D Finals in arithmetic

Posted on By 二价氢

题目大意

将一个没有前导零的数翻转后的数记为,如,则,现在给定一个数,求,使得

做法

显然,我们可以构造出一个答案

假设这个n的十进制表示为,那么通过观察,我们可以分如下几个情况分析:

  1. ,显然我们可以得出最高位与最低位的和为
  2. ,可以得出最高位与最低位的和为,同时次高位与次低位的和大于10

分情况讨论这两种即可,然后这里有很多细节需要处理。

同时还要注意答案的位数可能与的位数相等,或比的位数小1

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
char str[maxn];
int sss[maxn], ans1[maxn], ans2[maxn];
int len;
int l, r;
bool getAnswer(int _l, int _r) {
	memset(ans1, 0, sizeof(ans1));
	for (int i = 0; i < len; i++) sss[i] = str[i] - '0';
	l = _l;r = _r;
	if (l == 1) {
		if (sss[0] == 1) {
			sss[l] += 10;
			sss[r] += 10;
			sss[r - 1]--;
		} else
			return false;
	}
	for (; l <= r; l++, r--) {
		while (sss[l] < 0) sss[l] += 10;
		while (sss[r] < 0) {sss[r - 1]--;sss[r] += 10;}
		if (sss[l] == sss[r] + 10 || sss[l] == sss[r] + 11) {sss[r - 1]--;sss[r] += 10;}
		//cerr << sss[l] << ',' << sss[r] << endl;
		if (sss[l] == sss[r]) {
			ans1[r] = sss[l] / 2;
			ans1[l] = sss[l] - ans1[r];
			if (ans1[r] > 9 || ans1[l] > 9) return false;
			if (l == r) {if (sss[l] % 2 != 0) return false;}
		} else if (sss[l] == sss[r] + 1) {
			if (l == r || l == r - 1) return false;
			sss[l]--;
			ans1[r] = sss[r] / 2;
			ans1[l] = sss[r] - ans1[r];
			if (ans1[r] > 9 || ans1[l] > 9) return false;
			sss[l + 1] += 10;
		} else {
			return false;
		}
	}
	return ans1[_l] != 0;
}
int main() {
	ios::sync_with_stdio(0);
	cin >> str;
	len = strlen(str);
	if (getAnswer(0, len - 1)) {
		for (int i = 0; i < len; i++) cout << ans1[i];
		cout << endl;
	} else if (len > 1 && getAnswer(1, len - 1)) {
		for (int i = 1; i < len; i++) cout << ans1[i];
		cout << endl;
	} else {
		cout << "0\n";
	}
	return 0;
}