import(life): Merge remote-tracking branch 'origin/ac3'

58 files changed, 600 insertions, 0 deletions

diff --git a/works/life/.vscode/launch.json b/works/life/.vscode/launch.json
new file mode 100644
index 0000000..584e971
--- /dev/null
+++ b/works/life/.vscode/launch.json
@@ -0,0 +1,17 @@
+{
+    // Use IntelliSense to learn about possible attributes.
+    // Hover to view descriptions of existing attributes.
+    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
+    "version": "0.2.0",
+    "configurations": [
+        {
+            "name": "Debug",
+            "type": "gdb",
+            "request": "launch",
+            "target": "./a.out",
+            "cwd": "${workspaceRoot}",
+            "valuesFormatting": "parseText",
+            "terminal": "konsole"
+        }
+    ]
+}
diff --git a/works/life/.vscode/settings.json b/works/life/.vscode/settings.json
new file mode 100644
index 0000000..cad7657
--- /dev/null
+++ b/works/life/.vscode/settings.json
@@ -0,0 +1,3 @@
+{
+    "cmake.configureOnOpen": false
+}
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/.gitignore b/works/life/algorithm-contest-3/.gitignore
new file mode 100644
index 0000000..9d58650
--- /dev/null
+++ b/works/life/algorithm-contest-3/.gitignore
@@ -0,0 +1,4 @@
+.vscode
+temp
+output
+arc
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/README.md b/works/life/algorithm-contest-3/README.md
new file mode 100644
index 0000000..40dc66a
--- /dev/null
+++ b/works/life/algorithm-contest-3/README.md
@@ -0,0 +1,9 @@
+2021.3.26

+

+此文件夹包含第三届数计学院算法大赛相关的文件。

+

+# Update

+

+1. Update `gen.bash` script so that it can handle more than 9 pieces of test data. Because of `sed` does not support **lazy match** (aka. non-greedy match) so I turn to `perl`.

+

+2. There seems to be a bug in integer sanitizer in clang, which cause the program (exactly problem 2 solution) outputs different result. So I turn off it. But I do not file a bug to llvm for laziness!

diff --git a/works/life/algorithm-contest-3/code/1.cpp b/works/life/algorithm-contest-3/code/1.cpp
new file mode 100644
index 0000000..2c8ea1a
--- /dev/null
+++ b/works/life/algorithm-contest-3/code/1.cpp
@@ -0,0 +1,16 @@
+#include <iostream>
+
+int main() {
+  std::ios_base::sync_with_stdio(false);
+  std::cin.tie(nullptr);
+
+  long long n;
+  std::cin >> n;
+
+  while (n) {
+    std::cout << n << ' ';
+    n /= 3;
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/code/2.cpp b/works/life/algorithm-contest-3/code/2.cpp
new file mode 100644
index 0000000..ad4c840
--- /dev/null
+++ b/works/life/algorithm-contest-3/code/2.cpp
@@ -0,0 +1,106 @@
+#include <algorithm>
+#include <cstdio>
+#include <vector>
+
+int ConvertYear(int x) {
+  if (x >= 60)
+    return 1900 + x;
+  return 2000 + x;
+}
+
+bool CheckMonth(int x) {
+  if (x <= 0 && x >= 13) {
+    return false;
+  }
+
+  return true;
+}
+
+bool IsLeapYear(int y) {
+  if (y == 2000)
+    return false;
+  if (y % 4)
+    return false;
+  return true;
+}
+
+int days[] = {0, 31, 0, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
+
+bool CheckDay(int day, int month, int year) {
+  if (month == 2) {
+    const bool leap = IsLeapYear(year);
+    if (leap) {
+      return day >= 1 && day <= 29;
+    } else {
+      return day >= 1 && day <= 28;
+    }
+  }
+
+  return day >= 1 && day <= days[month];
+}
+
+struct Date {
+  int year;
+  int month;
+  int day;
+};
+
+bool operator==(const Date &l, const Date &r) {
+  return l.year == r.year && l.month == r.month && l.day == r.day;
+}
+
+bool operator<(const Date &l, const Date &r) {
+  if (l.year < r.year)
+    return true;
+  else if (l.year > r.year)
+    return false;
+  else if (l.month < r.month)
+    return true;
+  else if (l.month > r.month)
+    return false;
+  else if (l.day < r.day)
+    return true;
+  return false;
+}
+
+bool Check(int year, int month, int day, Date *result) {
+  if (!CheckMonth(month))
+    return false;
+  const auto y = ConvertYear(year);
+  if (!CheckDay(day, month, y))
+    return false;
+
+  result->year = y;
+  result->month = month;
+  result->day = day;
+  return true;
+}
+
+int main() {
+  std::vector<Date> results;
+
+  int a, b, c;
+  std::scanf("%d/%d/%d", &a, &b, &c);
+
+  Date temp;
+  if (Check(a, b, c, &temp)) {
+    results.push_back(temp);
+  }
+
+  if (Check(c, a, b, &temp)) {
+    results.push_back(temp);
+  }
+
+  if (Check(c, b, a, &temp)) {
+    results.push_back(temp);
+  }
+
+  results.erase(std::unique(results.begin(), results.end()), results.end());
+  std::sort(results.begin(), results.end());
+
+  for (const auto &r : results) {
+    std::printf("%d-%02d-%02d\n", r.year, r.month, r.day);
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/code/3.cpp b/works/life/algorithm-contest-3/code/3.cpp
new file mode 100644
index 0000000..20abfa1
--- /dev/null
+++ b/works/life/algorithm-contest-3/code/3.cpp
@@ -0,0 +1,22 @@
+#include <iostream>
+
+int n, m;
+long long f[31][31];
+
+int main() {
+  std::cin >> n >> m;
+
+  f[1][1] = 1;
+
+  for (int r = 1; r <= n; r++) {
+    for (int c = 1; c <= m; c++) {
+      if (!(r == 1 && c == 1) && !(r % 2 == 0 && c % 2 == 0)) {
+        f[r][c] = f[r - 1][c] + f[r][c - 1];
+      }
+    }
+  }
+
+  std::cout << f[n][m];
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/code/4.cpp b/works/life/algorithm-contest-3/code/4.cpp
new file mode 100644
index 0000000..aebd735
--- /dev/null
+++ b/works/life/algorithm-contest-3/code/4.cpp
@@ -0,0 +1,34 @@
+#include <algorithm>
+#include <iostream>
+#include <numeric>
+
+int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
+
+int N;
+int A[100010];
+
+int main() {
+  std::ios_base::sync_with_stdio(false);
+  std::cin.tie(nullptr);
+
+  std::cin >> N;
+
+  for (int i = 0; i < N; i++) {
+    std::cin >> A[i];
+  }
+
+  std::sort(A, A + N);
+
+  int g = A[1] - A[0];
+  for (int i = 1; i < N - 1; i++) {
+    g = gcd(g, A[i + 1] - A[i]);
+  }
+
+  if (g == 0) {
+    std::cout << N;
+  } else {
+    std::cout << (A[N - 1] - A[0]) / g + 1;
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/code/5.cpp b/works/life/algorithm-contest-3/code/5.cpp
new file mode 100644
index 0000000..8d70a55
--- /dev/null
+++ b/works/life/algorithm-contest-3/code/5.cpp
@@ -0,0 +1,52 @@
+#include <algorithm>
+#include <iostream>
+
+int N, K;
+long long A[100010];
+
+long long M = 1000000009;
+
+int main() {
+  std::ios_base::sync_with_stdio(false);
+  std::cin.tie(nullptr);
+
+  std::cin >> N >> K;
+
+  for (int i = 0; i < N; i++) {
+    std::cin >> A[i];
+  }
+
+  std::sort(A, A + N);
+
+  long long result = 1;
+  int left = 0, right = N - 1;
+  long long sign = 1;
+  int k = K;
+
+  if (k % 2) {
+    result = A[N - 1];
+    right--;
+    k--;
+
+    if (result < 0) {
+      sign = -1;
+    }
+  }
+
+  while (k) {
+    long long x = A[left] * A[left + 1], y = A[right] * A[right - 1];
+
+    if (x * sign > y * sign) {
+      result = x % M * result % M;
+      left += 2;
+    } else {
+      result = y % M * result % M;
+      right -= 2;
+    }
+    k -= 2;
+  }
+
+  std::cout << result;
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/gen.bash b/works/life/algorithm-contest-3/gen.bash
new file mode 100755
index 0000000..a93da88
--- /dev/null
+++ b/works/life/algorithm-contest-3/gen.bash
@@ -0,0 +1,31 @@
+#!/bin/bash
+shopt -s nullglob
+
+if [ $# -ne 1 ]; then
+    echo "please input exact one argument, problem number"
+    exit 1
+fi
+
+problem_number=$1
+
+mkdir -p ./output/$problem_number
+
+cp ./test-data/$problem_number/*.in ./output/$problem_number/
+
+mkdir -p ./temp
+
+clang++ ./code/$problem_number.cpp -o ./temp/$problem_number -O2
+
+
+for generator in ./test-data/$problem_number/*.cpp; do
+test_data_number=`echo $generator | perl -pe "s|.*?([0-9]+)\.cpp|\1|"` 
+
+clang++ $generator -o ./temp/$problem_number-$test_data_number-g -O2
+
+./temp/$problem_number-$test_data_number-g > ./output/$problem_number/$test_data_number.in
+done
+
+for test_data in ./output/$problem_number/*.in; do
+out_file=`echo $test_data | sed "s/\.in/.out/"`
+./temp/$problem_number < $test_data | tee > $out_file
+done
diff --git a/works/life/algorithm-contest-3/output.zip b/works/life/algorithm-contest-3/output.zip
new file mode 100644
index 0000000..d9aa182
--- /dev/null
+++ b/works/life/algorithm-contest-3/output.zip
diff --git a/works/life/algorithm-contest-3/test-data/1/1.in b/works/life/algorithm-contest-3/test-data/1/1.in
new file mode 100644
index 0000000..9a03714
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/1/1.in
@@ -0,0 +1 @@
+10
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/1/2.in b/works/life/algorithm-contest-3/test-data/1/2.in
new file mode 100644
index 0000000..8580e7b
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/1/2.in
@@ -0,0 +1 @@
+30
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/1/3.in b/works/life/algorithm-contest-3/test-data/1/3.in
new file mode 100644
index 0000000..d892ef5
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/1/3.in
@@ -0,0 +1 @@
+32158
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/1/4.in b/works/life/algorithm-contest-3/test-data/1/4.in
new file mode 100644
index 0000000..97b3e56
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/1/4.in
@@ -0,0 +1 @@
+49658245
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/1/5.in b/works/life/algorithm-contest-3/test-data/1/5.in
new file mode 100644
index 0000000..70dfac1
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/1/5.in
@@ -0,0 +1 @@
+436356535634
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/1/6.in b/works/life/algorithm-contest-3/test-data/1/6.in
new file mode 100644
index 0000000..2ced27a
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/1/6.in
@@ -0,0 +1 @@
+13425465454334
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/1/7.in b/works/life/algorithm-contest-3/test-data/1/7.in
new file mode 100644
index 0000000..384eda4
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/1/7.in
@@ -0,0 +1 @@
+123456789123456789
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/1.in b/works/life/algorithm-contest-3/test-data/2/1.in
new file mode 100644
index 0000000..79c38cd
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/1.in
@@ -0,0 +1 @@
+31/12/59
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/10.in b/works/life/algorithm-contest-3/test-data/2/10.in
new file mode 100644
index 0000000..bcdc0a9
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/10.in
@@ -0,0 +1 @@
+30/11/10
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/11.in b/works/life/algorithm-contest-3/test-data/2/11.in
new file mode 100644
index 0000000..56dc9d3
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/11.in
@@ -0,0 +1 @@
+04/02/29
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/12.in b/works/life/algorithm-contest-3/test-data/2/12.in
new file mode 100644
index 0000000..569a346
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/12.in
@@ -0,0 +1 @@
+05/02/29
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/2.in b/works/life/algorithm-contest-3/test-data/2/2.in
new file mode 100644
index 0000000..e7e8e8b
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/2.in
@@ -0,0 +1 @@
+01/01/60
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/3.in b/works/life/algorithm-contest-3/test-data/2/3.in
new file mode 100644
index 0000000..735e9d4
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/3.in
@@ -0,0 +1 @@
+12/31/60
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/4.in b/works/life/algorithm-contest-3/test-data/2/4.in
new file mode 100644
index 0000000..dd7f868
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/4.in
@@ -0,0 +1 @@
+01/02/03
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/5.in b/works/life/algorithm-contest-3/test-data/2/5.in
new file mode 100644
index 0000000..f740cc4
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/5.in
@@ -0,0 +1 @@
+13/12/11
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/6.in b/works/life/algorithm-contest-3/test-data/2/6.in
new file mode 100644
index 0000000..45fc450
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/6.in
@@ -0,0 +1 @@
+41/12/12
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/7.in b/works/life/algorithm-contest-3/test-data/2/7.in
new file mode 100644
index 0000000..5a71023
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/7.in
@@ -0,0 +1 @@
+01/01/01
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/8.in b/works/life/algorithm-contest-3/test-data/2/8.in
new file mode 100644
index 0000000..c11526c
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/8.in
@@ -0,0 +1 @@
+10/11/15
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/2/9.in b/works/life/algorithm-contest-3/test-data/2/9.in
new file mode 100644
index 0000000..eb24a27
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/2/9.in
@@ -0,0 +1 @@
+31/11/10
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/3/1.in b/works/life/algorithm-contest-3/test-data/3/1.in
new file mode 100644
index 0000000..cadb504
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/3/1.in
@@ -0,0 +1 @@
+4 5
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/3/2.in b/works/life/algorithm-contest-3/test-data/3/2.in
new file mode 100644
index 0000000..f5381fa
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/3/2.in
@@ -0,0 +1 @@
+7 7
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/3/3.in b/works/life/algorithm-contest-3/test-data/3/3.in
new file mode 100644
index 0000000..bb7be06
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/3/3.in
@@ -0,0 +1 @@
+12 17
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/3/4.in b/works/life/algorithm-contest-3/test-data/3/4.in
new file mode 100644
index 0000000..e17177b
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/3/4.in
@@ -0,0 +1 @@
+21 17
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/3/5.in b/works/life/algorithm-contest-3/test-data/3/5.in
new file mode 100644
index 0000000..ada4381
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/3/5.in
@@ -0,0 +1 @@
+29 30
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/4/1.in b/works/life/algorithm-contest-3/test-data/4/1.in
new file mode 100644
index 0000000..99e00b5
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/4/1.in
@@ -0,0 +1,2 @@
+3
+1 2 3
diff --git a/works/life/algorithm-contest-3/test-data/4/2.in b/works/life/algorithm-contest-3/test-data/4/2.in
new file mode 100644
index 0000000..f33d5ec
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/4/2.in
@@ -0,0 +1,2 @@
+3
+1 3 4
diff --git a/works/life/algorithm-contest-3/test-data/4/3.in b/works/life/algorithm-contest-3/test-data/4/3.in
new file mode 100644
index 0000000..a18e01d
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/4/3.in
@@ -0,0 +1,2 @@
+3
+1 1 1
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/4/4.in b/works/life/algorithm-contest-3/test-data/4/4.in
new file mode 100644
index 0000000..4ef3642
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/4/4.in
@@ -0,0 +1,2 @@
+4
+0 3 12 18
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/4/5.cpp b/works/life/algorithm-contest-3/test-data/4/5.cpp
new file mode 100644
index 0000000..774b407
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/4/5.cpp
@@ -0,0 +1,31 @@
+#include <algorithm>
+#include <iostream>
+#include <random>
+
+const int kCommonDifference = 25;
+const int kSequenceSize = 100;
+
+int main() {
+
+  std::random_device random_device;
+  auto random = std::default_random_engine{random_device()};
+  std::binomial_distribution<int> distribution{100, 0.4};
+
+  std::vector<int> sequence;
+
+  int current_value = 0;
+
+  for (int i = 0; i < kSequenceSize; i++) {
+    sequence.push_back(current_value);
+    current_value += distribution(random) * kCommonDifference;
+  }
+
+  std::shuffle(sequence.begin(), sequence.end(), random);
+
+  std::cout << kSequenceSize << "\n";
+  for (auto v : sequence) {
+    std::cout << v << ' ';
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/test-data/4/6.cpp b/works/life/algorithm-contest-3/test-data/4/6.cpp
new file mode 100644
index 0000000..32c3a9f
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/4/6.cpp
@@ -0,0 +1,31 @@
+#include <algorithm>
+#include <iostream>
+#include <random>
+
+const int kCommonDifference = 10;
+const int kSequenceSize = 1000;
+
+int main() {
+
+  std::random_device random_device;
+  auto random = std::default_random_engine{random_device()};
+  std::binomial_distribution<int> distribution{100, 0.4};
+
+  std::vector<int> sequence;
+
+  int current_value = 0;
+
+  for (int i = 0; i < kSequenceSize; i++) {
+    sequence.push_back(current_value);
+    current_value += distribution(random) * kCommonDifference;
+  }
+
+  std::shuffle(sequence.begin(), sequence.end(), random);
+
+  std::cout << kSequenceSize << "\n";
+  for (auto v : sequence) {
+    std::cout << v << ' ';
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/test-data/4/7.cpp b/works/life/algorithm-contest-3/test-data/4/7.cpp
new file mode 100644
index 0000000..185e27c
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/4/7.cpp
@@ -0,0 +1,31 @@
+#include <algorithm>
+#include <iostream>
+#include <random>
+
+const int kCommonDifference = 6;
+const int kSequenceSize = 10000;
+
+int main() {
+
+  std::random_device random_device;
+  auto random = std::default_random_engine{random_device()};
+  std::binomial_distribution<int> distribution{100, 0.4};
+
+  std::vector<int> sequence;
+
+  int current_value = 0;
+
+  for (int i = 0; i < kSequenceSize; i++) {
+    sequence.push_back(current_value);
+    current_value += distribution(random) * kCommonDifference;
+  }
+
+  std::shuffle(sequence.begin(), sequence.end(), random);
+
+  std::cout << kSequenceSize << "\n";
+  for (auto v : sequence) {
+    std::cout << v << ' ';
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/test-data/4/8.cpp b/works/life/algorithm-contest-3/test-data/4/8.cpp
new file mode 100644
index 0000000..d3c7d38
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/4/8.cpp
@@ -0,0 +1,31 @@
+#include <algorithm>
+#include <iostream>
+#include <random>
+
+const int kCommonDifference = 4;
+const int kSequenceSize = 100000;
+
+int main() {
+
+  std::random_device random_device;
+  auto random = std::default_random_engine{random_device()};
+  std::binomial_distribution<int> distribution{100, 0.4};
+
+  std::vector<int> sequence;
+
+  int current_value = 0;
+
+  for (int i = 0; i < kSequenceSize; i++) {
+    sequence.push_back(current_value);
+    current_value += distribution(random) * kCommonDifference;
+  }
+
+  std::shuffle(sequence.begin(), sequence.end(), random);
+
+  std::cout << kSequenceSize << "\n";
+  for (auto v : sequence) {
+    std::cout << v << ' ';
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/test-data/5/1.in b/works/life/algorithm-contest-3/test-data/5/1.in
new file mode 100644
index 0000000..67955b5
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/1.in
@@ -0,0 +1,6 @@
+5 3
+100
+200
+300
+400
+500
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/10.cpp b/works/life/algorithm-contest-3/test-data/5/10.cpp
new file mode 100644
index 0000000..c74d96d
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/10.cpp
@@ -0,0 +1,20 @@
+#include <algorithm>
+#include <iostream>
+#include <random>
+
+const int kNumberCount = 100;
+const int kChooseCount = 40;
+
+int main() {
+  std::random_device random_device;
+  auto random = std::default_random_engine{random_device()};
+  std::uniform_int_distribution<int> distribution{0, 200000};
+
+  std::cout << kNumberCount << ' ' << kChooseCount << "\n";
+
+  for (int i = 0; i < kNumberCount; i++) {
+    std::cout << distribution(random) - 100000 << "\n";
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/test-data/5/11.cpp b/works/life/algorithm-contest-3/test-data/5/11.cpp
new file mode 100644
index 0000000..039ca04
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/11.cpp
@@ -0,0 +1,20 @@
+#include <algorithm>
+#include <iostream>
+#include <random>
+
+const int kNumberCount = 1000;
+const int kChooseCount = 200;
+
+int main() {
+  std::random_device random_device;
+  auto random = std::default_random_engine{random_device()};
+  std::uniform_int_distribution<int> distribution{0, 200000};
+
+  std::cout << kNumberCount << ' ' << kChooseCount << "\n";
+
+  for (int i = 0; i < kNumberCount; i++) {
+    std::cout << distribution(random) - 100000 << "\n";
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/test-data/5/12.cpp b/works/life/algorithm-contest-3/test-data/5/12.cpp
new file mode 100644
index 0000000..f7488fb
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/12.cpp
@@ -0,0 +1,20 @@
+#include <algorithm>
+#include <iostream>
+#include <random>
+
+const int kNumberCount = 10000;
+const int kChooseCount = 1000;
+
+int main() {
+  std::random_device random_device;
+  auto random = std::default_random_engine{random_device()};
+  std::uniform_int_distribution<int> distribution{0, 200000};
+
+  std::cout << kNumberCount << ' ' << kChooseCount << "\n";
+
+  for (int i = 0; i < kNumberCount; i++) {
+    std::cout << distribution(random) - 100000 << "\n";
+  }
+
+  return 0;
+}
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/13.cpp b/works/life/algorithm-contest-3/test-data/5/13.cpp
new file mode 100644
index 0000000..b4e115e
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/13.cpp
@@ -0,0 +1,20 @@
+#include <algorithm>
+#include <iostream>
+#include <random>
+
+const int kNumberCount = 100000;
+const int kChooseCount = 30000;
+
+int main() {
+  std::random_device random_device;
+  auto random = std::default_random_engine{random_device()};
+  std::uniform_int_distribution<int> distribution{0, 200000};
+
+  std::cout << kNumberCount << ' ' << kChooseCount << "\n";
+
+  for (int i = 0; i < kNumberCount; i++) {
+    std::cout << distribution(random) - 100000 << "\n";
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-3/test-data/5/14.in b/works/life/algorithm-contest-3/test-data/5/14.in
new file mode 100644
index 0000000..9a880e1
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/14.in
@@ -0,0 +1,5 @@
+4 4
+-100
+-100
+-100
+100
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/2.in b/works/life/algorithm-contest-3/test-data/5/2.in
new file mode 100644
index 0000000..44e28ef
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/2.in
@@ -0,0 +1,6 @@
+5 3
+-100
+-200
+-300
+-400
+-500
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/3.in b/works/life/algorithm-contest-3/test-data/5/3.in
new file mode 100644
index 0000000..d784df0
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/3.in
@@ -0,0 +1,6 @@
+5 4
+-100
+-200
+-300
+-400
+-500
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/4.in b/works/life/algorithm-contest-3/test-data/5/4.in
new file mode 100644
index 0000000..f710da1
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/4.in
@@ -0,0 +1,6 @@
+5 3
+20
+-300
+100
+200
+-100
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/5.in b/works/life/algorithm-contest-3/test-data/5/5.in
new file mode 100644
index 0000000..7eba3f5
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/5.in
@@ -0,0 +1,6 @@
+5 3
+100
+-100
+-200
+300
+400
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/6.in b/works/life/algorithm-contest-3/test-data/5/6.in
new file mode 100644
index 0000000..106730a
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/6.in
@@ -0,0 +1,6 @@
+5 4
+100
+-100
+-200
+300
+400
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/7.in b/works/life/algorithm-contest-3/test-data/5/7.in
new file mode 100644
index 0000000..01bd232
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/7.in
@@ -0,0 +1,6 @@
+5 3
+-100
+-200
+0
+-300
+-400
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/8.in b/works/life/algorithm-contest-3/test-data/5/8.in
new file mode 100644
index 0000000..7e0ce0b
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/8.in
@@ -0,0 +1,6 @@
+5 3
+-100
+200
+0
+-300
+-400
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/test-data/5/9.in b/works/life/algorithm-contest-3/test-data/5/9.in
new file mode 100644
index 0000000..210953e
--- /dev/null
+++ b/works/life/algorithm-contest-3/test-data/5/9.in
@@ -0,0 +1,6 @@
+5 4
+-100
+-100
+100
+100
+200
\ No newline at end of file
diff --git a/works/life/algorithm-contest-3/zip.bash b/works/life/algorithm-contest-3/zip.bash
new file mode 100755
index 0000000..519dd45
--- /dev/null
+++ b/works/life/algorithm-contest-3/zip.bash
@@ -0,0 +1,11 @@
+if [ $# -ne 1 ]
+then
+    echo "please provide exact one argument, problem number"
+    exit 1
+fi
+
+pushd ./output/$1/
+zip ./$1.zip *.in *.out
+popd
+
+mv ./output/$1/$1.zip ./output