[C++]白準17968号:Fire on Field
5721 ワード
質問リンク
17968号:Fire on Field
問題の概要
数列AのA[0]A[0]A[0]およびA[1]A[1]A[1]は1である.iが2より大きい場合、a[i]は、以下を求めることができる.
k>0 k>0 k>0に対して、i-2 k≧0 i-2 kgeq 0 i-2 k≧0のすべての整数k
A[i]−A[i−k]≠A[i−k]−A[i−2×k]A[i] - A[i - k]\neq A[i -k] - A[i - 2\times k]A[i]−A[i−k]=A[i−k]−A[i−2×k]が成立する最小正の整数はA[i]である.
Nが与えられた場合、A[N]A[N]A[N]を出力する必要がある.
方法
簡単な実装、DP問題.A[0]、A[1]は予め値を初期化し、A[2]はすべてのkが条件に合致することを保証するために値を1から1に増やし始める.成立が見つかった場合、ループを終了し、次のA[i]値を得る.
コード#コード#
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int n;
cin >> n;
vector<int> a(n + 1);
a[0] = a[1] = 1;
for (int i = 2; i <= n; i++) {
int num = 1;
while (1) {
bool flag = false;
a[i] = num++;
for (int j = 1; i - 2 * j >= 0; j++) {
if (a[i] - a[i - j] == a[i - j] - a[i - 2 * j]) {
flag = true;
break;
}
}
if (!flag)
break;
}
}
cout << a[n] << '\n';
return 0;
}
Reference
この問題について([C++]白準17968号:Fire on Field), 我々は、より多くの情報をここで見つけました https://velog.io/@beclever/C-백준-17968번-Fire-on-Fieldテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol