はじめに

あやややや、射命丸文です！今回はCut the Cakesという問題を解いてみました！これは、ケーキを切るという作業をシミュレーションしていくだけという問題です。この問題では、p番目のケーキをどう見つければいいのかだけ思いついたら、あとはほぼ実装するだけですね。初心者の私でも簡単に実装できたので、スクープになるネタもありません！実装には、初心者ならとりあえずこれを触っておけばいいと言われるJavaなる言語を使いました！

問題の記事はこちらです！→ http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1149&lang=jp

ソースコード

ソースコードなるものを見たほうがわかりやすいかもしれません！p番目のケーキを見つけてくるのにはArrayListというものを使いました！

class Main {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(new InputStreamReader(System.in));
        while(true){
            int n = sc.nextInt();
            int w = sc.nextInt();
            int h = sc.nextInt();
            if(n + w + h == 0) break;

            // ArrayListでケーキを管理
            ArrayList<Cake> arr = new ArrayList<Cake>();
            arr.add(new Cake(w, h));

            for(int i = 0; i < n; i++){
                int p = sc.nextInt() - 1;
                int s = sc.nextInt();

                // ケーキを取得
                Cake target_cake = arr.get(p);
                arr.remove(p);
                // ケーキをカット
                Cake second_cake = target_cake.cut(s);
                arr.add(target_cake); // 小さい方を先にadd
                arr.add(second_cake); // 大きいほうを後にadd
            }

            // ケーキを小さい順にソート
            Collections.sort(arr, new CakeComp());

            // 出力
            StringBuffer buf = new StringBuffer();
            for (int i = 0; i < arr.size(); i++) {
                buf.append(arr.get(i).size());
                buf.append(" ");
            }
            System.out.println(buf.toString().trim());
        }
        sc.close();
    }
}

/**
 * ケーキを表すクラス
 */
class Cake {
    int w, h;
    
    Cake(int w, int h){
        this.w = w;
        this.h = h;
    }
    
    /**
    * @return ケーキのサイズ
    */
    int size(){
        return w * h;
    }
    
    /**
    * cakeをcutする。自身は小さい方のケーキになり、
    * 新しく出来た大きい方のケーキを返す。
    */
    Cake cut(int s){
        int half = w + h;
        s = s % half;
        
        // 縦に切る
        Cake cake1 = new Cake(s, h);
        Cake cake2 = new Cake(w-s, h);
        if(s > w){
            // 横に切る
            s -= w;
            cake1 = new Cake(w, s);
            cake2 = new Cake(w, h-s);
        }
        
        if(cake1.size() < cake2.size()){
            this.h = cake1.h;
            this.w = cake1.w;
            return cake2;
        }else{
            this.h = cake2.h;
            this.w = cake2.w;
            return  cake1;
        }
    }
}

/**
 * ケーキの面積で昇順ソートするためのComparator
 */
class CakeComp implements Comparator<Cake> {
    @Override
    public int compare(Cake a, Cake b) {
        return a.size() - b.size();
    }
}