Codeforces 333A 《Secrets》

九月 30, 2018 1556

枚举

题目链接

题目大意

Gerald 在卖一些国家机密，所有机密的花费相同——总价值为 n 的钢镚。所有的钢镚的价值都是 3^k\ (k ≥ 1) 。

某天来了一个交易者，他不会付出正好的价值，也就是说，Gerald 必须找钱给他。

求一个方案使得交易者付出的钢镚的价值 ≥n ，且付出最少额外价值的同时保证花费的钢镚数量最多。

Input / Output 格式 & 样例

输入样例

一行一个整数 n ，意义如题。

输出样例

一行一个整数，即最多花费的钢镚数量。

输入样例

Case #1:

1
1

Case #2:

1
4

输出样例

Case #1:

1
1

Case #2:

1
2

解题思路

显然，使用的金币面值越小，使用的金币数量就越大

那么答案就是第一个 i 使得 \frac{n}{i}=1\ (i ≥ 1)

又因为交易者不会付出正好为 n 价值的钢镚，所以答案就要 +1

代码实现

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x, bool returnValue) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x >= 10) putint(x / 10, false);
    putchar(x % 10 + '0');
    if (returnValue) putchar('\n');
}

int main(int argc, char *const argv[]) {
    long long int n, now = 1l;
    cin >> n;
    while (true) {
        now *= 3;
        if (n % now) {
            cout << n / now + 1 << endl;
            return 0;
        }
    }
    return 0;
}