Created
October 31, 2016 02:15
-
-
Save ia7ck/4cceff9c934c4a5e6537af37ed07cf7f to your computer and use it in GitHub Desktop.
yukicoder No.115 遠足のおやつ
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<vector> | |
using namespace std; | |
int mySum(int m){ | |
return (m)*(m+1)/2; | |
} | |
int main(){ | |
int N, D, K; | |
cin>> N>> D>> K; | |
int mi=mySum(K); | |
int ma=mySum(N)-mySum(N-K); | |
if(!(mi<=D&&D<=ma)){ | |
cout<< -1<< endl; | |
return 0; | |
} | |
int s=0; | |
vector<int> ans; | |
for(int n=1; n<=N; n++){ | |
int maS=mySum(N)-mySum(N-K+(ans.size()+1));// (nを採用するとして、)後ろから(K-(確定した個数+1))個の和(これから達成できる最大) | |
if(n+s+maS>=D){// n+今まで+これから>=D? | |
ans.push_back(n); | |
s+=n; | |
} | |
if(ans.size()==K) break; | |
} | |
for(int i=0; i<K; i++){ | |
if(i>0){ | |
cout<< " "; | |
} | |
cout<< ans[i]; | |
} | |
cout<< endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment