mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] A. A Problem about Polyline

Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] に参加しました。A, B を解いたんですが dynamic な scoring のせいでクソみたいな点数になって悲しかったです。

解法

まず, a < b の場合は, 明らかに無理なことがわかります。

他の場合は, 必ず解があります。その証明も, 次の最小の x を求める過程でわかります。

点 (a, b) が題意の線に含まれている場合, 次の 2 通りの可能性があります(写真のメモ書きみたいのは無視してください)。

・点 (a, b) が, y 軸の値が減少しているところでマッチする場合
f:id:mayokoex:20150917121329j:plain
・点 (a, b) が, y 軸の値が増加しているところでマッチする場合
f:id:mayokoex:20150917121352j:plain

それぞれの場合に, x の最小値がどうなるかを考えます。

まずひとつ目の場合。この場合は, b より上に突き出た山の高さは x-b です。よって, nx + (x-b) = a すなわち (n+1)x = a+b が成り立ちます。ところで, nx が山頂になるには, n は奇数である必要があります。そのため, (n+1) は 2 以上の偶数です。
故に, x = (a+b)/n (n は 2 以上の偶数)という条件下で x を最小化すれば良いです。

ただ, 闇雲に n をでかくすればいいというものではなく, x は b 以上でなければなりません。そこに注意しましょう(a+b >= 2*b となっているので, 最小の x が必ず存在するんですね)。

ふたつ目の場合も同様に考えると,
(n-1)x = a-b (n は奇数)
を満たす 最小の x を求めれば良いことがわかります。同じように x の最小値を計算しましょう。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    if (a < b) {
        cout << -1 << endl;
        return 0;
    }
    double ans = 2e9;
    int i = (a+b)/b;
    if (i%2 == 1) i--;
    ans = min(ans, 1.*(a+b)/(i));
    i = (a-b)/b;
    if (i%2 == 1) i--;
    if (i >= 2) ans = min(ans, 1.*(a-b)/(i));
    printf("%.10lf\n", ans);
    return 0;
}