Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1981-8a36985b
この記事にトラックバックする(FC2ブログユーザー)

2011 Qualification Round B問題 - Magicka (この記事を編集する[管理者用])

Source

Google code jam 2011 Qualification Round B問題
Problem Statement
2011 Qualification Round 自分の参加記録

問題概要

{Q, W, E, R, A, S, D, F} を基本文字と言う事にして,それ以外のアルファベットを基本じゃない文字ということにする.
最初リストは空で,リストに順番に1文字ずつ,合計でN文字入れていく.
最終的なリストを求める問題.
ただし,以下2種類の規則が与えられ,それが適応できる状況になったら適応していく.
 規則1: xyz (xとyはベース文字,zはベース文字でない) の形で与えられ,xとyが隣り合ったら,即座にxy (かyz) をzに置き換える
 規則2: xy の形で与えられ,規則1が即座に適応できない状況で,xとyの両方がリストに存在するなら,リストを空にする
Small: 与えられる規則1の数は1個以下,与えられる規則2の数は1個以下,Nは10以下
Large: 与えられる規則1の数は36個以下,与えられる規則2の数は28個以下,Nは100以下

解法

シミュレーションすれば良い.

Cによるスパゲッティなソースコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n,del;
  int n1,n2;
  char s1[100][10], s2[100][10];
  char in[1000];
  char res[1000]; int res_size;
  int size,count=0;

  scanf("%d",&size);
  while(size--){
    scanf("%d",&n1);
    rep(i,n1) scanf("%s",s1[i]);
    scanf("%d",&n2);
    rep(i,n2) scanf("%s",s2[i]);
    scanf("%d",&n);
    scanf("%s",in);

    res_size=0;

    rep(k,n){
      res[res_size++] = in[k];
      for(;;){
        int fg=0;

        rep(m,n1){
          rep(i,res_size) REP(j,i+1,res_size) if(i+1==j) if(!fg){
            if( (res[i]==s1[m][0]&&res[j]==s1[m][1]) || (res[i]==s1[m][1]&&res[j]==s1[m][0]) ){
              fg=1;
              res[i] = s1[m][2];
              res_size--;
              REP(l,i+1,res_size) res[l] = res[l+1];
            }
          }
        }
        
        rep(m,n2){
          rep(i,res_size) REP(j,i+1,res_size) if(!fg){
            if( (res[i]==s2[m][0]&&res[j]==s2[m][1]) || (res[i]==s2[m][1]&&res[j]==s2[m][0]) ){
              fg=1; res_size=0;
            }
          }
        }
        
        if(!fg) break;
      }
    }

    printf("Case #%d: [",++count);
    rep(i,res_size){
      if(i) printf(", ");
      putchar(res[i]);
    }
    puts("]");
  }


  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1981-8a36985b
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。