diff options
4 files changed, 130 insertions, 0 deletions
diff --git a/05-advanced_algorithms_and_complexity/03-np-completness/00_np-completeness.pdf b/05-advanced_algorithms_and_complexity/03-np-completness/00_np-completeness.pdf Binary files differnew file mode 100644 index 0000000..7a89a16 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/03-np-completness/00_np-completeness.pdf diff --git a/05-advanced_algorithms_and_complexity/03-np-completness/01-gsm_network/gsm_network.cpp b/05-advanced_algorithms_and_complexity/03-np-completness/01-gsm_network/gsm_network.cpp new file mode 100644 index 0000000..5eafa18 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/03-np-completness/01-gsm_network/gsm_network.cpp @@ -0,0 +1,45 @@ +#include <ios> +#include <iostream> +#include <vector> + +using namespace std; + +struct Edge { + int from; + int to; +}; + +struct ConvertGSMNetworkProblemToSat { + int numVertices; + vector<Edge> edges; + + ConvertGSMNetworkProblemToSat(int n, int m) : + numVertices(n), + edges(m) + { } + + void printEquisatisfiableSatFormula() { + // This solution prints a simple satisfiable formula + // and passes about half of the tests. + // Change this function to solve the problem. + cout << "3 2" << endl; + cout << "1 2 0" << endl; + cout << "-1 -2 0" << endl; + cout << "1 -2 0" << endl; + } +}; + +int main() { + ios::sync_with_stdio(false); + + int n, m; + cin >> n >> m; + ConvertGSMNetworkProblemToSat converter(n, m); + for (int i = 0; i < m; ++i) { + cin >> converter.edges[i].from >> converter.edges[i].to; + } + + converter.printEquisatisfiableSatFormula(); + + return 0; +} diff --git a/05-advanced_algorithms_and_complexity/03-np-completness/02-cleaning_apartment/cleaning_apartment.cpp b/05-advanced_algorithms_and_complexity/03-np-completness/02-cleaning_apartment/cleaning_apartment.cpp new file mode 100644 index 0000000..5690be7 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/03-np-completness/02-cleaning_apartment/cleaning_apartment.cpp @@ -0,0 +1,42 @@ +#include <bits/stdc++.h> +using namespace std; + +struct Edge { + int from; + int to; +}; + +struct ConvertHampathToSat { + int numVertices; + vector<Edge> edges; + + ConvertHampathToSat(int n, int m) : + numVertices(n), + edges(m) + { } + + void printEquisatisfiableSatFormula() { + // This solution prints a simple satisfiable formula + // and passes about half of the tests. + // Change this function to solve the problem. + cout << "3 2" << endl; + cout << "1 2 0" << endl; + cout << "-1 -2 0" << endl; + cout << "1 -2 0" << endl; + } +}; + +int main() { + ios::sync_with_stdio(false); + + int n, m; + cin >> n >> m; + ConvertHampathToSat converter(n, m); + for (int i = 0; i < m; ++i) { + cin >> converter.edges[i].from >> converter.edges[i].to; + } + + converter.printEquisatisfiableSatFormula(); + + return 0; +} diff --git a/05-advanced_algorithms_and_complexity/03-np-completness/03-budget_allocation/budget_allocation.cpp b/05-advanced_algorithms_and_complexity/03-np-completness/03-budget_allocation/budget_allocation.cpp new file mode 100644 index 0000000..d2bfc51 --- /dev/null +++ b/05-advanced_algorithms_and_complexity/03-np-completness/03-budget_allocation/budget_allocation.cpp @@ -0,0 +1,43 @@ +#include <ios> +#include <iostream> +#include <vector> + +using namespace std; + +struct ConvertILPToSat { + vector< vector<int> > A; + vector<int> b; + + ConvertILPToSat(int n, int m) : A(n, vector<int>(m)), b(n) + {} + + void printEquisatisfiableSatFormula() { + // This solution prints a simple satisfiable formula + // and passes about half of the tests. + // Change this function to solve the problem. + cout << "3 2" << endl; + cout << "1 2 0" << endl; + cout << "-1 -2 0" << endl; + cout << "1 -2 0" << endl; + } +}; + +int main() { + ios::sync_with_stdio(false); + + int n, m; + cin >> n >> m; + ConvertILPToSat converter(n, m); + for (int i = 0; i < n; i++) { + for (int j = 0; j < m; j++) { + cin >> converter.A[i][j]; + } + } + for (int i = 0; i < n; i++) { + cin >> converter.b[i]; + } + + converter.printEquisatisfiableSatFormula(); + + return 0; +} |