CODE FESTIVAL 2016 Final B- Exactly N points
int main() { cout << setprecision(10); cin >> n ; ll sum = 0 ; ll last ; ll skip = - 1 ; for(int i = 1 ; i <= n; i++){ sum += i; if(sum>=n){ skip = sum - n ; last = i ; break; } } for(int i = 1 ; i <= last ; i++){ if(i == skip)continue; else cout << i << endl; } }
解法
解く問題数は問題になっていないので、配点が低いもので得点を重ねていくのが良い。 初めてN点を超えたとき、問題の合計点をsum点とする。sum - n = 0 のとき、ちょうどn点になって、終了する。 このときは最後に足した配点が最大の得点だということに納得できると思う。 sum - n > k のとき、k点の問題だけ解かない。という風にすればよくて。最後に解いた問題の 配点をlast点とすると、last - 1 までの和では n に届かないから last 点は足さなきゃいけない大きな数の中で最小のもの みたいなイメージ
伝われ!! 最初3分くらい、難しいな。って思ったけど、配点が1からn点までと単純になっているし割といける。 で、last と skip が分かれば,1からlastまでを改行出力すれば勝ち