Codeforces Beta #92 Div2.A "The number of positions"

自分と同じ悲しみを産む人がいそうなのでメモ。

Problem - 124A - Codeforces

問題

Petrくんは 人の並び列の中にいます。Petrくんは自分が何番目の位置にいるのかは分かりませんが、前に 人以上、後ろに 人以下がいることが分かっています。Petrくんの位置としてありえる場所の数を出力してください。

考え方

例によって入力例だけで考えると死ぬやつ。何も考えずに解こうとすると「後ろの人の数は0人まで減らせるんだから単純に が答えでいいんじゃないか？」と自分は思ってしまったんですがそうではない。例えば以下の場合を考えてみる。

aaa....bbb (n = 10, a = 3, b = 3)

この時 n - a = 7 なので答えを7にしたくなるが、実は3つのaの真後ろに自分がいると、後ろのbは最大でも3人しかいてくれないため n = 7 となって矛盾する。

aaa#bbb

したがって の時はbが0人からb人までのb+1通りがある（aは何人でも増やせる）ので が正しい。

aaaaaa#bbb
aaaaaaa#bb
aaaaaaaa#b
aaaaaaaaa#

逆に の時は の時が最も多くの位置を取れるので が正解。

     ----> bを減らしていくと
.....bbbbb
aaaaaaa... <- (n - a)
       <-> 結局ここしか取れないことが分かる（この時bは条件を満たしている）

ソースコード

import std.stdio, std.range, std.string, std.conv, std.algorithm;
import std.math;

void main() {
    int n, a, b;
    readf("%d %d %d", &n, &a, &b);
    if (a + b < n) {
        writeln(b + 1);
    } else {
        writeln(n - a);
    }
}