2019-04-16

ICPC 国内予選2011C 同色パネル結合 AOJ 1174

パネルの変更の組み合わせを全通り試せばよい。（6^5 < 10^5　だから計算量は余裕）

結合パネルかどうかはunion-findで判定すれば楽。

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


int par[110];//親
int rank2[110];//木の深さ

void init(int n){
  for(int i = 0;i < n;i++){
    par[i] = i;
    rank2[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  
  if(rank2[x] < rank2[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank2[x] == rank2[y])rank2[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}
  




int h,w,c;
int p[12][12];
int ban[7];

int main(){
    while(true){
        cin >> h >> w >> c;
        if(h + w + c == 0)break;
        for(int i = 1;i <= h;i++){
            for(int j = 1;j <= w;j++){
                cin >> p[i][j];
            }
        }
        for(int j = 0;j <= w+1;j++){
            p[0][j] = -1;
            p[h+1][j] = -1;
        }
        for(int i = 0;i <= h+1;i++){
            p[i][0] = -1;
            p[i][w+1] = -1;
        }
        int ans = 0;
        for(int n = 11111;n <= 66666;n++){
            int maxban = -1;
            int div = 1;
            for(int i = 1;i <= 5;i++){
                ban[i] = (n / div) % 10;
                maxban = max(maxban,ban[i]);
                div *= 10;
            }
            if(maxban >= 7)continue;
            init(80);

            int tmpans = 0;
            queue<P> que;
            que.push(P(1,1));
            tmpans++;
            while(!que.empty()){
                P q = que.front(); que.pop();
                for(int k = 0;k < 4;k++){
                    int ni = q.fs + dy[k],nj = q.sc + dx[k];
                    if(p[ni][nj] == p[1][1] && same(1,w*(ni-1)+nj) == false){
                        tmpans++;
                        unite(1,w*(ni-1)+nj);
                        que.push(P(ni,nj));
                    }
                }
            }

            for(int l = 1;l <= 5;l++){
                for(int i = 1;i <= h;i++){
                    for(int j = 1;j <= w;j++){
                        if(same(1,w*(i-1)+j)){
                            que.push(P(i,j));
                        }
                    }
                }
                while(!que.empty()){
                  P q = que.front(); que.pop();
                  for(int k = 0;k < 4;k++){
                    int ni = q.fs + dy[k],nj = q.sc + dx[k];
                    if(p[ni][nj] == ban[l] && same(1,w*(ni-1)+nj) == false){
                      tmpans++;
                      unite(1,w*(ni-1)+nj);
                      que.push(P(ni,nj));
                    }
                  }
                }
            }
            if(ban[5] == c){
              ans = max(ans,tmpans);
            }
        }
        cout << ans << endl;
    }
}

2019-04-07

線形微分方程式　例題と解答

微分方程式大学数学

次の微分方程式と境界条件を満たす特解を求めよ.

$\displaystyle \frac{dy}{{dx}}+5y=xe^ x, y(0)=\frac{35}{{36}}$

解答
$y(x)=u(x)v(x)$
とする。両辺を微分して
$\displaystyle \frac{dy}{{dx}}=\frac{du}{{dx}}v+u\frac{dv}{{dx}}$
これを与式に代入して
$\displaystyle \frac{du}{{dx}}v+u\frac{dv}{{dx}}+5uv=xe^ x$
uでくくって
$\displaystyle u(\frac{dv}{{dx}} + 5v)+\frac{du}{{dx}}v - xe^ x =0\tag{1}$
式(1)が成立するためには
$\displaystyle \frac{dv}{{dx}} + 5v = 0 \tag{2}$
$\displaystyle \frac{du}{{dx}}v - xe^ x = 0 \tag{3}$
であれば十分である。式(2)は
$\displaystyle \frac{dv}{{v}}=-5dx$
となる。両辺を積分すると
$\displaystyle ln|v|=-5x + c'$
となるので
$|v| = e^ {-5x+c'} = e^ {-5x} e^ {c'} = ce^ {-5x} \tag{4}$
となる。最後の等号では $e^ {c'}=c$ により定数 $c'$ を $c$ におきかえた。 $c$ の値は負でもよいとすると式(4)は
$v=ce^ {-5x} \tag{5}$
となる。式(5)を式(3)に代入すると

眠いから中断してネル

2019-04-01

ICPC 国内予選2005D Traveling by Stagecoach AOJ 1138

ICPC国内予選グラフ

解法：全探索＋ダイクストラ

馬車券を使う順序が重要で、1 <= (馬車券の数) <= 8 であるからこれは明らかに全組み合わせを試せと言ってるようなもん。（8! = 40320のため
全組み合わせのそれぞれについてダイクストラで最短を求めてそのなかで一番小さい値が答え。
通常のダイクストラを拡張して、馬車券を何枚目まで使ったか、という次元を加える。

priority_queueに三つの値を持たせたくて、昔やったことあったような気がして自分のブログを探したら見つかってバリバリ参考にした。↓（もっとスマートな方法ある気がする、、、
intsawadan.hatenablog.com

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
//typedef pair<double, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
//const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


const double INF = 1000000.0;
const int MAX_V = 35;
struct edge{ int to,cost;};
//typedef pair<int,int> P;
typedef pair<int, int> P;
typedef pair<double,P> PP;
int V,N;
//vector<edge> G[MAX_V];
double d[MAX_V][10];
int t[10];
int main(){
    int n,m,p,a,b;
    while(true){
        cin >> n >> m >> p >> a >> b;
        if(n == 0)break;
        V = m; N = n;
        for(int i = 0;i < n;i++) cin >> t[i];
        vector<edge> G[MAX_V];
        for(int i = 0;i < p;i++){
            int x,y,z;
            cin >> x >> y >> z;
            edge tmp = {y,z};
            G[x].push_back(tmp);
            edge tmp2 = {x,z};
            G[y].push_back(tmp2);
        }
        sort(t, t + n); 
        double ans = INF;
        do {
            priority_queue<PP,vector<PP>,greater<PP> > que;
            for(int i = 0;i <= V;i++){
                for(int j = 0;j <= n;j++){
                    d[i][j] = INF;
                }
            }
            d[a][0] = 0.0;
            que.push(PP(0.0,P(a,0)));
            while(!que.empty()){
                PP p = que.top(); que.pop();
                int v = p.second.first;
                if(d[v][p.second.second] < p.first)continue;
                if(p.second.second == n)continue;
                for(int i = 0;i < G[v].size();i++){
                    edge e = G[v][i];
                    if(d[e.to][p.sc.sc+1] > d[v][p.sc.sc] + ((double) e.cost) / ((double)t[p.sc.sc] ) ){
                        d[e.to][p.sc.sc+1] = d[v][p.sc.sc] + ((double) e.cost) / ((double)t[p.sc.sc] ) ;
                        que.push(PP(d[e.to][p.sc.sc+1],P(e.to,p.sc.sc+1)));
                    }
                }
            }
            double tmp = INF;
            for(int i = 0;i <= n;i++) tmp = min(tmp,d[b][i]);
            if(tmp == INF)break;
            if(ans > tmp) ans = tmp;
        } while(next_permutation(t, t + n));
        if(ans == INF){
            cout << "Impossible" << endl;
        }else{
            printf("%.3f\n",ans);
        }
    }
}

2019-03-31

ICPC 国内予選2008D ちょろちょろロボット AOJ 1156

ICPC国内予選

基本的にやることはICPC 国内予選2007D 崖登り AOJ1150 - intさわだんのBlack Historyとおんなじ
幅優先探索でゴリ押す

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int, int> T;
 
const ll MOD=1e9+7;
//const ll INF=1e18;
int INF = 1000000;

int ban[35][35],w,h,c[4],dp[35][35][4];
int dj[4][4] = {{0,1,0,-1},
              {1,0,-1,0},
              {0,-1,0,1},
              {-1,0,1,0} };
int di[4][4] = {{-1,0,1,0},
              {0,1,0,-1},
              {1,0,-1,0},
              {0,-1,0,1}};

int next_direction(int i,int j,int ni,int nj){
    if(i == ni){
        if(j > nj){
            return 3;
        }else{
            return 1;
        }
    }else{
        if(i > ni){
            return 0;
        }else{
            return 2;
        }
    }
}

int main(){
    while(true){
        cin >> w >> h;
        if(w + h == 0)break;
        for(int i = 1;i <= h;i++){
            for(int j = 1;j <= w;j++){
                cin >> ban[i][j];
                for(int k = 0;k < 4;k++) dp[i][j][k] = INF;
            }
        }
        for(int i = 0;i < 4;i++){
            cin >> c[i];
        }
        queue<T> que;
        dp[1][1][1] = 0;
        que.push(make_tuple(1,1,1,0));
        while(!que.empty()){
            T t = que.front(); que.pop();
            int i = get<0>(t),j = get<1>(t),d = get<2>(t),cost = get<3>(t);
     //       cout << "i:" << i << ", j:" << j << ", d:" << d << ", cost:" << cost <<endl;
            if(dp[i][j][d] != cost || (i == h && j == w)) continue;
            for(int k = 0;k < 4;k++){
                int ni = i + di[d][k],nj = j + dj[d][k];
                int nd = next_direction(i,j,ni,nj);
                if(ni <= 0 || ni > h || nj <= 0 || nj > w)continue;
                int same_d = 0;
                if(k == ban[i][j]) same_d = c[k];
                if(dp[ni][nj][nd] > cost + c[k] - same_d){
                    dp[ni][nj][nd] = cost + c[k] - same_d;
                    que.push(make_tuple(ni,nj,nd,dp[ni][nj][nd]));
                }
            }
        }
        int ans = INF;
        for(int k = 0;k < 4;k++){
            ans = min(ans,dp[h][w][k]);
        }
        cout << ans << endl;
    }
}

2019-03-31

ICPC 国内予選2007D 崖登り AOJ1150

ICPC国内予選

解法：幅優先探索。右足でたどり着いたときの最小時間と左足の時の最小時間を分けて考える。

この手の問題は得意なので秒で通した。（実際は分で通した。

tupleとqueueのコンボが最強であることを知った。（自分が現役だったころはtupleなかった気がする。最近でてきた？？）

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int, int> T;
 
const ll MOD=1e9+7;
//const ll INF=1e18;
int INF = 1000000;


int dx[2][9]= { { 1,1,1,1,1,2,2,2,3},
                {-1,-1,-1,-1,-1,-2,-2,-2,-3}};
int dy[2][9] = {{ 2,1,0,-1,-2,1,0,-1,0},
                {2,1,0,-1,-2,1,0,-1,0}};


int w,h;
char cliff[65][35];
int dp[65][35][2];

bool check(int i,int j){
    if(i < 0 || i >= h || j < 0 || j >= w) return false;
    if(cliff[i][j] == 'X')return false;
    return true;
}

int main(){
    while(true){
        cin >> w >> h;
        if(w + h == 0)break;
        queue<T> que;
        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                dp[i][j][0] = INF;
                dp[i][j][1] = INF;
                cin >> cliff[i][j];
                if(cliff[i][j] == 'S'){
                    dp[i][j][0] = 0;
                    dp[i][j][1] = 0;
                    que.push(make_tuple(i,j,0,0));
                    que.push(make_tuple(i,j,1,0));
                    cliff[i][j] = '0';
                }
            }
        }
        while(!que.empty()){
            T t = que.front(); que.pop();
            int y = get<0>(t),x = get<1>(t),lr = get<2>(t),m = get<3>(t);
            if(dp[y][x][lr] != m)continue;
            for(int k = 0;k < 9;k++){
                int i = y + dy[lr][k],j = x + dx[lr][k];
                if(check(i,j) == false)continue;
                if(dp[i][j][(lr+1)%2] > m + (int) (cliff[y][x] - '0') ){
                    dp[i][j][(lr+1)%2] = m +  (int) (cliff[y][x] - '0') ;
                    if(cliff[i][j] != 'T'){
                        que.push(make_tuple(i,j,(lr+1)%2,dp[i][j][(lr+1)%2]));
                    }
                }
            }
        }
        int ans = INF;
        for(int i = 0;i < h;i++){
            for(int j = 0;j < w;j++){
                for(int k = 0;k < 2;k++){
                    if(cliff[i][j] == 'T') ans = min(ans,dp[i][j][k]);
                }
            }
        }
        if(ans == INF)ans = -1;
        cout << ans << endl;
    }
}

2019-03-31

ICPC 国内予選2006D カーリング 2.0 AOJ 1144

ICPC国内予選

解法：深さ優先探索でゴリ押す
特に難しいところはない。計算量も気にしない。

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<double, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int ans;
int w,h;
void solve(int n,int y,int x,int ban[22][22]){

    if(n > 10 || n >= ans) return;

    for(int k = 0;k < 4;k++){
        int ni = y + dy[k],nj = x + dx[k];
        if(ban[ni][nj] == -1 || ban[ni][nj] == 1)continue;
        if(ban[ni][nj] == 3){
            ans = min(ans,n);
            return;
        }
        while(true){
            ni += dy[k]; nj += dx[k];
            int state = ban[ni][nj];
            if(state == 3){
                ans = min(ans,n);
                return;
            }else if(state == 1){
                ban[ni][nj] = 0;
                solve(n+1,ni-dy[k],nj-dx[k],ban);
                ban[ni][nj] = 1;
                break;
            }else if(state == -1){
                break;
            }
        }
    }
}

int main(){
    int ban[22][22];
    
    while(1){
        cin >> w >> h;
        if(w + h == 0)break;
        ans = 11;
        int x,y;
        for(int i = 1;i <= h;i++){
            for(int j = 1;j <= w;j++){
                cin >> ban[i][j];
                if(ban[i][j] == 2){
                    y = i; x = j; ban[i][j] = 0;
                }
            }
        }
        for(int i = 0;i <= h+1;i++){
            ban[i][0] = -1;
            ban[i][w+1] = -1;
        }
        for(int j = 0;j <= w+1;j++){
            ban[0][j] = -1;
            ban[h+1][j] = -1;
        }
        solve(1,y,x,ban);
        if(ans == 11) ans = -1;
        cout << ans << endl;
    }
}

2019-03-31

ICPC 国内予選2003D Building a Space Station AOJ1127

ICPC国内予選

解法：Union-Findでそれぞれのcell同士つながってるかをわかるようにし、つながってないcall間で必要なcorridorの長さの最小値を求めそのcorridorを採用する。という処理をすべてのcellがつながるまで繰り返す。

小数の扱いが闇だった。printf使えば小数点以下の桁数指定できることを完全に忘れてて大変だった。

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


double cell[110][4];
double dist[110][110]; // お互いの距離

int par[110];//親
int rank2[110];//木の深さ

void init(int n){
  for(int i = 0;i < n;i++){
    par[i] = i;
    rank2[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  
  if(rank2[x] < rank2[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank2[x] == rank2[y])rank2[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}
  
  
  



int main(){
    int n;
    while(1){
        cin >> n;
        if(n == 0)break;
        init(n);
        for(int i = 0;i < n;i++){
            for(int j = 0;j < 4;j++){
                cin >> cell[i][j];
            }
        }
        for(int i = 0;i < n;i++){
            for(int j = i+1;j < n;j++){
                double xyz = 0.0,rsum = cell[i][3] + cell[j][3];
                for(int k = 0;k < 3;k++){
                    xyz += (cell[i][k]-cell[j][k])*(cell[i][k]-cell[j][k]);
                }
                if(rsum*rsum >= xyz){ // iとjはつながっている
                    unite(i,j);
                }else{
                    dist[i][j] = sqrt(xyz) - rsum;
                    dist[j][i] = sqrt(xyz) - rsum;
                }
            }
        }
        double ans = 0.0;
        while(true){
            int flag = 0;
            int a,b;
            double distmin = 1000000.0;
            for(int i = 0;i < n;i++){
                for(int j = i+1;j < n;j++){
                    if(same(i,j) == false && distmin > dist[i][j]){
                        a = i;
                        b = j;
                        distmin = dist[i][j];
                        flag = 1;
                    }
                }
            }
            if(flag == 0)break;
            unite(a,b);
            ans += distmin;
        }
       // ans += 0.00001;
        //cout << round(ans*1000)/1000  << endl;
        printf("%.3f\n",ans);
    }
}

2019-03-31

ICPC 国内予選2013C 階層民主主義 AOJ 1188

ICPC国内予選

やるだけ。解法はICPC 国内予選2015C ICPC 計算機 AOJ1602 - intさわだんのBlack Historyと完全に同じ

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


char data[10010];
int poll[10010];
int sum[10010];

int main(){
    int z;
    cin >> z;
    for(int zz = 0;zz < z;zz++){
        cin >> data;
        int count = 0,k = 0;
        for(int i = 0;i < strlen(data);i++){
            if(data[i] == '['){
                k++;
                sum[count] = k;
                poll[count] = -1;
                count++;
            }else if(data[i] == ']'){
                k--;
            }else{ //数字の時
                int num = data[i] - '0';
                for(int j = i+1;j < strlen(data);j++){
                    if(data[j] != '[' && data[j] != ']'){
                        num = num * 10 + (int)(data[j] - '0');
                        i++;
                    }else{
                        break;
                    }
                }
                count--;
                poll[count] = num;
                count++;
            }
        }
        for(int i = 0;i < count;i++){
//            cout << sum[i] << " " << poll[i] << endl;
        }
        while(count > 1){
            int kmax = 0,o = 0;
            for(int i = 0;i < count;i++){
                if(sum[i] > kmax){
                    kmax = sum[i];
                    o = i;
                }
            }
            priority_queue<int, vector<int> , greater<int> >que;
            int len = 0;
            for(int i = o;i < count;i++){
                if(sum[i] == kmax && poll[i] != -1){
                    len++;
                    que.push(poll[i]);
                }else{
                    break;
                }
            }
            int ne = 0; // next
            for(int i = 0;i < (len+1)/2;i++){
                int q = que.top(); que.pop();
                ne += (q+1)/2;
            }
            poll[o-1] = ne*2 -1;
            for(int i = o+len;i < count;i++){
                poll[i-len] = poll[i];
                sum[i-len] = sum[i];
            }
            count -= len;
        }
        cout << (poll[0]+1)/2 << endl;
    }
}

2019-03-30

ICPC 国内予選2014C バンパイア AOJ 1194

ICPC国内予選幾何

初心者なので幾何の問題に慣れてなくて焦ったけどかなりすんなりできた。

解説一応しますが説明がすこし面倒なのと解説が必要なほど難しい問題ではないと思うのでかなり簡潔にします

建物のx座標の値はありがたいことに整数なので（これが小数だと面倒）x座標で-r～rの範囲内で幅1で切り分けてそれぞれの幅1の領域について考えることにする
切り分けた幅1の領域について、どの高さまで建物があるか求める
切り分けた幅1の領域内のみについて、太陽がどこまで登ってきても大丈夫か二分探索で調べる
それぞれの領域についての太陽がのぼれる高さの最小値が答え

参考画像↓
f:id:intsawadan:20190330222914j:plain

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

double d = 0.00001;
int build[25][3];

int main(){
    int r,n;
    while(true){
        cin >> r >> n;
        if(r + n == 0)break;
        double ans = 100.0;
        for(int i = 0;i < n;i++){ // cin
            for(int j = 0;j < 3;j++){
                cin >> build[i][j];
            }
        }
        for(int x = -r+1;x <= r;x++){
            int hmax = 0;
            for(int i = 0;i < n;i++){
                if(build[i][0] < x && x <= build[i][1]) hmax = max(hmax,build[i][2]);
            }
       //     cout << "x:" << x << ", hmax:" << hmax << endl;
            double a = -30.0,b = (double)hmax,xx;
            if(x <= 0){
                xx = (double) x;
            }else{
                xx = (double) (x-1);
            }
            while(b - a > d){
                double half = (a + b) / 2.0;
                if( (double)r*r > ((double)hmax - half)*((double)hmax - half) + xx*xx){
                    b = half;
                }else{
                    a = half;
                }
            }
            if(ans > a + (double)r) ans = a + (double)r;
        }
        cout << round(ans*10000)/10000 << endl;
    }
}

2019-03-30

ICPC 国内予選2007C ケーキカット AOJ1149

ICPC国内予選

いわれたとおりにやるだけ。特に難しいことはない。
最後priority_queueを使えば楽に答えを求められる。（まあソートでもいいけど）

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int cake[110][4];
priority_queue<int, vector<int> , greater<int> >que;

int main(){
    int n,w,d;
    while(true){
        cin >> n >> w >> d;
        if(n + w + d == 0)break;
        cake[1][0] = 0; cake[1][1] = 0; cake[1][2] = w; cake[1][3] = d;
        for(int t = 1;t <= n;t++){
            int p,s;
            cin >> p >> s;
            int x1 = cake[p][0],y1 = cake[p][1],x2 = cake[p][2],y2 = cake[p][3];
            int count = 0;
            for(int i = 1;i <= t;i++){
                if(i == p)continue;
                count++;
                for(int j = 0;j < 4;j++){
                    cake[count][j] = cake[i][j];
                }
            }
            int x = x2 - x1,y = y2 - y1;
            s = s % ( 2*x + 2*y );
            int x1_2,y1_2,x2_2,y2_2,tate = 0,len = 0;
            if(s < x){
                len = s;
            }else if(s < x+y){
                len = s - x;
                tate = 1;
            }else if(s < x+y+x){
                len = x+y+x - s;
            }else{
                len = x+y+x+y - s;
                tate = 1;
            }

            if(tate == 1){
                if(len < (y+1)/2){
                    x2_2 = x2,  y2_2 = y2,  x1_2 = x1,  y1_2 = y1+len;
                    y2 = y1+len;
                }else{
                    x1_2 = x1,  y1_2 = y1,  x2_2 = x2,  y2_2 = y1+len;
                    y1 = y1+len;
                }
            }else{
                if(len < (x+1)/2){
                    x1_2 = x1+len,  y1_2 = y1,  x2_2 = x2,  y2_2 = y2;
                    x2 = x1+len;
                }else{
                    x1_2 = x1,  y1_2 = y1,  y2_2 = y2,  x2_2 = x1+len;
                    x1 = x1+len;
                }
            }
            count++;
            cake[count][0] = x1,cake[count][1] = y1,cake[count][2] = x2,cake[count][3] = y2;
            count++;
            cake[count][0] = x1_2,cake[count][1] = y1_2,cake[count][2] = x2_2,cake[count][3] = y2_2;

        }
        
        for(int i = 1;i <= n+1;i++){
            que.push( (cake[i][2]-cake[i][0])*(cake[i][3]-cake[i][1]) );
        }
        int ans = que.top(); que.pop();
        cout << ans ;
        while(!que.empty()){
            ans = que.top(); que.pop();
            cout << " " << ans;
        }
        cout << endl;
    }
}