[参加記][codeforces] Codeforces Round #104 div2

oooox 4332pt/16th だった。

C

4->7の個数と7->4の個数を数える。可能な限りswapして残りを反転すると操作数はmax(4->7の数,7->4の数)になる。

D

答えは4と7で構成された数になるっぽいので、4を0、7を1と置き換えて考えてみた。c - dが最初と最後の数の差になる。差は-1,0,1にしかならないから、それ以外は-1を出力する。差が-1のときは答えは 1(1+0)*0,1のときは 0(1+0)*1,0のときは 0(1+0)*0または1(1+0)*1になる。それぞれの場合についてうまく最小となるように数字を作れば良い。

int main(){
  int a,b,c,d;
  while(cin>>a>>b>>c>>d){
    //printf("%d %d %d %d\n",a,b,c,d);
    if(max(c,d) > min(a,b)){
      cout<<-1<<endl;
      continue;
    }
    if(abs(c-d) > 1){
      cout<<-1<<endl;
      continue;
    }
    if(c == d){
      if(a == c && b == c){
        cout<<-1<<endl;
      }else if(a == c){
        REP(i,a)cout<<"74";
        REP(i,b-c)cout<<"7";
        cout<<endl;
      }else{
        REP(i,a-c-1)cout<<"4";
        REP(i,c)cout<<"47";
        REP(i,b-c)cout<<"7";
        cout<<"4"<<endl;
      }
    }else if(c > d){
      REP(i,a-c)cout<<"4";
      REP(i,c)cout<<"47";
      REP(i,b-c)cout<<"7";
      cout<<endl;
    }else if(c < d){
      cout<<"74";
      REP(i,a-d)cout<<"4";
      REP(i,d-2)cout<<"74";
      REP(i,b-d)cout<<"7";
      cout<<"74"<<endl;
    }
  }
  return 0;
}

感想

D問題のような場合分けで失敗したら即死な問題は、小さい数について全探索で解が正しいか確認するべきだった。