diff options
Diffstat (limited to '01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator')
7 files changed, 40 insertions, 0 deletions
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp new file mode 100644 index 0000000..0131b53 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp @@ -0,0 +1,31 @@ +#include <iostream> +#include <vector> +#include <algorithm> + +using std::vector; + +vector<int> optimal_sequence(int n) { + std::vector<int> sequence; + while (n >= 1) { + sequence.push_back(n); + if (n % 3 == 0) { + n /= 3; + } else if (n % 2 == 0) { + n /= 2; + } else { + n = n - 1; + } + } + reverse(sequence.begin(), sequence.end()); + return sequence; +} + +int main() { + int n; + std::cin >> n; + vector<int> sequence = optimal_sequence(n); + std::cout << sequence.size() - 1 << std::endl; + for (size_t i = 0; i < sequence.size(); ++i) { + std::cout << sequence[i] << " "; + } +} diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01 new file mode 100644 index 0000000..d00491f --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01 @@ -0,0 +1 @@ +1 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a new file mode 100644 index 0000000..2734518 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a @@ -0,0 +1,2 @@ +0 +1 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02 new file mode 100644 index 0000000..7ed6ff8 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02 @@ -0,0 +1 @@ +5 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a new file mode 100644 index 0000000..fc544c9 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a @@ -0,0 +1,2 @@ +3 +1 2 4 5 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03 new file mode 100644 index 0000000..c18d157 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03 @@ -0,0 +1 @@ +96234 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a new file mode 100644 index 0000000..55a1c62 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a @@ -0,0 +1,2 @@ +14 +1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234 |