diff options
29 files changed, 213 insertions, 0 deletions
diff --git a/01-algorithmic_toolbox/04-dynamic_programming/00_dynamic_programming.pdf b/01-algorithmic_toolbox/04-dynamic_programming/00_dynamic_programming.pdf Binary files differnew file mode 100644 index 0000000..51f84fa --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/00_dynamic_programming.pdf diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp new file mode 100644 index 0000000..0131b53 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/primitive_calculator.cpp @@ -0,0 +1,31 @@ +#include <iostream> +#include <vector> +#include <algorithm> + +using std::vector; + +vector<int> optimal_sequence(int n) { + std::vector<int> sequence; + while (n >= 1) { + sequence.push_back(n); + if (n % 3 == 0) { + n /= 3; + } else if (n % 2 == 0) { + n /= 2; + } else { + n = n - 1; + } + } + reverse(sequence.begin(), sequence.end()); + return sequence; +} + +int main() { + int n; + std::cin >> n; + vector<int> sequence = optimal_sequence(n); + std::cout << sequence.size() - 1 << std::endl; + for (size_t i = 0; i < sequence.size(); ++i) { + std::cout << sequence[i] << " "; + } +} diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01 new file mode 100644 index 0000000..d00491f --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01 @@ -0,0 +1 @@ +1 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a new file mode 100644 index 0000000..2734518 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/01.a @@ -0,0 +1,2 @@ +0 +1 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02 new file mode 100644 index 0000000..7ed6ff8 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02 @@ -0,0 +1 @@ +5 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a new file mode 100644 index 0000000..fc544c9 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/02.a @@ -0,0 +1,2 @@ +3 +1 2 4 5 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03 b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03 new file mode 100644 index 0000000..c18d157 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03 @@ -0,0 +1 @@ +96234 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a new file mode 100644 index 0000000..55a1c62 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/01-primitive_calculator/tests/03.a @@ -0,0 +1,2 @@ +14 +1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp new file mode 100644 index 0000000..c284560 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/knapsack.cpp @@ -0,0 +1,25 @@ +#include <iostream> +#include <vector> + +using std::vector; + +int optimal_weight(int W, const vector<int> &w) { + //write your code here + int current_weight = 0; + for (size_t i = 0; i < w.size(); ++i) { + if (current_weight + w[i] <= W) { + current_weight += w[i]; + } + } + return current_weight; +} + +int main() { + int n, W; + std::cin >> W >> n; + vector<int> w(n); + for (int i = 0; i < n; i++) { + std::cin >> w[i]; + } + std::cout << optimal_weight(W, w) << '\n'; +} diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01 new file mode 100644 index 0000000..3fa3706 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01 @@ -0,0 +1,2 @@ +10 3 +1 4 8 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a new file mode 100644 index 0000000..ec63514 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/02-knapsack/tests/01.a @@ -0,0 +1 @@ +9 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp new file mode 100644 index 0000000..fd7d16e --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/edit_distance.cpp @@ -0,0 +1,17 @@ +#include <iostream> +#include <string> + +using std::string; + +int edit_distance(const string &str1, const string &str2) { + //write your code here + return 0; +} + +int main() { + string str1; + string str2; + std::cin >> str1 >> str2; + std::cout << edit_distance(str1, str2) << std::endl; + return 0; +} diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01 new file mode 100644 index 0000000..367ac87 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01 @@ -0,0 +1,2 @@ +ab +ab diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01.a new file mode 100644 index 0000000..573541a --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/01.a @@ -0,0 +1 @@ +0 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02 new file mode 100644 index 0000000..3ef52c8 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02 @@ -0,0 +1,2 @@ +short +ports diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02.a new file mode 100644 index 0000000..00750ed --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/02.a @@ -0,0 +1 @@ +3 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03 b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03 new file mode 100644 index 0000000..cc5b276 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03 @@ -0,0 +1,2 @@ +editing +distance diff --git a/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03.a b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03.a new file mode 100644 index 0000000..7ed6ff8 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/03-edit_distance/tests/03.a @@ -0,0 +1 @@ +5 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp new file mode 100644 index 0000000..06861ab --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/placing_parentheses.cpp @@ -0,0 +1,32 @@ +#include <iostream> +#include <cassert> +#include <string> +#include <vector> + +using std::vector; +using std::string; +using std::max; +using std::min; + +long long eval(long long a, long long b, char op) { + if (op == '*') { + return a * b; + } else if (op == '+') { + return a + b; + } else if (op == '-') { + return a - b; + } else { + assert(0); + } +} + +long long get_maximum_value(const string &exp) { + //write your code here + return 0; +} + +int main() { + string s; + std::cin >> s; + std::cout << get_maximum_value(s) << '\n'; +} diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01 new file mode 100644 index 0000000..cea3f71 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01 @@ -0,0 +1 @@ +1+5 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01.a new file mode 100644 index 0000000..1e8b314 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/01.a @@ -0,0 +1 @@ +6 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02 new file mode 100644 index 0000000..92a372d --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02 @@ -0,0 +1 @@ +5-8+7*4-8+9 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02.a new file mode 100644 index 0000000..08839f6 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/04-placing_parentheses/tests/02.a @@ -0,0 +1 @@ +200 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp new file mode 100644 index 0000000..2ca0339 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/lcs3.cpp @@ -0,0 +1,31 @@ +#include <iostream> +#include <vector> + +using std::vector; + +int lcs3(vector<int> &a, vector<int> &b, vector<int> &c) { + //write your code here + return std::min(std::min(a.size(), b.size()), c.size()); +} + +int main() { + size_t an; + std::cin >> an; + vector<int> a(an); + for (size_t i = 0; i < an; i++) { + std::cin >> a[i]; + } + size_t bn; + std::cin >> bn; + vector<int> b(bn); + for (size_t i = 0; i < bn; i++) { + std::cin >> b[i]; + } + size_t cn; + std::cin >> cn; + vector<int> c(cn); + for (size_t i = 0; i < cn; i++) { + std::cin >> c[i]; + } + std::cout << lcs3(a, b, c) << std::endl; +} diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01 b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01 new file mode 100644 index 0000000..354d6f0 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01 @@ -0,0 +1,6 @@ +3 +1 2 3 +3 +2 1 3 +3 +1 3 5 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01.a b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01.a new file mode 100644 index 0000000..0cfbf08 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/01.a @@ -0,0 +1 @@ +2 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02 b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02 new file mode 100644 index 0000000..3969ebb --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02 @@ -0,0 +1,6 @@ +5 +8 3 2 1 7 +7 +8 2 1 3 8 10 7 +6 +6 8 3 1 4 7 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02.a b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02.a new file mode 100644 index 0000000..00750ed --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/05-lcs3/tests/02.a @@ -0,0 +1 @@ +3 diff --git a/01-algorithmic_toolbox/04-dynamic_programming/check b/01-algorithmic_toolbox/04-dynamic_programming/check new file mode 100755 index 0000000..8bdb3d4 --- /dev/null +++ b/01-algorithmic_toolbox/04-dynamic_programming/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 |