結果

問題 No.3 ビットすごろく
ユーザー arishikiarishiki
提出日時 2016-04-02 00:37:00
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 26 ms / 5,000 ms
コード長 2,004 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 25,400 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-13 23:48:30
合計ジャッジ時間 1,959 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 3 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 8 ms
4,380 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 6 ms
4,380 KB
testcase_09 AC 13 ms
4,376 KB
testcase_10 AC 17 ms
4,376 KB
testcase_11 AC 12 ms
4,380 KB
testcase_12 AC 8 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 17 ms
4,376 KB
testcase_15 AC 25 ms
4,380 KB
testcase_16 AC 22 ms
4,376 KB
testcase_17 AC 25 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 25 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 17 ms
4,376 KB
testcase_23 AC 25 ms
4,380 KB
testcase_24 AC 26 ms
4,380 KB
testcase_25 AC 25 ms
4,380 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 2 ms
4,380 KB
testcase_28 AC 21 ms
4,380 KB
testcase_29 AC 11 ms
4,380 KB
testcase_30 AC 0 ms
4,376 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 11 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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