結果

問題 No.158 奇妙なお使い
コンテスト
ユーザー asugen0402
提出日時 2019-01-29 17:21:24
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 598 ms / 5,000 ms
コード長 3,866 bytes
コンパイル時間 991 ms
コンパイル使用メモリ 31,616 KB
実行使用メモリ 46,216 KB
最終ジャッジ日時 2024-07-01 11:07:59
合計ジャッジ時間 3,936 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 内部定数
#define D_CHG_CNT		2										// 換金数
#define D_TCNT_MAX		11										// 最大千円札数
#define D_HCNT_MAX		101										// 最大百円玉数
#define D_OCNT_MAX		10001									// 最大一円玉数

// 内部構造体 - 換金情報
typedef struct Chg {
	int miMoney;												// 必要額
	int miTCnt;													// 千円札数
	int miHCnt;													// 百円玉数
	int miOCnt;													// 一円玉数
} Chg;

// 内部変数
static FILE *szpFpI;											// 入力
static Chg sz1Chg[D_CHG_CNT];									// 換金
static int si3CCnt[D_TCNT_MAX][D_HCNT_MAX][D_OCNT_MAX];			// 換金回数[千円札数][百円玉数][一円玉数]
static int siMax;												// 最大回数

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

// 換金回数 - セット
int
fSetCCnt(
	int piTCnt					// <I> 千円札数
	, int piHCnt				// <I> 百円玉数
	, int piOCnt				// <I> 一円玉数
)
{
	int i, j, k;

	// 換金
	for (i = 0; i < D_CHG_CNT; i++) {

		// 千円札数
		int liTCnt = sz1Chg[i].miMoney / 1000;
		if (liTCnt > piTCnt) {
			liTCnt = piTCnt;
		}
		for (j = 0; j <= liTCnt; j++) {
			int liMoney = sz1Chg[i].miMoney - 1000 * j;

			// 百円玉数
			int liHCnt = liMoney / 100;
			if (liHCnt > piHCnt) {
				liHCnt = piHCnt;
			}
			for (k = 0; k <= liHCnt; k++) {

				// 一円玉数
				int liOCnt = liMoney - 100 * k;
				if (liOCnt > piOCnt) {
					continue;
				}

				// 換金
				int liTCnt2 = piTCnt - j + sz1Chg[i].miTCnt;
				int liHCnt2 = piHCnt - k + sz1Chg[i].miHCnt;
				int liOCnt2 = piOCnt - liOCnt + sz1Chg[i].miOCnt;

				// 換金回数 - 更新
				int liCnt = si3CCnt[piTCnt][piHCnt][piOCnt] + 1;
				if (si3CCnt[liTCnt2][liHCnt2][liOCnt2] >= liCnt) {
					continue;
				}
				si3CCnt[liTCnt2][liHCnt2][liOCnt2] = liCnt;

				// 最大回数 - 更新
				if (siMax < liCnt) {
					siMax = liCnt;
				}

				// 下位へ
				fSetCCnt(liTCnt2, liHCnt2, liOCnt2);
			}

		}
	}

	return 0;
}

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

	// データ - 初期化
	memset(si3CCnt, 0, sizeof(si3CCnt));						// 換金回数
	siMax = 0;													// 最大回数

	// 入力 - セット
#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

	// 各枚数 - 取得
	int liTCnt, liHCnt, liOCnt;
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d%d", &liTCnt, &liHCnt, &liOCnt);

	// 換金 - 取得
	for (i = 0; i < D_CHG_CNT; i++) {

		// 必要額
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d", &sz1Chg[i].miMoney);

		// 各枚数
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d%d", &sz1Chg[i].miTCnt, &sz1Chg[i].miHCnt, &sz1Chg[i].miOCnt);
	}

	// 換金回数 - セット
	fSetCCnt(liTCnt, liHCnt, liOCnt);

	// 結果 - セット
	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