1149-Cut the Cake
考え方
頑張って実装する。
実装(C++)
#include <vector> #include <iostream> #include <algorithm> using namespace std; struct Rect{ int w,h; Rect(){}; Rect(int w,int h):w(w),h(h){} }; bool operator<(const Rect &a,const Rect &b){ return a.w*a.h<b.w*b.h; } int main() { int W,H,n,N,s; for(;;){ cin>>n>>W>>H; if(n==0&&W==0&&H==0)break; vector<Rect> vec; vec.push_back(Rect(W,H)); for(int i=0;i<n;i++){ cin>>N>>s; N--; s%=vec[N].w+vec[N].h; if(s>vec[N].w){ s-=vec[N].w; vec.push_back(Rect(vec[N].w,s)); vec.push_back(Rect(vec[N].w,vec[N].h-s)); }else{ vec.push_back(Rect(vec[N].w-s,vec[N].h)); vec.push_back(Rect(s,vec[N].h)); } vector<Rect>::iterator it=vec.begin(); it+=N; vec.erase(it); N=vec.size(); N--; if(vec[N]<vec[N-1])swap(vec[N],vec[N-1]); } std::sort(vec.begin(),vec.end()); for(int i=0;i<vec.size();i++){ if(i)cout<<" "; cout<<vec[i].w*vec[i].h; } cout<<endl; } return 0; }