#include #include #include #include #include #include #include // 内部関数 int fGetCnt(int *, int *, int *); // 内部変数 static FILE *szpFpI; // 入力 static int siDel; // 減少値 // 内部変数 - テスト用 #ifdef D_TEST static int siRes; static FILE *szpFpA; #endif // 数値 - 入れ替え int fSwap( int *pipVal1 // 値1 , int *pipVal2 // 値2 ) { int liWork = *pipVal1; *pipVal1 = *pipVal2; *pipVal2 = liWork; return 0; } // 高さ - 減少 int fDel( int *pipVal // 値 , int piCnt // 回数 ) { // 値 - チェック if (*pipVal == 0) { return -1; } if (siDel < 1) { return -1; } // 値 - 減少 *pipVal -= siDel * piCnt; if (*pipVal < 0) { *pipVal = 0; } return piCnt; } // 回数 - 取得 - 真ん中を最大化 or 最小化 int fGetCntM( int piMode // [1]:最大化 [-1]:最小化 , int *pipBM // 真ん中の竹 , int *pipBL // 片側(大) , int *pipBS // 片側(小) ) { int liRet, liDCnt; // 削除回数 if (siDel < 1) { return INT_MAX; } if (piMode > 0) { liDCnt = (*pipBL - *pipBM) / siDel + 1; liDCnt = fDel(pipBL, liDCnt); } else { liDCnt = (*pipBM - *pipBS) / siDel + 1; liDCnt = fDel(pipBM, liDCnt); } if (liDCnt < 0) { return INT_MAX; } // 再帰 liRet = fGetCnt(pipBM, pipBL, pipBS); if (liRet < 0) { return INT_MAX; } return liDCnt + liRet; } // 回数 - 取得 int fGetCnt( int *pipBM // 真ん中の竹 , int *pipBL // 片側(大) , int *pipBS // 片側(小) ) { int liRet, liDCnt; // 3本同一 if (*pipBM == *pipBL && *pipBL == *pipBS) { liDCnt = fDel(pipBS, 1); if (liDCnt < 0) { return -1; } // 再帰 liRet = fGetCnt(pipBM, pipBL, pipBS); if (liRet < 0) { return -1; } return liDCnt + liRet; } // 2本同一 - 真ん中と片側(小) if (*pipBM == *pipBS) { liDCnt = fDel(pipBM, 1); if (liDCnt < 0) { return -1; } // 再帰 liRet = fGetCnt(pipBM, pipBL, pipBS); if (liRet < 0) { return -1; } return liDCnt + liRet; } // 2本同一 - 真ん中と片側(大) or 片側(大)と片側(小) if (*pipBM == *pipBL || *pipBL == *pipBS) { liDCnt = fDel(pipBL, 1); if (liDCnt < 0) { return -1; } if (*pipBL < *pipBS) { fSwap(pipBL, pipBS); } // 再帰 liRet = fGetCnt(pipBM, pipBL, pipBS); if (liRet < 0) { return -1; } return liDCnt + liRet; } // 片側(大) > 真ん中 > 片側(小) if (*pipBL > *pipBM && *pipBM > *pipBS) { // 真ん中を最大化 int liBM1 = *pipBM; int liBL1 = *pipBL; int liBS1 = *pipBS; int liCnt1 = fGetCntM(1, &liBM1, &liBL1, &liBS1); // 真ん中を最小化 int liBM2 = *pipBM; int liBL2 = *pipBL; int liBS2 = *pipBS; int liCnt2 = fGetCntM(-1, &liBM2, &liBL2, &liBS2); // 少ない回数を適用 if (liCnt1 < liCnt2) { *pipBM = liBM1; *pipBL = liBL1; *pipBS = liBS1; liDCnt = liCnt1; } else if (liCnt1 == INT_MAX) { return -1; } else { *pipBM = liBM2; *pipBL = liBL2; *pipBS = liBS2; liDCnt = liCnt2; } // 再帰 liRet = fGetCnt(pipBM, pipBL, pipBS); if (liRet < 0) { return -1; } return liDCnt + liRet; } return 0; } // 実行メイン int fMain( int piTNo // テスト番号 1~ ) { char lc1Buf[1024], lc1Out[1024]; // 入力 - セット #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", &siDel); // 片側の竹(大) - 取得 int liBL; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &liBL); // 真ん中の竹 - 取得 int liBM; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &liBM); // 片側の竹(小) - 取得 int liBS; fgets(lc1Buf, sizeof(lc1Buf), szpFpI); sscanf(lc1Buf, "%d", &liBS); if (liBL < liBS) { fSwap(&liBL, &liBS); } // 回数 - 取得 int liCnt = fGetCnt(&liBM, &liBL, &liBS); // 結果 - セット sprintf(lc1Out, "%d\n", liCnt); // 結果 - 表示 #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; }