Algorithms : add 05-advanced_algorithms_and_complexity 02-linear_programming

17 files changed, 108 insertions, 0 deletions

diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/diet.cpp b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/diet.cpp
new file mode 100644
index 0000000..efe4e89
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/diet.cpp
@@ -0,0 +1,56 @@
+#include <algorithm>
+#include <iostream>
+#include <vector>
+#include <cstdio>
+using namespace std;
+
+typedef vector<vector<double>> matrix;
+
+pair<int, vector<double>> solve_diet_problem(
+    int n,
+    int m,
+    matrix A,
+    vector<double> b,
+    vector<double> c) {
+
+  // Write your code here
+
+  return {0, vector<double>(m, 0)};
+}
+
+int main(){
+  int n, m;
+  cin >> n >> m;
+  matrix A(n, vector<double>(m));
+  for (int i = 0; i < n; i++) {
+    for (int j = 0; j < m; j++) {
+      cin >> A[i][j];
+    }
+  }
+  vector<double> b(n);
+  for (int i = 0; i < n; i++) {
+    cin >> b[i];
+  }
+  vector<double> c(m);
+  for (int i = 0; i < m; i++) {
+    cin >> c[i];
+  }
+
+  pair<int, vector<double>> ans = solve_diet_problem(n, m, A, b, c);
+
+  switch (ans.first) {
+    case -1:
+      printf("No solution\n");
+      break;
+    case 0:
+      printf("Bounded solution\n");
+      for (int i = 0; i < m; i++) {
+        printf("%.18f%c", ans.second[i], " \n"[i + 1 == m]);
+      }
+      break;
+    case 1:
+      printf("Infinity\n");
+      break;
+  }
+  return 0;
+}
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/01 b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/01
new file mode 100644
index 0000000..131e04c
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/01
@@ -0,0 +1,6 @@
+3 2
+-1 -1
+1 0
+0 1
+-1 2 2
+-1 2
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/01.a b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/01.a
new file mode 100644
index 0000000..32b2fa2
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/01.a
@@ -0,0 +1,2 @@
+Bounded solution
+-0.00000000000000 2.00000000000000
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/02 b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/02
new file mode 100644
index 0000000..311f32f
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/02
@@ -0,0 +1,5 @@
+2 2
+1 1
+-1 -1
+1 -2
+1 1
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/02.a b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/02.a
new file mode 100644
index 0000000..3deb2e2
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/02.a
@@ -0,0 +1 @@
+No solution
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/03 b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/03
new file mode 100644
index 0000000..ea6c924
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/03
@@ -0,0 +1,4 @@
+1 3
+0 0 1
+3
+1 1 1
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/03.a b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/03.a
new file mode 100644
index 0000000..3c62151
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/03.a
@@ -0,0 +1 @@
+Infinity
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/04 b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/04
new file mode 100644
index 0000000..276e03d
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/04
@@ -0,0 +1,4 @@
+1 1
+26
+4362
+27
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/04.a b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/04.a
new file mode 100644
index 0000000..9e3294b
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/04.a
@@ -0,0 +1,2 @@
+Bounded solution
+167.76923076923077
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/05 b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/05
new file mode 100644
index 0000000..aa71cd8
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/05
@@ -0,0 +1,4 @@
+1 1
+26
+8613
+27
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/05.a b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/05.a
new file mode 100644
index 0000000..f4a95cc
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/05.a
@@ -0,0 +1,2 @@
+Bounded solution
+331.26923076923077
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/06 b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/06
new file mode 100644
index 0000000..fbb4837
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/06
@@ -0,0 +1,4 @@
+1 1
+30
+1680
+-87
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/06.a b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/06.a
new file mode 100644
index 0000000..54226c3
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/06.a
@@ -0,0 +1,2 @@
+Bounded solution
+-0.00000000000000
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/36 b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/36
new file mode 100644
index 0000000..a1d491f
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/36
@@ -0,0 +1,6 @@
+3 1
+69
+-29
+-44
+6073 -2551 -3871
+-10
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/36.a b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/36.a
new file mode 100644
index 0000000..7c370cf
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/36.a
@@ -0,0 +1,2 @@
+Bounded solution
+87.97727272727273
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/43 b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/43
new file mode 100644
index 0000000..db9dd15
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/43
@@ -0,0 +1,6 @@
+3 3
+-88 -2 59
+-46 -46 14
+37 49 78
+11412 -1040 -27722
+16 66 95
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/43.a b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/43.a
new file mode 100644
index 0000000..3deb2e2
--- /dev/null
+++ b/05-advanced_algorithms_and_complexity/02-linear_programming/02-diet/tests/43.a
@@ -0,0 +1 @@
+No solution