2013-10-08 10:25:15Morris
[UVA][dfs] 845 - Gas Station Numbers
Gas Station Numbers
Many gas stations use plastic digits on an illuminated sign to indicate
prices. When there is an insufficient quantity of a particular digit,
the attendant may substitute another one upside down.
| Gas Station Numbers |
The digit ``6" looks much like ``9" upside down. The digits ``0", ``1" and ``8" look like themselves. The digit ``2" looks a bit like a ``5" upside down (well, at least enough so that gas stations use it).
Due to rapidly increasing prices, a certain gas station has used all of its available digits to display the current price. Fortunately, this shortage of digits need not prevent the attendant from raising prices. She can simply rearrange the digits, possibly reversing some of them as described above.
Input and Output
Your job is to compute, given the current price of gas, the next highest price that can be displayed using exactly the same digits. The input consists of several lines, each containing between 2 and 30 digits (to account for future prices) and a decimal point immediately before the last digit. There are no useless leading zeroes; that is, there is a leading zero only if the price is less than 1. You are to compute the next highest price that can be displayed using the same digits and the same format rules. An input line containing a decimal point alone terminates the input. If the price cannot be raised, print `The price cannot be raised.'
Sample Input
65.2 76.7 77.7 .
Sample Output
65.5 77.6 The price cannot be raised.
Miguel Revilla 2002-06-15
題目描述：
加油站的油價使用數字牌，然而 6 和 9、2 和 5 可以倒過來使用。
給定一個小數點 1 位的數字，問使用原本有的數字牌時，下一個比它大的數字為何？
題目解法：
使用 dfs 生成自己後，下一個就是答案。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int used[10], n;
int path[105], flag;
char s[105];
void dfs(int idx) {
if(flag == 2) return;
if(idx == n) {
if(flag == 1) {
for(int i = 0; i < n-1; i++)
printf("%d", path[i]);
printf(".%d\n", path[n-1]);
flag = 2;
}
if(flag == 0)
flag = 1;
return;
}
int i;
for(i = (flag == 0) ? s[idx]-'0' : 0; i < 10; i++) {
if(i == 2 && used[2] == 0 && used[5]) {
used[5]--;
path[idx] = 2;
dfs(idx+1);
used[5]++;
} else if(i == 5 && used[5] == 0 && used[2]) {
used[2]--;
path[idx] = 5;
dfs(idx+1);
used[2]++;
} else if(i == 6 && used[6] == 0 && used[9]) {
used[9]--;
path[idx] = 6;
dfs(idx+1);
used[9]++;
} else if(i == 9 && used[9] == 0 && used[6]) {
used[6]--;
path[idx] = 9;
dfs(idx+1);
used[6]++;
} else if(used[i]) {
used[i]--;
path[idx] = i;
dfs(idx+1);
used[i]++;
}
}
}
int main() {
int i, j, k;
while(scanf("%s", &s) == 1 && s[0] != '.') {
int len = strlen(s);
s[len-2] = s[len-1], s[len-1] = '\0';
n = --len;
memset(used, 0, sizeof(used));
for(i = 0; i < len; i++)
used[s[i]-'0']++;
flag = 0;
dfs(0);
if(flag == 1)
puts("The price cannot be raised.");
}
return 0;
}