Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

February 2011 Cook-Off 4問目 - Integer Sequences (この記事を編集する[管理者用])

Source

codechef February 2011 Cook-Off 4問目
Problem Statement
codechef February 2011 Cook-Offの参加記録

問題概要

nとaとbが与えられる.nは15以下で,aとbは0以上2^n未満のそれぞれ異なる整数.
0~2^n-1が1回ずつ現れる数列で,以下の条件を満たすものを1つ求める問題.(存在しないならそれを指摘する)
 aとbは隣り合っていない (最初と最後も隣り合っているとみなす)
 隣合う2つの整数は,2進数で表したとき,ちょうど1桁のみ違う

解法

基本的にはグレイコード.Wikipedia
最上位のビットを付け加えて,ひっくり返しながらコピーしていくなり,なんなりで作れる.
aとbが隣り合っていないというのは,適当に隣り合わなくなるまでビットの入れ替えを行えば良い.
(勿論,ちゃんと考えるとどう入れ替えれば良いかはわかるし,実装できるが)

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)

void intIntSort(int d[],int m[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}

int res[1000000];
int val[20], ind[20];

int main(){
  int i,j,k,l,m,n,num,dame;
  int a,b;
  int size;

  srand(time(NULL));

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d",&n,&a,&b);
    num = (1<<n); dame=0;
    rep(i,num) res[i] = (i^(i>>1));
    for(;;){
      rep(i,num) if( (res[i]==a && res[(i+1)%num]==b) || (res[i]==b && res[(i+1)%num]==a) ) break;
      if(i==num) break;
      if(n<=2){dame=1; break;}

      rep(i,n) ind[i]=(1<<i), val[i] = rand()%29999;
      intIntSort(val,ind,n);
      rep(i,num){
        k=0;
        rep(j,n) if(res[i]&1<<j) k += ind[j];
        res[i]=k;
      }
    }
    if(dame){puts("-1"); continue;}
    rep(i,num){
      if(i) putchar(' ');
      printf("%d",res[i]);
    }
    puts("");
  }

  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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