結果

問題 No.3 ビットすごろく
ユーザー jokin_tokeijokin_tokei
提出日時 2017-10-14 18:16:57
言語 C
(gcc 12.3.0)
結果
RE  
実行時間 -
コード長 2,954 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-17 14:45:09
合計ジャッジ時間 3,449 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

// I referred to the follow
// http://www.geocities.jp/m_hiroi/puzzle/puzdoc03.html

#define SUCCESS 1
#define FAILURE 0

#define THOUSAND 1000
#define HUNDRED 100

void bit_map();    // main
int next_go(int num, int goal);  //
int back_go(int num);
int Is_already_reach(int reach_point);

void bit_map() {          // 先に進む中で到着する点までは行くことができる。いったん戻ってから先に進むと到着できる点には行けない。(11のデバッグ途中で力尽きる)
	int goal;
	int queue[HUNDRED][THOUSAND] = { };  // 要素数はfree!!
	int front, rear;
	int back_point, next_point;
	int length[THOUSAND] = { };
	int i;  // loop variable

	scanf("%d", &goal);

	if(goal == 1){
		printf("%d", 1);
		exit(0);
	}

	front = 0;
	rear = 1;
	length[0] = 1;

	queue[0][0] = 1;
	i = 0;

	// infinite loop counter measure
	int debug = 0;
	while (front < rear && debug++ < 100) {
		int len = length[front];  //  ex 1, 12, 123, 124 ...4

		next_point = next_go(queue[front][len - 1], goal);
		if (next_point == goal) {
			printf("%d", len+1);
			exit(0);
		} else if (next_point == FAILURE) {

		} else {    // new root add the queue
			memcpy(queue[rear], queue[front], sizeof(int) * len);
			queue[rear][len] = next_point;
			length[rear] = len + 1;
			rear++;
		}

		// follow is back
		back_point = back_go(queue[front][len-1]);
		if (back_point == FAILURE) {

		} else {   // new back root add the queue
			memcpy(queue[rear], queue[front], sizeof(int) * len);
			queue[rear][len] = back_point;
			length[rear] = len + 1;
			rear++;
		}
		front++;
	}
	printf("-1");

}

int next_go(int num, int goal) {   //Outputs the point that arrived earlier from the given num

	int ad_re_num = 0;
	int next_point = num;

	while (num > 0) {
		ad_re_num += num % 2;
		num = num / 2;
	}

	next_point += ad_re_num;

	if (next_point > goal) {
		return FAILURE;
	}

	if (Is_already_reach(next_point) == SUCCESS) {
		return next_point;
	} else {
		return FAILURE;
	}
}

int back_go(int num) {    //Proceed to the back from the given argument and output the arrival point
	int ad_re_num = 0;
	int back_point = num;

	while (num > 0) {
		ad_re_num += num % 2;
		num = num / 2;
	}

	back_point -= ad_re_num;
	if (back_point < 1) {
		return FAILURE;
	}

	if (Is_already_reach(back_point) == SUCCESS) {
		return back_point;
	} else {
		return FAILURE;
	}
}

int Is_already_reach(int reach_point) {
	static int already_reach[THOUSAND] = { };
	int i = 0;

	already_reach[0] = 1;

	for (i = 0; already_reach[i] != '\0'; i++) {
		if (reach_point == already_reach[i]) {
			return FAILURE;
		}
	}

	already_reach[i] = reach_point;

	return SUCCESS;

}

int main(void) {
//	int ma1[2][5] = {{1,2,3,4,5},{6,7,8,9,0}};
//	int ma2[2][5] = {};
//
//
//	memcpy(ma2[1] , ma1[1], sizeof(int) * 2);

	bit_map();

//	printf("%d  %d",next_go(13,100),back_go(1));

	return 0;
}
0