diff options
Diffstat (limited to '05-advanced_algorithms_and_complexity/02-linear_programming/02-diet')
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 |