結果
問題 | No.320 眠れない夜に |
ユーザー |
![]() |
提出日時 | 2016-10-23 19:08:27 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,822 bytes |
コンパイル時間 | 688 ms |
コンパイル使用メモリ | 77,780 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-24 02:04:14 |
合計ジャッジ時間 | 1,935 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 31 |
ソースコード
#include <iostream>#include <tuple>#include <vector>#include <cstdio>#include <map>#include <algorithm>using namespace std;typedef long long ll;const int INF = 1e9;#define rep(i,n) for(int i=0;i<(n);i++)// のこり n 回 普通のフィボナッチ数列をやった場合いくつになるかを求めるll upper(ll a, ll b, ll n){vector<ll> dp(n + 10);dp[0] = a, dp[1] = b;for (int i = 2; i < n + 2; ++i){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n + 1];}// のこり n 回 毎回 -1 するフィボナッチ数列をやった場合いくつになるかを求めるll lower(ll a, ll b, ll n){vector<ll> dp(n + 10);dp[0] = a, dp[1] = b;for (int i = 2; i < n + 2; ++i){dp[i] = dp[i - 1] + dp[i - 2] - 1;}return dp[n + 1];}map<tuple<ll, ll, int, ll>, int> memo;// fib3 = fib2(b) + fib1(a) n:残りの回数 m:目指す値int branch_and_bound(ll a, ll b, int n, ll m){auto key = make_tuple(a, b, n, m);if(memo.count(key)) return memo[key];if(n == 0){if(b == m){//正解return memo[key] = 0;//間違えたの 0回}else{return memo[key] = INF;}}// どんなに間違えなくても、mに達しない (上界)if(upper(a, b, n) < m){return memo[key] = INF;}//どんなに間違えても、mより小さくできない (下界)if(lower(a, b, n) > m){return memo[key] = INF;}//普通のフィボナッチ数列int ret1 = branch_and_bound(b, a + b, n - 1, m);//-1したフィボナッチ数列int ret2 = branch_and_bound(b, a + b - 1, n - 1, m) + 1;//間違える回数が少ないほうを選択return memo[key] = min(ret1, ret2);}int main(void){int n;ll m;cin >> n >> m;int ret = branch_and_bound(1, 1, n - 2, m);if(ret == INF){printf("-1\n");}else{printf("%d\n", ret);}return 0;}