ぱーぽーの競プロ記

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

AOJ 0199 Chairs Where Demanding People Sit

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

イスにどのように座っているかをシミュレートするだけの問題です。


・解法
やるだけ問題です。

が、正答率見れば分かりますがこの問題すごくバグを埋め込みやすいです。
特にD国人の座り方が一番ややこしいと思うので慎重に実装しましょう。


ソースコード

#include<iostream>
#include<algorithm>
using namespace std;
 
int n,m;
char c[100];
 
void A(){
  for(int i = 0 ; i < n ; i++){
    if(c[i]=='#'){
      c[i] = 'A';
      return;
    }
  }
}
 
void B(){
  for(int i = n-1 ; i >= 0 ; i--){
    if(c[i]=='#'){
      if(i==n-1 && c[i-1]!='A')c[i] = 'B';
      else if(i==0 && c[i+1]!='A')c[i] = 'B';
      else if(c[i-1]!='A' && c[i+1]!='A')c[i] = 'B';
      if(c[i]=='B')return;
    }
  }
    
  for(int i = 0 ; i < n ; i++){
    if(c[i]=='#'){
      c[i] = 'B';
      return;
    }
  }
}
 
void C(){
  for(int i = 0 ; i < n ; i++){
    if(c[i]!='#'){
      if(i+1!=n && c[i+1]=='#'){
        c[i+1] = 'C';
        return;
      }
      if(i!=0 && c[i-1]=='#'){
        c[i-1] = 'C';
        return;
      }
    }
  }
  c[n/2] = 'C';
}
 
void D(){
  int left,right;
  left = right = 0;
  for(int i = 0 ; i < n ; i++){
    if(c[i]!='#')break;
    left++;
  }
  for(int i = n-1 ; i >= 0 ; i--){
    if(c[i]!='#')break;
    right++;
  }
    
  if(left==right && left==n){
    c[0] = 'D';
    return;
  }
    
  int tmpS = -1;
  int l,r,mid;
  l = r = 0;
  mid = 2;
  for(int i = 0 ; i < n ; i++){
    if(c[i]!='#'){
      if(tmpS!=-1 && (mid-1)/2 < (i-tmpS-1)/2){
        l = tmpS;
        r = i - 1;
        mid = i - tmpS;
      }
      tmpS = -1;
    }
    else{
      if(tmpS==-1) tmpS = i;
    }
  }
    
  if(left < 2 && right < 2 && mid < 3){
    for(int i = 0 ; i < n ; i++){
      if(c[i]=='#'){
        c[i] = 'D';
        return;
      }
    }
  }
  else if(left >= right && left-1 >= (mid-1)/2){
    c[0] = 'D';
    return;
  }
  else if((left-1 < (mid-1)/2) && (mid-1)/2 >= right-1){
    c[(l+r)/2] = 'D';
    return;
  }
  else if(left < right && (mid-1)/2 < right-1){
    c[n-1] = 'D';
    return;
  }
}
 
int main(){
  while(cin >> n >> m, (n|m)){
    for(int i = 0 ; i < 100 ; i++){
      c[i] = '#';
    }
    for(int i = 0 ; i < m ; i++){
      char in;
      cin >> in;
      if(in=='A') A();
      if(in=='B') B();
      if(in=='C') C();
      if(in=='D') D();
    }
    for(int i = 0 ; i < n ; i++){
      cout << c[i];
    }
    cout << endl;
  }
  return 0;
}