結果

問題 No.3 ビットすごろく
ユーザー arishikiarishiki
提出日時 2016-04-02 00:37:00
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 29 ms / 5,000 ms
コード長 2,004 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 21,760 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-01 07:48:29
合計ジャッジ時間 1,393 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:14:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |   scanf("%d", &N);
      |   ^~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>

int bitsum(int k);

int main(void){
  /* 必要なものたち
     現在k手目
     今まで通過したリスト 1
     直前にきていたリスト 2
     最新のやつ 3
   */
  int s=-1, k, i, N, owa=0, temp, lst[10000];
  
  scanf("%d", &N);
  if(N==1){
    printf("%d\n", 1);
    return 0;}
  for(i=0;i<N;i++) lst[i]=0; //デフォルトは0

  /* lst[n]が表すのはn+1のマス目であることに注意 */
  
  lst[0]=2;
  /* 最初にいるのは1のマス目である */
  
  /* 2のマス目がない=すべての選択肢はループする＝オワ */
  
  for(k=1;k<N && owa==0 && s<0;k++){
    /* sはデフォルトで-1であり、それ以外の値が得られたら終了する */
    /* kの最大値はN */
    
    owa=1;
    /* 2のマス目がない=すべての選択肢はループする＝オワ */
    /* デフォルトではowa=1,owaじゃない時owa=0とする */
    
    for(i=0;i<N;i++){
      if(lst[i]==2){
	lst[i]=1; //もう調べたので過去になる
	temp = i-bitsum(i+1); //引いたやつについて調べる
	if(0<=temp && temp<N && lst[temp] == 0)
	  /* 戻った場合がしかるべき範囲に含まれかつ未到達の時に限り */
	  lst[temp]=3;
	temp = i+bitsum(i+1);
	if(temp == N-1){
	  s=k+1;
	  /* sはデフォルト-1で、このときのみ到達したということでs=k+1として
	   脱出して終了する*/
	  break;
	}
	if(0<=temp && temp<N && lst[temp] == 0)
	  /* 進んだ場合がしかるべき範囲に含まれかつ未到達の時に限り */
	  lst[temp]=3;
      }
    }
    for(i=0;i<N;i++){
      if(lst[i]==3){
	lst[i]=2; //調べ終わったので次に備えて3を2にする
	owa=0; //2のますがあったらowaじゃない
      }
    }
  }

  printf("%d\n", s);
  return 0;
}

int bitsum(int k){
  /* k<=10000よりk<2^15としてよい
   */
  int d=0, s=0;

  if(0<=k && k<10001) {
    for(;d<15;d++){
      s+=k%2;
      k=k >> 1;
    }
    return s;
  }
  else return 0;
}
0