A-Too Min Too Max

题意

数据范围

$t(1≤t≤500)$

$n(4≤n≤100)$

$a_i(-10^6\le a_i\le 10^6)$

思路

选则最大的两个数和最小的两个数，结果为最大-最小+次大-最小+最大-次小+次大-次小。

参考代码

1
void solve() {
2
    int n;cin >> n;
3
    vector<ll>a(n);
4
    for (int i = 0;i < n;i++)
5
        cin >> a[i];
6
    sort(a.begin(), a.end());
7
    cout << a[n - 1] - a[0] + a[n - 2] - a[0] + a[n - 1] - a[1] + a[n - 2] - a[1] << '\n';
8
}

B-Yet Another Coin Problem

题意

有一些5种不同面值的金币，面值有：$1,3,6,10,15$。找到使用金币数目最少的组合方式达到数值为$n$的组合。

数据范围

$t(1≤t≤10^4)$

$n(1≤n≤10^9)$

思路

打表。

参考代码

1
void solve() {
2
    ll n;cin >> n;
3
    vector<ll>p = { 0,
4
    1,2,1,2,3,1,2,3,2,1,
5
    2,2,2,3,1,2,3,2,3,2,
6
    2,3,3,3,2,3,3,3,4,2
7
    };
8
    ll ans = n / 15 + p[n % 15];
9
    if (n / 15 > 0)
10
        ans = min(ans, n / 15 - 1 + p[n % 15 + 15]);
11
    cout << ans << endl;
12

13
}

C-Find a Mine

题意

交互题。

$n\times m$的地图有两个地雷，每次询问一个坐标点，评审机会返回距离询问点最近的地雷的与询问点的曼哈顿距离。

数据范围

$t(1≤t≤3\times 10^3)$

$n,m (2≤n≤10^8,2\le m\le 10^8)$

思路

第一次询问可以获得一条斜线，斜线上至少有一个地雷。

第二次询问可能可以找到正好一个交点，这个交点可能正好是地雷或者是两个地雷的行列序号的组合。再做第三次询问，得到两个交点至少有一个是地雷。第四次询问即可排除。

参考代码

1
bool f = false;
2

3
int ask(int x, int y) {
4
    cout << "? " << x << ' ' << y << endl;
5
    int res;cin >> res;
6
    if (res == 0) {
7
        cout << "! " << x << ' ' << y << endl;
8
        f = true;
9
    }
10

11
    return res;
12
}
13

14
void solve() {
15
    int n, m;cin >> n >> m;
16
    f = false;
17

18
    int x1 = ask(1, 1);
19
    if (f) { return; }
20

21
    int x2 = ask(1, m);
22
    if (f) { return; }
23

24
    int x3 = ask(n, 1);
25
    if (f) { return; }
26

27
    int x, y;
28
    if (x2 + x3 == n + m - 2) {
29
        // 同一条斜线
30
        y = (x1 + x3 - n + 1) / 2;
31
        x = x1 - y;
32
        x += 1;y += 1;
33
        cout << "! " << x << ' ' << y << endl;
34
        return;
35
    }
36
    else if ((n + m - x2 - x3) % 2 != 0) {
37
        // 有一个交点
38
        if ((x1 + x2 - m + 1) % 2 == 0) {
39
            x = (x1 + x2 - m + 1) / 2;
40
            y = x1 - x;
41
            x += 1;y += 1;
42
            cout << "! " << x << ' ' << y << endl;
43
        }
44
        else {
45
            y = (x1 + x3 - n + 1) / 2;
46
            x = x1 - y;
47
            x += 1;y += 1;
48
            cout << "! " << x << " " << y << endl;
49
        }
50

51
        return;
52
    }
53

54
    y = (x1 + x3 - n + 1) / 2;
55
    x = x1 - y;
56
    x += 1;y += 1;
57

58
    if (x < 1 || x > n || y < 1 || y > m) {
59
        f = true;
60
    }
61
    if (!f) {
62
        int x4 = ask(x, y);
63
        if (f) { return; }
64
    }
65

66
    x = (x1 + x2 - m + 1) / 2;
67
    y = x1 - x;
68
    x += 1;y += 1;
69
    cout << "! " << x << ' ' << y << endl;
70
}