题目描述：
给出 $ n $ 个数字，可以将数字中的 $ 9 $ 翻转为 $ 6 $ ，反之亦可。问能否只靠翻转，得到一个升序序列。能，则输出序列，不能，输出 impossible
数据范围：
$ 1\le n \le 10000, 1\le a_i \le 10^{18} $
题解：
直接模拟，可以先把数字中的 $ 6 $ 全翻转为 $ 9 $ ，第一个数字要全翻转为 $ 6 $ 。然后从高位到低位，如果数值翻转为 $ 6 $ 仍大于前一个，则翻转。如果全是 $ 9 $ 也不能翻转，直接不行
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e4 + 10;
const int maxm = 1e5 + 10;
ll n, k;
struct Node
{
ll num;
char s[20];
int len;
void toStr()
{
len = 0;
ll tmp = num;
while (tmp)
{
s[len] = tmp % 10 + '0';
len++;
tmp /= 10;
}
}
void toll()
{
ll tmp = 1;
num = 0;
for (int i = 0; i < len; i++)
{
num *= tmp;
num += s[i] - '0';
tmp *= 10;
}
}
void toNine()
{
ll tmp = 1;
for (int i = 0; i < len; i++)
{
if (s[i] == '6')
{
s[i] = '9';
num += 3ll * tmp;
}
tmp *= 10;
}
}
} a[maxn];
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
read(n);
for (int i = 1; i <= n; i++)
{
read(a[i].num);
a[i].toStr();
}
Node pre;
pre.num = 0;
pre.toStr();
bool flag;
for (int i = 1; i <= n; i++)
{
flag = true;
a[i].toNine();
ll tmp = pow(10, a[i].len - 1);
for (int j = a[i].len - 1; j >= 0; j--)
{
if (a[i].num >= pre.num)
{
if (a[i].s[j] == '9')
{
if (a[i].num - 3ll * tmp >= pre.num)
{
a[i].s[j] = '6';
a[i].num -= 3ll * tmp;
}
}
}
else
{
flag = false;
break;
}
tmp /= 10;
}
pre = a[i];
if (!flag)
break;
}
if (flag)
{
printf("possible\n");
for (int i = 1; i <= n; i++)
{
printf("%lld\n", a[i].num);
}
}
else
{
printf("impossible\n");
}
return 0;
}
|