2014
03-23

# Shift Number

If a number is the sum of an integer’s several shifting forms, it is called the Shift Number.
For example, by shifting 123 four times and adding the four numbers together, we get 136653, which is a Shift Number.
However, a shift number may be the sum of more than one integer’s shifting forms. Such as, 45177 is a Shift Number, which could be generated from both 407 and 4107.
123+1230+12300+123000=136653
407+4070+40700=45177
4107+41070=45177
Given a Shift Number x , would you please help us find the least integer which could generate x by shifting.

A shift number x.
Input ends with x=0.

A shift number x.
Input ends with x=0.

136653
45177
0

123
407
Hint

If you are not familiar with “long long”, you can consult to FAQ.

【题目大意】

123+1230+12300+123000=136653
407+4070+40700=45177
4107+41070=45177

【解题思路】

136653=123*1+123*10+123*100+123*1000=123*（1+10+100+1000）=123*1111

45177=407*1+407*10+407*100=407*（1+10+100）=407*111

#include <cstdio>
#define LL __int64
int main()
{
LL x,k;
while(scanf("%I64d",&x)&&x){
k=1;
while(k<x)k=k*10+1;
k/=10;
while(x%k!=0)k/=10;
printf("%I64d/n",x/k);
}
return 0;
}

/*
* File: main.cpp
* Author: Prowindy
*
* Created on 2011��10��17��, ����2:21
*/

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
/*
*
*/
char str[100000];
char s[100000];
int Len;
vector<int> ans[100000];
int ansT;

void check(int cnt) {
int i,j,carry;
s[0] = str[0];
carry = 0;
for (i = 1; i < Len; i++) {
int tmp = 0;
for (j = 1; j <= min(i, cnt - 1); j++)
tmp += s[i - j];
s[i] = (str[i] + 10 - tmp % 10 + 10 - carry % 10) % 10;
carry = (carry + s[i] + tmp) / 10;
}
int tmp = 0;
for (j = 1; j <= min(i, cnt - 1); j++)
tmp += s[i - j];
if (tmp + carry == 0) {
ansT++;
ans[ansT].clear();
for (j = Len - 1; j >= 0; j--)
ans[ansT].push_back(s[j]);
}
}

int main(int argc, char** argv) {
int i,len;
while (gets(str)) {
if (strcmp(str, "0") == 0) break;
Len = strlen(str);
ansT = -1;
reverse(str, str + Len);
for (i = 0; i < Len; i++)
str[i] -= '0';
for (len = 1; len <= Len; len++) {
check(len);
}
sort(ans,ans+ansT+1);
i = 0;
while(ans[0][i]==0) i++;
for (;i<ans[0].size();i++)
printf("%c",ans[0][i]+'0');
printf("\n");

}
return (EXIT_SUCCESS);
}

1. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。