Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

2010 Qualification Round A問題 - Snapper Chain (この記事を編集する[管理者用])

Source

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

問題概要

N個のコネクタが直列につないである.
1番目は電源に,N番目はライドにつながっている.
スイッチがONの時だけコネクタは電気を通す.
1番目がONで2番目がOFFのとき,電源につながっているのは1番目と2番目だけと考える.
指を弾くと,電源につながっているコネクタのみON,OFFが入れ替わる.
最初は全部のコネクタがOFFである.
K回指を弾いたあとライトがついているかどうかを求める問題.
small: Nは10以下,Kは100以下.
large: Nは30以下,Kは10^8以下.

解法

各コネクタの状態は2進数でインクリメントしたときと同じように動いていく.
なので,Kの下Nビットが全部1のときのみ,ライトが光る.

Cによるスパゲッティなソースコード

このコードは実際に本番でサブミットしたコードです.見にくいと思われます.

#include<stdio.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,size,count=0;
  scanf("%d",&size);
  while(size--){
    printf("Case #%d: ",++count);
    scanf("%d%d",&n,&k);
    n=(1<<n)-1;
    if((n&k)==n) puts("ON"); else puts("OFF");
  }
  return 0;
}

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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