Codeforces Beta #92 Div2.A "The number of positions"
自分と同じ悲しみを産む人がいそうなのでメモ。
問題
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); } }