From 16620176eaf6ebf6e7e24a4e27f3e68f7431f2fc Mon Sep 17 00:00:00 2001
From: Angel Dimitriev <achi_d@abv.bg>
Date: Mon, 17 Jan 2022 02:00:07 +0200
Subject: Add files via upload

---
 Sem. 15/task1.cpp | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 46 insertions(+)
 create mode 100644 Sem. 15/task1.cpp

(limited to 'Sem. 15/task1.cpp')

diff --git a/Sem. 15/task1.cpp b/Sem. 15/task1.cpp
new file mode 100644
index 0000000..502b7a5
--- /dev/null
+++ b/Sem. 15/task1.cpp	
@@ -0,0 +1,46 @@
+#include <iostream>
+
+int min(int a, int b)
+{
+	return a < b ? a : b;
+}
+int min(int a, int b, int c)
+{
+	return min(min(a, b), c);
+}
+int getMinOperations(size_t N, int* cache)
+{
+	if (N == 1)
+		return 0;
+
+	if (cache[N] != 0)
+		return cache[N];
+
+	int dvBy3 = INT_MAX;
+	int dvBy2 = INT_MAX;
+	int s1 = INT_MAX;
+
+	if (N % 3 == 0)
+		dvBy3 = getMinOperations(N / 3, cache);
+	if (N % 2 == 0)
+		dvBy2 = getMinOperations(N / 2, cache);
+	s1 = getMinOperations(N - 1, cache);
+
+	int result = 1 + min(dvBy2, dvBy3, s1);
+	cache[N] = result;
+	return result;
+}
+
+int getMinOperationsWrapper(size_t N)
+{
+	int* cache = new int[N + 1];
+	for (size_t i = 0; i < N + 1; i++)
+		cache[i] = 0;
+
+	return getMinOperations(N, cache);
+}
+
+int main()
+{
+	std::cout << getMinOperationsWrapper(19);// 1 -> 3 -> 6 -> 18 -> 19
+}
\ No newline at end of file
-- 
cgit v1.3.1-23-gd82d