# acwing-2058. 笨拙的手指(acwing-2058. Clumsy fingers)-其他

## acwing-2058. 笨拙的手指(acwing-2058. Clumsy fingers)

0≤N≤10^9，且存在唯一解。

### 输入样例：

``````1010
212
``````

### 输出样例：

``````14
``````

### 样例解释

14 在二进制下的正确表示为 1110，在三进制下的正确表示为 112。

### 方法一：遍历每种出错的可能

``````#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
scanf("%s%s", &s1, &s2);
int i, j;
unsigned int num1 = 0, num2 = 0;
unsigned int r = 1;
for (i = s1.length() - 1; i >= 0; i--) {
num1 += r * (s1[i] - '0');
r <<= 1;
}
r = 1;
for (i = s2.length() - 1; i >= 0; i--) {
num2 += r * (s2[i] - '0');
r *= 3;
}
unsigned int r2; r = 1;
for (i = s1.length() - 1; i >= 0; i--) {
int t = s1[i] - '0';
if (t) num1 -= r; else num1 += r;
r2 = 1;
for (j = s2.length() - 1; j >= 0; j--) {
for (int k = 0; k <= 2; ++k) {
int u = s2[j] - '0';
if(u == k) continue;
num2 += (k - u) * r2;
if (num1 == num2){
printf("%d", num1);
break;
}
num2 += (u - k) * r2;
}
r2 *= 3;
}
if (t) num1 += r; else num1 -= r;
r <<= 1;
}
}
``````

### 方法二：借助unordered_set

``````#include <bits/stdc++.h>
using namespace std;

// 秦九昭算法，仅限base<=10
int convert(string s, int base) {
int res = 0;
for (const auto &item : s)
res = res * base + item - '0';
return res;
}

int main() {
string a, b;
unordered_set<int> S;
cin >> a >> b;
for (auto &item : a) {
item ^= 1; // 48->49 or 49->48
S.insert(convert(a, 2));
item ^= 1;
}
for (auto &item : b) {
char t = item;
for (char i = '0'; i < '3'; i++) {
if (t == i) continue;
item = i;
int x = convert(b, 3);
if (S.count(x)) {
printf("%d", x);
return 0;
}
}
item = t;
}
}
``````
————————

Bessie the cow is learning how to convert numbers between different bases.
But she always makes mistakes because she can’t easily hold the pen with her two front feet.
Whenever Bessie converts a number to a new base and writes down the result, she always writes one of the numbers wrong.
For example, if she converts the number 14 to a binary number, the correct result would be 1110, but she might write 0110 or 1111.
Bessie will not add or delete additional numbers, but may write down numbers with leading zeros due to wrong numbers.
Given the result of Bessie’s conversion of the number n to binary and ternary digits, please determine the correct initial value of n (decimal representation).

### Input format

The first line contains the binary representation of N, one of which is wrong.
The second line contains the ternary representation of N, one of which is wrong.

### Output format

Output the correct value of n.

### Data range

0 ≤ n ≤ 10 ^ 9, and there is a unique solution.

### Input example:

``````1010
212
``````

### Output example:

``````14
``````

### Example explanation

14 is correctly represented as 1110 in binary and 112 in ternary.

Essence: traverse all error combinations

### Method 1: traverse every possible error

For example, there are 4 * 3 possibilities in the sample, and the complexity = n ^ 2

``````#include <bits/stdc++.h>
using namespace std;
int main() {
string s1, s2;
scanf("%s%s", &s1, &s2);
int i, j;
unsigned int num1 = 0, num2 = 0;
unsigned int r = 1;
for (i = s1.length() - 1; i >= 0; i--) {
num1 += r * (s1[i] - '0');
r <<= 1;
}
r = 1;
for (i = s2.length() - 1; i >= 0; i--) {
num2 += r * (s2[i] - '0');
r *= 3;
}
unsigned int r2; r = 1;
for (i = s1.length() - 1; i >= 0; i--) {
int t = s1[i] - '0';
if (t) num1 -= r; else num1 += r;
r2 = 1;
for (j = s2.length() - 1; j >= 0; j--) {
for (int k = 0; k <= 2; ++k) {
int u = s2[j] - '0';
if(u == k) continue;
num2 += (k - u) * r2;
if (num1 == num2){
printf("%d", num1);
break;
}
num2 += (u - k) * r2;
}
r2 *= 3;
}
if (t) num1 += r; else num1 -= r;
r <<= 1;
}
}
``````

### 方法二：借助unordered_set

With unordered_ Set first records all possible binary numbers and compares them one by one when traversing the ternary system

``````#include <bits/stdc++.h>
using namespace std;

// 秦九昭算法，仅限base<=10
int convert(string s, int base) {
int res = 0;
for (const auto &item : s)
res = res * base + item - '0';
return res;
}

int main() {
string a, b;
unordered_set<int> S;
cin >> a >> b;
for (auto &item : a) {
item ^= 1; // 48->49 or 49->48
S.insert(convert(a, 2));
item ^= 1;
}
for (auto &item : b) {
char t = item;
for (char i = '0'; i < '3'; i++) {
if (t == i) continue;
item = i;
int x = convert(b, 3);
if (S.count(x)) {
printf("%d", x);
return 0;
}
}
item = t;
}
}
``````