Codeforces 231 B. Magic, Wizardry and Wonders

問題

n枚のカードがあり、それぞれには1以上l以下の整数一つが書かれている。
このカードに対して以下の操作を繰り返す。

右端の二枚のカードを取り、書かれている数字をa, bとするとき、
二枚のカードをa - bの数字の書かれたカード一枚に置き換える。
（新たなカードの数字は、1以上l以下になっていなくてもよい）

この操作を、カードが一枚になるまで繰り返したとき、最後に残ったカードに書かれた数字はdであった。
元のカードの列として正しいものを、どれか一通り出力せよ。
答えが存在しない場合、-1を出力せよ。
答えが複数ある場合、どれを出力してもよいものとする。

制約条件

2≦n≦100

d

≦10^4

1≦l≦100

方針

最初のカードに書かれていた数字をa1, a2, a3, ..., anとすると、
最後に残るカードの数字dは、d = a1 - a2 + a3 - a4 + … anとなる。

なので、プラスのカードが全部lで、マイナスのカードが全部1のとき、
そのnとlから作れる最大の数字になり、
プラスのカードが全部1で、マイナスのカードが全部lのとき、最小の数字ができる。

この範囲にdがあれば、そのdはちゃんと作れる。そうでない場合は-1を出力する。

そのようなdをどうやって作るかと言うと、まずは全部のカードを1にしておいて、
dと違っている部分だけ直せばいい。

n = 5, d = -4, l = 4の場合（サンプル3）、

最初に1 1 1 1 1を作っておいて、

このままだとdが1なので、あと5を減らしたい。
なので、偶数番目のカードを出来るだけ（減る分まで大きくするか、lまで大きくするかのどちらか）大きくしていく。

dに足りなくて、増やす場合は、奇数番目のカードを増やしていく。

ソースコード

void run()
{
	int n, d, l, ans[100];
	cin >> n >> d >> l;
	
	int b = n / 2, a = n - b;
	//a: プラスのカードの枚数, b: マイナスのカードの枚数

	if(!(a - b * l <= d && d <= a * l - b)){
		cout << -1 << endl;
		return;
	}
	
	rep(i, n) ans[i] = 1, d += i % 2 ? 1 : -1;
	if(d > 0){
		for(int i = 0; i < n; i += 2){
			int p = min(d, l - ans[i]);
			ans[i] += p;
			d -= p;
			if(d <= 0) break;
		}
	}
	else if(d < 0){
		for(int i = 1; i < n; i += 2){
			int p = min(-d, l - ans[i]);
			ans[i] += p;
			d += p;
			if(d >= 0) break;
		}
	}
	rep(i, n) cout << ans[i] << (i == n-1 ?"\n":" ");
}