Algorithms : add 01-algorithmic_toolbox 02-greedy_algorithms

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
new 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