diff options
Diffstat (limited to '01-algorithmic_toolbox')
29 files changed, 202 insertions, 0 deletions
diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/00_greedy_algorithms.pdf b/01-algorithmic_toolbox/02-greedy_algorithms/00_greedy_algorithms.pdf Binary files differnew file mode 100644 index 0000000..2f1e34a --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/00_greedy_algorithms.pdf diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/01-change/change.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/change.cpp new file mode 100644 index 0000000..e25cd67 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/change.cpp @@ -0,0 +1,12 @@ +#include <iostream> + +int get_change(int n) { + //write your code here + return n; +} + +int main() { + int n; + std::cin >> n; + std::cout << get_change(n) << '\n'; +} diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/01 b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/01 new file mode 100644 index 0000000..0cfbf08 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/01 @@ -0,0 +1 @@ +2 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/01.a b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/01.a new file mode 100644 index 0000000..0cfbf08 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/01.a @@ -0,0 +1 @@ +2 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/02 b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/02 new file mode 100644 index 0000000..9902f17 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/02 @@ -0,0 +1 @@ +28 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/02.a b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/02.a new file mode 100644 index 0000000..1e8b314 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/01-change/tests/02.a @@ -0,0 +1 @@ +6 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp new file mode 100644 index 0000000..02e3fd8 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/fractional_knapsack.cpp @@ -0,0 +1,29 @@ +#include <iostream> +#include <vector> + +using std::vector; + +double get_optimal_value(int capacity, vector<int> weights, vector<int> values) { + double value = 0.0; + + // write your code here + + return value; +} + +int main() { + int n; + int capacity; + std::cin >> n >> capacity; + vector<int> values(n); + vector<int> weights(n); + for (int i = 0; i < n; i++) { + std::cin >> values[i] >> weights[i]; + } + + double optimal_value = get_optimal_value(capacity, weights, values); + + std::cout.precision(10); + std::cout << optimal_value << std::endl; + return 0; +} diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01 b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01 new file mode 100644 index 0000000..0094f93 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01 @@ -0,0 +1,4 @@ +3 50 +60 20 +100 50 +120 30 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01.a b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01.a new file mode 100644 index 0000000..3af99ee --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/01.a @@ -0,0 +1 @@ +180 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02 b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02 new file mode 100644 index 0000000..762e5ef --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02 @@ -0,0 +1,2 @@ +1 10 +500 30 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02.a b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02.a new file mode 100644 index 0000000..53ed09b --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/02-fractional_knapsack/tests/02.a @@ -0,0 +1 @@ +166.6666667 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/dot_product.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/dot_product.cpp new file mode 100644 index 0000000..d9df791 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/dot_product.cpp @@ -0,0 +1,27 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +using std::vector; + +long long min_dot_product(vector<int> a, vector<int> b) { + // write your code here + long long result = 0; + for (size_t i = 0; i < a.size(); i++) { + result += a[i] * b[i]; + } + return result; +} + +int main() { + size_t n; + std::cin >> n; + vector<int> a(n), b(n); + for (size_t i = 0; i < n; i++) { + std::cin >> a[i]; + } + for (size_t i = 0; i < n; i++) { + std::cin >> b[i]; + } + std::cout << min_dot_product(a, b) << std::endl; +} diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/01 b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/01 new file mode 100644 index 0000000..cde8746 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/01 @@ -0,0 +1,3 @@ +1 +23 +39 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/01.a b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/01.a new file mode 100644 index 0000000..8a65506 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/01.a @@ -0,0 +1 @@ +897 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/02 b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/02 new file mode 100644 index 0000000..36302ec --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/02 @@ -0,0 +1,3 @@ +3 +1 3 -5 +-2 4 1 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/02.a b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/02.a new file mode 100644 index 0000000..bd90f33 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/03-dot_product/tests/02.a @@ -0,0 +1 @@ +-25 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp new file mode 100644 index 0000000..c8f1fcd --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/covering_segments.cpp @@ -0,0 +1,34 @@ +#include <algorithm> +#include <iostream> +#include <climits> +#include <vector> + +using std::vector; + +struct Segment { + int start, end; +}; + +vector<int> optimal_points(vector<Segment> &segments) { + vector<int> points; + //write your code here + for (size_t i = 0; i < segments.size(); ++i) { + points.push_back(segments[i].start); + points.push_back(segments[i].end); + } + return points; +} + +int main() { + int n; + std::cin >> n; + vector<Segment> segments(n); + for (size_t i = 0; i < segments.size(); ++i) { + std::cin >> segments[i].start >> segments[i].end; + } + vector<int> points = optimal_points(segments); + std::cout << points.size() << "\n"; + for (size_t i = 0; i < points.size(); ++i) { + std::cout << points[i] << " "; + } +} diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/01 b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/01 new file mode 100644 index 0000000..c37582a --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/01 @@ -0,0 +1,4 @@ +3 +1 3 +2 5 +3 6 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/01.a b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/01.a new file mode 100644 index 0000000..aedb333 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/01.a @@ -0,0 +1,2 @@ +1 +3 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/02 b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/02 new file mode 100644 index 0000000..694ef84 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/02 @@ -0,0 +1,5 @@ +4 +4 7 +1 3 +2 5 +5 6 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/02.a b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/02.a new file mode 100644 index 0000000..11ac08e --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/04-covering_segments/tests/02.a @@ -0,0 +1,2 @@ +2 +3 6 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp new file mode 100644 index 0000000..0f8b4cb --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp @@ -0,0 +1,20 @@ +#include <iostream> +#include <vector> + +using std::vector; + +vector<int> optimal_summands(int n) { + vector<int> summands; + //write your code here + return summands; +} + +int main() { + int n; + std::cin >> n; + vector<int> summands = optimal_summands(n); + std::cout << summands.size() << '\n'; + for (size_t i = 0; i < summands.size(); ++i) { + std::cout << summands[i] << ' '; + } +} diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/01 b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/01 new file mode 100644 index 0000000..1e8b314 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/01 @@ -0,0 +1 @@ +6 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/01.a b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/01.a new file mode 100644 index 0000000..f3ce152 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/01.a @@ -0,0 +1,2 @@ +3 +1 2 3 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/02 b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/02 new file mode 100644 index 0000000..45a4fb7 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/02 @@ -0,0 +1 @@ +8 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/02.a b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/02.a new file mode 100644 index 0000000..175e44e --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/02.a @@ -0,0 +1,2 @@ +3 +1 2 5 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/03 b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/03 new file mode 100644 index 0000000..0cfbf08 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/03 @@ -0,0 +1 @@ +2 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/03.a b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/03.a new file mode 100644 index 0000000..db496fe --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/tests/03.a @@ -0,0 +1,2 @@ +1 +2 diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/check b/01-algorithmic_toolbox/02-greedy_algorithms/check new file mode 100755 index 0000000..8bdb3d4 --- /dev/null +++ b/01-algorithmic_toolbox/02-greedy_algorithms/check @@ -0,0 +1,38 @@ +#! /bin/bash + +RESET="\033[0m" +BLACK="\033[0;30m" +RED="\033[0;31m" +GREEN="\033[0;32m" +BROWN="\033[0;33m" + +BIN=/tmp/bin +OUTA=/tmp/_outa +OUTB=/tmp/_outb +GPP_OPTS="-std=c++11 -O2" + +for path in $(find -name \*.cpp | sort); do + src=${path##*/} + dir=${path%/*} + echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET" + pushd $dir >/dev/null || exit 1 + echo -e " ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1 + if [ -d tests ]; then + echo -e " ${RED}check $GREEN$src$RESET" + for t in $(find ./tests -name "*[^a~]"|sort); do + if [ -f $t -a -f "$t.a" ]; then + cat $t | $BIN > $OUTA + cat $t.a > $OUTB + cmp $OUTA $OUTB >/dev/null + if [ $? -ne 0 ]; then + echo -e " $BROWN$t$RESET is ${RED}KO$RESET" + else + echo -e " $BROWN$t$RESET is ${GREEN}ok$RESET" + fi + fi + done + else + echo -e " ${RED}no tests$RESET" + fi + popd > /dev/null +done |