Aizu Online Judge 1149 Cut the Cakes

■1149 Cut the Cakes

やればできる．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int n, w, h;  
17.  int[] ps, ss;  
18.   
19.  void run(){  
20.   for(;;){  
21.    n=sc.nextInt();  
22.    w=sc.nextInt();  
23.    h=sc.nextInt();  
24.    if((n|w|h)==0){  
25.     break;  
26.    }  
27.    ps=new int[n];  
28.    ss=new int[n];  
29.    for(int i=0; i<n; i++){  
30.     ps[i]=sc.nextInt()-1;  
31.     ss[i]=sc.nextInt();  
32.    }  
33.    solve();  
34.   }  
35.  }  
36.   
37.  void solve(){  
38.   LinkedList<R> list=new LinkedList<R>();  
39.   list.add(new R(0, 0, w, h));  
40.   for(int i=0; i<n; i++){  
41.    R r=list.remove(ps[i]);  
42.    debug(i, r.x, r.y, r.w, r.h);  
43.    int x=r.x, y=r.y;  
44.    for(int k=0; k<ss[i]; k++){  
45.     if(y==r.y&&x<r.x+r.w){  
46.      x++;  
47.     }else if(x==r.x+r.w&&y<r.y+r.h){  
48.      y++;  
49.     }else if(y==r.y+r.h&&x>r.x){  
50.      x--;  
51.     }else if(x==r.x&&y>r.y){  
52.      y--;  
53.     }else{  
54.      debug("Error!");  
55.     }  
56.     // debug(x,y);  
57.    }  
58.    debug(x, y);  
59.    R r1=null, r2=null;  
60.    if(x==r.x||x==r.x+r.w){  
61.     r1=new R(r.x, r.y, r.w, y-r.y);  
62.     r2=new R(r.x, r.y+r1.h, r.w, r.h-r1.h);  
63.    }else{  
64.     r1=new R(r.x, r.y, x-r.x, r.h);  
65.     r2=new R(r.x+r1.w, r.y, r.w-r1.w, r.h);  
66.    }  
67.    debug("r1", r1.x, r1.y, r1.w, r1.h);  
68.    debug("r2", r2.x, r2.y, r2.w, r2.h);  
69.    if(r1.w*r1.h<r2.w*r2.h){  
70.     list.add(r1);  
71.     list.add(r2);  
72.    }else{  
73.     list.add(r2);  
74.     list.add(r1);  
75.    }  
76.   }  
77.   R[] rs=list.toArray(new R[0]);  
78.   sort(rs);  
79.   String ans="";  
80.   for(R r : rs){  
81.    ans+=(r.w*r.h)+" ";  
82.    debug(r.x, r.y, r.w, r.h, r.w*r.h);  
83.   }  
84.   println(ans.substring(0, ans.length()-1));  
85.  }  
86.   
87.  class R implements Comparable<R>{  
88.   int x, y, w, h;  
89.   
90.   R(int x, int y, int w, int h){  
91.    this.x=x;  
92.    this.y=y;  
93.    this.w=w;  
94.    this.h=h;  
95.   }  
96.   
97.   @Override  
98.   public int compareTo(R r){  
99.    return w*h-r.w*r.h;  
100.   }  
101.  }  
102.   
103.  void debug(Object... os){  
104.   // System.err.println(Arrays.deepToString(os));  
105.  }  
106.   
107.  void print(String s){  
108.   System.out.print(s);  
109.  }  
110.   
111.  void println(String s){  
112.   System.out.println(s);  
113.  }  
114.   
115.  public static void main(String[] args){  
116.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
117.   new Main().run();  
118.  }  
119. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n, w, h;
 int[] ps, ss;

 void run(){
  for(;;){
   n=sc.nextInt();
   w=sc.nextInt();
   h=sc.nextInt();
   if((n|w|h)==0){
    break;
   }
   ps=new int[n];
   ss=new int[n];
   for(int i=0; i<n; i++){
    ps[i]=sc.nextInt()-1;
    ss[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  LinkedList<R> list=new LinkedList<R>();
  list.add(new R(0, 0, w, h));
  for(int i=0; i<n; i++){
   R r=list.remove(ps[i]);
   debug(i, r.x, r.y, r.w, r.h);
   int x=r.x, y=r.y;
   for(int k=0; k<ss[i]; k++){
    if(y==r.y&&x<r.x+r.w){
     x++;
    }else if(x==r.x+r.w&&y<r.y+r.h){
     y++;
    }else if(y==r.y+r.h&&x>r.x){
     x--;
    }else if(x==r.x&&y>r.y){
     y--;
    }else{
     debug("Error!");
    }
    // debug(x,y);
   }
   debug(x, y);
   R r1=null, r2=null;
   if(x==r.x||x==r.x+r.w){
    r1=new R(r.x, r.y, r.w, y-r.y);
    r2=new R(r.x, r.y+r1.h, r.w, r.h-r1.h);
   }else{
    r1=new R(r.x, r.y, x-r.x, r.h);
    r2=new R(r.x+r1.w, r.y, r.w-r1.w, r.h);
   }
   debug("r1", r1.x, r1.y, r1.w, r1.h);
   debug("r2", r2.x, r2.y, r2.w, r2.h);
   if(r1.w*r1.h<r2.w*r2.h){
    list.add(r1);
    list.add(r2);
   }else{
    list.add(r2);
    list.add(r1);
   }
  }
  R[] rs=list.toArray(new R[0]);
  sort(rs);
  String ans="";
  for(R r : rs){
   ans+=(r.w*r.h)+" ";
   debug(r.x, r.y, r.w, r.h, r.w*r.h);
  }
  println(ans.substring(0, ans.length()-1));
 }

 class R implements Comparable<R>{
  int x, y, w, h;

  R(int x, int y, int w, int h){
   this.x=x;
   this.y=y;
   this.w=w;
   this.h=h;
  }

  @Override
  public int compareTo(R r){
   return w*h-r.w*r.h;
  }
 }

 void debug(Object... os){
  // System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}