一題很騙人的暴力搜尋跟數學討論題。

C - Walk on Multiplication Table

令 $d$ 為 $n$ 的因數，那這題就是找 $(1, 1)$ 到 $(n, \frac{n}{d})$ = $n + \frac{n}{d} - 2$ 的最小值。

$n$ 最大是 $10^{12}$ 沒錯，可是我們只要暴力到 $10^6$ 就夠了！

AC 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


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

int main()
{
    ll n;
    scanf("%lld", &n);

    ll ans = 1 + n;
    for (ll i = 1; i * i <= n; i++) {
        ll a = i;
        ll b = n / i;
        if (a * b == n) {
            ans = min(ans, a + b - 2);
        }
    }

    printf("%lld\n", ans);

    return 0;
}

D - Water Bottle

這題只要分成兩個case，以需不需要傾斜超過容器對角線為水平時的角度討論即可。

AC 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


#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const double PI = atan(1) * 4.0;

int main()
{
    int a, b, x;
    scanf("%d %d %d", &a, &b, &x);

    int total = a * a * b;

    double ans = 0.0;
    // case 1
    double z = (2.0 * (total - x)) / (1.0 * a * a);
    if (z <= b) {
        // printf("z1 = %.15lf, ans = %.15lf\n", z, ans);
        ans = atan(z / a);
    } else {
        // case 2
        z = (2.0 * x) / (1.0 * b * a);
        ans = PI / 2 - atan(z / (1.0 * b));
        // printf("z2 = %.15lf, ans = %.15lf\n", z, ans);
    }

    printf("%.15lf\n", ans * 180.0 / PI);

    return 0;
}