2014
02-17

# Without Zero

Everyone is familiar to the natural number system: 1, 2, 3… Today we will consider a different one: a no-zero number system, which means it only uses the digits 1 through 9. So counting begins with 1, the first “counting number”, and continues: 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12…, 19, 21…, 98, 99, 111, 112…
So, in this system 9 is the ninth counting number and 11 is the tenth counting number. As usual, addition can be defined by reference to the counting sequence. Addition of the i-th counting number and the j-th counting number is defined to mean the (i+j)-th counting number. Thus, in this system 5 + 8 = 14, since 5 is the fifth counting number, 8 is the eighth, and 14 is the thirteenth counting number. Subtraction is the reverse of addition.
Here is your task, given two numbers: a and b, you should output a subtract b which is defined in no-zero number system.

Multiple test cases, each line contains two positive integers: a and b, 1 <= b < a < 1000000000, it is guaranteed that both a and b will not contain digit 0.

Multiple test cases, each line contains two positive integers: a and b, 1 <= b < a < 1000000000, it is guaranteed that both a and b will not contain digit 0.

14 5
111 99
191 111

8
1
79

Analysis: 我的想法是先将Without Zero的进制给转化成10进制，做减法以后再转化为Without Zero进制。实际上，我们很容易可以看出，Without Zero只是一个变相的9进制，我们完全可以按照9进制进行计算。但是从10进制转化回去就不那么容易，我在这里采取的是这样的办法，对于十进制A，查看其Without Zero进制有多少位；对于每一位，尝试1到9之间的数字x，如果该位为数字x时刚好其10进制等于A，那么输出即可，否则设置该位为x-1。Source Code:

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
char a[20], b[20];__int64 getValue(char * p){//Without Zero进制转化为10进制
__int64 v = 0;
for(int i = 0; i < strlen(p); ++i){
v = v * 9 + p[i] - '0';
}
return v;
}int main(){
while(scanf("%s%s", b, a) != EOF){
__int64 sb = 0, sa = 0;
sb = getValue(b);
sa = getValue(a);
sb -= sa;
sa = 0;   memset(a, '1', sizeof(a));//计算Without Zero进制有多少位
a[19] = 0;
int idx = 0;
for(; ; ++idx){
sa = sa * 9 + a[idx] - '0';
if(sa == sb){
a[idx+1] = 0;
printf("%s\n", a);
goto Exit;
}
else if(sa > sb){
a[idx] = 0;
break;
}
}
for(int i = 0; i < idx; ++i){//计算Without Zero进制
for(char j = '2'; j <= '9'; ++j){
a[i] = j;
sa = getValue(a);
if(sa == sb){
printf("%s\n", a);
goto Exit;
}
if(sa > sb){
a[i] = j - 1;
break;
}
}
}
Exit:;
}
return 0;
}

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
char a[20], b[20];__int64 parseInt64(const char * p, int radix){
__int64 v = 0;
for(size_t i = 0; i < strlen(p); ++i){
v = v * radix + p[i] - '0';
}
return v;
}__int64 getWithoutZeroValue(__int64 rank){
memset(a, '1', sizeof(a));
__int64 val = 0;
for(int idx = 0; ; ++idx){
val = val * 9 + a[idx] - '0';
if(val == rank){
a[idx+1] = 0;
return parseInt64(a, 10);
}
else if(val > rank){
a[idx] = 0;
break;
}
}
for(size_t i = 0; i < strlen(a); ++i){
for(char j = '2'; j <= '9'; ++j){
a[i] = j;
val = parseInt64(a, 9);
if(val == rank){
return parseInt64(a, 10);
}
if(val > rank){
a[i] = j - 1;
break;
}
}
} return 0;
}int main(){
while(scanf("%s%s", b, a) != EOF){
__int64 rank = parseInt64(b, 9) - parseInt64(a, 9);
printf("%I64d\n", getWithoutZeroValue(rank));
}
return 0;
}

1. 爱在西元前、简单爱是最初听的两首。后来就一发不可收拾了。02年到如今，现在的生活中已经没有可以和我聊他的朋友了，想想还真是忧伤啊！今天我把他的老专辑翻出来听了一天……

2. 站长，你好！
你创办的的网站非常好，为我们学习算法练习编程提供了一个很好的平台，我想给你提个小建议，就是要能把每道题目的难度标出来就好了，这样我们学习起来会有一个循序渐进的过程！