【World Finals】2011 A

【试题编号】
2011 A
【名称】
To Add or to Multiply
【题目大意】
一个数x 你可以对他进行+a操作 或*m操作 给定的数范围在p~q 最后达到的范围要是r~s 问是否可行 如果可行 输出字典序最小的方案
【算法讨论】
可以发现 M操作的次数很小 不妨枚举M的次数i 然后p,q变为p*M^i,q*M^i 然后再某个位置的一个A 可以看成+a*m^j 贪心的从次数高的开始加 能加就加 一定是当前i的最优解 然后跟一个全局的答案比较 更新
【时空复杂度】
O(logn*logn)
O(logn)
【code】

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
113
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
ll c[35], a, m, p, q, r, s, t[35], ans, as[35];
bool check()
{
    for (ll cc = c[34], aa = as[34]; cc >= 0 && aa >= 0; --cc, --aa)
    {
        if (c[cc] < as[aa]) return false;
        if (c[cc] > as[aa]) return true;
    }
    return false;
}
int main()
{
    ll test = 0;
    while (scanf("%I64d%I64d%I64d%I64d%I64d%I64d", &a, &m, &p, &q, &r, &s) && (a | m | p | q | r | s))
    {
        ans = 0x7fffffff;
        printf("Case %I64d: ", ++test);
        if (p >= r && q <= s)
        {
            printf("empty\n");
            continue;
        }
        int k = -1;
        if (m != 1)
        for (ll i = 1, lf = p * m, rt = q * m; rt <= s; ++i, lf *= m, rt *= m)
            if (lf >= r && rt <= s)
            {
                k = i;
                break;
            }
        if (q - p > s - r)
        {
            printf("impossible\n");
            continue;
        }
        if (m == 1)
        {
            if (p + ((r - p + a - 1) / a) * a >= r && q + ((r - p + a - 1) / a) * a <= s)
            printf("%I64dA\n", ((r - p + a - 1) / a));
            else printf("impossible\n");
            continue;
        }
        t[0] = 1;
        for (ll i = 0, k = 1; q * k <= s && (q - p) * k <= (s - r); ++i, k *= m)
        {
            if (i) t[i] = t[i - 1] * m;
            ll lf = r - p * t[i], rt = s - q * t[i], z = -1, tans = 0;
            memset(c, 0, sizeof(c));
            if (lf > 0)
            for (ll j = i; j >= 0; --j)
            {
                z = j;
                c[j] = rt / t[j] / a;
                if (lf - c[j] * t[j] * a <= 0)
                    c[j] = (lf + t[j] * a - 1) / t[j] / a;
                lf -= c[j] * t[j] * a;
                rt -= c[j] * t[j] * a;
                tans += c[j];
                if (lf <= 0) break;
            }/*
            for (ll j = 0; j < z; ++j)
                if (lf + t[z] - t[j] <= 0)
                {
                    c[z] -= 1;
                    c[j] += 1;
                    break;
                }*/

            if (lf > 0) tans = 0x7fffffff;
            c[34] = i;
            tans += i;
            if (tans < ans || (tans == ans && check()))
            {
                ans = tans;
                for (ll j = 0; j < 35; ++j)
                    as[j] = c[j];
            }
        }
        if (ans >= 0x3f3f3f3f) printf("impossible");
        else
        for (ll i = as[34]; i >= 0;)
        {
            if (as[i]) printf("%I64dA ", as[i]);
            if (i)
            {
                --i;
                ll t = 1;
                while (i && !as[i])
                    --i, ++t;
                printf("%I64dM ", t);
            }
            else break;
        }
        printf("\n");
    }
}

发表评论