読者です 読者をやめる 読者になる 読者になる

矮小

井の中の蛙

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

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

Problem - 124A - Codeforces

問題

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

考え方

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

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

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

aaa#bbb

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

aaaaaa#bbb
aaaaaaa#bb
aaaaaaaa#b
aaaaaaaaa#

逆に  a + b \geq n の時は  b = 0 の時が最も多くの位置を取れるので  n - a が正解。

     ----> 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);
    }
}