結果

問題 No.12 限定された素数
ユーザー asugen0402asugen0402
提出日時 2019-01-23 15:18:25
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 154 ms / 5,000 ms
コード長 4,042 bytes
コンパイル時間 963 ms
コンパイル使用メモリ 30,688 KB
実行使用メモリ 6,800 KB
最終ジャッジ日時 2023-08-16 00:57:08
合計ジャッジ時間 5,298 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 113 ms
6,800 KB
testcase_01 AC 96 ms
6,716 KB
testcase_02 AC 85 ms
6,788 KB
testcase_03 AC 110 ms
6,712 KB
testcase_04 AC 95 ms
6,668 KB
testcase_05 AC 109 ms
6,656 KB
testcase_06 AC 111 ms
6,712 KB
testcase_07 AC 110 ms
6,720 KB
testcase_08 AC 106 ms
6,776 KB
testcase_09 AC 110 ms
6,776 KB
testcase_10 AC 109 ms
6,668 KB
testcase_11 AC 108 ms
6,736 KB
testcase_12 AC 102 ms
6,700 KB
testcase_13 AC 102 ms
6,776 KB
testcase_14 AC 101 ms
6,716 KB
testcase_15 AC 98 ms
6,776 KB
testcase_16 AC 98 ms
6,660 KB
testcase_17 AC 154 ms
6,660 KB
testcase_18 AC 97 ms
6,664 KB
testcase_19 AC 95 ms
6,760 KB
testcase_20 AC 98 ms
6,712 KB
testcase_21 AC 103 ms
6,656 KB
testcase_22 AC 104 ms
6,712 KB
testcase_23 AC 105 ms
6,688 KB
testcase_24 AC 137 ms
6,696 KB
testcase_25 AC 108 ms
6,700 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_ON			1										// 汎用フラグ - ON
#define D_OFF			0										// 汎用フラグ - OFF
#define D_NUM_MAX		5000000									// 最大値

// 内部変数
static FILE *szpFpI;											// 入力
static char sc1Prm[D_NUM_MAX + 5];								// 素数
static int si1Need[10];											// 必要な数字
static int si1Now[10];											// 現在の数字
static int siMax;												// 最大範囲

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
#endif

// 素数 - 初期化
int
fIniPrm(
)
{
	// 初期値
	memset(sc1Prm, D_ON, sizeof(sc1Prm));
	sc1Prm[1] = D_OFF;

	// 開始
	int liPrm = 2;
	while (1) {

		// 素数の倍数をOFF
		int liVal = liPrm * 2;
		while (liVal <= D_NUM_MAX) {
			sc1Prm[liVal] = D_OFF;
			liVal += liPrm;
		}

		// 次の素数を検索
		while (1) {
			liPrm++;
			if (liPrm > D_NUM_MAX) {
				return 0;
			}
			if (sc1Prm[liPrm] == D_ON) {
				break;
			}
		}
	}

	return 0;
}

// 状況 - 取得
int
fGetSts(
)
{
	int i;

	int liNGCnt = 0;
	for (i = 0; i < 10; i++) {

		// 必要な数字チェック
		if (si1Need[i] > 0 && si1Now[i] == 0) {		// なし
			return -1;
		}

		// 余計な数字チェック
		if (si1Need[i] == 0 && si1Now[i] > 0) {
			liNGCnt++;
		}
	}

	// 余計な数字
	if (liNGCnt > 0) {							// あり
		return 1;
	}

	return 0;
}

// 現在の数字 - 加算
int
fAddNow(
	int piPrm					// <I> 素数
	, int piAdd					// <I> [1]加算 [-1]減算
)
{
	while (piPrm > 0) {

		// 対象数字
		int liNum = piPrm % 10;
		si1Now[liNum] += piAdd;

		// 桁移動
		piPrm /= 10;
	}

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i;
	char lc1Buf[1024], lc1Out[1024];

	// データ - 初期化
	memset(si1Now, 0, sizeof(si1Now));							// 現在の数字
	siMax = -1;													// 最大範囲

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 素数 - 初期化
	fIniPrm();

	// 必要な数字の数 - 取得
	int liCnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d", &liCnt);

	// 必要な数字 - 取得
	memset(si1Need, 0, sizeof(si1Need));
	for (i = 0; i < liCnt; i++) {
		int liNum;
		fscanf(szpFpI, "%d", &liNum);
		si1Need[liNum] = 1;
	}
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);

	// 範囲 - 初期化
	int liSNo = 1;
	int liENo = 1;

	// 範囲 - 取得
	while (1) {

		// 状況 - 取得
		int liSts = fGetSts();

		if (liSts == 0) {					// OK

			// 最大範囲 - 更新
			int liRng = liENo - liSNo;
			if (siMax < liRng) {
				siMax = liRng;
			}
		}

		if (liSts <= 0) {					// OK or 必要な数字なし
			liENo++;
			if (liENo > D_NUM_MAX) {
				break;
			}

			// 素数チェック
			if (sc1Prm[liENo] == D_ON) {		// 素数
				fAddNow(liENo, 1);					// 現在の数字 - 加算
			}
		}
		else if (liSts > 0) {				// 余計な数字あり

			// 素数チェック
			if (sc1Prm[liSNo] == D_ON) {		// 素数
				fAddNow(liSNo, -1);					// 現在の数字 - 減算
			}

			liSNo++;
		}
	}

	// 結果 - セット
	sprintf(lc1Out, "%d\n", siMax);

	// 結果 - 表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}
0