diff options
| author | Jérémy Zurcher <jeremy@asynk.ch> | 2022-03-25 09:36:09 +0100 |
|---|---|---|
| committer | Jérémy Zurcher <jeremy@asynk.ch> | 2022-03-25 09:36:09 +0100 |
| commit | 7b224832b3795baaa5334f5f8f352c7aec330ae5 (patch) | |
| tree | 3efad8638cd3b9cfacbca5982a40360352d2ebd0 /05-advanced_algorithms_and_complexity/02-linear_programming | |
| parent | 2bfae41038b8b5c82eb8109ca59d556fff65fadd (diff) | |
| download | coursera-7b224832b3795baaa5334f5f8f352c7aec330ae5.zip coursera-7b224832b3795baaa5334f5f8f352c7aec330ae5.tar.gz | |
Algorithms : add 05-advanced_algorithms_and_complexity 02-linear_programming
Diffstat (limited to '05-advanced_algorithms_and_complexity/02-linear_programming')
96 files changed, 923 insertions, 0 deletions
diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/00_linear_programming.pdf b/05-advanced_algorithms_and_complexity/02-linear_programming/00_linear_programming.pdf Binary files differnew file mode 100644 index 0000000..e954c13 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/00_linear_programming.pdf diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/energy_values.cpp b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/energy_values.cpp new file mode 100644 index 0000000..b7956a7 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/energy_values.cpp @@ -0,0 +1,104 @@ +#include <cmath> +#include <iostream> +#include <vector> + +const double EPS = 1e-6; +const int PRECISION = 20; + +typedef std::vector<double> Column; +typedef std::vector<double> Row; +typedef std::vector<Row> Matrix; + +struct Equation { + Equation(const Matrix &a, const Column &b): + a(a), + b(b) + {} + + Matrix a; + Column b; +}; + +struct Position { + Position(int column, int row): + column(column), + row(row) + {} + + int column; + int row; +}; + +Equation ReadEquation() { + int size; + std::cin >> size; + Matrix a(size, std::vector <double> (size, 0.0)); + Column b(size, 0.0); + for (int row = 0; row < size; ++row) { + for (int column = 0; column < size; ++column) + std::cin >> a[row][column]; + std::cin >> b[row]; + } + return Equation(a, b); +} + +Position SelectPivotElement( + const Matrix &a, + std::vector <bool> &used_rows, + std::vector <bool> &used_columns) { + // This algorithm selects the first free element. + // You'll need to improve it to pass the problem. + Position pivot_element(0, 0); + while (used_rows[pivot_element.row]) + ++pivot_element.row; + while (used_columns[pivot_element.column]) + ++pivot_element.column; + return pivot_element; +} + +void SwapLines(Matrix &a, Column &b, std::vector <bool> &used_rows, Position &pivot_element) { + std::swap(a[pivot_element.column], a[pivot_element.row]); + std::swap(b[pivot_element.column], b[pivot_element.row]); + std::swap(used_rows[pivot_element.column], used_rows[pivot_element.row]); + pivot_element.row = pivot_element.column; +} + +void ProcessPivotElement(Matrix &a, Column &b, const Position &pivot_element) { + // Write your code here +} + +void MarkPivotElementUsed(const Position &pivot_element, std::vector <bool> &used_rows, std::vector <bool> &used_columns) { + used_rows[pivot_element.row] = true; + used_columns[pivot_element.column] = true; +} + +Column SolveEquation(Equation equation) { + Matrix &a = equation.a; + Column &b = equation.b; + int size = a.size(); + + std::vector <bool> used_columns(size, false); + std::vector <bool> used_rows(size, false); + for (int step = 0; step < size; ++step) { + Position pivot_element = SelectPivotElement(a, used_rows, used_columns); + SwapLines(a, b, used_rows, pivot_element); + ProcessPivotElement(a, b, pivot_element); + MarkPivotElementUsed(pivot_element, used_rows, used_columns); + } + + return b; +} + +void PrintColumn(const Column &column) { + int size = column.size(); + std::cout.precision(PRECISION); + for (int row = 0; row < size; ++row) + std::cout << column[row] << std::endl; +} + +int main() { + Equation equation = ReadEquation(); + Column solution = SolveEquation(equation); + PrintColumn(solution); + return 0; +} diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/01 b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/01 new file mode 100644 index 0000000..573541a --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/01 @@ -0,0 +1 @@ +0 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/01.a b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/01.a new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/01.a diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/02 b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/02 new file mode 100644 index 0000000..9c4fceb --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/02 @@ -0,0 +1,5 @@ +4 +1 0 0 0 1 +0 1 0 0 5 +0 0 1 0 4 +0 0 0 1 3 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/02.a b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/02.a new file mode 100644 index 0000000..de24e7d --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/02.a @@ -0,0 +1,4 @@ +1 +5 +4 +3 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/03 b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/03 new file mode 100644 index 0000000..9fe7e97 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/03 @@ -0,0 +1,3 @@ +2 +1 1 3 +2 3 7 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/03.a b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/03.a new file mode 100644 index 0000000..5f1d0ec --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/03.a @@ -0,0 +1,2 @@ +2 +1 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/04 b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/04 new file mode 100644 index 0000000..20669c3 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/04 @@ -0,0 +1,3 @@ +2 +5 -5 -1 +-1 -2 -1 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/04.a b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/04.a new file mode 100644 index 0000000..6b11ee2 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/01-energy_values/tests/04.a @@ -0,0 +1,2 @@ +0.2 +0.4 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 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/ad_allocation.cpp b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/ad_allocation.cpp new file mode 100644 index 0000000..88bd8e6 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/ad_allocation.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>> allocate_ads( + 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 = allocate_ads(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/03-ad_allocation/tests/00 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/00 new file mode 100644 index 0000000..4d1319b --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/00 @@ -0,0 +1,5 @@ +2 2 +1 1 +-1 1 +10 -10 +1 2 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/00.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/00.a new file mode 100644 index 0000000..ef8a4cf --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/00.a @@ -0,0 +1,2 @@ +Bounded solution +10.000000000000000000 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/01 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/01 new file mode 100644 index 0000000..131e04c --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/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/03-ad_allocation/tests/01.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/01.a new file mode 100644 index 0000000..71a03d8 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/01.a @@ -0,0 +1,2 @@ +Bounded solution +0.000000000000000000 2.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/02 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/02 new file mode 100644 index 0000000..311f32f --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/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/03-ad_allocation/tests/02.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/02.a new file mode 100644 index 0000000..3deb2e2 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/02.a @@ -0,0 +1 @@ +No solution diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/03 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/03 new file mode 100644 index 0000000..5c2a7de --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/03 @@ -0,0 +1,6 @@ +3 3 +2 1 1 +1 3 2 +2 1 2 +180 300 240 +6 5 4 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/03.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/03.a new file mode 100644 index 0000000..263dd93 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/03.a @@ -0,0 +1,2 @@ +Bounded solution +48.000000000000000000 84.000000000000000000 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/04 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/04 new file mode 100644 index 0000000..f9d16c5 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/04 @@ -0,0 +1,10 @@ + 7 7 +-62 -40 -77 -91 46 -64 40 +52 11 41 51 40 -71 87 +-57 73 -66 89 18 11 91 +34 -68 87 -32 19 -1 37 +-74 24 -13 29 97 -91 -86 +69 24 -70 67 -68 -98 76 +89 86 -1 -2 -77 -62 -27 +769628 -834013 499389 616207 -254336 -994356 -56081 +-7 -80 -96 -87 -20 56 14 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/04.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/04.a new file mode 100644 index 0000000..3abe1da --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/04.a @@ -0,0 +1,2 @@ +Bounded solution +6031244.782175937667489052 2821669.525851520244032145 0.000000000000000000 0.000000000000000000 0.000000000000000000 12572587.836078854277729988 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/05 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/05 new file mode 100644 index 0000000..4e919ac --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/05 @@ -0,0 +1,13 @@ +10 9 +17 39 69 62 72 -76 -57 -37 -16 +19 11 -84 -30 -69 65 29 -9 -67 +-17 -37 -84 49 72 27 -60 -96 -30 +46 -44 8 -93 39 57 -98 5 -24 +11 -99 -35 -9 73 90 -51 -53 100 +35 -41 54 -96 -38 -44 40 -38 -42 +55 -27 53 -56 -42 77 -38 20 -33 +18 -26 5 77 100 -70 -73 75 -36 +-66 81 29 58 -69 -67 96 48 50 +85 -76 -11 -29 96 -24 79 -12 -63 +4839 -7430 -5842 -10630 3291 -8238 -5307 5007 9231 12393 +-91 -63 43 55 86 -9 11 71 -64 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/05.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/05.a new file mode 100644 index 0000000..4884294 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/05.a @@ -0,0 +1,2 @@ +Bounded solution +82.000000000000000000 38.000000000000000000 27.000000000000000000 72.000000000000000000 80.000000000000000000 30.000000000000000000 100.000000000000000000 32.000000000000000000 60.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/06 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/06 new file mode 100644 index 0000000..1b2625c --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/06 @@ -0,0 +1,6 @@ +3 2 +1 0 +0 1 +1 1 +2 2 3 +1 2 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/06.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/06.a new file mode 100644 index 0000000..3f0fd9b --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/06.a @@ -0,0 +1,2 @@ +Bounded solution +1.000000000000000000 2.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/07 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/07 new file mode 100644 index 0000000..975a882 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/07 @@ -0,0 +1,5 @@ +2 3 +2 3 2 +1 1 2 +1000 800 +7 8 10 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/07.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/07.a new file mode 100644 index 0000000..de2c272 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/07.a @@ -0,0 +1,2 @@ +Bounded solution +200.000000000000000000 0.000000000000000000 300.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/08 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/08 new file mode 100644 index 0000000..a0559e1 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/08 @@ -0,0 +1,10 @@ +7 7 +-62 -40 -77 -91 46 -64 40 +52 11 41 51 40 -71 87 +-57 73 -66 89 18 11 91 +34 -68 87 -32 19 -1 37 +-74 24 -13 29 97 -91 -86 +69 24 -70 67 -68 -98 76 +89 86 -1 -2 -77 -62 -27 +769628 -834013 499389 616207 -254336 -994356 -56081 +-7 -80 -96 -87 -20 56 14 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/08.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/08.a new file mode 100644 index 0000000..3abe1da --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/08.a @@ -0,0 +1,2 @@ +Bounded solution +6031244.782175937667489052 2821669.525851520244032145 0.000000000000000000 0.000000000000000000 0.000000000000000000 12572587.836078854277729988 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/09 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/09 new file mode 100644 index 0000000..31f8df8 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/09 @@ -0,0 +1,18 @@ +15 16 +-8 26 72 65 72 12 -95 -90 -71 44 -9 33 73 91 0 -48 +60 -54 -52 -98 -14 60 47 35 34 89 -81 -85 36 98 -94 -10 +40 -5 -84 7 -53 -33 -11 79 -58 -20 46 -15 -6 50 50 17 +-3 96 -44 46 3 95 67 35 -34 52 16 8 -24 -41 73 98 +29 35 -39 -19 70 -53 51 28 10 21 30 -62 -100 33 -56 53 +-81 98 18 66 -5 -60 34 91 72 -97 -74 29 58 45 77 30 +7 -74 2 6 -38 71 -23 -6 -22 90 -60 14 -39 -56 -32 -79 +-11 48 -22 -28 72 53 -93 -14 66 22 -97 -23 86 81 -66 34 +-23 36 18 24 77 27 49 -66 85 74 62 45 -14 -7 74 0 +81 -20 -79 -53 -21 -30 -71 24 57 -68 -76 90 60 -57 -63 66 +-26 42 -68 -57 5 -62 35 -98 -87 41 76 -85 3 -11 -15 -66 +-62 32 73 36 -84 93 74 -68 -3 -91 -12 48 -13 30 -19 -27 +-32 65 -15 78 94 -4 25 64 -41 64 61 68 26 0 -27 -80 +-40 81 13 13 -19 -53 48 -10 18 3 71 -49 64 88 -49 62 +-77 -9 35 52 27 -80 55 86 18 24 -81 72 -80 71 84 64 +-155075 -78060 -992018 -197842 163377 -420166 707675 624881 319527 -432471 -579283 -234053 3854 587974 -873497 +46 -27 -33 11 -31 68 -45 -73 -78 54 30 -48 59 -29 -51 -97 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/09.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/09.a new file mode 100644 index 0000000..a613e49 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/09.a @@ -0,0 +1,2 @@ +Bounded solution +3300871.385047724936157465 0.000000000000000000 4143412.492377914953976870 0.000000000000000000 0.000000000000000000 539056.294073629891499877 0.000000000000000000 2439271.805425878148525953 636119.051952804904431105 0.000000000000000000 1245146.014359659515321255 0.000000000000000000 253163.508762339886743575 0.000000000000000000 275279.459835145215038210 439962.202773899713065475 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/10 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/10 new file mode 100644 index 0000000..61ce0ae --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/10 @@ -0,0 +1,5 @@ +2 2 +2 4 +4 3 +12 16 +1 2 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/10.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/10.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/10.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/11 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/11 new file mode 100644 index 0000000..6529da4 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/11 @@ -0,0 +1,13 @@ +10 50 +38 6 49 39 80 43 60 -27 42 2 -70 70 56 -2 75 -65 -72 80 62 -12 -83 -85 32 74 -16 -11 78 -41 42 -59 35 73 -11 -17 -10 -8 -15 100 -82 -11 -53 -65 -77 -44 92 3 56 92 -13 3 +-33 -25 35 85 -98 42 29 5 -48 76 -88 -59 -52 6 51 62 -95 22 37 93 -45 65 -39 -17 -85 57 69 80 -15 13 -77 -84 92 46 70 -10 -48 -75 -64 -57 66 -81 -83 70 59 79 29 36 -73 61 +-36 43 94 13 -71 48 -35 -49 99 -58 -28 49 -88 -24 -44 -76 -46 -75 -83 9 -93 18 -70 -26 45 -55 -97 -57 47 2 -75 35 -74 -93 90 -44 83 80 -18 -2 22 83 -91 -15 91 1 -63 98 -24 -25 +56 98 38 59 -4 92 23 -49 85 84 82 92 87 14 -30 21 -27 -8 71 35 -59 69 37 -52 79 40 -67 23 82 49 -40 99 -89 67 32 -69 47 76 -83 -49 6 79 -6 0 33 95 -72 -33 -28 -81 +7 65 -28 85 41 21 -57 63 38 -55 76 80 33 6 83 -83 81 0 8 13 96 99 100 -97 30 -17 57 12 91 -11 85 15 38 -35 63 56 16 53 -64 -50 -64 -2 -49 -22 80 -94 20 17 -84 -73 +74 65 -86 -98 51 82 -18 -1 -46 65 -3 -4 -9 -86 76 96 54 -63 -39 -71 70 77 -30 19 -30 -47 -64 -78 -67 -11 -96 64 -57 -90 -10 13 -35 -22 32 42 50 -39 65 14 44 -11 23 -56 -87 6 +-32 22 57 75 87 42 61 -36 62 75 -23 98 8 6 4 8 56 20 27 -40 -97 -79 -33 -94 -11 -98 -61 31 77 -38 67 75 64 16 -43 52 28 13 49 -79 24 -18 -81 -82 68 12 41 -56 -61 20 +2 52 -91 33 60 39 19 14 -87 -84 -58 -7 -46 -67 71 -8 -79 -64 16 70 -77 -100 -54 36 18 59 28 -40 -90 -42 13 -37 15 -18 100 -74 29 -51 65 -18 -11 35 16 35 54 -94 -59 -100 89 79 +28 -56 -92 81 67 -87 18 3 31 58 -59 55 2 0 86 33 65 13 36 33 86 88 0 -39 65 -37 73 73 31 26 -7 86 17 29 70 95 48 -37 52 58 59 -39 -83 -33 -50 -83 -31 71 100 -81 +80 -21 11 7 1 21 -76 -15 85 -89 -37 46 -92 -90 2 41 -34 36 -14 30 -82 -14 6 97 17 10 19 48 -96 -73 70 -63 7 -28 68 -77 -42 -51 93 66 -89 -84 -25 95 -15 -81 78 -70 -24 -12 +-233967 -47354 -394233 93582 -454468 -455668 -257657 21742 -328352 -143274 +-34 76 58 61 18 72 -43 -20 -7 49 82 76 40 77 91 -56 -66 29 -37 -51 -15 -25 -65 -67 -92 -53 60 -82 70 75 -89 -43 -44 -78 -97 -26 91 -89 -99 -90 -8 84 -69 81 -54 22 -53 17 -52 -75 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/11.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/11.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/11.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/12 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/12 new file mode 100644 index 0000000..93a6434 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/12 @@ -0,0 +1,13 @@ +10 50 +38 6 49 39 80 43 60 -27 42 2 -70 70 56 -2 75 -65 -72 80 62 -12 -83 -85 32 74 -16 -11 78 -41 42 -59 35 73 -11 -17 -10 -8 -15 100 -82 -11 -53 -65 -77 -44 92 3 56 92 -13 3 +-33 -25 35 85 -98 42 29 5 -48 76 -88 -59 -52 6 51 62 -95 22 37 93 -45 65 -39 -17 -85 57 69 80 -15 13 -77 -84 92 46 70 -10 -48 -75 -64 -57 66 -81 -83 70 59 79 29 36 -73 61 +-36 43 94 13 -71 48 -35 -49 99 -58 -28 49 -88 -24 -44 -76 -46 -75 -83 9 -93 18 -70 -26 45 -55 -97 -57 47 2 -75 35 -74 -93 90 -44 83 80 -18 -2 22 83 -91 -15 91 1 -63 98 -24 -25 +56 98 38 59 -4 92 23 -49 85 84 82 92 87 14 -30 21 -27 -8 71 35 -59 69 37 -52 79 40 -67 23 82 49 -40 99 -89 67 32 -69 47 76 -83 -49 6 79 -6 0 33 95 -72 -33 -28 -81 +7 65 -28 85 41 21 -57 63 38 -55 76 80 33 6 83 -83 81 0 8 13 96 99 100 -97 30 -17 57 12 91 -11 85 15 38 -35 63 56 16 53 -64 -50 -64 -2 -49 -22 80 -94 20 17 -84 -73 +74 65 -86 -98 51 82 -18 -1 -46 65 -3 -4 -9 -86 76 96 54 -63 -39 -71 70 77 -30 19 -30 -47 -64 -78 -67 -11 -96 64 -57 -90 -10 13 -35 -22 32 42 50 -39 65 14 44 -11 23 -56 -87 6 +-32 22 57 75 87 42 61 -36 62 75 -23 98 8 6 4 8 56 20 27 -40 -97 -79 -33 -94 -11 -98 -61 31 77 -38 67 75 64 16 -43 52 28 13 49 -79 24 -18 -81 -82 68 12 41 -56 -61 20 +2 52 -91 33 60 39 19 14 -87 -84 -58 -7 -46 -67 71 -8 -79 -64 16 70 -77 -100 -54 36 18 59 28 -40 -90 -42 13 -37 15 -18 100 -74 29 -51 65 -18 -11 35 16 35 54 -94 -59 -100 89 79 +28 -56 -92 81 67 -87 18 3 31 58 -59 55 2 0 86 33 65 13 36 33 86 88 0 -39 65 -37 73 73 31 26 -7 86 17 29 70 95 48 -37 52 58 59 -39 -83 -33 -50 -83 -31 71 100 -81 +80 -21 11 7 1 21 -76 -15 85 -89 -37 46 -92 -90 2 41 -34 36 -14 30 -82 -14 6 97 17 10 19 48 -96 -73 70 -63 7 -28 68 -77 -42 -51 93 66 -89 -84 -25 95 -15 -81 78 -70 -24 -12 +205034 45424 248692 499862 171963 96863 143609 328323 138701 389952 +-34 76 58 61 18 72 -43 -20 -7 49 82 76 40 77 91 -56 -66 29 -37 -51 -15 -25 -65 -67 -92 -53 60 -82 70 75 -89 -43 -44 -78 -97 -26 91 -89 -99 -90 -8 84 -69 81 -54 22 -53 17 -52 -75 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/12.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/12.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/12.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/13 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/13 new file mode 100644 index 0000000..cffcf40 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/13 @@ -0,0 +1,13 @@ +10 50 +74 13 14 35 68 9 72 94 64 94 67 78 67 90 85 76 70 45 13 59 31 62 48 13 16 20 31 40 16 80 78 19 45 79 79 6 67 3 79 72 84 97 73 59 29 68 48 21 92 40 +90 -8 100 25 96 -53 81 -4 -66 41 -35 4 0 -2 -18 -69 -6 -69 -1 -76 49 88 -77 87 57 -9 15 -87 -82 -28 64 -28 3 99 53 7 -40 -6 -44 -55 86 52 -63 -96 64 -52 -44 39 -7 21 +-66 93 -25 -76 56 56 -78 -78 40 67 -17 86 60 -23 63 44 90 -60 -43 -20 -7 44 13 16 10 51 -68 54 31 -56 98 -62 -11 -3 54 -75 77 -82 -64 -97 -97 99 30 30 -20 -69 44 -40 -22 55 +-97 22 46 50 -67 99 -51 -1 19 -79 3 39 -60 -40 -20 52 -16 27 44 -60 -14 64 -94 -36 -42 51 -59 46 -23 18 75 0 38 -20 -67 34 22 -6 -66 -86 -45 -15 23 2 5 63 16 -85 81 95 +-4 -83 -61 -60 42 -29 75 62 67 -39 30 68 58 -92 -96 42 -31 -71 -96 57 82 45 -78 32 -16 -33 -67 39 81 -23 38 -71 -54 97 29 93 -8 -98 86 38 12 -99 80 -3 -48 55 74 71 18 -6 +-37 -58 -97 -5 -100 -47 -12 -83 -60 5 4 -9 12 15 44 -65 16 -80 -69 -43 -47 -50 42 -78 -91 86 -45 58 -83 -71 -62 17 -27 -23 74 -67 0 -39 29 6 16 44 -13 -5 80 60 78 -69 40 55 +-56 -34 -27 93 13 21 -29 -53 78 75 -13 -56 53 -3 -25 -17 -31 -96 93 8 -35 -58 97 8 -41 -17 -45 -15 -21 -79 -62 -94 -40 -63 -10 -92 100 0 19 -73 77 -6 81 -36 25 -38 -84 59 -20 -49 +-58 -15 43 -51 11 -27 -15 -10 29 -23 89 -27 15 -9 -17 -39 70 -51 54 -28 -95 -46 -92 19 82 9 -85 -90 38 -2 -46 -12 74 30 7 -11 84 70 19 23 -93 91 17 70 45 -2 -11 71 23 -32 +-27 77 -72 70 53 39 62 68 -69 15 30 81 77 34 24 39 10 78 -80 -85 70 9 -64 -13 -99 -7 -73 -79 48 80 -91 67 20 26 -52 -46 26 61 -91 -61 -64 25 57 50 -48 -99 92 -63 -11 -22 +23 -51 -11 -61 -50 95 5 -7 -45 -83 -47 67 -61 -33 -68 33 -40 -13 -57 -85 -79 14 33 -61 21 -8 93 -87 -73 -47 80 3 -89 -2 56 -71 -13 -55 11 84 61 2 57 34 -48 -90 -73 -78 81 82 +146237 3104 16710 2013 -7713 -39687 -39362 6034 22227 -19680 +-31 -58 41 -51 -77 -55 -43 33 39 7 -30 51 87 16 -41 -94 -3 30 -82 -32 57 23 92 -32 18 -11 32 -17 -52 -54 -96 63 -32 22 -15 93 97 47 -71 -29 63 -9 -97 -61 -37 -2 15 -11 8 91 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/13.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/13.a new file mode 100644 index 0000000..9ef8e2d --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/13.a @@ -0,0 +1,2 @@ +Bounded solution +0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 1120.138930705165900000 0.000000000000000000 0.000000000000000000 0.000000000000000000 1364.110733882038200000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 6264.225868194424900000 0.000000000000000000 4199.181122214102300000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/14 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/14 new file mode 100644 index 0000000..eb17f8d --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/14 @@ -0,0 +1,13 @@ +10 50 +5 24 47 69 53 17 15 41 100 23 95 100 75 85 56 49 12 66 36 54 2 28 72 65 14 95 10 69 10 29 81 88 35 94 39 22 37 50 55 90 71 94 81 61 50 37 76 95 73 39 +-9 -54 23 -61 5 -95 -42 -24 -26 72 88 34 11 5 -92 -46 -2 55 15 -74 95 25 1 92 46 21 56 16 71 95 15 62 10 -60 77 23 41 55 -13 -46 -64 44 -12 -6 40 -1 -19 13 0 47 +21 -92 29 74 28 97 -15 28 46 -23 25 -41 -66 -13 52 78 -42 83 34 33 73 0 3 31 76 -14 15 -44 51 -49 51 -55 -76 1 -64 -30 70 83 -59 5 89 -59 -44 7 -87 -51 20 44 89 24 +2 -53 8 -1 26 15 33 -99 -26 -89 -36 68 -8 -29 -44 -18 -90 19 -2 46 40 9 -36 69 -15 28 35 -28 -21 -51 83 -19 90 -31 -85 33 90 -47 37 45 -34 97 96 -47 45 -39 6 -61 23 -90 +82 -79 -9 -40 64 100 -39 -15 -29 -29 -77 66 21 76 15 -15 -73 -41 78 -3 53 70 -10 69 25 -38 -14 33 -89 53 60 -22 -42 14 90 49 -11 -56 4 -50 -41 -80 79 0 -71 -13 -41 -70 -98 65 +67 39 80 -18 -12 9 89 -37 -64 74 -39 -44 95 -30 -68 -51 70 -84 -41 -95 3 84 -99 73 -7 87 -62 51 -66 -45 -10 8 7 -9 -73 -60 -88 -65 68 69 -65 93 2 40 31 -76 -75 -70 -10 21 +20 26 -74 36 -8 39 -32 86 100 9 -40 -26 80 -35 -32 81 -79 -33 7 -41 -21 -2 -19 -55 -21 -4 -22 -24 -37 16 -3 10 -35 -8 -65 -37 -57 97 63 -49 10 57 9 41 41 79 -79 -67 52 -87 +-3 37 99 -31 -57 -78 22 -67 -6 -82 -37 5 -43 45 86 -94 50 10 45 57 94 70 16 51 59 -65 -2 -36 13 31 -66 61 -83 95 17 -19 -30 63 -90 10 -98 -75 84 79 -25 -11 -59 -78 -50 97 +45 -19 -84 -53 44 39 42 79 -15 56 10 84 47 -34 0 -62 52 -20 90 6 -9 -13 55 -56 -98 -25 38 44 -10 78 85 63 -68 70 -6 -24 23 -13 -13 34 41 42 93 1 54 10 15 88 61 15 +-51 68 28 -1 -82 13 -52 42 29 24 -39 42 -43 -42 -20 -94 45 -34 -21 70 -42 50 -36 0 -67 5 -69 -52 -35 54 71 -60 7 31 -12 -9 -57 -88 22 -99 -52 -20 -29 94 -78 -38 -20 -13 17 22 +127133 19563 35027 -11640 -18053 -11012 -5229 631 38877 -31440 +67 -41 -21 -93 79 -26 -79 53 -72 99 45 -15 -24 79 32 -50 -28 -67 -71 43 -63 -90 47 38 -6 99 -93 2 -92 -66 73 -38 -76 1 92 -98 78 17 -14 48 27 -45 -8 58 81 -60 88 16 -79 -34 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/14.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/14.a new file mode 100644 index 0000000..d9a2aff --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/14.a @@ -0,0 +1,2 @@ +Bounded solution +586.486824744511410000 203.749229771460250000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 713.136160556873390000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 250.021254121081450000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 416.609370682305040000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 54.516097556823944000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 1071.692709896677800000 0.000000000000000000 0.000000000000000000 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/15 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/15 new file mode 100644 index 0000000..7a9d775 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/15 @@ -0,0 +1,13 @@ +10 50 +-33 -25 35 85 -98 42 29 5 -48 76 -88 -59 -52 6 51 62 -95 22 37 93 -45 65 -39 -17 -85 57 69 80 -15 13 -77 -84 92 46 70 -10 -48 -75 -64 -57 66 -81 -83 70 59 79 29 36 -73 61 +-36 43 94 13 -71 48 -35 -49 99 -58 -28 49 -88 -24 -44 -76 -46 -75 -83 9 -93 18 -70 -26 45 -55 -97 -57 47 2 -75 35 -74 -93 90 -44 83 80 -18 -2 22 83 -91 -15 91 1 -63 98 -24 -25 +74 65 -86 -98 51 82 -18 -1 -46 65 -3 -4 -9 -86 76 96 54 -63 -39 -71 70 77 -30 19 -30 -47 -64 -78 -67 -11 -96 64 -57 -90 -10 13 -35 -22 32 42 50 -39 65 14 44 -11 23 -56 -87 6 +2 52 -91 33 60 39 19 14 -87 -84 -58 -7 -46 -67 71 -8 -79 -64 16 70 -77 -100 -54 36 18 59 28 -40 -90 -42 13 -37 15 -18 100 -74 29 -51 65 -18 -11 35 16 35 54 -94 -59 -100 89 79 +80 -21 11 7 1 21 -76 -15 85 -89 -37 46 -92 -90 2 41 -34 36 -14 30 -82 -14 6 97 17 10 19 48 -96 -73 70 -63 7 -28 68 -77 -42 -51 93 66 -89 -84 -25 95 -15 -81 78 -70 -24 -12 +-53 54 -54 -50 89 19 31 -82 37 47 -34 76 58 61 18 72 -43 -20 -7 49 82 76 40 77 91 -56 -66 29 -37 -51 -15 -25 -65 -67 -92 -53 60 -82 70 75 -89 -43 -44 -78 -97 -26 91 -89 -99 -90 +-27 75 -50 -1 23 -54 -33 42 -87 -44 70 23 -26 -86 2 55 94 11 -79 -23 88 69 -82 -11 -96 -93 57 -5 -75 -81 -60 92 -69 -43 100 32 -2 49 -23 -96 78 96 26 95 -74 -70 4 -57 0 -81 +-85 7 87 -52 27 -55 -87 -85 10 -65 -48 28 39 83 40 54 78 29 -67 94 -97 -39 42 90 -80 -90 -59 3 -70 64 -88 8 -68 -48 -75 -3 43 29 96 1 46 -80 -79 -2 24 -51 87 74 -74 67 +3 -49 31 27 2 -4 8 33 -74 18 10 49 86 -57 -39 35 -49 -60 42 100 16 -55 -49 -11 -72 0 10 83 39 -7 -64 34 47 -24 -33 -72 -12 58 33 -91 -33 76 95 -39 -8 -42 -2 72 -62 32 +-11 -68 43 42 -39 8 82 -4 17 -72 -62 -93 -99 -26 55 -17 84 53 20 19 -27 -61 63 21 17 65 83 -71 -65 5 -58 86 83 -55 -50 33 -16 -80 -23 -66 38 -67 -11 27 -63 -51 -46 60 -25 -69 +230289 -203890 290951 187630 -113420 -156909 398448 -21845 -132744 -229343 +10 -24 -47 56 34 34 83 69 -85 43 -33 78 -36 -54 17 70 15 -54 -100 21 -69 22 63 89 -9 47 -38 -34 -32 -4 54 -21 -86 3 -80 20 -59 25 -93 -36 -1 59 -39 19 29 -42 -68 23 -13 96 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/15.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/15.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/15.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/16 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/16 new file mode 100644 index 0000000..a5e2776 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/16 @@ -0,0 +1,13 @@ +10 100 +-68 10 87 22 30 89 82 -97 -52 25 76 -22 -20 95 21 25 2 -3 45 -7 -98 -56 -15 16 -79 -3 -11 -97 -29 -73 -71 59 -40 -67 -78 10 -46 85 -81 -62 -23 -90 -59 -25 -100 -24 -73 91 72 38 -71 -14 -8 -10 -75 47 -1 -14 6 -26 26 67 45 37 -68 -10 -31 -57 62 78 -90 74 80 60 22 54 -73 31 -40 24 -5 -25 22 64 -53 -56 43 22 -47 -65 -32 57 87 41 14 -7 82 10 77 -59 +38 84 9 -92 71 42 -26 -30 -59 90 27 -52 -84 45 77 -41 -90 -7 -83 37 -39 2 88 89 91 -41 10 5 34 93 -74 85 -70 24 -77 95 -98 77 -88 18 -89 -61 -77 -16 -52 -84 -46 -86 9 -27 -90 14 -64 90 94 -80 -65 -79 73 -24 -31 72 -2 27 -39 -30 -68 22 61 -1 76 21 -17 21 -66 -64 -45 45 57 21 78 -70 62 84 47 -100 -32 -55 -92 -88 -8 -53 -23 -17 59 81 28 -100 -2 41 +54 25 65 -15 -97 54 -68 -6 -98 -77 41 -76 -83 77 74 -44 -26 84 62 -65 34 43 -83 -64 22 45 -60 16 -25 -72 68 -86 -52 -66 -28 -92 39 -82 96 -1 -52 -95 -4 98 37 -14 11 19 51 80 -62 54 -37 -15 -64 -61 74 70 -76 39 -85 -29 -45 -48 93 71 -74 16 -5 -84 66 7 15 -66 39 11 -86 -7 52 13 -98 -69 26 -90 -58 77 63 -21 77 -52 -23 -25 8 17 -96 -77 95 -11 45 -43 +45 72 -97 99 10 6 59 70 -71 -2 74 26 92 -93 54 -17 63 69 33 -32 67 -46 95 -92 64 -92 5 53 -69 -56 10 -19 -17 -1 -7 -30 -35 -11 1 -85 -63 -71 15 -46 -63 62 -12 -39 -95 94 -14 -51 -91 93 -24 -95 69 -7 20 -28 9 -54 81 -58 -33 90 22 47 68 -50 18 -17 -11 -90 -48 28 -14 39 5 -98 -81 -6 -9 -10 54 10 -65 39 -52 47 -37 56 41 -35 -61 -82 -34 -100 -20 19 +-87 -90 -53 -88 -56 -92 -3 20 67 95 -36 -81 21 -64 -63 40 -100 -67 -90 -24 4 -65 -32 -68 45 -1 -39 28 8 -26 26 -50 97 -23 -1 -87 52 -6 -13 51 -41 -57 27 -82 33 0 -21 -36 -52 -77 -66 15 64 -22 22 -93 -68 -9 -28 -46 -39 5 47 82 28 24 -14 72 74 -55 95 -39 51 -38 6 23 77 72 66 83 79 -34 -17 -89 30 22 76 87 -84 -16 -18 30 82 -12 18 -33 -59 -48 41 100 +7 74 -21 32 -2 28 -75 82 -31 59 43 -54 -67 72 87 73 97 84 -11 -34 13 -29 -93 -73 99 68 66 47 -34 -91 99 50 -80 70 -18 45 -77 -16 -35 -77 56 62 -3 -43 12 -22 -11 78 8 100 55 39 -33 -4 18 -99 100 39 -2 19 78 -33 -26 -43 -40 -20 74 -15 -92 -61 20 29 42 79 74 67 41 78 19 56 -88 24 -18 -29 14 -11 66 -63 -43 -27 53 -27 -18 50 -60 95 100 0 30 44 +55 19 -36 1 16 64 -49 78 -95 45 -37 71 6 -38 -22 -100 -13 47 -30 -83 -49 47 -91 27 95 46 8 67 -66 89 -12 83 -32 -93 77 43 -33 -3 -50 26 -92 23 77 -93 55 42 -77 99 -52 15 45 -2 -75 83 86 -51 1 -46 -73 -65 -33 -82 45 -2 55 -15 38 -1 -55 81 53 31 -63 -92 -56 -99 24 -75 -10 -45 58 29 -94 67 6 69 52 52 43 59 -1 5 -79 -43 -30 74 12 -47 -60 65 +-58 -11 -64 28 10 81 24 56 -93 -84 -19 -72 14 -95 97 5 -80 58 -55 -18 -41 -92 -65 -52 -44 -78 -6 -46 73 37 -98 88 17 -91 36 62 -42 49 -3 8 2 94 -19 -83 -61 -53 80 60 71 -75 23 -74 -30 -70 93 38 70 -37 -72 -36 55 26 43 -74 -94 -21 16 -39 -66 89 -98 -54 -81 -48 -39 1 -97 26 20 44 100 9 -89 11 -49 99 -37 -90 -69 70 -56 22 62 -87 49 51 -30 -11 -77 87 +-72 -93 24 -80 26 44 -52 71 75 -31 46 66 -5 -49 71 -55 53 36 -5 -46 12 14 60 -90 -22 -59 -78 19 -9 78 43 -56 -33 20 58 60 90 -62 -21 -92 5 4 95 75 20 73 82 39 -86 -13 -74 -58 42 53 -73 89 -46 -89 57 -81 70 78 8 -99 70 -85 92 41 -94 -56 -31 -96 -7 91 8 -50 -23 -88 75 78 73 -30 64 -98 -4 -42 -19 -52 -15 -7 -56 27 -49 97 81 60 100 33 -70 19 +-59 -36 75 -74 -41 47 -88 -46 -16 32 8 75 9 32 -72 -8 -67 78 14 -19 90 -36 19 36 -98 -77 -62 -49 95 88 -9 -65 -64 53 20 100 -7 69 -67 37 95 -10 -25 46 -77 58 50 -73 -40 -25 90 60 26 -14 -81 -41 -77 -74 -79 36 26 -74 18 6 -88 79 -96 83 91 -79 83 -43 -95 92 -27 15 -55 -33 0 -26 46 -17 -48 -70 -72 84 -73 17 41 -32 60 56 -85 -25 10 -81 -82 -77 13 -34 +920043 315362 586502 433212 261913 -475317 -546198 -977484 852834 -334772 +70 35 -3 -16 32 -90 -89 -96 66 -79 4 39 -72 91 6 -72 26 16 23 5 -88 60 15 50 -41 -47 -18 -70 27 -91 -55 -52 93 -22 -53 -82 89 -75 -77 65 -79 62 94 -60 14 -45 -80 -37 -51 -56 -52 93 -79 -21 -100 83 -87 70 -40 30 -10 -6 -84 -14 -36 -54 -20 30 -24 59 -64 -58 9 -4 -21 -97 30 14 17 -18 -45 -74 -55 16 -79 17 37 -87 55 30 28 -5 -69 -2 17 26 -3 -16 -60 -61 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/16.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/16.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/16.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/17 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/17 new file mode 100644 index 0000000..a222a1d --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/17 @@ -0,0 +1,13 @@ +10 100 +-68 10 87 22 30 89 82 -97 -52 25 76 -22 -20 95 21 25 2 -3 45 -7 -98 -56 -15 16 -79 -3 -11 -97 -29 -73 -71 59 -40 -67 -78 10 -46 85 -81 -62 -23 -90 -59 -25 -100 -24 -73 91 72 38 -71 -14 -8 -10 -75 47 -1 -14 6 -26 26 67 45 37 -68 -10 -31 -57 62 78 -90 74 80 60 22 54 -73 31 -40 24 -5 -25 22 64 -53 -56 43 22 -47 -65 -32 57 87 41 14 -7 82 10 77 -59 +38 84 9 -92 71 42 -26 -30 -59 90 27 -52 -84 45 77 -41 -90 -7 -83 37 -39 2 88 89 91 -41 10 5 34 93 -74 85 -70 24 -77 95 -98 77 -88 18 -89 -61 -77 -16 -52 -84 -46 -86 9 -27 -90 14 -64 90 94 -80 -65 -79 73 -24 -31 72 -2 27 -39 -30 -68 22 61 -1 76 21 -17 21 -66 -64 -45 45 57 21 78 -70 62 84 47 -100 -32 -55 -92 -88 -8 -53 -23 -17 59 81 28 -100 -2 41 +54 25 65 -15 -97 54 -68 -6 -98 -77 41 -76 -83 77 74 -44 -26 84 62 -65 34 43 -83 -64 22 45 -60 16 -25 -72 68 -86 -52 -66 -28 -92 39 -82 96 -1 -52 -95 -4 98 37 -14 11 19 51 80 -62 54 -37 -15 -64 -61 74 70 -76 39 -85 -29 -45 -48 93 71 -74 16 -5 -84 66 7 15 -66 39 11 -86 -7 52 13 -98 -69 26 -90 -58 77 63 -21 77 -52 -23 -25 8 17 -96 -77 95 -11 45 -43 +45 72 -97 99 10 6 59 70 -71 -2 74 26 92 -93 54 -17 63 69 33 -32 67 -46 95 -92 64 -92 5 53 -69 -56 10 -19 -17 -1 -7 -30 -35 -11 1 -85 -63 -71 15 -46 -63 62 -12 -39 -95 94 -14 -51 -91 93 -24 -95 69 -7 20 -28 9 -54 81 -58 -33 90 22 47 68 -50 18 -17 -11 -90 -48 28 -14 39 5 -98 -81 -6 -9 -10 54 10 -65 39 -52 47 -37 56 41 -35 -61 -82 -34 -100 -20 19 +-87 -90 -53 -88 -56 -92 -3 20 67 95 -36 -81 21 -64 -63 40 -100 -67 -90 -24 4 -65 -32 -68 45 -1 -39 28 8 -26 26 -50 97 -23 -1 -87 52 -6 -13 51 -41 -57 27 -82 33 0 -21 -36 -52 -77 -66 15 64 -22 22 -93 -68 -9 -28 -46 -39 5 47 82 28 24 -14 72 74 -55 95 -39 51 -38 6 23 77 72 66 83 79 -34 -17 -89 30 22 76 87 -84 -16 -18 30 82 -12 18 -33 -59 -48 41 100 +7 74 -21 32 -2 28 -75 82 -31 59 43 -54 -67 72 87 73 97 84 -11 -34 13 -29 -93 -73 99 68 66 47 -34 -91 99 50 -80 70 -18 45 -77 -16 -35 -77 56 62 -3 -43 12 -22 -11 78 8 100 55 39 -33 -4 18 -99 100 39 -2 19 78 -33 -26 -43 -40 -20 74 -15 -92 -61 20 29 42 79 74 67 41 78 19 56 -88 24 -18 -29 14 -11 66 -63 -43 -27 53 -27 -18 50 -60 95 100 0 30 44 +55 19 -36 1 16 64 -49 78 -95 45 -37 71 6 -38 -22 -100 -13 47 -30 -83 -49 47 -91 27 95 46 8 67 -66 89 -12 83 -32 -93 77 43 -33 -3 -50 26 -92 23 77 -93 55 42 -77 99 -52 15 45 -2 -75 83 86 -51 1 -46 -73 -65 -33 -82 45 -2 55 -15 38 -1 -55 81 53 31 -63 -92 -56 -99 24 -75 -10 -45 58 29 -94 67 6 69 52 52 43 59 -1 5 -79 -43 -30 74 12 -47 -60 65 +-58 -11 -64 28 10 81 24 56 -93 -84 -19 -72 14 -95 97 5 -80 58 -55 -18 -41 -92 -65 -52 -44 -78 -6 -46 73 37 -98 88 17 -91 36 62 -42 49 -3 8 2 94 -19 -83 -61 -53 80 60 71 -75 23 -74 -30 -70 93 38 70 -37 -72 -36 55 26 43 -74 -94 -21 16 -39 -66 89 -98 -54 -81 -48 -39 1 -97 26 20 44 100 9 -89 11 -49 99 -37 -90 -69 70 -56 22 62 -87 49 51 -30 -11 -77 87 +-72 -93 24 -80 26 44 -52 71 75 -31 46 66 -5 -49 71 -55 53 36 -5 -46 12 14 60 -90 -22 -59 -78 19 -9 78 43 -56 -33 20 58 60 90 -62 -21 -92 5 4 95 75 20 73 82 39 -86 -13 -74 -58 42 53 -73 89 -46 -89 57 -81 70 78 8 -99 70 -85 92 41 -94 -56 -31 -96 -7 91 8 -50 -23 -88 75 78 73 -30 64 -98 -4 -42 -19 -52 -15 -7 -56 27 -49 97 81 60 100 33 -70 19 +-59 -36 75 -74 -41 47 -88 -46 -16 32 8 75 9 32 -72 -8 -67 78 14 -19 90 -36 19 36 -98 -77 -62 -49 95 88 -9 -65 -64 53 20 100 -7 69 -67 37 95 -10 -25 46 -77 58 50 -73 -40 -25 90 60 26 -14 -81 -41 -77 -74 -79 36 26 -74 18 6 -88 79 -96 83 91 -79 83 -43 -95 92 -27 15 -55 -33 0 -26 46 -17 -48 -70 -72 84 -73 17 41 -32 60 56 -85 -25 10 -81 -82 -77 13 -34 +487397 6723 203206 524370 4328 50619 929899 822062 747200 309537 +70 35 -3 -16 32 -90 -89 -96 66 -79 4 39 -72 91 6 -72 26 16 23 5 -88 60 15 50 -41 -47 -18 -70 27 -91 -55 -52 93 -22 -53 -82 89 -75 -77 65 -79 62 94 -60 14 -45 -80 -37 -51 -56 -52 93 -79 -21 -100 83 -87 70 -40 30 -10 -6 -84 -14 -36 -54 -20 30 -24 59 -64 -58 9 -4 -21 -97 30 14 17 -18 -45 -74 -55 16 -79 17 37 -87 55 30 28 -5 -69 -2 17 26 -3 -16 -60 -61 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/17.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/17.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/17.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/18 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/18 new file mode 100644 index 0000000..01e0391 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/18 @@ -0,0 +1,13 @@ +10 100 +34 80 41 30 52 94 73 36 85 69 54 63 35 9 5 1 11 89 26 20 63 17 96 69 27 92 2 6 11 51 41 61 57 77 79 73 38 40 9 53 32 86 80 53 94 77 26 73 84 27 52 82 98 81 3 26 24 60 32 49 45 22 32 79 17 15 91 87 19 73 78 81 22 38 40 30 80 85 55 21 77 10 39 14 100 5 79 36 22 99 63 26 80 86 33 96 36 54 12 96 +75 -64 38 57 -16 -26 20 83 -98 -29 82 -70 -59 -65 -16 -60 8 -66 99 95 47 -88 -47 -93 -6 -99 6 -65 -11 -90 -93 87 -89 41 -61 11 -7 38 -59 89 -25 -17 64 -38 -99 -35 42 -54 6 39 47 -70 -26 -7 5 83 91 52 92 -85 -60 -45 -50 -14 -15 31 20 78 3 -20 96 -100 -93 56 63 40 84 -30 -63 -24 69 -91 -22 0 -98 -86 19 -53 88 88 -92 63 25 -47 -34 24 5 -58 -21 -58 +-62 -10 85 -48 65 36 27 -91 43 28 -21 -71 -31 -45 -24 11 89 -21 -51 12 -35 -68 -70 28 -95 -43 -25 11 8 -73 -67 -81 -85 -46 -31 28 -41 -52 40 -20 -7 86 -6 86 -1 -73 81 -7 -27 88 -51 -2 21 -9 8 75 56 -89 85 49 83 74 34 0 -25 7 37 80 -11 -30 -72 -55 -10 92 75 70 -36 -29 -39 65 -36 39 -19 47 -17 38 84 -75 53 -68 -73 55 85 -91 -94 80 0 -32 -6 -7 +82 -18 -29 -35 -91 -94 -1 34 82 63 -7 -16 -30 64 64 20 -81 4 -62 -11 10 65 61 4 10 -67 -26 -42 -13 36 95 -97 -79 39 15 37 91 -19 18 -12 55 -2 94 31 -76 -13 64 -6 39 77 -87 -48 41 -39 20 74 -55 4 -30 -55 -49 53 -5 -55 24 4 52 -70 26 27 91 74 -58 48 -39 87 9 74 -42 -50 92 97 74 91 -26 40 -97 -36 22 -68 -89 -33 36 -35 75 -94 30 7 19 -53 +76 100 3 -3 -60 -21 -81 -61 13 -52 88 -40 30 77 91 42 78 -45 61 -68 -38 15 60 -22 55 83 22 -11 -2 -57 -16 43 36 -30 -8 -75 -81 -29 -29 -33 -34 -39 -45 -19 -77 55 86 -64 15 -77 70 84 -85 31 5 64 -66 16 74 -74 75 67 17 52 -59 38 82 4 -90 5 -90 -40 67 15 48 58 -70 -72 44 -43 8 -3 83 -45 -57 17 -71 -89 27 49 -14 7 8 -98 -46 -79 -21 39 13 60 +-65 -38 -67 43 45 73 66 -43 -25 21 -97 -18 -48 -93 -6 28 19 27 -81 99 -89 -52 -42 -45 75 77 -64 71 -58 20 76 -87 -66 -47 -65 -94 -42 -8 -92 5 -38 100 8 4 -83 -74 75 98 77 -82 -19 28 42 -85 -82 -59 88 -58 90 41 -12 67 92 17 97 7 -10 -8 44 99 -4 -16 -95 -92 -7 -90 78 -77 1 -29 43 25 89 8 -60 -66 63 98 -68 75 -32 17 -67 -63 -89 80 -14 5 83 39 +21 84 -90 32 -35 72 94 -78 -27 33 74 -95 79 28 -27 -60 -73 -61 -98 44 -18 4 -76 -13 62 46 -32 66 83 89 -100 -48 -91 -39 -67 27 63 -58 71 7 -47 33 11 32 -1 96 -30 -55 -20 -5 -40 66 53 73 96 -96 94 -31 76 -66 91 5 2 89 93 -42 -23 27 72 60 -69 -50 -52 97 61 40 -33 -58 6 89 -71 58 -17 -98 -94 40 53 -17 -96 10 1 -24 -28 -50 -77 70 1 82 -95 -62 +83 22 38 -12 4 -1 -25 -36 17 -51 -19 36 -51 67 58 -39 91 41 55 46 -51 44 -75 90 67 57 8 -9 62 -7 -99 19 98 -25 47 66 -11 -53 8 -48 1 64 -17 98 -83 -67 -74 -4 -21 86 37 -11 54 73 100 50 -62 -35 -49 -16 42 -58 -42 63 61 67 -43 -21 -83 -59 -17 18 48 -87 76 97 -55 35 -8 54 -27 -73 -4 59 -33 -95 -79 85 -97 -92 -33 32 -11 -44 -73 -70 -57 -89 -48 -3 +-8 -62 -49 41 57 -13 64 75 48 -65 -48 -81 83 99 21 -18 99 74 78 97 44 44 44 -53 -63 80 98 -42 -100 -53 -33 -35 -11 -94 23 90 -42 35 15 -5 65 -16 -19 76 41 -56 89 61 -97 2 60 -27 25 22 -98 52 -45 54 -16 -52 8 91 47 -82 -82 78 6 77 99 66 -1 66 91 61 65 87 -7 -81 8 -42 -73 -39 17 -67 -63 -68 -39 -41 -55 96 -33 7 -23 -69 -8 -5 -59 60 -64 48 +19 -65 -36 0 79 5 60 -39 25 -90 54 -19 -57 1 -40 -33 89 -17 -43 -100 -72 -11 70 -18 46 50 58 60 -30 -25 74 -49 23 78 -8 56 -56 48 -7 33 94 -9 73 84 97 -61 26 69 50 17 23 65 77 25 33 -64 16 -27 -32 58 47 -57 -40 11 89 -43 -65 -94 99 -91 -38 62 90 -37 4 -92 56 81 -55 43 -89 -31 -53 62 -88 57 58 -83 3 -45 20 -49 8 1 21 87 -20 89 82 -29 +266781 -23705 -8512 14607 -7462 -4114 -27583 -16426 65883 40821 +89 14 -57 -56 53 46 -29 25 53 25 46 -52 -59 -25 41 80 -41 50 -57 -77 -15 75 -15 86 -26 -78 -51 4 24 -51 -63 -82 -26 -75 82 -42 3 -48 -56 40 -89 -32 1 43 7 14 28 32 -81 -97 -39 -38 43 -55 -42 7 -100 -95 72 57 24 92 -53 -17 -73 -25 -40 -69 15 45 69 -79 -21 -30 -43 -63 -5 -69 -97 -75 -10 -62 13 99 -82 55 -59 78 8 -77 94 -97 82 -39 67 43 -82 -17 -20 5 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/18.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/18.a new file mode 100644 index 0000000..537cafb --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/18.a @@ -0,0 +1,2 @@ +Bounded solution +0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 465.438818401036600000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 7421.252771793550000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 1681.627539503071400000 0.000000000000000000 4706.998805647629500000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 4299.263650429885300000 0.000000000000000000 4403.343568835362000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/19 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/19 new file mode 100644 index 0000000..143bfd0 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/19 @@ -0,0 +1,13 @@ +10 100 +47 100 88 69 75 26 36 19 20 91 6 94 63 45 88 85 52 26 67 57 42 86 20 90 90 30 44 83 1 19 4 42 38 88 2 89 83 67 14 32 99 33 2 72 85 39 48 50 76 7 72 63 38 16 33 24 32 99 59 56 16 63 68 41 38 74 1 50 43 47 2 33 80 95 72 14 97 21 32 90 17 10 84 54 73 0 71 90 22 59 34 49 35 88 4 96 66 50 44 50 +73 -63 0 32 78 -9 3 84 59 -63 43 -16 -7 -54 -40 46 -67 -73 -22 -1 0 83 11 10 -53 -21 -100 -37 -9 -57 -62 68 -36 54 21 10 -40 -77 -56 19 85 -81 -65 -87 -60 64 -69 -5 49 -45 32 35 26 37 -74 10 79 76 97 -75 -91 30 88 -47 -80 -26 -96 -93 2 -80 -8 24 -50 93 -97 35 -65 -37 68 -50 -83 -17 -34 17 -61 71 16 90 7 -76 -69 82 -52 -45 -57 -69 92 2 -37 -88 +-83 -14 61 -61 -73 93 27 -44 39 -4 -39 -81 -50 10 40 -75 -82 -25 1 -65 -87 41 90 -22 91 60 58 29 -74 79 -40 -89 -51 68 22 36 -4 98 80 18 -87 -66 -67 5 51 -8 -96 -34 100 54 -76 83 -26 -66 -13 -81 53 24 6 -16 56 -98 61 45 94 -96 14 18 4 -80 67 -75 75 -98 -6 83 62 -37 -55 34 -2 17 86 1 -97 -33 3 22 -3 -44 36 92 -12 86 23 -30 -71 18 41 56 +-63 9 -74 -15 42 56 -64 77 47 4 68 -59 -89 -83 91 -34 100 -36 -72 -51 -2 56 68 37 13 -40 -44 37 -14 -7 76 52 -61 3 25 29 51 -27 9 75 51 -68 -40 40 80 -21 17 47 -33 -95 87 57 3 63 -89 -28 -74 16 -76 86 6 -45 -35 -98 100 2 94 34 20 -83 -88 -24 61 6 -38 -31 21 -3 -100 -52 67 94 86 10 -56 -40 0 91 25 -48 17 84 74 -82 -24 -10 53 56 -8 9 +2 -81 -84 -43 -91 98 62 -12 87 -45 -80 -65 48 -57 -38 14 -39 -92 98 88 -2 51 92 13 66 96 -39 49 37 44 75 -19 30 78 -77 -13 -100 -62 -17 86 -46 -87 -30 41 69 6 38 -100 -49 90 67 1 -47 -11 60 -7 -3 -64 64 41 -75 2 -70 15 15 -44 -44 8 -80 80 -9 73 -78 -40 99 -33 -68 -53 -20 47 -24 97 39 -67 75 -74 -89 8 83 -75 75 -29 -4 -56 -4 63 -23 89 1 11 +2 -100 -5 32 -60 88 -22 -63 73 59 -7 37 52 -3 -77 -44 29 -96 -61 62 65 4 -47 14 -87 -22 -36 1 -51 19 -63 -97 2 -21 15 1 90 85 -71 -61 59 22 20 -43 -80 34 -37 -34 -27 -80 54 24 42 -39 -36 50 67 -21 14 10 -19 22 86 46 71 41 -10 82 -49 74 -53 33 -62 -38 -31 -57 -5 -100 -47 53 -85 64 20 96 -41 -34 -61 74 -1 -75 -51 54 50 -4 -64 -15 99 -84 -53 -71 +-22 88 -52 -68 24 71 -99 28 -73 -49 -60 -54 60 -93 57 -60 -99 -33 -98 -32 -12 -10 49 46 49 -16 52 -95 -54 -54 13 37 -3 72 25 -99 -41 -29 -100 -17 -15 18 21 -34 56 -73 -63 -36 -60 -35 44 -41 28 50 61 -36 17 95 -42 92 -99 -64 -35 28 14 -50 -43 77 91 -67 -62 -93 10 10 59 -87 -67 29 -72 35 41 56 61 -36 77 3 -32 59 38 -43 -35 48 49 -79 -81 55 -37 64 -16 93 +-39 22 -34 3 -96 -93 98 -47 89 -65 -23 -79 -97 7 81 -35 -72 59 21 26 -98 95 63 77 38 -47 58 -68 -5 -78 -51 -23 -42 -27 91 73 -22 38 85 90 78 -27 -92 -94 -75 64 33 -1 -33 -84 89 -46 -24 -71 -14 -25 93 57 -17 96 -88 56 -39 -42 38 39 23 37 26 -76 77 72 18 -77 -21 7 57 -7 -75 86 55 -78 -97 62 99 96 -30 35 -33 -94 35 72 -56 53 -53 70 84 -60 99 -8 +82 -4 93 -51 96 -84 90 2 -75 -26 51 85 -75 33 5 -97 82 85 79 -24 89 65 -51 -1 -4 -45 -68 -50 49 -98 -66 -2 12 -91 94 12 -46 55 20 69 6 59 -45 -38 -44 36 -33 48 -69 -4 71 4 -75 -51 -100 63 41 78 51 -15 72 -99 62 11 -46 87 -58 18 -40 -41 -44 39 8 -84 -43 -68 25 100 -22 18 77 -8 91 58 0 88 -61 4 -75 15 -58 -81 -91 57 49 13 27 2 42 90 +58 9 -9 -91 80 88 26 65 -83 -44 84 86 -44 -15 -100 33 12 -38 70 -12 23 -45 72 83 16 12 -30 90 -21 -37 -13 53 -26 33 86 29 83 43 -38 7 -20 -8 -20 -53 60 86 5 -86 43 -88 -66 -23 -66 -83 38 -59 -63 72 -88 13 -15 -23 -58 73 84 -78 83 94 -35 -5 -54 -65 79 -86 -32 3 -1 49 99 -38 -60 -63 16 16 -1 -18 -13 40 73 70 -39 10 85 -28 -98 84 -2 45 30 -22 +258730 -65681 -485 -1287 -13912 -13984 -92762 -4320 18412 -11656 +17 -4 -49 17 -4 -20 58 78 -32 -67 -99 -18 30 33 -26 -14 -45 89 -51 89 -59 -16 -85 -40 -85 -72 34 -20 -29 67 85 -60 57 -85 -52 -86 -73 -74 -14 -21 98 -64 65 97 73 39 -71 81 95 27 22 63 76 -21 -57 -1 -89 35 20 41 -95 -18 -30 39 79 -55 64 -7 11 9 -15 85 -72 -81 54 -43 -18 -92 -25 72 8 4 91 32 95 -48 -46 -50 29 9 45 81 65 43 -29 -25 -2 -85 100 62 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/19.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/19.a new file mode 100644 index 0000000..915d65c --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/19.a @@ -0,0 +1,2 @@ +Bounded solution +0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 11629.431884773454000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 80440.452626108439000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 28493.478015080316000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 11418.944596804493000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/20 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/20 new file mode 100644 index 0000000..d1775e5 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/20 @@ -0,0 +1,13 @@ +10 100 +38 84 9 -92 71 42 -26 -30 -59 90 27 -52 -84 45 77 -41 -90 -7 -83 37 -39 2 88 89 91 -41 10 5 34 93 -74 85 -70 24 -77 95 -98 77 -88 18 -89 -61 -77 -16 -52 -84 -46 -86 9 -27 -90 14 -64 90 94 -80 -65 -79 73 -24 -31 72 -2 27 -39 -30 -68 22 61 -1 76 21 -17 21 -66 -64 -45 45 57 21 78 -70 62 84 47 -100 -32 -55 -92 -88 -8 -53 -23 -17 59 81 28 -100 -2 41 +54 25 65 -15 -97 54 -68 -6 -98 -77 41 -76 -83 77 74 -44 -26 84 62 -65 34 43 -83 -64 22 45 -60 16 -25 -72 68 -86 -52 -66 -28 -92 39 -82 96 -1 -52 -95 -4 98 37 -14 11 19 51 80 -62 54 -37 -15 -64 -61 74 70 -76 39 -85 -29 -45 -48 93 71 -74 16 -5 -84 66 7 15 -66 39 11 -86 -7 52 13 -98 -69 26 -90 -58 77 63 -21 77 -52 -23 -25 8 17 -96 -77 95 -11 45 -43 +45 72 -97 99 10 6 59 70 -71 -2 74 26 92 -93 54 -17 63 69 33 -32 67 -46 95 -92 64 -92 5 53 -69 -56 10 -19 -17 -1 -7 -30 -35 -11 1 -85 -63 -71 15 -46 -63 62 -12 -39 -95 94 -14 -51 -91 93 -24 -95 69 -7 20 -28 9 -54 81 -58 -33 90 22 47 68 -50 18 -17 -11 -90 -48 28 -14 39 5 -98 -81 -6 -9 -10 54 10 -65 39 -52 47 -37 56 41 -35 -61 -82 -34 -100 -20 19 +-87 -90 -53 -88 -56 -92 -3 20 67 95 -36 -81 21 -64 -63 40 -100 -67 -90 -24 4 -65 -32 -68 45 -1 -39 28 8 -26 26 -50 97 -23 -1 -87 52 -6 -13 51 -41 -57 27 -82 33 0 -21 -36 -52 -77 -66 15 64 -22 22 -93 -68 -9 -28 -46 -39 5 47 82 28 24 -14 72 74 -55 95 -39 51 -38 6 23 77 72 66 83 79 -34 -17 -89 30 22 76 87 -84 -16 -18 30 82 -12 18 -33 -59 -48 41 100 +55 19 -36 1 16 64 -49 78 -95 45 -37 71 6 -38 -22 -100 -13 47 -30 -83 -49 47 -91 27 95 46 8 67 -66 89 -12 83 -32 -93 77 43 -33 -3 -50 26 -92 23 77 -93 55 42 -77 99 -52 15 45 -2 -75 83 86 -51 1 -46 -73 -65 -33 -82 45 -2 55 -15 38 -1 -55 81 53 31 -63 -92 -56 -99 24 -75 -10 -45 58 29 -94 67 6 69 52 52 43 59 -1 5 -79 -43 -30 74 12 -47 -60 65 +-58 -11 -64 28 10 81 24 56 -93 -84 -19 -72 14 -95 97 5 -80 58 -55 -18 -41 -92 -65 -52 -44 -78 -6 -46 73 37 -98 88 17 -91 36 62 -42 49 -3 8 2 94 -19 -83 -61 -53 80 60 71 -75 23 -74 -30 -70 93 38 70 -37 -72 -36 55 26 43 -74 -94 -21 16 -39 -66 89 -98 -54 -81 -48 -39 1 -97 26 20 44 100 9 -89 11 -49 99 -37 -90 -69 70 -56 22 62 -87 49 51 -30 -11 -77 87 +-72 -93 24 -80 26 44 -52 71 75 -31 46 66 -5 -49 71 -55 53 36 -5 -46 12 14 60 -90 -22 -59 -78 19 -9 78 43 -56 -33 20 58 60 90 -62 -21 -92 5 4 95 75 20 73 82 39 -86 -13 -74 -58 42 53 -73 89 -46 -89 57 -81 70 78 8 -99 70 -85 92 41 -94 -56 -31 -96 -7 91 8 -50 -23 -88 75 78 73 -30 64 -98 -4 -42 -19 -52 -15 -7 -56 27 -49 97 81 60 100 33 -70 19 +-59 -36 75 -74 -41 47 -88 -46 -16 32 8 75 9 32 -72 -8 -67 78 14 -19 90 -36 19 36 -98 -77 -62 -49 95 88 -9 -65 -64 53 20 100 -7 69 -67 37 95 -10 -25 46 -77 58 50 -73 -40 -25 90 60 26 -14 -81 -41 -77 -74 -79 36 26 -74 18 6 -88 79 -96 83 91 -79 83 -43 -95 92 -27 15 -55 -33 0 -26 46 -17 -48 -70 -72 84 -73 17 41 -32 60 56 -85 -25 10 -81 -82 -77 13 -34 +45 17 -82 -6 -20 -3 30 0 -33 91 70 35 -3 -16 32 -90 -89 -96 66 -79 4 39 -72 91 6 -72 26 16 23 5 -88 60 15 50 -41 -47 -18 -70 27 -91 -55 -52 93 -22 -53 -82 89 -75 -77 65 -79 62 94 -60 14 -45 -80 -37 -51 -56 -52 93 -79 -21 -100 83 -87 70 -40 30 -10 -6 -84 -14 -36 -54 -20 30 -24 59 -64 -58 9 -4 -21 -97 30 14 17 -18 -45 -74 -55 16 -79 17 37 -87 55 30 +-2 59 22 -26 86 -47 -44 -61 -48 65 -31 -90 -71 -62 -96 -13 46 17 -66 26 -51 35 -90 -31 37 35 23 -87 -62 44 -33 44 -84 33 17 -71 64 -23 -87 -94 -67 -8 1 2 -95 14 -63 47 -17 94 -98 -12 -75 -86 -87 63 67 -76 99 -9 100 -79 92 28 69 21 -36 21 -95 -83 78 11 40 -42 -80 9 56 6 -84 -38 -15 -56 -89 20 41 -80 44 92 1 -27 -48 -20 -58 -28 -2 77 54 67 50 -2 +-230268 -430267 -123260 -277395 -131623 823973 538504 -373571 -621234 69477 +5 0 -15 33 81 19 -92 -87 -49 93 11 79 -99 68 -37 27 41 97 -93 63 -76 79 79 61 -19 83 0 -41 -75 58 97 97 -41 6 89 -67 -24 -51 -52 29 44 19 47 -67 73 -27 37 -39 93 75 -79 28 39 81 89 10 81 -87 -74 -27 68 35 18 68 -48 40 11 -31 -10 -2 62 12 -73 -58 -36 16 13 -64 -93 24 23 6 98 -26 -5 74 65 -28 45 28 67 -73 25 2 -53 81 54 52 -94 -15 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/20.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/20.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/20.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/21 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/21 new file mode 100644 index 0000000..eb23619 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/21 @@ -0,0 +1,13 @@ +10 8 +83 -72 -98 -49 -16 74 -60 -83 +-3 69 59 -3 84 22 15 0 +-92 -39 -80 74 -55 -85 -84 -73 +100 -84 23 12 26 -60 -67 -13 +13 58 80 38 -85 68 31 65 +-45 0 77 -70 59 -74 6 -76 +57 72 54 58 -38 -83 -5 67 +25 88 -57 58 -59 17 -56 -85 +-1 -39 -94 -35 -61 -56 -40 73 +-76 80 18 -6 -71 -49 62 81 +4263 -71631 -36104 52586 63937 36325 30195 31255 53755 -52712 +89 59 -28 -83 -51 -72 -8 52 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/21.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/21.a new file mode 100644 index 0000000..3deb2e2 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/21.a @@ -0,0 +1 @@ +No solution diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/41 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/41 new file mode 100644 index 0000000..073c76e --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/41 @@ -0,0 +1,23 @@ +20 10 +-1 0 0 0 0 0 0 0 0 0 +1 0 0 0 0 0 0 0 0 0 +0 -1 0 0 0 0 0 0 0 0 +0 1 0 0 0 0 0 0 0 0 +0 0 -1 0 0 0 0 0 0 0 +0 0 1 0 0 0 0 0 0 0 +0 0 0 -1 0 0 0 0 0 0 +0 0 0 1 0 0 0 0 0 0 +0 0 0 0 -1 0 0 0 0 0 +0 0 0 0 1 0 0 0 0 0 +0 0 0 0 0 -1 0 0 0 0 +0 0 0 0 0 1 0 0 0 0 +0 0 0 0 0 0 -1 0 0 0 +0 0 0 0 0 0 1 0 0 0 +0 0 0 0 0 0 0 -1 0 0 +0 0 0 0 0 0 0 1 0 0 +0 0 0 0 0 0 0 0 -1 0 +0 0 0 0 0 0 0 0 1 0 +0 0 0 0 0 0 0 0 0 -1 +0 0 0 0 0 0 0 0 0 1 +-18 84 -71 91 -21 82 -67 89 -38 75 -13 69 -99 99 -37 47 -47 51 -76 92 +93 -45 53 30 -84 23 -65 -46 66 47 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/41.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/41.a new file mode 100644 index 0000000..5d470f0 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/41.a @@ -0,0 +1,2 @@ +Bounded solution +84.000000000000000000 71.000000000000000000 82.000000000000000000 89.000000000000000000 38.000000000000000000 69.000000000000000000 99.000000000000000000 37.000000000000000000 51.000000000000000000 92.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/45 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/45 new file mode 100644 index 0000000..97401fd --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/45 @@ -0,0 +1,13 @@ +10 10 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 +0 0 0 0 0 0 0 0 0 0 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/45.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/45.a new file mode 100644 index 0000000..082904b --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/45.a @@ -0,0 +1,2 @@ +Bounded solution +0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/47 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/47 new file mode 100644 index 0000000..4216e98 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/47 @@ -0,0 +1,53 @@ +50 10 +15 18 10 36 27 98 44 58 66 28 +-69 -29 64 -29 19 -95 65 92 14 79 +-29 25 -20 61 -39 72 100 -41 -14 -17 +31 37 -56 16 -60 68 34 43 97 -22 +39 -99 41 -44 67 13 79 77 61 37 +20 -97 62 83 96 -72 45 -72 -6 -30 +-11 -43 -77 -62 -73 72 -67 -69 55 68 +35 29 -14 -80 -65 78 72 -92 -92 -80 +81 68 22 -37 12 -91 -91 16 3 -93 +62 -93 10 66 21 84 -6 13 77 -7 +38 -8 1 83 82 -65 -88 100 -54 -56 +12 93 64 22 -25 62 93 93 -72 -92 +-19 -67 -18 41 38 3 -35 -45 46 41 +-34 55 -65 -27 -7 18 62 40 -40 17 +33 -80 -32 -26 -54 100 -75 -35 -59 45 +-14 -24 98 60 -26 41 50 21 -67 88 +-43 -57 -34 17 -1 -19 -69 49 40 -92 +62 -86 -72 -30 -1 -41 15 59 -84 -70 +11 -94 -18 90 -7 84 -29 -54 93 64 +-100 -54 94 -57 -48 -77 15 13 -50 -58 +-7 -22 25 28 10 46 -19 27 39 27 +88 -25 -47 15 73 81 -59 42 -100 -7 +-67 -28 55 -48 79 81 68 81 -46 -34 +3 -73 98 90 -53 -77 39 39 -72 -4 +-64 37 72 -84 -67 42 22 59 79 -20 +37 60 -21 -34 -58 -27 -82 99 77 -59 +59 71 -35 -27 -92 34 -17 -9 -53 31 +66 51 -53 -1 43 25 24 -76 -100 -3 +-90 40 -98 71 64 78 20 90 -72 59 +61 -39 32 18 -99 13 -13 -92 43 -14 +99 60 48 -36 32 -74 -34 -95 -39 -55 +30 89 -46 -8 -19 -50 -69 -34 17 67 +-46 39 6 -8 -6 -42 -92 -95 -92 -8 +-69 89 -87 -3 70 -14 -43 -57 -22 16 +98 -2 -35 -22 49 11 30 -23 -94 -99 +-76 88 -98 90 -36 31 -22 -5 -6 -99 +-21 26 79 57 22 34 53 27 -65 76 +-80 80 47 26 -1 20 -58 40 83 42 +-82 -16 66 -11 2 70 -46 -27 99 15 +-92 17 39 69 62 72 -76 -57 -37 -16 +-74 19 11 -84 -30 -69 65 29 -9 -67 +19 -17 -37 -84 49 72 27 -60 -96 -30 +-13 46 -44 8 -93 39 57 -98 5 -24 +-65 11 -99 -35 -9 73 90 -51 -53 100 +-48 35 -41 54 -96 -38 -44 40 -38 -42 +-26 55 -27 53 -56 -42 77 -38 20 -33 +-96 -32 30 38 95 89 -45 64 61 -60 +23 18 -26 5 77 100 -70 -73 75 -36 +-57 -66 81 29 58 -69 -67 96 48 50 +-51 85 -76 -11 -29 96 -24 79 -12 -63 +24484 4961 1465 11546 14854 -8767 -11396 -11298 -2433 9900 7031 18846 -4929 5671 -7192 10624 -11261 -10520 1504 -21741 8852 12747 13006 -7090 5830 5600 2389 1201 17397 -12734 -6576 980 -19210 -3319 -1756 -6346 16403 12892 1383 -1049 -12166 -4626 -11462 -869 -11310 -6971 10760 6479 5583 9129 +-4 -91 -63 43 55 86 -9 11 71 -64 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/47.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/47.a new file mode 100644 index 0000000..08732f1 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/47.a @@ -0,0 +1,2 @@ +Bounded solution +64.000000000000000000 82.000000000000000000 38.000000000000000000 27.000000000000000000 72.000000000000000000 80.000000000000000000 30.000000000000000000 100.000000000000000000 32.000000000000000000 60.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/49 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/49 new file mode 100644 index 0000000..a0559e1 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/49 @@ -0,0 +1,10 @@ +7 7 +-62 -40 -77 -91 46 -64 40 +52 11 41 51 40 -71 87 +-57 73 -66 89 18 11 91 +34 -68 87 -32 19 -1 37 +-74 24 -13 29 97 -91 -86 +69 24 -70 67 -68 -98 76 +89 86 -1 -2 -77 -62 -27 +769628 -834013 499389 616207 -254336 -994356 -56081 +-7 -80 -96 -87 -20 56 14 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/49.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/49.a new file mode 100644 index 0000000..0fa072f --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/49.a @@ -0,0 +1,2 @@ +Bounded solution +6031244.782178217545151711 2821669.525852585211396217 0.000000000000000000 0.000000000000000000 0.000000000000000000 12572587.836083607748150826 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/50 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/50 new file mode 100644 index 0000000..31f8df8 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/50 @@ -0,0 +1,18 @@ +15 16 +-8 26 72 65 72 12 -95 -90 -71 44 -9 33 73 91 0 -48 +60 -54 -52 -98 -14 60 47 35 34 89 -81 -85 36 98 -94 -10 +40 -5 -84 7 -53 -33 -11 79 -58 -20 46 -15 -6 50 50 17 +-3 96 -44 46 3 95 67 35 -34 52 16 8 -24 -41 73 98 +29 35 -39 -19 70 -53 51 28 10 21 30 -62 -100 33 -56 53 +-81 98 18 66 -5 -60 34 91 72 -97 -74 29 58 45 77 30 +7 -74 2 6 -38 71 -23 -6 -22 90 -60 14 -39 -56 -32 -79 +-11 48 -22 -28 72 53 -93 -14 66 22 -97 -23 86 81 -66 34 +-23 36 18 24 77 27 49 -66 85 74 62 45 -14 -7 74 0 +81 -20 -79 -53 -21 -30 -71 24 57 -68 -76 90 60 -57 -63 66 +-26 42 -68 -57 5 -62 35 -98 -87 41 76 -85 3 -11 -15 -66 +-62 32 73 36 -84 93 74 -68 -3 -91 -12 48 -13 30 -19 -27 +-32 65 -15 78 94 -4 25 64 -41 64 61 68 26 0 -27 -80 +-40 81 13 13 -19 -53 48 -10 18 3 71 -49 64 88 -49 62 +-77 -9 35 52 27 -80 55 86 18 24 -81 72 -80 71 84 64 +-155075 -78060 -992018 -197842 163377 -420166 707675 624881 319527 -432471 -579283 -234053 3854 587974 -873497 +46 -27 -33 11 -31 68 -45 -73 -78 54 30 -48 59 -29 -51 -97 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/50.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/50.a new file mode 100644 index 0000000..c047372 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/50.a @@ -0,0 +1,2 @@ +Bounded solution +3300871.385048407129943371 0.000000000000000000 4143412.492378769442439079 0.000000000000000000 0.000000000000000000 539056.294073740369640291 0.000000000000000000 2439271.805426382925361395 636119.051952935289591551 0.000000000000000000 1245146.014359915861859918 0.000000000000000000 253163.508762392535572872 0.000000000000000000 275279.459835202898830175 439962.202773990633431822 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/52 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/52 new file mode 100644 index 0000000..c14dd2b --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/52 @@ -0,0 +1,53 @@ +50 50 +57 97 24 30 39 32 82 35 41 27 32 59 97 1 68 84 28 69 21 12 46 10 42 7 80 37 40 83 13 98 95 13 87 53 26 91 47 96 62 60 21 83 46 46 37 97 16 2 100 95 +80 -1 -83 83 53 -59 -12 -79 2 36 -67 60 83 -36 -27 -98 83 13 4 50 -63 -95 82 -20 -31 -26 77 -46 -31 -65 44 -88 -77 -64 -99 -48 -91 -70 83 -33 -11 -42 42 78 91 -80 -67 -84 38 -38 +-50 -64 -63 37 -42 -99 -55 89 84 89 -17 1 90 90 -14 -35 97 28 -3 53 30 -20 -98 -94 -11 -15 -35 56 43 -80 -63 -46 -82 -100 -98 -93 -79 -97 -98 96 30 -66 -58 1 -10 69 -91 13 -54 -45 +-98 -31 -83 39 -59 32 -51 -64 88 -14 59 33 -80 8 58 -78 -73 -29 84 42 -85 80 -7 1 34 -17 48 75 -71 -82 9 -94 63 77 76 -77 -45 40 0 31 20 67 79 -55 91 9 -15 -93 21 -39 +3 -56 -2 75 68 67 92 76 -7 -70 6 37 48 32 66 36 12 67 14 52 54 43 62 -88 90 41 57 -87 -79 48 35 -51 -33 21 67 -38 -7 -50 -51 61 -66 -39 87 -22 -55 71 36 27 -91 51 +-83 16 -95 -56 -74 -37 -3 93 -7 -62 -68 -89 -32 -81 36 19 74 -36 4 94 66 -99 -20 30 -36 5 52 -13 -54 72 97 96 11 31 -53 -68 6 -89 60 -1 -76 -2 42 -24 -50 -44 -71 -5 -58 -82 +-39 -10 -37 69 49 46 -69 61 20 -57 93 95 52 88 -69 11 82 32 22 -44 -98 -12 -51 9 -2 73 42 13 -36 61 59 0 -60 -19 -59 -29 81 20 -22 1 -83 25 71 -22 16 62 -72 -91 -51 59 +41 -84 71 -79 33 19 -54 -96 -23 -68 81 10 -26 -50 -47 -23 6 65 82 60 6 -16 -32 51 -19 -3 -10 14 -92 -60 -47 45 -86 49 -100 -68 -25 93 -98 -40 72 76 -89 -42 55 8 100 60 -89 -12 +-28 -66 -84 17 -49 -40 -23 81 75 -99 -40 -15 53 55 66 100 -88 65 -93 -46 44 -84 -62 -36 47 -41 96 33 -27 41 84 -9 24 -92 59 -90 86 88 -99 56 -41 -17 64 36 44 -77 -45 -15 96 -44 +-73 -12 -37 -12 -80 -9 47 45 40 97 100 57 -72 7 95 73 31 -44 39 32 73 -20 77 65 -47 -43 -81 -60 67 -73 33 -41 -63 94 32 -3 -94 -55 -39 -82 20 -35 14 -36 36 -58 -5 -89 -58 50 +99 75 36 -60 78 -50 15 70 -37 -52 75 -74 -69 38 -41 -78 -87 -48 -58 68 30 -48 48 83 98 39 -77 87 47 43 -21 -21 -55 -14 -90 -73 20 -25 36 26 -81 13 74 7 29 -49 16 20 -23 -9 +-41 -11 100 -11 -8 -86 52 96 -13 16 54 82 26 -42 32 77 55 97 -87 -7 65 79 78 61 9 100 -38 89 -21 -25 92 -59 59 -34 52 6 -48 68 0 -7 77 -63 -50 -9 -11 81 -99 42 49 50 +-60 -79 2 -5 76 85 65 -93 39 -87 91 -48 45 96 -37 87 -66 78 -50 -54 91 90 82 -90 -10 24 18 13 -25 -20 -78 -84 10 -83 -88 -87 -23 71 34 45 91 -13 -51 2 -58 98 97 68 55 -70 +-83 9 -85 -8 -100 -52 -77 44 -16 37 -21 75 2 -79 -73 37 64 95 84 90 94 -84 -90 53 94 76 -49 92 99 0 -55 37 100 -59 -24 -9 -40 4 26 -18 -67 59 77 92 -99 -81 47 -80 99 14 +-3 16 41 -33 -11 -58 99 58 -47 -96 -63 -71 73 38 56 22 -10 53 0 -91 -34 92 -87 -18 -98 5 -48 -87 67 42 34 -97 -100 -74 24 30 21 -23 -78 -39 -72 84 -34 66 13 -74 25 29 -8 -7 +-54 -4 24 13 -90 85 86 -14 10 -5 -39 55 -5 -20 -97 -19 -3 -42 96 8 -5 99 -53 29 -52 79 2 47 36 1 -71 -98 70 -43 -63 51 86 5 46 35 74 -54 -12 28 -46 50 -86 66 35 86 +-32 81 23 -59 -85 34 23 15 -85 49 -34 -72 -99 -94 -7 41 40 -7 52 99 -1 -68 49 79 40 -40 -96 -75 95 52 -76 49 47 -85 88 -47 56 73 -9 64 92 -45 34 -3 -8 -14 57 57 15 -24 +-79 -78 -53 -91 39 -15 -47 -4 -47 88 67 87 98 -69 91 -46 93 -39 -17 76 79 -46 -6 90 -51 25 -8 -83 19 88 29 2 73 74 74 92 -38 -23 10 82 -58 -3 63 -44 79 -47 59 11 -51 75 +56 39 -24 -68 -60 -37 91 14 3 -45 35 97 -58 76 -15 59 33 -47 -94 68 26 67 -25 90 88 -33 9 -50 -46 24 -65 73 16 27 -89 4 -32 71 44 49 16 -4 91 -91 -23 -7 -12 51 72 92 +88 44 -61 -51 -54 78 -87 -26 -18 -76 83 96 16 62 19 -27 -11 -3 -39 31 43 -65 78 -93 43 -65 21 -60 -35 -36 -49 -19 91 -78 -61 92 -90 79 -54 -82 24 63 80 -39 17 -83 41 -28 -35 -90 +-16 -78 93 42 -16 40 47 30 -18 70 87 -17 56 53 -10 0 -82 48 -51 9 -14 50 75 74 -16 34 -14 -15 22 44 77 -32 100 -61 -73 98 -42 41 -70 7 54 86 29 -7 0 -38 -99 0 -11 -82 +-99 24 62 -79 -46 -29 4 43 -76 65 88 -70 58 84 -69 14 66 65 84 -46 9 92 6 -94 43 95 -72 83 -34 -14 -9 95 -9 43 -55 -96 -24 -4 78 64 85 13 -27 -45 -75 98 52 -95 62 -39 +-12 73 -79 -86 -13 13 56 77 37 -44 92 68 77 98 99 -38 2 40 -70 12 24 -82 42 -79 11 -41 -38 55 55 16 -7 63 23 -81 61 -93 9 -99 -37 42 -22 -69 0 -67 -41 9 -78 -64 72 -29 +-14 70 22 16 -68 82 -77 -63 65 -45 33 65 -100 41 -23 -28 68 -67 -20 -56 -13 -82 52 -53 72 -63 52 -77 65 28 26 30 6 -67 -82 93 33 -2 -16 -53 11 -30 -18 14 -58 74 -78 24 -24 -62 +2 99 3 47 96 -91 -8 -32 -41 44 57 -21 -91 32 66 7 -58 67 11 -80 87 5 -49 79 47 -65 -85 -76 -59 -52 49 -19 -55 62 -62 3 -65 60 55 -42 -70 68 82 -52 71 3 -91 -41 85 62 +20 -36 88 2 -70 -5 35 -6 -48 -81 58 25 -72 64 56 16 38 21 -10 -81 67 82 -18 75 -42 -33 80 -93 98 76 92 54 11 -95 60 -56 22 95 75 -46 27 -73 53 -62 87 22 -6 17 100 85 +91 18 19 75 65 -55 4 43 -100 64 54 25 -65 54 17 -33 -95 81 13 57 99 78 64 -41 55 -10 17 3 -99 -16 -76 -41 63 -54 78 -71 -95 -38 63 51 27 -62 -20 -51 47 15 -4 78 -37 51 +24 -29 25 64 82 -41 0 -60 -82 63 -97 -31 93 -32 36 -95 90 -31 -42 45 -57 -77 -23 -54 88 -32 -32 10 -42 -89 -59 -45 -44 50 -9 -38 -32 90 -46 31 -99 -75 -84 87 1 18 93 -34 38 83 +75 36 -34 9 -42 -73 -78 -18 28 -29 49 -55 -91 90 -78 -59 17 100 10 -93 62 -44 -93 -49 60 -80 -48 -67 88 57 62 -13 33 -28 -32 -29 -32 -79 -67 34 -20 27 -20 5 -35 -100 -88 -68 79 55 +-77 -10 33 62 79 -14 -26 42 76 -85 61 11 99 -51 -65 9 53 54 -85 -53 -87 7 64 -12 -18 33 96 -91 -45 -50 -93 51 82 -98 24 21 93 79 50 80 -19 -74 -37 -60 64 -36 -24 -19 -11 -47 +-29 41 83 -56 36 16 -28 -94 76 4 -27 -26 -77 88 -48 28 -7 -82 -59 -18 31 45 -79 -23 -62 26 82 -20 31 88 73 94 -58 -72 -42 -14 88 19 93 57 -79 27 -66 -94 -72 -28 87 49 43 20 +-49 52 82 -29 -46 -30 63 23 6 -52 57 41 36 31 -40 70 34 25 -36 -12 -10 -95 99 -47 45 -13 -54 -80 73 100 61 -86 -45 56 -76 23 67 12 -92 -37 85 34 98 -64 99 70 -27 -27 -17 9 +-51 32 69 96 -91 -85 -41 57 82 46 38 46 -53 -77 23 -8 100 -51 -24 -19 -26 -98 18 25 -32 92 -35 3 -79 23 -54 80 21 44 81 -10 74 71 12 -12 47 -9 59 -40 98 54 44 58 -63 -47 +-7 86 58 -40 -14 33 -99 58 11 96 58 62 86 -8 43 -22 93 -59 20 -12 -9 -43 57 42 80 -13 20 99 -56 60 -96 -16 -16 71 -96 -25 98 89 -81 -37 -8 -44 -3 -47 20 89 12 34 89 77 +80 -97 9 -14 -29 17 89 -100 -77 -4 88 9 -34 22 47 0 -83 9 -99 83 -36 13 -79 -39 23 -28 -78 29 91 -95 47 -74 -55 66 -64 -49 76 -15 67 -64 27 96 -47 -46 71 75 8 -83 -91 16 +47 46 7 -47 42 65 87 62 23 -69 9 -7 -90 4 48 -92 57 -55 59 33 -43 88 82 -90 14 -12 44 -42 -36 84 -16 -40 -39 2 73 -50 -66 58 68 85 -14 -63 90 -39 96 -57 -47 -17 72 -9 +-68 -16 22 100 -25 36 -33 -12 90 56 -31 96 25 -4 48 88 54 98 83 42 -21 12 -21 -34 39 -18 -21 14 5 15 14 18 26 7 -22 -27 -16 -79 -8 64 74 -22 -68 70 61 44 96 -8 27 -25 +-3 -26 85 -5 -14 -14 4 12 -9 72 30 -23 34 -62 13 24 13 2 40 -1 93 -91 -90 15 -58 71 44 -59 -30 -87 -97 1 57 84 1 -87 67 70 58 71 41 66 -57 -42 86 -38 19 51 -38 -91 +27 67 -81 41 7 12 -39 -48 -74 -76 -14 -13 9 -21 -43 74 98 -19 -22 -8 87 -97 51 76 20 99 -56 -13 89 0 -15 32 77 -69 1 -45 38 -48 -69 -100 29 70 -20 -20 -84 -47 -16 -26 86 37 +-99 48 -34 0 -87 49 35 46 -22 -29 27 -22 -23 82 -66 56 53 36 54 -52 2 21 28 37 99 29 21 -71 98 14 8 32 -27 -5 41 71 -9 -70 -1 -48 12 39 -18 4 -34 -53 14 11 66 -30 +19 -59 -22 9 -91 -98 12 -99 -66 -89 -80 56 90 70 70 -23 28 -80 -13 -58 8 92 29 -33 -1 -31 -73 74 4 11 -91 22 -45 -4 63 -76 -52 -19 37 94 -14 9 -42 79 87 -83 11 -18 -33 -27 +30 20 -9 -74 71 78 13 41 -78 -81 3 58 34 -65 -60 -57 -10 -68 22 2 -66 1 46 89 -19 -46 83 -38 3 54 9 28 34 2 -23 53 -90 -17 -10 9 79 100 -30 -71 79 -13 -28 38 52 -41 +-77 48 0 9 81 -29 74 43 -7 -83 -76 38 4 -11 96 36 -70 36 -19 -7 13 -92 39 -41 -1 -5 64 64 98 39 23 99 -1 -41 71 -48 -39 -57 83 -22 -28 -94 -13 -25 -98 98 14 26 -77 -82 +14 77 -46 72 24 26 -24 65 -5 -78 -89 2 24 2 -62 41 85 62 36 87 -98 54 -61 38 -88 -84 -23 -59 -70 53 -63 -93 8 29 48 -87 -51 -33 67 64 55 54 -69 47 10 -51 -51 27 65 -62 +1 36 -87 -80 91 51 21 -47 91 -25 54 8 -72 -86 -48 -85 58 4 2 15 90 20 75 55 -43 17 68 -97 92 4 96 -84 56 -7 -22 -71 -87 -26 -100 -83 -68 -7 94 -49 -68 15 -18 59 81 59 +-84 -45 -9 -21 21 -17 -47 -45 -57 -63 37 61 25 44 -36 45 44 -49 -36 12 39 -77 -84 -63 -1 35 23 -74 -59 93 -23 21 14 10 23 56 -81 92 24 2 -46 87 14 19 -80 91 76 -34 47 -47 +95 18 21 -91 61 57 -3 -31 -70 -9 -73 85 68 -25 15 98 -82 -75 -69 -60 33 -91 -47 -95 -92 2 -87 85 47 50 5 -100 87 86 -77 65 75 -99 1 -89 -71 28 -18 56 92 -65 47 25 -77 -75 +95 23 93 52 76 -72 15 -97 66 -69 -56 51 -85 54 -30 -80 10 81 92 52 -93 98 -45 -11 -37 -89 100 91 -41 81 9 -93 -17 91 45 1 -85 -48 31 -58 -50 -1 -91 99 -29 -99 27 -40 81 -28 +29 -35 19 -14 50 -5 -37 29 -28 69 4 97 -33 94 -87 42 -15 24 -9 76 -30 63 83 63 54 54 10 -76 -18 -92 52 61 81 22 -47 -18 -37 99 -8 21 98 -15 -16 100 -9 46 12 81 -92 -99 +54 -9 -61 32 -11 57 98 37 64 -61 -95 -51 25 -15 -66 65 51 97 -35 -34 93 14 54 -81 -35 -89 -47 -87 -62 73 -51 3 16 97 94 37 50 85 90 22 -39 0 91 -36 49 97 -93 21 77 100 +145481 -40248 -40148 4056 25891 -41831 3593 -37132 -7704 -2694 -8394 56285 11659 25883 -27019 20485 18281 24683 15612 -35069 15911 19898 -4003 -3901 -4484 31141 9009 -14396 -30834 -7948 8747 16007 35117 43881 -2232 -6681 63503 -1165 5882 18070 -17452 -19130 3501 -9769 1130 -12950 -20801 4198 28459 27160 +-68 -25 51 97 1 -18 0 62 69 85 -59 13 35 -76 -77 95 -1 -1 29 1 5 76 -46 56 -89 -65 -94 -68 -1 -36 37 73 24 32 -47 -89 78 46 90 1 96 97 -85 -32 86 81 -28 37 -47 25 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/52.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/52.a new file mode 100644 index 0000000..d9f70f5 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/52.a @@ -0,0 +1,2 @@ +Bounded solution +0.000000000000000000 0.000000000000000000 0.000000000000000000 128.907571002061810000 228.196017399579740000 19.154374988214435000 0.000000000000000000 38.113188120175920000 150.000186953825590000 256.156415139845250000 0.000000000000000000 0.000000000000000000 74.409631215420319000 0.000000000000000000 66.357652725149222000 0.000000000000000000 0.000000000000000000 31.332923476594804000 17.008975440917038000 0.000000000000000000 0.000000000000000000 160.712304346468300000 0.000000000000000000 60.843232138317617000 0.000000000000000000 0.000000000000000000 0.000000000000000000 145.749341933913310000 100.050694487942740000 0.000000000000000000 36.378602723696183000 226.321433693633680000 0.000000000000000000 33.706270238079945000 245.375782348505650000 43.315940623275587000 206.283749335645440000 0.000000000000000000 38.241642245214706000 0.000000000000000000 283.260379926609000000 213.064518580678200000 8.350038318450568700 168.511011773298630000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 17.313794204134364000 252.091293669138910000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/55 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/55 new file mode 100644 index 0000000..6227bc6 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/55 @@ -0,0 +1,53 @@ +50 100 +55 2 -12 -27 92 -22 -11 43 -7 15 98 3 -57 -10 95 -89 -10 -13 -1 -45 6 -93 31 61 35 5 87 -62 -70 19 -95 -38 63 100 -1 -75 -5 -38 -16 -85 23 19 30 96 -28 3 -57 16 -63 47 -74 74 65 -20 -13 61 53 67 -17 99 -33 60 -87 -83 -26 -16 30 -64 92 -6 83 -56 64 81 -89 -67 -81 60 -25 88 35 73 -28 67 73 42 -7 22 -82 -72 41 -60 83 -49 9 36 58 -19 60 84 +29 91 -100 -34 -72 36 83 -5 84 10 -5 5 -2 -63 -57 55 -100 76 23 62 -51 20 47 -19 -98 42 -54 21 -14 -44 -93 26 27 87 73 40 -48 -88 -86 41 -86 46 53 82 52 -13 6 94 54 90 -74 83 99 -99 95 -59 59 -38 -85 -2 -6 63 28 -61 -40 -9 15 85 -75 72 -88 82 73 -14 13 -29 88 47 94 22 17 46 -8 -13 96 -18 -12 31 75 31 -81 -18 -11 -22 44 -83 69 54 -10 -84 +78 49 -63 75 -89 -89 -68 -68 -28 90 97 -56 -4 24 -49 3 18 29 1 62 37 -43 4 73 -1 -24 73 -56 -74 -70 1 21 73 56 13 98 -3 64 -40 -8 13 12 -25 -59 22 -43 81 11 -8 47 -55 -19 23 -81 -14 -66 -8 84 51 -93 -33 41 -80 76 -46 -36 -6 -72 5 -89 38 4 54 16 45 86 13 -33 -32 58 100 -49 47 10 -44 47 89 -73 41 72 75 35 -86 -27 98 39 32 71 37 15 +-24 45 -95 48 36 -9 43 -81 8 -68 -100 46 -53 88 -53 -8 -79 -88 -19 4 -21 5 33 17 -82 -97 0 -18 -40 87 -33 61 -80 -49 67 -31 -29 41 6 -92 47 82 69 -90 8 -67 -61 25 -92 57 -22 -28 -100 -32 12 -69 -48 7 88 66 -86 -80 -97 -66 -77 19 59 -27 98 -1 -19 54 -58 86 -10 -83 -28 -34 -11 42 40 -12 -55 33 -20 -28 17 35 -92 -56 4 87 -70 79 -69 -82 -21 53 -51 52 +-12 42 -24 84 67 -71 59 -91 15 50 -44 57 55 -81 -93 81 -90 24 -63 39 -19 -35 3 -11 70 -13 36 32 79 -60 0 -93 -63 -30 -8 -44 -59 92 72 -37 23 -73 96 83 -58 -16 90 -47 37 -83 34 -53 27 -75 21 -47 -52 -96 -10 -35 -9 -15 24 2 -31 -16 -12 -41 60 84 69 95 -48 -85 -24 -11 -29 85 -9 -32 -48 -9 88 -6 -60 -23 35 -88 8 0 30 13 89 -26 9 -86 30 -1 -53 78 +-90 -62 -22 -43 -32 100 -8 -92 -72 38 -10 -64 23 -89 74 87 67 -48 85 8 -61 -63 -47 -48 55 -68 -7 -26 -95 59 -73 31 -54 65 -41 -89 68 84 15 -17 15 25 29 12 95 34 57 66 96 68 -15 46 64 89 72 6 31 77 48 60 59 44 -82 -20 -13 96 90 8 31 38 93 -42 -27 -8 53 -59 -42 -19 -83 -48 86 -36 -41 -65 -85 24 15 -34 65 27 -91 96 77 41 7 48 2 55 98 -81 +-23 -74 -3 38 -83 34 -37 28 -9 -64 12 -23 -51 4 -5 -90 -35 23 -16 -35 -18 -93 37 -91 -97 94 -14 65 55 71 10 -14 -91 64 77 -59 25 -64 65 -58 7 14 -61 -87 81 19 37 30 40 46 -84 -92 10 -63 49 45 -53 -18 22 -70 73 -70 94 60 -21 42 -56 2 -73 1 82 -79 -7 -62 38 -39 -14 -51 -70 -88 -70 56 60 -33 -16 -79 66 -70 17 -18 -10 -32 71 78 22 -57 94 -83 21 -95 +44 18 97 -28 -33 -75 -36 29 24 54 -74 71 -26 -96 -56 -34 47 30 -32 77 -94 91 -93 0 -57 5 1 61 21 -24 79 -45 30 -19 50 -69 74 -99 51 0 41 -44 86 65 80 -78 95 39 60 0 72 88 59 -7 88 13 25 42 70 66 7 -69 79 -6 -77 -23 66 -73 -12 -82 -51 1 35 -77 -49 45 -82 35 -61 -42 -19 -71 -83 91 -86 -26 -29 98 84 -16 -2 -22 20 78 -27 -67 11 55 92 33 +42 66 50 -18 43 73 12 -35 60 40 39 -48 -64 90 43 -83 -59 51 33 -20 -91 -85 -85 48 28 56 -40 -87 83 -41 -91 14 41 -30 88 -52 -1 -13 36 -5 54 -85 -99 93 68 82 10 12 -57 22 20 -9 -13 -96 -54 -20 56 12 -60 -28 -18 -39 17 40 83 67 99 -50 82 -91 24 -9 -95 -91 -21 53 86 89 -98 -94 2 84 87 62 93 -38 62 -36 -48 -97 14 38 -44 -22 46 23 -42 67 39 79 +8 -31 -44 -54 88 8 45 -15 -44 -85 31 64 -54 -56 88 38 -86 100 69 -89 35 -30 -44 -38 -35 40 32 -80 84 -35 -97 97 -76 -56 82 53 36 -65 73 -93 41 -42 -13 -64 64 -69 -61 82 -96 -77 -81 21 -8 56 -14 28 -33 -75 99 -72 -42 95 -40 -10 -69 -54 26 56 -30 -86 -71 -70 -49 6 -99 60 26 -16 74 72 -11 56 77 2 -86 -40 -6 68 -84 -60 64 -22 94 92 25 67 88 -32 70 13 +-25 4 45 51 92 88 76 -15 61 -42 72 22 -91 -27 30 79 15 -72 -33 11 14 86 34 -36 -46 22 -13 -8 -98 -15 -54 -67 38 -81 -34 35 -91 -21 -30 -85 -28 3 69 92 14 54 36 -44 -59 -33 54 33 -9 31 48 -74 -27 -96 75 54 -100 89 78 17 -87 -47 -96 88 -51 51 73 25 23 69 34 -30 -5 -41 -32 29 38 -16 -97 -76 70 18 36 -5 55 17 89 -41 -28 77 -87 -7 -45 70 43 36 +87 9 53 11 64 -36 -39 -57 13 99 -15 37 19 9 17 -2 39 -34 1 -68 56 23 -46 81 28 -79 5 38 8 28 39 -59 21 -6 -10 -52 79 -62 -72 21 -80 89 -16 40 -5 38 77 18 -53 -53 -12 -59 26 -48 -29 51 -60 -51 -22 3 9 -6 -87 98 98 98 63 49 55 52 63 -11 52 -61 -28 -94 4 35 54 27 70 -29 7 -81 98 -54 4 16 -17 49 19 76 94 48 77 27 -34 3 21 40 +65 27 -67 -2 -94 -7 48 -18 81 51 34 -45 -11 49 -17 -45 -35 -3 88 64 -92 83 17 -91 -99 -16 -3 -83 63 -12 62 -1 -81 53 74 -17 2 -74 -65 -17 74 3 4 -14 -52 -27 71 44 65 -67 -62 50 50 10 -43 7 54 -13 -33 5 -97 6 30 -48 -4 -4 -57 -94 -76 8 -43 80 -5 -39 94 -68 68 -64 46 -5 14 -76 40 -69 65 91 -26 -91 18 -41 10 -27 5 -100 68 97 -53 -31 -70 98 +-12 -75 5 -43 64 -8 -48 86 -65 -78 24 14 -20 -55 -79 -75 73 87 -14 -63 69 91 -17 -2 94 45 -53 -70 14 87 -63 28 24 65 -27 -43 -43 -100 -25 32 44 -54 -4 -3 55 3 84 18 -66 10 82 1 -31 25 -54 -35 -14 -28 -41 20 56 56 40 -33 79 74 -60 -75 -6 19 -60 10 -91 99 80 95 -12 55 -20 28 -48 86 26 21 97 88 -97 46 86 -21 -41 -65 46 -15 0 21 16 26 71 40 +-73 -70 -71 -6 70 -74 47 0 0 -96 -88 50 -35 -64 -78 56 -91 90 59 52 53 -61 -38 -39 -62 -93 -70 21 -97 -26 -22 -98 58 -54 -80 88 -22 -29 -38 76 -74 -70 0 64 -14 -18 -62 -38 -45 -3 -31 -73 -14 25 -42 -57 30 -35 11 -1 23 -51 -7 1 -30 -52 -30 69 -25 100 94 22 -35 68 9 -65 -47 38 -70 0 30 -55 -11 41 -18 -47 45 -20 7 40 -37 -28 -2 -22 91 -41 -91 21 81 -56 +52 41 -85 50 -86 2 -88 -88 62 77 -23 89 3 -55 -91 -90 -24 45 -51 -82 28 -62 87 50 -9 -80 -12 40 -22 -94 56 36 12 46 -90 83 57 35 30 90 27 90 99 51 3 -66 -4 39 18 90 55 51 7 10 -65 2 -5 97 93 -89 45 -19 11 74 63 -81 56 -37 3 45 0 -30 27 10 -29 -99 -87 -77 -95 51 51 56 8 -58 -76 76 3 11 -37 41 58 28 61 -6 -60 -66 49 -9 12 -24 +-32 -37 32 12 -24 86 36 -20 97 -42 67 -68 70 -42 -74 -20 11 75 34 50 -7 -10 -30 45 8 -74 70 -64 26 -49 -98 -65 7 70 -55 3 82 -30 2 26 96 -72 -64 16 -56 -57 -21 -95 -36 -61 -65 96 95 69 -6 33 -59 75 58 -68 -65 -4 -92 98 72 -90 30 -99 9 53 -32 -98 97 -34 -11 -96 82 21 -72 -29 66 50 66 96 77 -100 -12 -52 38 -77 -21 16 -37 -58 -90 36 60 -46 47 -33 +18 -64 -38 8 51 -5 90 37 92 71 92 -61 96 -54 -72 -59 -33 24 -49 -56 -6 3 -50 4 77 64 -71 93 62 49 3 17 49 9 100 32 -30 -10 -59 10 -33 -52 -49 56 54 -1 67 -23 -45 93 -33 77 12 16 44 83 -56 21 -77 61 72 -65 15 66 -83 58 10 -13 56 -38 71 -98 76 -34 -94 -68 16 -73 33 -42 17 -20 11 49 -34 -23 -49 53 -84 -70 -85 -46 -27 100 -79 71 -15 3 87 -1 +39 58 -36 5 85 -18 88 6 67 -57 -69 -31 34 63 -59 8 -83 70 -88 28 -71 -94 56 27 -19 17 34 -61 -83 -78 74 -25 18 -69 -3 -62 -34 -86 -24 38 -9 -5 59 3 18 -54 -67 -49 47 -42 39 -93 42 49 -63 -51 -2 45 58 53 -75 0 -76 33 66 28 -29 -34 -70 23 -68 5 -53 53 64 82 -97 54 14 -63 -91 76 -95 -96 -88 -83 47 -27 91 84 -89 69 -22 -12 -93 -71 -26 -23 -11 -98 +-82 -15 -2 -34 18 -79 -65 79 5 -14 9 77 -45 -22 67 -47 -83 79 62 -9 -70 70 61 -44 -70 68 24 -96 -97 80 54 -86 25 -34 -59 42 27 29 38 -46 40 -90 13 31 15 66 50 -44 40 -71 94 39 62 12 -83 28 52 -2 -52 -77 61 -35 100 88 -92 -22 72 -37 -55 -94 -16 -89 63 -2 -54 -33 90 78 18 -99 -46 -81 -79 42 32 -36 41 -1 68 64 41 4 -40 -4 10 19 40 -60 41 42 +77 -8 -23 -85 40 24 94 -30 -5 25 52 18 52 93 76 56 64 -70 79 51 100 -35 -55 -1 -52 32 60 70 -17 3 27 -43 70 91 79 -6 -52 -22 98 -92 15 -5 91 63 59 -26 55 79 53 94 -1 52 -60 99 -62 12 93 27 100 -6 -18 16 -1 62 20 19 -42 44 92 89 -75 -18 87 -24 -89 -15 78 -83 -80 25 -70 61 -55 37 86 61 65 -86 71 27 -77 30 -1 44 -94 83 73 -66 -50 66 +7 -68 13 -97 10 99 74 -25 -57 86 -70 3 -54 30 -69 -40 97 94 81 -48 74 28 27 69 -32 46 39 -59 -71 -69 94 31 45 -84 65 -68 -25 19 -6 -32 51 83 48 -78 -60 73 -14 -55 44 -52 97 97 -93 68 37 31 19 24 46 61 -82 -13 -56 8 39 43 78 -56 83 26 77 26 -27 24 -45 -91 -85 -34 -90 -56 30 22 3 90 -65 -32 22 -31 -34 -28 91 -73 13 -75 -66 -32 24 -57 15 -72 +-16 -88 19 85 54 -23 83 -65 -76 29 29 76 -78 2 -17 -65 36 -89 72 15 -1 87 4 38 -83 69 -54 71 45 -54 61 -35 -86 -80 64 -77 -39 97 -70 -89 78 -73 91 49 -59 -32 -48 -97 37 -79 -59 -37 10 -6 25 45 -9 43 -46 -69 54 49 -94 41 44 43 61 -6 -62 -20 84 52 67 -9 32 61 77 -19 53 36 66 -45 62 30 89 -16 -57 -57 -50 -88 41 -5 -9 52 22 -87 -49 41 83 -97 +-21 11 4 13 -40 33 39 13 -38 15 6 -39 10 -3 53 -94 -55 -27 -73 -75 57 27 51 96 -31 12 25 33 60 -44 -23 -89 37 55 23 20 91 -95 -54 -83 35 6 -77 -84 63 -92 99 -100 44 -6 -93 35 81 20 -83 -37 -43 99 20 -100 -26 80 -31 45 -41 -62 -71 -65 -60 7 15 -49 41 30 92 -80 97 -90 -86 76 -75 -74 86 -45 -52 86 -44 -6 -64 52 -53 77 55 -57 -79 37 -14 -42 -83 82 +-91 22 67 -50 -59 34 30 -66 42 -30 93 -18 -31 -27 34 -100 74 -100 -25 -27 21 -51 -59 0 15 -34 -96 0 -47 -78 43 -7 17 91 1 -1 95 28 -100 -99 49 7 4 10 -53 32 92 71 -84 4 11 -93 -53 -16 15 -90 -88 -67 -83 -95 95 99 -68 -29 36 45 -9 -56 54 78 -40 -65 -71 75 81 30 -84 -49 -23 -22 94 -14 -74 -64 -15 67 -96 25 28 9 -57 -84 8 16 74 36 26 56 60 12 +16 33 -13 84 14 -88 -46 87 48 95 -3 14 -62 -70 2 97 38 89 -57 30 -53 -26 -85 -42 -44 -24 -10 -90 8 -93 -55 16 56 -39 9 -1 15 95 50 51 23 87 -82 -40 66 38 -71 -47 -34 -90 -84 -79 -98 80 74 12 -18 45 19 -68 -41 -88 86 65 -95 -63 -73 -65 -16 86 -2 73 51 -43 -32 76 43 -65 -89 -2 27 -34 -23 48 42 -81 -49 71 -100 96 23 -91 -50 72 -30 94 4 -62 -45 42 +-40 -17 50 52 -70 -18 20 -60 -3 9 18 -87 -40 66 5 -27 -91 75 -34 49 -69 -7 4 -62 56 25 -11 25 74 18 -74 -65 -40 -66 -15 -53 29 -39 -4 50 -4 -72 2 69 -12 56 -55 6 22 96 21 -4 53 99 -46 20 -77 -53 -28 -18 94 -3 -54 -86 72 63 -32 41 -22 -3 28 -15 -5 12 -16 -84 15 -63 22 98 69 7 58 -21 39 66 58 -4 74 70 26 -44 71 -31 18 71 -51 25 -67 -22 +98 -66 -57 -94 26 -8 -33 48 66 -9 -60 35 -81 -68 -83 -79 -68 81 79 -23 10 4 83 68 -49 -47 77 -46 -29 28 -88 48 23 54 -42 -88 -66 22 54 -75 -80 54 97 -78 16 -89 -65 -48 -54 25 -27 61 3 -99 -74 -37 26 91 52 87 76 95 31 66 -12 -75 -93 35 9 -31 44 -87 -57 62 3 95 41 -70 9 87 45 -51 95 -21 -87 -75 33 -8 -46 7 68 -71 31 -33 94 -96 -49 -93 -2 -9 +26 -32 72 88 -71 -66 -80 -18 -53 -93 60 -19 56 50 -38 100 -62 87 -22 93 -39 24 -83 -38 31 -37 72 -2 -17 -6 25 53 93 99 61 26 90 -18 22 7 39 -61 64 -92 22 -41 -18 37 23 -94 17 -100 -2 7 -75 -33 27 17 -48 -90 -45 0 -13 60 8 72 79 -15 -5 1 29 19 12 66 51 -54 69 -22 5 -60 -6 -35 29 -45 95 40 57 35 12 -54 32 -27 66 20 22 23 -13 -98 25 59 +-30 -80 -7 98 -23 -20 41 -39 93 7 84 18 -93 80 64 40 89 12 19 -52 71 5 64 91 -56 1 0 81 40 29 -4 -15 -30 36 -53 57 30 13 41 42 -23 39 -85 42 -52 38 45 -72 -81 -49 88 -3 67 -36 -96 -5 61 41 24 -44 -18 23 -5 90 -30 91 99 27 -29 50 63 93 28 7 87 -74 -91 -39 -100 86 38 2 -88 40 86 -71 -100 13 -84 96 46 88 -27 -52 -23 -89 -3 -53 34 76 +-42 -50 6 3 87 63 -15 -24 -66 -21 -88 -97 87 -29 -38 96 -65 81 27 3 -51 65 -37 -14 -83 85 20 84 36 -42 62 -45 37 9 48 -71 27 61 -24 -76 84 -20 28 -61 78 15 93 36 -2 3 -72 42 -75 15 -18 -40 39 -7 -36 21 -1 77 -98 85 62 9 100 -23 5 75 -49 -4 11 -3 23 36 59 2 -50 -40 96 -36 -92 -82 -60 79 28 88 97 56 64 -42 -83 10 -43 -21 7 96 -7 -78 +-9 -58 44 81 22 -31 -72 3 30 60 54 60 -99 -66 70 -65 -52 33 14 48 -31 34 -57 -22 -24 -32 77 24 54 43 -76 -75 11 74 41 37 -20 -4 77 -82 -59 -27 -61 -3 -99 50 95 -83 -35 40 98 84 -40 -40 -87 -8 65 59 -91 -32 17 -89 51 72 41 -44 -62 -27 39 29 94 78 26 -26 76 -61 -18 19 78 71 -74 68 2 -56 92 -59 29 2 -1 -79 3 60 -34 -42 97 -30 77 -25 -41 16 +-47 64 -15 5 -87 -75 21 69 32 -25 -87 8 66 -42 -80 -12 25 -37 -69 -37 65 34 51 75 -65 56 37 -20 30 55 27 59 -2 80 35 -36 -3 -31 78 -21 26 47 -5 94 63 48 44 37 68 23 37 -58 48 -66 -1 89 15 -67 21 -54 -73 -56 17 -18 45 58 31 -64 32 100 -37 60 -96 -83 37 29 -86 -12 100 36 79 33 -60 -62 39 -60 -20 51 47 66 62 69 44 -3 -80 -25 -5 -15 -95 63 +43 -71 -98 -61 72 -35 -39 39 38 -73 76 -97 39 -43 -54 53 -69 -90 36 -43 72 0 0 -53 17 86 -67 -87 16 -85 21 63 90 22 -23 -88 69 6 -92 45 -41 -19 91 -22 70 -71 52 76 -42 -51 63 99 -77 -23 -43 -39 65 -19 -44 65 35 81 -7 -57 2 39 -83 78 51 -81 14 60 52 -84 -19 45 67 -45 76 92 -68 -98 -79 -11 53 -45 -64 29 41 -100 99 90 -59 -7 -57 -4 40 -9 85 -58 +-49 -17 0 76 90 -41 -39 -44 -95 40 -78 -49 -33 -70 93 -25 17 87 -14 48 -11 -84 -44 25 43 -36 12 -25 -85 27 25 -47 26 -66 -54 -52 44 -80 -54 -5 -41 27 94 -7 -49 -85 79 58 65 -74 -60 27 84 -22 19 -28 29 77 95 -19 -38 -35 -39 -62 74 -9 92 20 -72 18 -52 -96 -32 -61 -97 3 -33 -83 17 59 81 -93 -30 -4 72 27 -49 -73 -62 8 94 22 -52 -55 40 100 -8 29 40 64 +58 -44 -36 85 2 11 -57 -55 95 -77 74 11 -56 -46 -67 38 -19 -46 35 75 -89 93 15 -7 -19 -1 83 -33 41 9 52 -25 79 17 35 94 30 55 7 61 67 -34 69 -20 -45 67 70 13 -6 87 -8 77 -54 -35 -89 43 6 17 -31 2 37 75 -86 1 65 54 -9 79 -19 16 -99 -65 44 31 -49 -29 -44 -20 -18 42 69 -50 -10 -89 40 24 -60 18 31 5 82 93 17 -36 68 67 62 65 -19 -64 +25 0 2 90 99 -82 -28 -86 18 60 -80 27 80 -85 -99 -51 -1 41 -85 42 79 8 96 -58 61 -61 -13 -30 -2 28 3 -15 33 -17 82 29 3 61 13 8 -44 89 75 -28 99 32 -55 -27 26 64 -17 97 -22 14 -65 -74 -40 -31 -49 20 -62 -17 35 -66 13 12 77 71 84 67 -26 -86 50 -63 27 -88 -7 -44 -68 48 -7 -83 58 16 -69 -92 5 73 0 15 31 -33 -43 -40 96 -78 75 -56 71 38 +-61 61 -56 90 39 35 -72 -4 53 -26 -25 51 -90 -65 64 26 63 -35 -16 -24 46 7 46 8 -72 -8 -72 -77 -74 -11 -39 -32 -20 -41 22 49 -29 -30 32 83 75 43 70 -73 -8 78 80 -70 50 68 -6 -57 -14 11 -4 -75 40 35 73 -78 -18 -15 -26 75 45 -56 -74 -97 1 -89 70 84 44 -28 -41 61 58 -26 -59 -16 89 89 -100 22 34 47 5 -97 48 44 66 56 -87 53 91 87 71 -36 100 63 +98 35 63 97 89 -66 91 -10 39 32 -68 -84 84 -36 99 28 -27 64 -97 37 -6 4 -53 78 -49 -16 -44 0 42 -20 11 10 -12 -64 -36 -65 -76 27 31 -84 45 65 93 99 98 -31 -45 15 -67 -76 72 -47 32 42 -74 -61 52 58 -17 -40 -67 61 25 -32 22 -27 -39 -98 -84 -75 -10 -15 -48 -65 -81 22 -40 6 -99 17 46 96 -89 -93 28 -55 -29 91 99 21 -39 -29 90 71 -43 13 33 -40 25 -72 +13 82 5 -20 84 -96 -57 81 29 -15 -13 -100 -75 -13 -12 -52 -74 44 -6 -79 44 81 19 37 84 -30 -14 99 61 -45 -2 -87 98 -39 -34 63 90 1 -83 -13 -17 -96 -64 46 -30 59 -97 -77 36 -22 -80 1 71 -63 -93 67 -16 -3 2 36 -97 -16 63 71 -68 -40 -83 -90 -14 -36 76 92 72 -84 71 -60 3 -53 -54 -22 31 80 -86 -42 -63 57 69 73 -30 97 -3 -71 26 69 -9 -90 -2 99 -80 -59 +-29 -47 87 64 21 -1 44 -57 9 -38 -53 31 58 -3 41 -45 -60 57 51 -88 -80 -51 2 -31 95 -9 20 -56 2 -23 20 39 -92 -26 -47 -56 74 83 -95 69 40 100 23 3 -85 -14 -27 87 40 36 6 29 -13 61 23 -44 85 -22 -29 59 29 63 68 -11 21 -75 -26 94 -47 30 26 -42 -88 95 -34 -17 55 -43 -84 -16 31 60 -46 77 18 95 -93 50 -32 -92 80 8 -40 -99 72 92 -32 88 -17 30 +17 -46 44 60 -68 -71 -21 99 -8 44 -70 -21 12 29 -68 -48 48 -14 -33 64 36 34 8 68 -87 -84 -86 41 30 -89 -3 -41 -65 -10 -72 55 68 -76 75 65 98 -34 -86 76 -78 -96 8 -25 -18 58 16 -49 -50 -28 -64 72 -49 15 35 65 -61 -59 42 -89 -20 68 -6 53 44 53 48 40 -48 -12 -29 -9 -62 88 -91 17 -26 66 48 82 25 40 89 -22 -18 -32 64 26 -94 62 -8 -49 19 -29 20 11 +-93 -29 -89 42 12 43 -79 49 -47 -91 -30 14 -52 62 -40 -9 95 -64 -15 45 1 -21 38 99 92 -9 -68 2 62 -95 -71 31 23 -76 -91 -8 -12 -78 -62 6 -35 -56 37 32 90 -32 -23 1 -93 12 -72 23 38 7 -27 -29 64 -64 5 75 -30 43 73 -1 -41 86 39 62 20 -75 22 81 61 -9 64 -7 3 36 31 2 80 12 99 -67 -73 67 -27 25 -38 51 -86 42 -35 92 67 -60 -56 27 100 88 +64 -98 41 16 -2 71 62 32 -34 -72 -4 -43 -1 -12 -78 17 99 -33 -68 -8 -59 -2 -38 68 33 43 44 78 -36 -58 54 75 -41 66 54 100 25 24 -16 80 -100 -15 -63 55 -52 1 33 19 -14 26 34 -55 46 2 -65 65 4 20 72 44 -21 58 -88 26 -74 -50 -71 40 71 95 -18 -17 89 -45 77 97 15 94 -25 10 47 40 -55 22 -30 -78 33 -93 30 -37 52 23 -60 45 88 -15 -53 10 -88 -7 +34 33 83 -70 29 68 -41 61 -21 60 32 -71 -8 -84 -80 51 66 35 -14 -96 -20 -55 92 -62 -12 90 -92 24 -49 42 78 -72 33 4 4 -72 96 -77 4 55 62 -99 -89 40 38 -69 11 -88 -7 -69 -97 -49 99 13 14 97 -71 44 -84 -25 57 -37 -16 99 -71 72 95 -7 79 36 -18 67 25 -65 61 -12 5 98 -38 -99 13 -72 79 64 -86 -6 -21 87 -16 32 18 -16 -9 -63 17 10 -55 92 -33 15 +54 5 5 4 -42 -59 23 -2 25 82 78 -20 -71 60 -59 16 -88 -99 -28 -29 39 -57 41 79 -24 -100 26 -69 73 -36 20 -69 -88 48 -55 -42 -13 -74 83 -60 -71 63 58 -80 -33 43 -70 93 -42 27 60 -12 83 19 -25 53 59 53 -14 37 -49 13 7 13 70 62 -69 81 77 16 85 39 -1 16 99 53 -1 -88 39 55 49 -94 73 -92 56 40 65 -95 -18 77 94 -88 16 70 53 96 83 -68 80 -43 +1 50 94 51 -19 -48 -2 19 -11 77 -58 10 85 -75 -27 54 92 -54 -84 -88 -21 -87 -9 19 -61 22 -70 22 13 -51 87 -98 86 -14 -99 18 83 67 13 -48 -43 -94 -19 -29 55 52 -51 -19 0 12 -26 18 56 -8 -24 86 41 62 -61 -26 -55 68 61 -5 61 68 -52 54 75 42 -47 100 62 33 5 -46 -10 -100 68 -74 53 -95 44 7 26 45 9 -89 -61 12 24 -84 -70 36 -15 -47 -57 -20 -8 -98 +-3 56 2 -39 -54 -100 -59 4 -8 29 54 -55 30 51 100 2 0 -75 20 96 -71 94 83 -82 -90 -75 -39 13 -68 -17 93 -76 -51 -100 -53 -50 -64 78 -46 33 -24 -14 42 38 -63 50 51 -55 -85 34 69 -53 43 -81 -19 -9 89 37 30 70 94 83 44 -63 -68 54 17 -3 79 15 -81 -27 -44 -25 -41 -10 -6 -21 -63 -84 -90 49 -59 12 8 64 21 67 -96 -73 34 -63 49 99 71 -41 -70 6 68 72 +-3 -73 -74 17 -47 -33 -12 51 87 26 -46 96 -68 -62 54 86 -40 97 62 20 46 -25 21 78 100 -54 97 -4 -11 -55 -12 45 92 62 65 0 -84 -83 16 15 20 -72 -37 19 14 86 -21 55 -66 -54 35 66 15 39 20 77 53 50 -47 -83 -21 -47 -80 52 33 -62 -62 24 -78 -27 -90 -87 57 -85 -50 -41 -14 27 90 -97 30 39 20 -57 18 -82 34 -93 -75 -20 90 33 70 -8 2 -56 28 -41 39 -14 +-91 53 -42 78 33 62 82 41 -60 50 98 -11 -26 -96 -48 24 -19 -78 0 22 14 50 18 -22 27 -56 55 -88 -25 -62 45 -92 -19 -63 45 53 -40 -32 68 -24 59 14 -35 57 73 -49 -14 -20 -81 -9 -53 -52 93 -96 -71 -46 -78 38 60 -26 -10 19 -12 10 35 -85 35 -34 77 77 60 -94 13 -91 73 -45 61 7 -69 83 -34 -97 23 96 77 94 -94 -43 26 -53 -96 -90 47 -33 -10 68 -22 9 98 -46 +841814 610824 -294015 -340024 161441 55356 196412 192396 111821 -852793 -795714 384643 477988 -560410 -474305 2504 -965957 214276 479795 -765034 -719619 935698 823607 -441335 616374 785078 -771608 774974 291922 736895 -714896 -869607 886475 730924 -35250 236880 -578918 -776928 -349599 -691568 172665 209605 745142 -642306 577732 -416771 -762600 -684224 -932099 354596 +-72 -14 -11 11 -94 88 25 89 -31 -87 -32 63 -36 -15 -85 33 -61 -37 -74 89 74 -66 -87 69 -36 78 -18 -70 -34 69 -98 75 37 -86 -35 43 2 -98 16 -100 -30 -47 89 -29 84 -74 10 -17 9 -14 27 -18 56 19 -14 88 -27 -91 -86 -72 100 75 -25 32 -57 -40 -70 -4 16 -57 -63 -27 27 42 -31 -36 -96 64 16 47 21 -76 65 89 -72 24 -46 -20 -88 -3 61 88 64 -97 -38 52 65 23 -54 30 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/55.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/55.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/55.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/57 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/57 new file mode 100644 index 0000000..010f434 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/57 @@ -0,0 +1,53 @@ +50 100 +7 45 66 11 45 31 93 86 83 57 31 38 13 60 14 89 64 52 0 37 92 28 15 42 99 50 4 78 38 76 61 99 56 31 67 26 23 83 71 90 15 90 7 49 89 72 22 18 83 52 8 1 29 78 81 31 60 58 93 58 33 52 95 92 48 82 65 97 58 87 14 13 27 6 26 12 83 14 53 8 50 3 95 87 67 21 60 99 75 75 91 50 76 51 84 82 85 67 83 92 +47 7 -80 -32 99 -29 -40 -34 -43 -85 -8 -46 -11 80 -26 -19 -88 -23 -26 -99 34 -90 -5 34 75 13 -81 3 63 10 -40 10 78 -23 -99 66 -71 -65 -87 -82 5 90 77 31 34 -5 60 -29 37 -71 91 -17 13 92 -39 44 -57 39 20 71 23 -79 -37 84 -83 75 -48 -37 -41 -76 -27 30 -22 -99 -67 55 -59 71 -8 84 16 -87 81 -59 -57 -5 -99 -38 8 -34 52 14 12 64 -72 84 47 91 -9 5 +-21 -81 -53 -13 -63 -18 -23 56 12 86 -63 24 11 -2 -52 28 100 -64 -5 42 -29 32 50 -45 99 -91 43 42 74 -68 -29 -89 47 -59 -40 -65 -53 -22 -83 -82 68 -82 -67 79 -1 32 26 66 75 12 1 -73 -41 96 17 -33 21 76 -1 88 -51 12 45 94 -7 29 85 37 98 -10 68 -60 -45 46 -86 -7 -22 43 41 -63 -7 -86 -19 54 48 -34 55 -32 51 -81 -2 -38 18 -56 88 -6 17 -36 -68 -42 +55 -48 -95 -13 69 4 -83 -82 -52 -59 -69 37 -13 19 -36 -37 -43 17 76 -94 -45 -79 45 -100 72 23 -97 59 98 12 67 -61 -49 -91 52 -15 26 27 -64 -69 4 -61 -97 26 23 -71 86 -18 -35 47 -57 15 28 -99 36 61 -34 -71 -43 -9 5 35 -65 44 -1 88 39 -38 -77 22 22 44 4 34 31 -75 17 -50 58 -43 64 -20 0 -87 -46 80 68 -10 8 72 89 63 -51 -9 18 62 65 32 -76 -94 +-80 -56 -50 -45 -53 -84 -79 30 -27 55 48 -79 88 -31 -7 21 -18 85 89 91 38 34 70 24 28 -7 20 49 -50 -88 -94 -82 70 -17 -22 27 38 -85 88 11 37 -62 13 90 -43 -65 -59 -28 -45 -72 69 -74 100 77 94 -90 -34 -86 -11 -78 72 52 -83 -21 -48 -22 78 -24 93 -25 -29 72 -31 -3 67 87 -34 27 -2 46 69 1 13 -50 38 91 -99 12 22 60 39 -96 61 -7 73 70 -53 42 -41 -67 +-58 82 -30 -62 -87 -79 -24 4 67 -53 -95 -38 -64 82 47 73 -65 50 -66 -84 90 -41 83 -14 51 -85 -9 -27 35 -17 37 26 -67 -52 -86 26 9 63 34 46 68 -68 17 -48 10 -5 -87 -48 40 16 -62 -5 -4 -19 91 -94 -7 89 43 59 -77 73 38 19 86 68 45 41 18 -84 76 43 30 12 -32 18 -60 36 -56 100 -34 5 67 1 -11 34 43 -97 -17 0 -12 97 18 81 -39 90 34 99 -74 34 +52 -58 16 62 -17 25 40 16 -98 -59 79 -65 91 86 -11 97 47 -37 -32 56 -91 -75 39 -51 31 76 72 86 -53 -44 -29 -55 -67 -29 -80 61 54 18 30 -26 17 -77 40 -73 11 -45 -16 -31 77 -97 35 73 -57 -61 -74 -69 -57 46 -28 100 -92 -57 10 -33 42 -66 -65 -43 68 96 88 -7 -77 -96 -86 60 -73 -79 87 12 -62 98 -48 74 -25 -23 -62 62 -77 -79 58 -100 -2 75 2 -3 -90 49 -29 44 +-80 90 -25 27 55 -87 23 11 -82 94 -10 83 -93 20 5 9 -3 -21 67 -72 -22 -24 76 -4 59 90 -30 69 53 -53 -86 2 66 -36 33 36 46 62 -93 13 30 7 35 72 -65 -66 36 12 -30 -9 4 39 -89 38 72 -36 67 25 76 42 -44 -5 -92 100 97 -1 56 -54 33 -31 -36 -39 -30 43 43 73 72 -51 40 79 72 26 -87 69 79 1 -69 19 6 6 -64 -5 90 -70 95 61 73 33 -55 -45 +-87 -92 -53 -15 81 47 -100 -40 -10 -9 42 27 75 43 77 16 94 81 44 -81 36 9 40 -54 -36 -79 82 -86 -58 -15 52 0 89 96 62 -22 -57 -41 76 54 -29 -54 0 44 -68 77 -93 52 16 -94 1 99 99 23 -48 73 26 97 -20 97 -26 -12 -13 35 6 36 -100 100 -79 70 -87 -70 -80 74 47 -91 46 -94 16 -22 18 -87 -46 -82 67 -39 -55 -43 -50 -66 -96 29 22 39 76 34 69 -34 -67 -56 +-81 11 44 95 -41 -41 -49 77 64 94 50 -58 -86 -93 44 47 -54 44 58 -50 7 5 19 -31 45 1 -41 27 -32 30 -96 58 -58 -76 -38 -36 51 36 76 83 59 -85 -45 6 90 -66 75 -88 -10 -32 44 -1 -41 -70 78 -79 -17 20 11 68 -79 -20 73 42 -84 25 48 -78 67 -44 52 46 -64 88 99 0 88 87 -39 93 80 10 -78 2 16 -67 -63 -53 40 -17 50 86 -3 -100 -14 -95 -90 16 61 92 +-87 23 -52 -89 -65 86 68 60 -97 31 24 -55 30 2 33 -46 -77 31 -19 70 -31 97 92 7 19 -63 -18 12 22 98 -77 73 -82 -99 -19 -39 -89 -64 85 -45 -10 9 -83 74 -67 16 -100 51 77 82 -7 -4 -26 37 -98 6 -26 86 -61 41 6 -1 -76 -21 -12 -67 -75 -55 -45 -31 13 -75 5 -49 79 13 3 -82 -97 -16 99 -44 -79 26 -49 63 -85 -41 -74 62 28 99 78 41 -31 -3 -64 -14 -17 84 +69 -55 -38 -9 -94 60 14 4 -46 3 77 -21 -11 27 67 -29 -44 -18 64 -76 73 75 16 -87 -22 -14 -59 -79 -69 37 56 -19 -87 28 58 76 -82 -12 73 -97 6 38 -39 72 94 -98 56 48 -64 -78 -83 22 -69 -91 84 62 -63 13 -34 57 77 -98 83 94 25 94 -71 10 82 -86 10 -91 59 -62 5 42 -62 -27 66 -95 27 61 -98 45 68 39 72 54 -18 0 64 25 -66 -40 -31 55 -46 16 23 -65 +62 28 -26 66 50 -29 94 52 -15 18 61 -35 -73 86 -4 -25 23 45 -23 -82 79 -84 96 -11 86 72 90 -95 38 41 -76 76 84 69 -61 -27 20 95 89 -13 -20 -71 60 27 -16 -13 -66 61 -80 -90 -60 50 -91 47 33 -94 40 60 52 56 -97 -44 -69 48 -98 78 74 -51 -88 -29 21 11 -56 -15 -21 25 55 -22 51 -31 9 -36 -41 -94 31 33 -62 43 -65 -54 -37 55 -14 -97 -55 -50 7 -57 11 -34 +49 100 95 67 -59 63 10 45 100 26 -10 23 -16 -21 30 24 77 -79 -50 29 -62 23 38 -59 7 89 51 12 93 69 -41 14 33 86 91 20 -75 94 62 -4 12 11 36 67 93 3 77 24 13 -59 -3 69 56 -34 -10 -83 62 79 47 38 -91 -69 80 -52 -75 -9 -21 -50 -34 -53 63 66 -78 -5 12 -4 41 -1 -12 -89 51 11 -81 11 -87 -24 60 -51 83 76 40 100 -27 -41 12 -77 -68 62 71 -21 +-29 19 -54 96 89 41 75 4 61 -40 21 -3 -36 4 -41 -13 -8 -47 21 -80 43 53 -14 69 -53 55 38 50 -87 -7 -43 20 -36 23 95 60 65 -83 1 -72 -43 -11 -44 37 16 -31 -100 -99 66 3 67 68 57 57 97 -6 90 60 -51 88 -65 -5 -99 77 -52 -26 100 47 -97 -12 -62 -65 88 -75 43 90 84 61 -20 3 69 21 -23 -69 63 -54 -6 20 78 -10 -82 -34 40 92 -80 -71 -2 41 83 25 +-64 48 -64 -55 -30 13 -65 -34 -98 19 -4 40 -97 33 -29 47 49 -78 55 55 92 -87 54 -54 66 6 11 -12 -20 -61 -39 -83 -87 -26 -42 -33 49 84 54 -26 -20 -12 46 18 -84 73 63 -20 -38 -76 -1 -22 -27 71 -40 20 53 90 91 73 -33 -54 30 25 75 -48 99 -70 95 100 83 10 98 84 -97 -7 -4 84 72 -62 53 13 -23 -64 0 -56 -67 -63 -32 99 15 30 -16 -14 -6 -9 97 -60 -19 79 +78 -83 70 -34 -38 74 -29 -30 -65 -44 -7 40 -78 93 93 -25 -96 -11 -19 24 -94 9 58 -78 -60 52 57 -91 -69 57 64 -4 31 8 9 1 50 -42 38 -50 64 -56 21 87 75 -69 -48 95 11 13 28 63 -96 -69 -39 -42 -54 6 25 -97 87 -94 -20 9 -56 78 33 -84 -7 -83 -54 1 -100 65 84 -2 -73 52 54 87 -29 99 -49 -22 98 39 81 -55 -7 -7 26 -29 32 55 77 75 28 66 76 20 +-40 70 -55 -15 -22 -25 -76 94 34 86 -82 34 -94 -81 -54 54 -52 -54 100 30 39 42 -52 4 83 -57 63 -79 99 -53 -69 79 -21 87 -93 20 74 14 78 93 -26 51 71 63 -63 20 84 -48 18 21 -91 -84 -43 77 32 92 -47 79 -57 -47 -16 -20 12 99 9 -81 -70 -79 -48 86 10 -44 58 72 -67 -29 62 -99 -79 -71 8 24 33 -32 26 31 -9 2 29 -70 55 19 -30 -40 -99 -82 99 -59 11 94 +-66 96 -89 53 21 -61 88 74 -85 -89 36 -70 43 -34 -100 -15 91 -88 85 -97 -8 -43 82 -85 -37 -89 -9 -1 -83 -57 -97 96 74 40 50 10 -22 -2 91 47 -24 16 -78 -55 46 -18 57 -50 95 -85 10 -22 76 -25 -69 37 82 -21 -86 57 -41 -12 21 62 -36 80 18 -7 -41 -33 -5 -50 100 -22 -96 -4 88 94 46 88 53 -61 -36 -94 -86 -86 89 -90 100 28 -29 37 -20 13 -5 -48 7 0 6 42 +74 -11 -52 18 39 65 -44 51 -73 -20 -42 25 -83 93 41 98 -37 -50 -20 -51 30 28 -23 -15 88 -96 -85 -27 5 16 63 -82 -13 16 -42 17 -79 -7 95 77 -58 51 -91 -61 67 -100 32 57 -83 -51 -10 -89 31 34 -55 13 -76 34 82 -47 -13 42 28 -70 -26 -37 72 -53 -20 97 39 87 -89 22 40 80 -93 -58 89 28 -43 -13 -94 -6 47 15 -95 -46 -90 -5 27 -45 -56 87 76 53 -1 71 59 -60 +15 -43 67 32 -96 -87 58 24 52 -26 -87 5 15 85 -17 84 -91 -8 89 89 -57 52 -42 94 43 -8 -55 -68 -31 86 27 69 -39 85 63 -9 55 6 -14 -54 31 1 -95 -95 -98 -40 -33 -92 -17 -16 -9 -36 -16 16 40 2 98 -66 90 -11 68 -95 16 -64 -82 -8 -41 -58 62 99 53 -94 59 19 -66 -33 -32 -49 7 1 -42 30 47 37 -93 80 54 19 -36 -4 -7 29 96 -61 -70 -50 -99 5 23 -55 +99 -96 -40 3 36 -82 -94 68 61 60 6 41 62 -4 -26 -22 -92 -20 -39 65 -87 13 13 90 99 -23 38 -58 87 1 33 -49 -47 -73 41 -49 100 63 -99 56 -79 -19 71 6 -18 92 16 22 -34 99 -94 14 54 32 30 62 -59 -37 -55 -90 -5 36 -17 -86 100 -36 81 -72 64 59 -6 -23 -60 18 -40 -4 19 -19 -82 -86 32 -94 -84 40 91 -84 -96 23 20 84 -40 -25 -25 -33 42 -74 1 42 88 10 +-65 20 84 -74 -15 43 -84 54 -77 -60 -89 52 -38 34 -64 -83 -9 -79 61 -78 56 -4 51 33 -93 90 48 -43 -9 12 59 -25 86 52 28 6 62 -30 -80 -53 -43 85 0 -15 15 49 73 -91 -71 7 -62 52 65 87 71 -50 -56 -46 56 -97 -82 -52 -90 86 -68 74 -20 41 67 38 -7 -49 48 33 -42 51 42 88 -89 -91 -87 -98 -69 -57 -39 -16 -65 56 -27 -63 15 70 39 -72 28 77 29 -55 69 -50 +33 45 -11 74 8 52 -68 -14 -44 -1 -20 -16 66 -62 -19 -74 -51 21 30 -3 99 16 -70 -1 21 20 9 -100 99 -99 -85 -97 35 -66 -45 -5 27 3 70 46 -43 -91 -79 31 71 -14 26 -13 -19 -75 0 89 -31 9 -66 23 53 -24 -44 71 -33 86 28 -1 62 51 63 81 -92 -47 39 -90 58 11 -2 -39 -40 13 -17 95 88 -38 71 -33 -58 38 -46 -99 82 -97 -43 -95 86 -22 -39 -43 -77 62 -45 -63 +73 -93 -9 83 -48 -95 -74 20 -5 -46 -39 -88 -23 83 -51 48 27 2 -7 -19 -59 -46 29 4 50 90 89 94 -60 24 45 -90 -53 -67 46 -35 4 -42 66 99 24 -69 4 -29 50 -88 -38 36 -87 75 -57 32 -57 96 74 -24 -95 -48 33 43 -86 -30 67 53 70 82 -34 -34 -75 -16 47 -73 97 -12 12 -37 33 55 -36 51 -81 76 76 -89 -25 47 -43 -18 -89 26 -76 -2 79 -92 -81 35 35 -57 -21 38 +26 82 -83 97 9 20 54 2 14 -27 64 29 -34 97 89 -10 -51 -86 22 -76 -91 0 -38 94 -47 -23 -21 1 84 16 -9 -28 33 -13 39 58 -44 -26 -75 -67 86 5 -55 79 -65 11 88 -71 -34 81 32 -98 -89 91 -30 -14 -65 5 -74 -84 -31 90 -85 6 -22 -81 -63 -9 -62 -15 19 -50 86 -25 88 -78 30 -8 -75 -35 77 11 50 14 -79 -23 40 -29 -3 -75 97 -86 24 -42 -19 -82 -75 -6 -58 9 +-72 -75 -2 54 -14 10 39 17 73 8 58 33 -45 -52 68 47 -44 63 21 -21 -95 52 49 3 -5 38 45 -95 76 83 -25 -7 14 -61 -46 67 -30 -97 -98 -97 23 0 32 -21 -1 -62 93 -2 -76 -3 86 6 60 -46 -46 -81 -54 92 64 19 -21 69 -5 87 -46 -86 95 39 82 70 55 -56 93 -85 26 -26 16 -40 49 98 67 -50 -49 15 0 -2 70 -64 -92 39 -54 72 -98 60 14 7 80 77 59 -75 +-36 51 -96 9 -23 -21 -1 -6 -11 -41 67 65 93 -98 29 65 60 58 19 46 -10 38 -19 -12 -18 40 13 66 -59 47 -57 21 76 -97 -90 99 -47 -43 45 16 70 100 -24 -2 59 -27 -88 38 -44 -87 -43 -26 19 34 10 75 98 -84 2 38 74 -23 -62 12 38 71 -46 19 27 -82 -24 -39 -93 74 -89 -6 22 -48 17 -38 86 -93 9 -60 61 6 -90 -84 -84 -44 -73 -88 -74 42 84 67 11 -71 -16 67 +-7 -65 -29 -20 -15 -2 37 -28 52 -10 52 -19 -27 5 21 -25 -46 -97 7 -8 -93 1 -88 87 -8 -40 -37 98 -87 52 34 43 -6 59 -33 -45 8 -35 92 -20 -30 17 -5 54 30 -17 -61 -35 -61 -26 76 71 -58 -66 -16 45 -97 55 -14 -8 -48 41 53 -1 68 82 -82 30 -77 -9 -23 86 4 23 -42 -59 -58 -20 74 66 -76 20 59 -37 100 -34 -78 41 45 60 57 -34 31 -74 61 62 43 24 28 -59 +49 60 39 -8 -39 8 47 22 42 22 -34 79 -11 13 33 53 -94 -40 21 -31 -88 -63 -52 28 -80 -89 94 -3 -48 -90 -79 -10 34 -12 -29 -85 69 9 -63 -11 56 -62 62 77 -23 -45 87 -63 71 30 -21 8 91 27 -86 -59 -23 40 -36 42 38 -81 10 -36 99 -24 77 39 -59 -94 -27 -79 15 -1 64 -99 -8 91 56 70 -2 75 -72 3 72 -22 -31 -93 -24 46 -98 8 -45 96 59 -64 -24 -42 69 57 +-71 85 -21 -70 -57 -14 51 -34 3 26 -19 -65 -22 20 0 42 95 34 -91 41 -81 -40 51 -100 -15 37 -16 -65 -54 76 -11 -39 70 11 -48 88 49 -74 64 39 4 -75 -65 90 38 -11 -25 -16 33 19 -87 -42 55 53 -84 35 -99 23 6 -96 91 -46 93 -52 -69 54 30 80 4 -24 58 -78 3 100 -4 -86 -1 5 40 70 89 -76 -24 -27 18 -52 -95 46 81 34 -90 5 -15 70 -86 -81 -55 71 71 6 +25 -15 81 -89 -33 -14 27 44 33 -77 85 -40 71 -78 66 43 96 56 9 83 40 -57 94 39 -7 88 32 -99 44 96 14 -8 14 20 -38 89 -15 -28 73 60 40 47 63 -87 -99 -33 45 51 -72 70 83 90 48 -71 -66 -6 -55 -85 99 -16 22 -16 15 -76 -2 46 -95 -52 66 -31 46 -45 -13 51 97 83 -91 -25 20 -30 -94 65 64 89 76 75 -58 -49 -26 8 -61 100 40 16 52 80 -14 -67 11 25 +87 44 61 -5 22 52 -83 57 -28 -17 -76 -73 67 11 60 41 79 40 81 15 -72 -25 31 -100 58 3 93 21 -2 -22 -46 6 -15 -97 -15 87 -19 28 -82 -57 65 20 -97 -88 96 -46 -62 45 29 -72 -28 11 17 -69 53 4 85 27 36 7 -72 95 81 -4 44 -5 61 80 -40 49 3 -98 78 -77 10 -57 -86 91 -26 40 -72 -27 5 80 15 14 -74 80 33 10 2 -11 43 -52 38 -50 71 1 -59 75 +86 -50 99 -60 95 78 0 -29 -76 -85 -5 -39 22 -12 -45 37 72 -58 15 -97 12 18 75 -26 -47 -10 83 -11 -61 95 26 65 -25 -61 68 98 -78 -57 -80 9 -100 57 26 31 -42 13 9 -51 75 -99 90 87 -19 67 -42 7 -27 -2 31 27 12 -92 -65 100 67 49 66 -34 -65 30 41 92 99 -14 -59 -20 -40 85 39 -88 97 -58 -54 -5 14 -13 -12 83 -66 24 76 -24 47 -78 -97 -35 -77 -71 -96 -12 +18 36 26 23 -62 42 -53 97 -5 -85 41 90 48 45 11 -94 -84 -53 87 -73 -20 48 73 53 1 13 -99 -57 -53 -80 -96 -23 -84 40 30 24 50 50 100 -36 -36 -74 6 -51 36 9 -10 -73 -27 -27 51 81 -34 64 96 80 -100 19 -67 72 -11 78 97 90 20 -73 -13 -62 61 -11 -29 -54 -41 -35 89 -58 31 33 -84 84 -23 13 -35 -63 -82 22 -41 -76 -62 16 -30 40 -38 32 -96 -47 31 -63 -86 69 +-10 93 -17 64 8 -25 37 -99 -42 17 -66 -80 69 48 -79 95 74 -77 -9 39 -49 -5 -33 -36 -68 26 41 -25 -44 9 10 50 46 54 -43 38 -50 53 -73 -67 -42 47 10 11 -48 38 -24 79 -33 -47 -60 87 -76 -40 29 52 19 -57 -52 -87 9 -61 78 -12 52 -54 -62 57 97 -51 -87 -70 -13 -82 31 -55 65 50 56 -48 94 11 82 22 -31 -44 -34 30 -72 49 -37 -34 92 -61 -17 58 9 -93 84 9 +-92 -28 41 21 -37 83 98 -28 -85 40 0 35 56 -67 -59 100 -18 61 -52 23 7 -89 -12 10 -11 -20 91 72 66 -73 44 62 29 99 56 -78 35 23 -57 -1 13 -13 -44 -83 61 -15 43 -7 61 -100 -28 50 49 32 -28 -2 -67 -7 -70 13 9 92 -31 1 70 32 91 -21 -40 2 59 3 -37 -48 86 -29 -19 68 -91 -27 99 -98 26 -16 6 -28 44 39 -15 43 3 75 -77 82 52 -22 -70 35 7 1 +88 -82 19 -63 66 -88 -32 3 -36 52 -17 53 -81 -23 51 67 -49 75 -24 -93 39 17 -46 76 28 -36 -57 39 25 73 -86 40 -74 66 -40 84 96 -17 23 -25 -91 49 -91 -64 81 49 62 75 -85 84 -59 82 -36 -25 -33 63 -65 -60 -61 28 -89 83 34 41 38 -98 -68 95 -16 24 -76 -57 -93 -100 -84 0 68 -14 -6 -28 3 -5 53 73 26 -17 29 -40 85 57 -76 -70 -19 -73 -54 9 -11 -72 -61 -21 +96 14 62 -54 -63 39 -82 76 -61 89 -53 -2 -7 -12 15 19 -40 -19 -67 -31 -15 18 -22 -83 76 -45 49 -88 41 -64 -68 -58 43 48 -57 29 41 71 -98 -52 83 30 10 -77 48 75 50 -95 -94 -15 -70 97 -11 -23 -71 -75 -58 -82 -37 1 83 -52 13 -24 -78 -100 88 -88 4 -83 24 99 48 -37 -58 -77 -61 32 -70 -4 53 37 20 -83 70 -56 -99 -68 5 -64 -22 15 81 17 -36 -13 -55 -64 22 68 +-3 14 -25 -9 10 -57 -55 -18 -91 -32 -99 -36 20 -4 -55 -5 -19 -40 -72 57 67 37 -72 -39 56 11 59 52 61 -95 87 41 -58 61 -31 76 -25 49 -29 -32 52 71 -28 90 28 -24 -13 5 -97 -85 32 20 -36 27 -13 -54 -57 -91 14 -72 76 -55 62 -66 -54 -12 -97 17 -29 43 -42 80 -95 80 26 96 -35 96 29 91 -15 44 87 -45 55 47 41 27 -18 29 -70 -42 62 -34 95 -95 70 95 50 81 +-30 29 11 36 59 100 48 -83 90 85 -19 99 -22 72 -28 60 90 -24 71 -60 10 -78 32 79 88 12 -14 -72 -93 -82 77 49 -57 4 90 83 0 -39 24 72 62 69 -59 -49 -83 -1 12 -34 -69 -93 -94 -9 -8 -26 26 69 68 60 47 28 68 -80 -42 51 -5 49 -26 -10 83 50 56 34 62 -64 79 -57 -4 19 -69 -22 20 -41 -97 -65 -93 -90 77 24 58 -38 -91 -13 59 41 -41 33 1 -7 -46 -70 +-59 95 21 5 -94 -38 2 -51 76 30 -97 35 52 -41 57 43 -41 29 -5 -63 57 -56 41 -61 -61 94 31 -69 -67 -6 23 84 43 -6 80 17 -21 -37 87 83 -70 -33 37 86 30 -49 -88 85 100 100 -90 -10 -27 55 90 -92 -10 87 3 -95 -36 -59 97 -48 42 15 18 -8 -42 -42 -46 -5 -59 55 94 55 -14 -11 97 59 -96 -41 -79 17 68 18 -35 -3 -1 -100 -55 -9 75 -34 -38 -19 -5 27 -85 60 +13 36 61 94 55 -77 -59 -9 -61 8 41 -53 -38 -6 -76 86 -8 36 -82 -90 69 53 3 5 19 -7 -99 -68 20 -83 -69 76 -5 81 -35 81 16 -47 -56 -31 -18 21 -77 17 85 24 54 48 -14 -56 -10 -99 -2 86 14 57 73 83 -4 -5 84 86 35 -19 -61 19 -48 82 8 74 89 97 100 -10 -97 -22 -73 -26 3 -40 46 73 98 -7 93 -37 8 40 -37 42 -78 47 71 27 -4 32 -50 -58 -32 21 +-94 -79 70 52 -82 6 27 89 47 -80 0 -3 80 -99 -81 81 13 4 -92 -17 -23 61 64 78 55 -19 36 -80 -89 -35 55 91 98 -69 83 82 68 -56 -75 73 30 -100 -45 79 -100 99 53 62 76 12 3 -23 26 -98 -28 58 -90 60 56 -84 17 79 -84 -37 -97 51 -65 -19 -12 59 31 98 -11 -58 42 75 32 66 5 35 82 23 -73 -60 -55 87 15 -43 -35 28 -35 1 -45 -49 24 98 9 19 -88 98 +3 -23 91 -52 -73 -33 23 -26 -32 -34 -63 11 -67 98 68 57 -53 62 -51 -1 -70 -80 -39 -27 -89 -31 -82 34 -79 -100 23 -55 -11 -19 43 16 -5 -21 16 -78 71 -42 -28 -1 -72 -23 -82 56 25 -25 31 -15 64 -35 -14 -57 93 50 -51 -30 66 96 72 -98 16 -90 -59 -12 -77 3 88 -75 37 -44 -77 -64 -87 19 -87 58 -94 -89 -46 -57 32 6 68 -73 80 -81 67 70 3 -93 -72 -34 -25 88 47 75 +40 -34 -73 -96 -41 27 16 59 -93 -58 25 -26 11 -55 -28 16 98 -10 48 56 -97 11 -49 -85 64 -97 56 -94 -70 -94 -33 59 -64 -52 34 -39 7 -80 -49 -39 -46 37 -92 37 -84 46 92 -8 -67 -95 -71 -74 -71 9 -15 -60 -22 7 38 30 16 -86 80 -16 -100 70 24 -30 50 -80 -56 39 -22 -12 35 -71 -95 43 -56 -94 51 -69 -35 26 91 -92 -25 40 -24 76 5 56 19 -56 -66 -29 23 -17 54 82 +23 16 23 11 -79 15 -2 92 97 -9 -91 -62 -95 -69 96 -49 -60 23 15 -64 24 11 67 -60 11 61 -80 17 -11 79 43 -78 17 15 -99 69 18 -17 19 4 -75 -77 50 23 -73 -99 -71 35 51 -100 -61 -13 91 -12 3 56 5 26 -52 71 -4 -95 -16 -32 -20 -47 -78 -34 15 -18 -23 -20 -86 5 -76 -90 -48 -80 -67 8 -27 -50 75 -94 -2 -12 -90 13 42 55 -61 26 86 -59 -23 80 94 46 -13 51 +-17 97 35 -56 -11 77 82 -62 -93 -71 -41 18 22 98 -19 -41 -7 -39 -75 0 81 100 84 29 51 82 -18 -69 39 80 -35 -29 27 27 7 7 38 36 16 7 -75 32 -79 70 -98 -9 -7 -51 45 -84 -86 66 7 19 48 11 49 -85 -19 16 -95 -94 -18 18 11 -78 70 80 -56 29 93 -87 -96 80 0 -40 5 48 -76 25 23 58 81 -56 57 -60 48 84 53 26 99 89 53 -26 18 72 1 -17 -32 -86 +0 -7 99 -85 -99 -93 46 36 -1 79 66 79 59 81 -32 82 -66 28 38 -69 23 -12 -46 -47 28 51 -62 30 83 -65 -38 83 -92 24 72 73 29 36 38 61 7 -63 7 89 -41 18 -68 -33 -23 -24 54 51 45 50 43 -57 -69 2 -56 37 -60 -52 -25 -79 -46 -26 18 26 -33 -32 50 6 41 61 -81 85 11 5 -97 -26 -39 64 84 -53 95 -86 -28 -77 -11 -27 -23 -66 -92 67 22 59 -79 71 84 -44 +68 -23 -50 -8 92 62 20 28 54 57 99 60 50 -87 48 92 57 -8 85 -89 -31 -2 -49 69 92 -32 -51 -9 55 -76 73 -80 -20 18 -98 -66 71 -26 -63 -93 92 -99 43 -18 67 9 -42 -70 81 89 -70 -67 16 -70 14 -42 5 -94 27 -33 59 -79 -81 -3 -30 2 -23 97 19 63 60 61 -61 -31 -55 93 31 -8 -7 -99 87 20 23 43 85 35 -69 66 56 33 -30 -85 98 -67 9 13 53 21 68 28 +237654 -9397 18997 -18868 -826 5545 -20211 56486 -4611 1464 -34990 -5479 -11851 33456 13209 28633 769 19543 -87 -32117 -13695 -29087 -48802 -12978 -52194 -21935 17424 -2281 50 -2338 -11547 72518 33788 -5280 -33196 -18300 28018 -10834 -29164 14916 17523 -34472 62499 5141 -40159 -69127 -42810 18242 -11205 42128 +-71 -75 75 39 -63 3 14 -78 11 62 -16 -15 -16 -31 10 -93 -68 77 50 -27 -12 -95 96 -46 86 77 -35 -99 -21 -90 -85 -2 51 98 71 -91 14 52 60 -21 7 -38 -71 -47 -37 -68 -93 14 -78 56 -33 -32 40 -62 -89 85 72 -64 16 14 -69 -44 30 80 -10 65 89 27 -61 59 52 95 -12 74 -76 -66 52 14 -17 -52 -79 -67 -57 -92 -4 80 -69 18 20 86 28 95 -8 -98 -87 41 -42 24 66 -89 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/57.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/57.a new file mode 100644 index 0000000..722d7b3 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/57.a @@ -0,0 +1,2 @@ +Bounded solution +0.000000000000000000 0.000000000000000000 37.494217136472507000 0.000000000000000000 0.000000000000000000 211.285579121390550000 162.557646416048020000 0.000000000000000000 0.000000000000000000 520.718237384810550000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 82.681385154927568000 0.000000000000000000 0.000000000000000000 412.009481984876460000 0.000000000000000000 11.458784049469948000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 143.256431926484790000 70.477267168304053000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 345.507712101587800000 0.000000000000000000 0.000000000000000000 0.000000000000000000 179.889281762344150000 0.000000000000000000 0.000000000000000000 0.000000000000000000 36.888876075954549000 216.448869478838050000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 503.440927213623920000 565.300625071891660000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 852.133274314137110000 540.090116482175860000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 21.264033991432409000 0.000000000000000000 136.522336416610050000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 525.494747985582310000 0.000000000000000000 146.773425604869090000 0.000000000000000000 0.000000000000000000 0.000000000000000000 286.034998527348650000 0.000000000000000000 0.528123181079178770 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 364.456991224499290000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 82.228365575449985000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 0.000000000000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/65 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/65 new file mode 100644 index 0000000..3c7e41a --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/65 @@ -0,0 +1,53 @@ +50 49 +77 51 10 32 8 27 90 -43 -52 -64 -47 -21 49 -49 -42 -80 28 50 -100 -95 9 18 77 5 91 -97 97 80 -98 5 -34 -71 55 -44 48 39 86 70 10 -21 93 64 -70 65 -61 -44 78 -69 96 +11 -41 -90 -21 -62 -3 -31 -57 -78 92 -80 18 93 -19 34 88 -50 53 -53 91 19 -64 96 93 -29 -93 47 50 -38 -21 -81 -85 -60 64 94 -24 -36 100 -71 -68 -10 65 70 -15 42 6 88 -56 -88 +95 -4 -73 99 -97 73 -9 40 -69 66 29 73 -14 -71 -8 92 61 -39 -42 35 4 -71 -28 -96 99 -4 57 -47 -34 88 72 -83 -33 -1 15 6 -3 95 -81 70 -52 11 -56 -92 100 70 -69 -62 -74 +-87 26 4 33 52 19 80 76 22 88 89 62 -69 7 36 -62 58 -95 -97 11 69 -48 56 49 -15 65 -29 -95 -24 14 -73 48 -64 -16 -82 -80 -28 -11 89 33 -3 94 -57 -26 -72 -84 29 -59 66 +2 -52 57 43 -19 -32 2 -35 -52 -42 -32 3 9 -88 6 89 36 54 30 -28 -9 -7 10 40 5 50 -72 -59 35 27 69 25 15 -28 -44 90 -69 35 -56 51 -64 -57 -30 -26 63 97 -81 86 -88 +-94 -85 44 -45 66 -41 -21 42 34 87 71 92 19 31 -59 41 -55 59 87 -71 -18 22 31 -96 48 -77 1 -1 -32 -7 20 -85 17 15 25 -53 -10 88 -25 3 29 -28 18 -52 18 25 31 10 -28 +29 44 45 82 -15 33 99 -63 -7 -93 -84 -8 72 -68 73 -56 -26 -90 -31 96 -45 -53 -45 7 75 -23 28 88 -83 78 3 -81 -28 -8 -44 -95 9 69 -81 -41 98 35 -41 3 2 0 63 -39 -14 +99 -47 -17 48 94 62 -60 -89 -9 71 -84 -28 -78 25 -11 -61 -75 -72 61 40 96 -81 -32 -55 -8 -82 -17 -99 68 5 -90 68 -26 78 -13 -59 -80 26 49 99 -96 93 -15 -63 -41 53 -29 -96 75 +9 -97 -25 -70 -46 32 -81 89 95 -57 -23 -7 -69 35 -56 8 81 86 -32 1 -12 32 18 -74 36 -17 26 -5 9 -99 -58 -39 54 -14 34 -9 -35 71 -19 15 -60 -9 -13 -76 3 -22 36 78 -77 +39 35 76 -39 48 -17 54 18 48 30 98 71 95 68 -88 -46 38 65 53 67 45 -35 84 24 -51 93 0 0 -79 98 63 -72 -24 -47 14 80 -19 -60 91 -42 -12 -63 -4 -59 -54 70 77 49 -52 +-21 1 68 -61 43 6 -53 7 -14 95 -75 -28 -94 -32 51 -84 24 -47 -43 -88 -28 62 -26 52 -10 73 88 80 -9 99 -9 6 4 79 22 6 -65 -31 16 53 -46 4 -45 95 7 -86 55 -88 -23 +-97 70 -54 87 -54 69 -21 -13 17 -75 28 51 -78 79 -48 -53 -83 61 37 -89 18 -34 16 17 28 -39 -71 -93 48 -51 -36 -29 94 92 -54 32 -49 60 48 76 -89 98 74 14 -18 -54 -26 86 -95 +-41 -49 85 -27 -69 87 28 98 -11 -64 20 58 24 79 16 -8 -68 -74 -77 -96 57 80 -7 -30 -52 -55 98 92 67 -25 99 -46 -99 23 57 -91 73 -11 -70 -19 -3 -20 -12 65 21 88 -34 -11 78 +-84 74 -53 -93 49 52 -93 6 -61 -76 45 33 -94 92 -23 9 -91 48 -54 -89 97 17 94 -46 61 95 43 -61 51 25 77 -92 96 -22 38 84 79 -39 76 -1 33 -51 -6 35 49 87 48 51 -34 +-78 74 78 -65 -4 31 30 -17 75 -85 -84 -88 -22 -51 -37 -50 -39 80 -64 -41 100 -13 7 -61 -1 -10 67 5 44 -65 -21 -65 66 6 -80 47 65 -65 12 29 4 52 -85 7 -13 -30 -37 63 48 +-16 -26 -65 -15 -34 82 89 6 0 -88 -81 7 79 48 -48 -57 -63 0 92 -82 -24 -68 -65 16 -86 -48 -59 -43 31 -34 82 89 22 31 -40 -81 87 -13 67 90 23 86 -38 37 61 -29 93 64 -62 +59 -94 -19 28 -29 5 63 20 -12 56 -54 -96 29 -48 63 13 30 18 4 29 -92 -65 -74 -40 32 -44 1 42 -80 -83 -71 -27 -100 -51 24 8 45 76 -4 -93 49 -34 65 75 -7 99 -49 17 39 +-6 0 -59 31 -17 71 36 84 75 88 -54 -28 -90 32 -14 2 -68 -56 -80 22 40 3 -72 -97 -29 4 -56 -83 -10 79 20 45 58 49 -48 -41 -69 -66 -19 -82 84 -66 39 -54 -19 43 -99 -76 -33 +60 55 8 -100 81 -45 47 0 47 81 74 35 79 -51 53 46 -46 41 37 -76 -30 -85 -96 -27 8 -32 -35 -6 -53 -23 -8 2 -95 -81 84 30 0 -94 38 -94 -73 13 -62 61 -56 -70 -30 83 2 +46 51 23 -84 94 -50 16 -80 6 -100 -17 98 63 13 82 68 29 12 -59 93 -30 72 34 -38 -67 -70 -52 85 12 37 -98 17 42 -14 83 -83 -72 4 -67 -8 -17 99 -39 -96 17 -76 -3 40 93 +-61 -73 61 95 57 45 70 -87 -39 68 -67 -64 -72 -72 66 39 74 57 -71 -27 1 -84 31 58 -11 35 -64 32 -53 -91 68 -78 -18 1 -7 17 98 48 63 -62 65 57 -3 29 27 -13 76 -56 -46 +-57 -74 78 18 -67 87 -55 48 -56 43 85 -32 -63 22 7 -50 -80 60 47 34 38 80 -6 -43 -60 -79 -50 5 -52 -1 -50 -90 43 -78 -13 -43 81 -62 78 43 87 -11 -51 12 89 -96 -21 17 89 +-93 56 39 -83 17 53 -99 -29 6 -22 -66 20 -31 -15 -25 70 17 -87 -3 87 -84 -41 -68 -22 -54 -68 78 65 -43 82 27 -81 27 -78 -35 40 49 78 -89 42 -67 -29 -14 -36 -91 -40 98 53 20 +-10 -46 -81 -1 -28 53 -95 -10 82 82 79 82 -60 31 -26 28 90 11 49 -85 100 99 -95 20 -14 -99 97 67 -41 35 5 -5 87 77 79 44 70 -47 33 -24 -50 -45 25 57 1 -65 -36 -27 64 +56 -64 15 -98 65 -44 -46 -94 -1 36 15 -74 -61 13 -32 -28 93 -84 -21 -61 93 88 -8 -77 -83 -71 -97 -87 -7 -75 67 -12 -72 38 72 43 39 -67 68 99 93 -51 -3 -8 9 90 -68 -82 40 +-81 17 61 -39 99 -11 95 -5 -70 13 -28 -32 -15 18 84 41 -91 92 -6 -96 -58 1 73 -97 86 67 92 -96 58 -32 27 -46 90 59 60 -2 -16 59 21 -25 52 66 23 16 -57 -46 -96 11 2 +-2 82 48 -53 -55 79 91 -43 -79 -65 -1 -14 -12 -7 -93 62 -80 -75 -57 -83 76 27 -5 -87 6 -89 33 84 90 -8 16 -37 -82 87 2 -53 -77 58 -46 12 77 16 81 -87 -3 74 -11 -52 54 +-100 -8 98 96 -64 -25 -60 -79 -48 23 -87 23 21 -99 -60 -14 72 -20 16 55 -76 -98 27 90 -63 81 -55 -82 10 26 -27 -44 -62 13 41 -71 -60 -52 -36 -47 -33 -86 91 -72 16 40 -32 15 96 +30 -14 12 -49 -83 96 22 9 -27 38 -83 31 -44 76 -98 81 66 -21 81 97 62 46 40 -59 -64 47 -20 27 -93 -34 -92 -26 -92 99 94 -56 -68 30 -82 64 11 -90 -55 -79 11 -21 -55 26 29 +16 4 -71 84 11 63 21 70 78 -62 94 -40 -41 -97 -65 -28 -48 -81 -14 61 61 -58 17 -10 -33 -28 -42 -7 14 84 -80 2 -33 37 18 -1 -87 -70 34 17 60 62 -93 -10 14 -7 96 -10 18 +-60 23 -62 82 63 -55 -54 -25 -8 13 58 -33 77 64 -47 45 -13 -15 -47 -44 10 51 -38 92 -5 26 -60 24 -55 44 21 -50 94 -94 41 -69 99 -46 34 63 -31 5 48 -53 49 36 -19 -81 85 +-2 -92 -57 22 96 -97 -42 58 -85 -72 -71 53 -87 86 -93 -46 -75 82 52 -51 48 -92 -29 30 16 85 -5 89 44 -27 -12 -71 67 -1 -40 41 -64 -72 -44 -36 -34 -58 -61 8 77 -64 81 -100 47 +22 -63 -29 88 -85 36 52 -19 98 -89 -2 -15 -96 49 -50 -39 80 43 -84 38 56 97 44 -27 8 19 89 50 -9 -95 -22 -92 7 -25 76 -83 -56 99 -65 13 48 -72 20 52 -89 -45 98 48 -10 +21 -79 -80 -78 14 84 70 18 -2 24 -46 -62 48 78 21 62 6 -11 67 19 -94 -69 -96 18 -75 59 38 52 -72 86 36 -58 44 -14 -86 91 -38 55 -38 89 -9 -35 -91 34 -23 -86 99 -36 -93 +-60 -94 98 60 -66 22 78 42 -12 -94 42 -20 100 11 -7 -12 -79 88 -3 -69 -8 37 -100 48 -8 6 -6 -58 -61 23 -46 -86 -18 66 45 95 -88 18 -87 27 -65 -98 -48 -45 74 93 -99 52 31 +13 74 -69 -63 0 -83 86 41 9 -43 -90 -20 -15 45 86 -9 35 -4 71 -60 -95 23 12 -64 12 -44 -35 39 -78 57 -57 -90 -94 29 -46 -73 -8 -33 24 3 20 -63 -23 -28 17 -56 47 30 32 +-32 45 -55 -86 40 -97 42 -12 -32 2 -17 44 2 13 -47 58 59 -93 -46 3 45 -91 -9 -84 -82 38 31 -83 75 -65 5 72 87 90 99 5 39 93 44 -28 76 -21 -34 24 -73 -91 62 -97 23 +-27 35 94 -20 82 -30 -16 -47 -6 -3 92 14 -42 -56 -49 84 38 -48 57 67 81 -53 83 -34 56 -8 43 98 -9 13 -26 -47 -52 -14 67 87 -84 -62 -96 45 -68 94 -50 -27 -21 -33 -76 -42 -19 +-58 72 -2 -72 -50 -55 45 -78 58 32 -84 -68 -43 4 -18 -77 -88 -13 29 54 75 36 49 -53 -37 2 27 -94 96 -98 95 -97 59 -76 -8 -25 33 -52 2 52 -83 76 36 33 -75 -36 -93 56 34 +-43 41 98 80 39 77 27 86 92 51 -28 94 90 -48 -29 -59 -71 12 89 -48 32 18 -43 -60 -93 62 -6 -64 86 78 -71 -8 -24 63 37 -96 85 -64 39 -47 -39 -34 7 -14 -52 51 47 64 -19 +79 -95 -84 -89 -36 -96 -84 57 1 69 -83 28 3 29 -8 -19 -44 -17 87 -47 62 88 51 -29 -57 58 37 21 -1 -96 86 -98 44 -54 -85 76 -100 97 46 2 48 -58 -50 92 52 79 42 91 91 +-75 44 78 -74 -48 13 21 -75 98 83 -94 -9 -10 -99 1 -21 -45 -92 18 -90 90 -12 -70 77 -49 -48 4 48 -97 -16 -40 15 30 11 -77 -64 -67 4 -63 -99 5 -35 74 42 8 31 82 -56 16 +-5 -68 13 -70 63 -70 -11 25 -36 9 -55 84 21 -40 36 40 -67 -50 -29 58 -24 -17 95 42 89 96 5 -53 84 -88 64 23 -64 -2 60 -67 30 -39 14 -85 -64 -2 -94 5 -92 -26 -49 5 -40 +-19 99 -16 40 80 38 -87 -66 5 94 46 7 50 -3 35 41 -8 -43 -62 -13 -64 -77 -100 -15 -14 52 -32 24 35 -90 93 -1 -28 -28 -27 65 -46 -70 -36 -49 12 -73 -12 -64 -83 66 62 97 -63 +31 -8 59 30 93 -94 -10 50 76 -66 93 -15 -85 90 -51 43 -10 53 82 25 -70 -1 -82 -30 3 -72 -62 -78 31 -100 -27 75 56 -27 53 -28 53 -31 -88 75 -36 73 -59 -97 -4 67 -4 -36 -23 +-76 -27 -89 -33 61 12 66 48 -1 -31 -9 -25 62 61 77 -92 87 -8 -37 13 20 4 3 -57 -44 -31 79 42 -6 29 -100 47 97 61 81 -27 51 12 -86 24 -53 4 -25 32 -53 -38 -22 66 71 +82 88 54 -42 42 -38 -38 -13 58 -6 -34 -26 -29 -100 38 -50 -39 73 -67 -19 -68 -64 -72 61 34 75 46 -67 72 -69 84 35 27 17 -14 -22 94 29 -97 73 -68 67 33 89 38 -84 -23 84 65 +58 83 41 -66 21 -48 -43 33 9 -61 62 -48 45 94 -72 -88 31 51 -46 17 55 -47 39 -43 44 -27 -30 -95 -1 -45 -36 -59 -2 92 86 75 61 95 58 -79 -77 -11 90 78 -67 -10 88 -14 -42 +72 23 -32 25 -52 41 -39 53 -71 37 -69 3 8 -83 19 -32 -29 34 27 -17 -63 -40 -11 0 -96 14 18 -37 38 96 -74 65 70 -38 58 -42 35 -30 47 -9 10 4 52 47 44 11 75 81 2 +81 23 15 -79 -81 -55 -99 -84 -92 53 86 49 -14 -96 55 21 -37 45 28 4 -99 74 57 -4 3 -72 -17 -52 4 -60 93 -74 96 -42 -99 79 -86 -87 -80 -63 -12 65 84 -50 24 75 -33 -38 -34 +132641 375022 13361 -54188 435177 411903 -149905 -421796 -25450 441714 -380500 136872 -321397 -430381 479748 148984 303621 191343 -98975 479042 389259 -157910 -437493 -190514 8015 354564 -284001 -303846 -174639 -400603 -469832 -246171 -360692 -8816 -59986 14588 357982 35613 -430880 170742 46710 22361 -35481 -354019 368094 161639 94721 98141 144224 -402954 +-39 -31 -13 -94 13 -28 -22 44 -73 13 8 -48 65 -42 3 48 89 74 61 -85 87 53 97 -76 -35 92 -47 -57 -97 -23 -14 80 -41 33 56 8 -69 -51 -16 80 12 -40 -60 52 -81 -1 54 -18 -37 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/65.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/65.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/65.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/69 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/69 new file mode 100644 index 0000000..5818194 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/69 @@ -0,0 +1,6 @@ +3 3 +2 -1 2 +2 -3 1 +-1 1 -2 +4 -5 -1 +1 -1 1 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/69.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/69.a new file mode 100644 index 0000000..2f6a2d1 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/69.a @@ -0,0 +1,2 @@ +Bounded solution +0.000000000 2.800000000 3.4000000000 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/98 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/98 new file mode 100644 index 0000000..8c9bf17 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/98 @@ -0,0 +1,6 @@ +3 2 +-1 -1 +-2 1 +0 3 +-1 -1 2 +6 3 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/98.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/98.a new file mode 100644 index 0000000..3c62151 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/98.a @@ -0,0 +1 @@ +Infinity diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/99 b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/99 new file mode 100644 index 0000000..5bbe30f --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/99 @@ -0,0 +1,6 @@ +3 2 +-1 -1 +-2 1 +0 3 +-1 -1 2 +-6 -3 diff --git a/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/99.a b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/99.a new file mode 100644 index 0000000..27e0eed --- /dev/null +++ b/05-advanced_algorithms_and_complexity/02-linear_programming/03-ad_allocation/tests/99.a @@ -0,0 +1,2 @@ +Bounded solution +0.666666666666666667 0.333333333333333333 |