ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1149 Cut the Cakes

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149&lang=jp

ケーキをn回切ったあとのケーキのピースのサイズを出力する問題です。


・解法
シミュレーションするだけ問題です。

vectorにケーキのピースを入れたり消したりして、最終的にvectorの中に入っている情報を出力させればよいです。

ナイフで切る場所は地道に求めました。


ソースコード

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

struct Cake{
  int w,d,s;
  Cake(){}
  Cake(int w, int d, int s):w(w),d(d),s(s){}
  bool operator < (Cake c) const{
    return s < c.s;
  }
};

int n,w,d,p,s;
vector<Cake> cake;

void solve(){
  int a = cake[p-1].w;
  int b = cake[p-1].d;
  cake.erase(cake.begin() + p - 1);
  int len = s % (2 * (a+b));
  if(0 < len && len < a){
    if(len*b < (a-len)*b){
      cake.push_back(Cake(len, b, len*b));
      cake.push_back(Cake(a-len, b, (a-len)*b));
    }
    else{
      cake.push_back(Cake(a-len, b, (a-len)*b));
      cake.push_back(Cake(len, b, len*b));
    }
    return;
  }
  else len -= a;
  if(0 < len && len < b){
    if(a*len < a*(b-len)){
      cake.push_back(Cake(a, len, a*len));
      cake.push_back(Cake(a, b-len, a*(b-len)));
    }
    else{
      cake.push_back(Cake(a, b-len, a*(b-len)));
      cake.push_back(Cake(a, len, a*len));
    }      
    return;
  }
  else len -= b;
  if(0 < len && len < a){
    if(len*b < (a-len)*b){
      cake.push_back(Cake(len, b, len*b));
      cake.push_back(Cake(a-len, b, (a-len)*b));
    }
    else{
      cake.push_back(Cake(a-len, b, (a-len)*b));
      cake.push_back(Cake(len, b, len*b));
    }
    return;
  }
  else len -= a;
  if(0 < len && len < b){
    if(a*len < a*(b-len)){
      cake.push_back(Cake(a, len, a*len));
      cake.push_back(Cake(a, b-len, a*(b-len)));
    }
    else{
      cake.push_back(Cake(a, b-len, a*(b-len)));
      cake.push_back(Cake(a, len, a*len));
    }
    return;
  }
  else len -= b;
}


int main(){
  while(cin >> n >> w >> d, (n|w|d)){
    cake.clear();
    cake.push_back(Cake(w,d,w*d));

    for(int i = 0 ; i < n ; i++){
      cin >> p >> s;
      solve();
    }
      
    sort(cake.begin(), cake.end());

    for(int i = 0 ; i < cake.size() ; i++){
      if(i+1!=cake.size())cout << cake[i].s << " ";
      else cout << cake[i].s << endl;
    }
  }
  return 0;
}