Codeforces 148C. Terse princess
問題
n人がいて、それぞれの人は1以上50000以下の整数のお金を持っている。
n人を先頭から見ていったとき、
「直前の人よりもお金を多く持っている人」がa人
「今までの人の持っているお金の合計よりも多くお金を持っている人」がb人いた。
(ただし、後者に該当するとき前者の数に入れない)
一番最初の人は前者にも後者にも該当しないものとする。
このとき、それぞれの人の持っているお金の額としてありうるものを、どれか一通り出力せよ。
答えが存在しない場合は-1を出力せよ。
制約条件
n≦100
a,b≦15
n>a+b
方針
最初の人の持っているお金は1としてよい。
bに該当する人からgreedyに金額を決めていく。
その後、aに該当する人の金額を決める。
bが0人のときがコーナーケースで、
1 1 2 3……のようにしなければいけない。
ソースコード
int main(){ int n, a, b; cin>>n>>a>>b; if(b==0){ if(a==0){ rep(i,n)cout<<"1 "; cout<<endl; } else if(n<a+2)cout<<-1<<endl; else{ cout<<"1 1 "; rep(i,a)cout<<i+2<<" "; rep(i,n-a-2)cout<<"1 "; cout<<endl; } return 0; } int sum=1; cout<<1<<" "; rep(i,b){ cout<<sum+1<<" "; sum=sum*2+1; } rep(i,a)cout<<(sum-1)/2+i+2<<" "; rep(i,n-a-b-1)cout<<"1 "; cout<<endl; return 0; }