SRM 168 DIV1 Easy - NumberGuesser (復習××)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=1869&rd=4645
１～９９９８までの数字を考える。
（例）４３２１
各桁の数を入れ替えて、元の数字より小さければ入れ替えた数を引く。
（例）４３２１－１２３４＝３０８７
引いた後の数に、０ではない桁の数字を引き、３ケタ未満であれば０を最初につける。
（例）０８７
この操作をしたあとにできる数があらかじめ与えられた時、
引かれた桁の数字が何であるかを求める。
解き方
数字が10^4、かつ数の入れ替えが4!=24通りであるため、
全探索可能。
あとはシミュレーションなので、シンプルに間違いのないよう実装する。
別解として、元の数を1000a+100b+10c+dとすると引く数は1000d+100c+10b+aとなる。
この数を引くと、999a+99b-90c-999d、つまり9の倍数となる。
9の倍数は各桁の数の和も9の倍数となるから、これを利用して簡単に解くことができる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class NumberGuesser {
public:
int f(vector<int> a,vector<int> b){
int num=0,idx=-1;
FORE(i,1,10){
if(b[i]-a[i]==1)num++,idx=i;
else if(b[i]-a[i]>0||b[i]-a[i]<0)return -1;
}
return num==1 ? idx : -1;
}
int guess(string leftOver) {
vector<int> org(10,0);
FORE(i,0,leftOver.size())org[leftOver[i]-'0']++;
FORE(i,1,9999){
int num=i;
vector<int> vx;
while(num>0){
vx.push_back(num%10);
num/=10;
}
sort(all(vx));
num=i;
do{
int tmp=0,p=1;
for(int j=vx.size()-1;j>=0;j--){
tmp+=vx[j]*p;
p*=10;
}
if(num>=tmp){
int dif=num-tmp;
vector<int> check(10,0);
while(dif>0){
check[dif%10]++;
dif/=10;
}
int ans=f(org,check);
if(ans!=-1)return ans;
}
}while(next_permutation(all(vx)));
}
return -1;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class NumberGuesser {
public:
int f(vector<int> a,vector<int> b){
int num=0,idx=-1;
FORE(i,1,10){
if(b[i]-a[i]==1)num++,idx=i;
else if(b[i]-a[i]>0||b[i]-a[i]<0)return -1;
}
return num==1 ? idx : -1;
}
int guess(string leftOver) {
vector<int> org(10,0);
FORE(i,0,leftOver.size())org[leftOver[i]-'0']++;
FORE(i,1,9999){
int num=i;
vector<int> vx;
while(num>0){
vx.push_back(num%10);
num/=10;
}
sort(all(vx));
num=i;
do{
int tmp=0,p=1;
for(int j=vx.size()-1;j>=0;j--){
tmp+=vx[j]*p;
p*=10;
}
if(num>=tmp){
int dif=num-tmp;
vector<int> check(10,0);
while(dif>0){
check[dif%10]++;
dif/=10;
}
int ans=f(org,check);
if(ans!=-1)return ans;
}
}while(next_permutation(all(vx)));
}
return -1;
}
};
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class NumberGuesser {
public:
int guess(string leftOver) {
int x=0;
FORE(i,0,leftOver.size())x+=leftOver[i]-'0';
return 9-(x%9);
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class NumberGuesser {
public:
int guess(string leftOver) {
int x=0;
FORE(i,0,leftOver.size())x+=leftOver[i]-'0';
return 9-(x%9);
}
};
