結果
問題 | No.320 眠れない夜に |
ユーザー | 小指が強い人 |
提出日時 | 2015-12-13 03:53:14 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,346 bytes |
コンパイル時間 | 806 ms |
コンパイル使用メモリ | 75,400 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 11:03:18 |
合計ジャッジ時間 | 1,772 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 2 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
testcase_26 | AC | 2 ms
5,376 KB |
testcase_27 | AC | 2 ms
5,376 KB |
testcase_28 | AC | 2 ms
5,376 KB |
testcase_29 | AC | 1 ms
5,376 KB |
testcase_30 | AC | 2 ms
5,376 KB |
testcase_31 | AC | 2 ms
5,376 KB |
testcase_32 | AC | 2 ms
5,376 KB |
testcase_33 | AC | 2 ms
5,376 KB |
testcase_34 | AC | 2 ms
5,376 KB |
ソースコード
#include <iostream>#include <unordered_map>using namespace std;typedef long long int64;int64 fib[80 + 1] = {0, 1, 1};unordered_map<int,unordered_map<int64, int>> memo;int64 n, m;int solve(int i, int64 k, int d){if(memo.find(i) != memo.end() && memo[i].find(k) != memo[i].end())return memo[i][k];if(k == m)return memo[i][k] = d;if(i > n || k < m)return memo[i][k] = -1;int res1 = solve(i + 1, k, d);int res2 = solve(i + 1, k - fib[i], d + 1);if(res1 == -1)return memo[i][k] = res2;if(res2 == -1)return memo[i][k] = res1;return memo[i][k] = (res1 < res2) ? res1 : res2;}int solve2(int i, int64 k, int d){int j = i;while(j >= 1 && k - fib[j] < m)j--;if(j < 1)return -1;if(k - fib[j] == m)return d + 1;int res1 = -1;int res2 = -1;res1 = solve2(j - 1, k - fib[j], d + 1);//res2 = solve2(j - 2, k - fib[j - 1], d + 1);if(res1 == -1)return res2;if(res2 == -1)return res1;return (res1 < res2) ? res1 : res2;}int main(void){cin >> n >> m;for(int i = 3; i <= n; i++)fib[i] = fib[i - 1] + fib[i - 2];if(fib[n] == m){cout << 0 << endl;return 0;}cout << solve2(n - 2, fib[n], 0) << endl;return 0;}