The numberic keypad on your mobile phone looks like below:
1 2 3 4 5 6 7 8 9 0
Suppose you are holding your mobile phone with single hand. Your thumb points at digit 1. Each time you can 1) press the digit your thumb pointing at, 2) move your thumb right, 3) move your thumb down. Moving your thumb left or up is not allowed.
By using the numeric keypad under above constrains, you can produce some numbers like 177 or 480 while producing other numbers like 590 or 52 is impossible.
Given a number K, find out the maximum number less than or equal to K that can be produced.
The first line contains an integer T, the number of testcases.
Each testcase occupies a single line with an integer K.
For 50% of the data, 1 <= K <= 999.
For 100% of the data, 1 <= K <= 10^500, t <= 20.
For each testcase output one line, the maximum number less than or equal to the corresponding K that can be produced.
3 25 83 131
25 80 129
1 #include <iostream> 2 #include <vector> 3 using namespace std; 4 5 int M[10][10] = {{1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 6 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 7 {1, 0, 1, 1, 0, 1, 1, 0, 1, 1}, 8 {0, 0, 0, 1, 0, 0, 1, 0, 0, 1}, 9 {1, 0, 0, 0, 1, 1, 1, 1, 1, 1}, 10 {1, 0, 0, 0, 0, 1, 1, 0, 1, 1}, 11 {0, 0, 0, 0, 0, 0, 1, 0, 0, 1}, 12 {1, 0, 0, 0, 0, 0, 0, 1, 1, 1}, 13 {1, 0, 0, 0, 0, 0, 0, 0, 1, 1}, 14 {0, 0, 0, 0, 0, 0, 0, 0, 0, 1}}; 15 16 17 int main() { 18 ios_base::sync_with_stdio(false); 19 int T; 20 cin >>T; 21 while (T--) { 22 vector<char> _S; 23 string str; 24 cin >> str; 25 char ch = str[0]; 26 _S.push_back(ch); 27 int i; 28 bool F = true; 29 for (i = 1; F && i < str.length(); ++i) { 30 if (M[ch-‘0‘][str[i]-‘0‘]) { 31 ch = str[i]; 32 _S.push_back(ch); 33 } 34 else { 35 char cc = str[i]; 36 while (1) { 37 char c = _S.back(); 38 int k = cc - ‘0‘ - 1; 39 for (; k >= 0; --k) { 40 if (M[c-‘0‘][k]) break; 41 } 42 43 if (k >= 0) { 44 for (int j = 0; j < i; ++j) { 45 cout << _S[j]; 46 } 47 cout << k; 48 cc = ‘0‘ + k; 49 for (int j = i + 1; j < str.length(); ++j) { 50 int s = 9; 51 for (; s >= 0; --s) { 52 if (M[cc-‘0‘][s]) break; 53 } 54 cc = ‘0‘ + s; 55 cout << cc; 56 } 57 F = false; 58 break; 59 } 60 else { 61 cc = c; 62 _S.pop_back(); 63 i--; 64 if (_S.empty()) { 65 cc--; 66 if (cc == ‘0‘) { 67 for (int j = 1; j < str.length(); ++j) { 68 cout << ‘9‘; 69 } 70 } 71 else { 72 cout << cc; 73 74 for (int j = 1; j < str.length(); ++j) { 75 int s = 9; 76 for (; s >= 0; --s) { 77 if (M[cc-‘0‘][s]) break; 78 } 79 cc = ‘0‘ + s; 80 cout << cc; 81 } 82 } 83 F = false; 84 break; 85 } 86 } 87 } 88 } 89 } 90 if (F) { 91 for (int i = 0; i < _S.size(); ++i) cout << _S[i]; 92 } 93 cout << endl; 94 } 95 }
hihoCoder #1153 Numeric Keypad
原文：http://www.cnblogs.com/liew/p/4735327.html