#include #include #include #include #include #include // 内部定数 #define D_ON 1 // 汎用フラグ - ON #define D_OFF 0 // 汎用フラグ - OFF #define D_WCNT_MAX 100 // 最大おもり数 #define D_WEIGHT_MAX 100 // 最大重さ // 内部変数 static FILE *szpFpI; // 入力 static int siWCnt; // おもり数 static int si1Weight[D_WCNT_MAX]; // 重さ[おもり] static int si2Done[D_WCNT_MAX][D_WEIGHT_MAX * D_WCNT_MAX + 5]; // 処理済フラグ[選択数][重さ合計] // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; #endif // ソート関数 - int昇順 int fSortFnc( const void *pzpVal1 // 値1 , const void *pzpVal2 // 値2 ) { int *lipVal1 = (int *)pzpVal1; int *lipVal2 = (int *)pzpVal2; // int昇順 if (*lipVal1 > *lipVal2) { return(1); } else if (*lipVal1 < *lipVal2) { return(-1); } return 0; } // 判定 int fJudge( int piWCnt // おもり数 , int piLSum // 重さ合計 - 左 , int piRSum // 重さ合計 - 右 ) { int liRet; // 終了チェック if (piWCnt == siWCnt) { if (piLSum == piRSum) { return 0; } else { return -1; } } // 処理済フラグ if (si2Done[piWCnt][piLSum] != D_OFF) { return -1; } si2Done[piWCnt][piLSum] = D_ON; // 左へ liRet = fJudge(piWCnt + 1, piLSum + si1Weight[piWCnt], piRSum); if (liRet == 0) { return 0; } // 右へ liRet = fJudge(piWCnt + 1, piLSum, piRSum + si1Weight[piWCnt]); if (liRet == 0) { return 0; } return -1; } // 実行メイン int fMain( int piTNo // テスト番号 1~ ) { int i, liRet; char lc1Buf[1024], lc1Out[1024]; // データ - 初期化 memset(si2Done, D_OFF, sizeof(si2Done)); // 処理済フラグ // 入力 - セット #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 // おもり数 - 取得 fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &siWCnt); // 重さ - 取得 for (i = 0; i < siWCnt; i++) { fscanf(szpFpI, "%d", &si1Weight[i]); } fgets(lc1Buf, sizeof(lc1Buf), szpFpI); // 重さ - ソート qsort(si1Weight, siWCnt, sizeof(int), fSortFnc); // 判定 liRet = fJudge(0, 0, 0); // 結果 - セット if (liRet == 0) { sprintf(lc1Out, "possible\n"); } else { sprintf(lc1Out, "impossible\n"); } // 結果 - 表示 #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; }