import(life): Add 2020-algorithm-contest.

27 files changed, 474 insertions, 0 deletions

diff --git a/works/life/2020-algorithm-contest/.gitignore b/works/life/2020-algorithm-contest/.gitignore
new file mode 100644
index 0000000..9d58650
--- /dev/null
+++ b/works/life/2020-algorithm-contest/.gitignore
@@ -0,0 +1,4 @@
+.vscode
+temp
+output
+arc
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/README.md b/works/life/2020-algorithm-contest/README.md
new file mode 100644
index 0000000..babf984
--- /dev/null
+++ b/works/life/2020-algorithm-contest/README.md
@@ -0,0 +1,5 @@
+这是在武汉轻工大学举办2020年数计学院算法大赛时候，我出题时用于生成测试数据的相关代码和脚本。

+

+其中`v1.1-output.zip`就是比赛时的测试数据，如果我没记错的话。

+

+当然，这是一个很***water***的比赛！

diff --git a/works/life/2020-algorithm-contest/code/1.cpp b/works/life/2020-algorithm-contest/code/1.cpp
new file mode 100644
index 0000000..1ae1783
--- /dev/null
+++ b/works/life/2020-algorithm-contest/code/1.cpp
@@ -0,0 +1,22 @@
+#include <iostream>
+#include <set>
+
+int main()
+{
+    int size;
+    std::cin >> size;
+    std::set<int> s;
+    int v;
+    for (int i = 0; i< size; i++)
+    {
+        std::cin >> v;
+        s.insert(v);
+    }
+
+    for (auto value : s)
+    {
+        std::cout << value << ' ';
+    }
+
+    return 0;
+}
diff --git a/works/life/2020-algorithm-contest/code/2.cpp b/works/life/2020-algorithm-contest/code/2.cpp
new file mode 100644
index 0000000..2d5fded
--- /dev/null
+++ b/works/life/2020-algorithm-contest/code/2.cpp
@@ -0,0 +1,54 @@
+#include <iostream>
+#include <map>
+#include <vector>
+#include <algorithm>
+
+int main()
+{
+    int size;
+    std::cin >> size;
+    int target;
+    std::cin >> target;
+
+    std::map<int, int> nums;
+
+    for (int i = 0; i < size; i++)
+    {
+        int v;
+        std::cin >> v;
+
+        nums[v]++;
+    }
+
+    std::vector<int> counts;
+    std::vector<std::vector<int>> sets;
+
+    for (const auto &pair : nums)
+    {
+        auto iter = std::lower_bound(counts.cbegin(), counts.cend(), pair.second);
+        if (iter != counts.cend() && *iter == pair.second)
+        {
+            sets[iter - counts.cbegin()].push_back(pair.first);
+        }
+        else
+        {
+            const auto offset = iter - counts.cbegin();
+            counts.insert(iter, pair.second);
+            sets.insert(sets.cbegin() + offset, std::vector<int>{pair.first});
+        }
+    }
+
+    if (target > counts.size())
+    {
+        std::cout << 0;
+    }
+    else
+    {
+        const auto &set = sets[counts.size() - target];
+        std::cout << set.size() << '\n';
+        for (auto i : set)
+            std::cout << i << ' ';
+    }
+
+    return 0;
+}
diff --git a/works/life/2020-algorithm-contest/code/3.cpp b/works/life/2020-algorithm-contest/code/3.cpp
new file mode 100644
index 0000000..088cc5e
--- /dev/null
+++ b/works/life/2020-algorithm-contest/code/3.cpp
@@ -0,0 +1,38 @@
+#include <iostream>
+
+int main()
+{
+    int length, numRows;
+    std::cin >> length >> numRows;
+
+    if (numRows == 1)
+    {
+        for (int i = 1; i <= length; i++)
+            std::cout << i << ' ';
+        return 0;
+    }
+
+    const int count_per_group = numRows * 2 - 2;
+    for (int row = 0; row < numRows; row++)
+    {
+        if (row == 0)
+        {
+            for (int p = 0; p < length; p += count_per_group)
+                std::cout << p + 1 << ' ';
+        }
+        else if (row == numRows - 1)
+        {
+            for (int p = row; p < length; p += count_per_group)
+                std::cout << p + 1 << ' ';
+        }
+        else
+        {
+            bool former = true;
+            const auto former_gap = count_per_group - row * 2;
+            const auto latter_gap = count_per_group - former_gap;
+            for (int p = row; p < length; p += (former ? former_gap : latter_gap), former = !former)
+                std::cout << p + 1 << ' ';
+        }
+    }
+    return 0;
+}
diff --git a/works/life/2020-algorithm-contest/code/4.cpp b/works/life/2020-algorithm-contest/code/4.cpp
new file mode 100644
index 0000000..4ee94cb
--- /dev/null
+++ b/works/life/2020-algorithm-contest/code/4.cpp
@@ -0,0 +1,71 @@
+#include <iostream>
+#include <vector>
+
+int calc(std::vector<std::vector<int>> &obstacleGrid)
+{
+
+    int R = obstacleGrid.size();
+    int C = obstacleGrid[0].size();
+
+    // If the starting cell has an obstacle, then simply return as there would be
+    // no paths to the destination.
+    if (obstacleGrid[0][0] == 1)
+    {
+        return 0;
+    }
+
+    // Number of ways of reaching the starting cell = 1.
+    obstacleGrid[0][0] = 1;
+
+    // Filling the values for the first column
+    for (int i = 1; i < R; i++)
+    {
+        obstacleGrid[i][0] = (obstacleGrid[i][0] == 0 && obstacleGrid[i - 1][0] == 1) ? 1 : 0;
+    }
+
+    // Filling the values for the first row
+    for (int i = 1; i < C; i++)
+    {
+        obstacleGrid[0][i] = (obstacleGrid[0][i] == 0 && obstacleGrid[0][i - 1] == 1) ? 1 : 0;
+    }
+
+    // Starting from cell(1,1) fill up the values
+    // No. of ways of reaching cell[i][j] = cell[i - 1][j] + cell[i][j - 1]
+    // i.e. From above and left.
+    for (int i = 1; i < R; i++)
+    {
+        for (int j = 1; j < C; j++)
+        {
+            if (obstacleGrid[i][j] == 0)
+            {
+                obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
+            }
+            else
+            {
+                obstacleGrid[i][j] = 0;
+            }
+        }
+    }
+
+    // Return value stored in rightmost bottommost cell. That is the destination.
+    return obstacleGrid[R - 1][C - 1];
+}
+
+int main()
+{
+    int row, column, bs;
+    std::cin >> row >> column >> bs;
+
+    std::vector<std::vector<int>> grid(row, std::vector<int>(column, 0));
+
+    for (int i = 0; i < bs; i++)
+    {
+        int r, c;
+        std::cin >> r >> c;
+        grid[r][c] = 1;
+    }
+
+    std::cout << calc(grid);
+
+    return 0;
+}
diff --git a/works/life/2020-algorithm-contest/code/5.cpp b/works/life/2020-algorithm-contest/code/5.cpp
new file mode 100644
index 0000000..24d3fd6
--- /dev/null
+++ b/works/life/2020-algorithm-contest/code/5.cpp
@@ -0,0 +1,133 @@
+#include <iostream>
+#include <string>
+#include <vector>
+#include <cassert>
+
+enum class Op
+{
+    Add,
+    Sub,
+    Mul,
+    Div
+};
+
+struct OpInfo
+{
+    explicit OpInfo(Op op) : op(op), count(0) {}
+
+    Op op;
+    int count; // operand count
+};
+
+int main()
+{
+    std::string expr;
+    std::getline(std::cin, expr);
+
+    std::vector<int> operands;
+    std::vector<OpInfo> op_infos;
+
+    for (auto c : expr)
+    {
+        if (c == '+')
+        {
+            op_infos.emplace_back(Op::Add);
+        }
+        else if (c == '-')
+        {
+            op_infos.emplace_back(Op::Sub);
+        }
+        else if (c == '*')
+        {
+            op_infos.emplace_back(Op::Mul);
+        }
+        else if (c == '/')
+        {
+            op_infos.emplace_back(Op::Div);
+        }
+        else if (c == '(')
+        {
+            if (!op_infos.empty())
+                op_infos.back().count++;
+        }
+        else if (c >= '0' && c <= '9')
+        {
+            operands.push_back(c - '0');
+            op_infos.back().count++;
+        }
+        else if (c == ')')
+        {
+            const auto &info = op_infos.back();
+            if ((info.op == Op::Sub || info.op == Op::Div) && info.count != 2)
+            {
+                std::cerr << "Sub or Div Op has not 2 operands.";
+                return 1;
+            }
+
+            switch (info.op)
+            {
+            case Op::Add:
+            {
+                int r = 0;
+                for (int i = 0; i < info.count; i++)
+                {
+                    r += operands.back();
+                    operands.pop_back();
+                }
+                operands.push_back(r);
+                op_infos.pop_back();
+                break;
+            }
+            case Op::Sub:
+            {
+                int a = operands.back();
+                operands.pop_back();
+                int b = operands.back();
+                operands.pop_back();
+                operands.push_back(b - a);
+                op_infos.pop_back();
+                break;
+            }
+            case Op::Mul:
+            {
+                int r = 1;
+                for (int i = 0; i < info.count; i++)
+                {
+                    r *= operands.back();
+                    operands.pop_back();
+                }
+                operands.push_back(r);
+                op_infos.pop_back();
+                break;
+            }
+            case Op::Div:
+            {
+                int a = operands.back();
+                operands.pop_back();
+                int b = operands.back();
+                operands.pop_back();
+                operands.push_back(b / a);
+                op_infos.pop_back();
+                break;
+            }
+            default:
+                std::terminate();
+            }
+        }
+    }
+
+    if (operands.size() != 1)
+    {
+        std::cerr << "final operand count is not 1, but " << operands.size();
+        return 1;
+    }
+    if (!op_infos.empty())
+    {
+        std::cerr << "final op_info is not empty";
+        return 1;
+    }
+
+    std::cout << operands.front();
+
+    return 0;
+}
diff --git a/works/life/2020-algorithm-contest/gen.bash b/works/life/2020-algorithm-contest/gen.bash
new file mode 100644
index 0000000..08a4897
--- /dev/null
+++ b/works/life/2020-algorithm-contest/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 -fsanitize=integer
+
+
+for generator in ./test-data/$problem_number/*.cpp; do
+test_data_number=`echo $generator | sed -r "s/.*([0-9]+)\.cpp/\1/"` 
+
+clang++ $generator -o ./temp/$problem_number-$test_data_number-g -O2 -fsanitize=integer
+
+./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/2020-algorithm-contest/test-data/1/1.in b/works/life/2020-algorithm-contest/test-data/1/1.in
new file mode 100644
index 0000000..0caae7c
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/1/1.in
@@ -0,0 +1,2 @@
+4
+4 3 2 4
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/1/2.cpp b/works/life/2020-algorithm-contest/test-data/1/2.cpp
new file mode 100644
index 0000000..3bdaf19
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/1/2.cpp
@@ -0,0 +1,15 @@
+#include <iostream>
+#include <random>
+
+int main()
+{
+    std::default_random_engine engine;
+    std::uniform_int_distribution<> distribution(0, 10000);
+    const int size = 10000;
+    std::cout << size << '\n';
+    for (int i = 0 ; i < size; i++)
+    {
+        std::cout << distribution(engine) << ' ';
+    }
+    return 0;
+}
diff --git a/works/life/2020-algorithm-contest/test-data/2/1.in b/works/life/2020-algorithm-contest/test-data/2/1.in
new file mode 100644
index 0000000..2c27ec3
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/2/1.in
@@ -0,0 +1,2 @@
+8 2
+2 1 4 3 2 1 2 3
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/2/2.in b/works/life/2020-algorithm-contest/test-data/2/2.in
new file mode 100644
index 0000000..129c127
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/2/2.in
@@ -0,0 +1,2 @@
+8 4
+2 1 4 3 2 1 2 3
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/2/3.cpp b/works/life/2020-algorithm-contest/test-data/2/3.cpp
new file mode 100644
index 0000000..c19d9e3
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/2/3.cpp
@@ -0,0 +1,17 @@
+#include <iostream>
+#include <random>
+#include <cmath>
+
+int main()
+{
+    std::default_random_engine engine;
+    std::normal_distribution<> distribution(5000, 50);
+    const int size = 5000;
+    std::cout << size << ' ';
+    std::cout << 6 << '\n';
+    for (int i = 0 ; i < size; i++)
+    {
+        std::cout << std::abs((static_cast<int>(distribution(engine)) % 10000)) << ' ';
+    }
+    return 0;
+}
diff --git a/works/life/2020-algorithm-contest/test-data/3/1.in b/works/life/2020-algorithm-contest/test-data/3/1.in
new file mode 100644
index 0000000..83884b9
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/3/1.in
@@ -0,0 +1 @@
+10 1
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/3/2.in b/works/life/2020-algorithm-contest/test-data/3/2.in
new file mode 100644
index 0000000..0355e8d
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/3/2.in
@@ -0,0 +1 @@
+5 8
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/3/3.in b/works/life/2020-algorithm-contest/test-data/3/3.in
new file mode 100644
index 0000000..86f1abd
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/3/3.in
@@ -0,0 +1 @@
+12 4
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/3/4.in b/works/life/2020-algorithm-contest/test-data/3/4.in
new file mode 100644
index 0000000..20085c7
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/3/4.in
@@ -0,0 +1 @@
+10000 1234
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/4/1.in b/works/life/2020-algorithm-contest/test-data/4/1.in
new file mode 100644
index 0000000..d9d2898
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/4/1.in
@@ -0,0 +1,3 @@
+3 4 2
+0 3
+1 0
diff --git a/works/life/2020-algorithm-contest/test-data/4/2.in b/works/life/2020-algorithm-contest/test-data/4/2.in
new file mode 100644
index 0000000..afe3aef
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/4/2.in
@@ -0,0 +1,5 @@
+3 4 4
+0 3
+1 0
+1 2
+2 1
diff --git a/works/life/2020-algorithm-contest/test-data/4/3.cpp b/works/life/2020-algorithm-contest/test-data/4/3.cpp
new file mode 100644
index 0000000..20428a6
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/4/3.cpp
@@ -0,0 +1,50 @@
+#include <iostream>
+#include <random>
+#include <set>
+#include <algorithm>
+
+struct Point
+{
+    int x;
+    int y;
+};
+
+bool operator<(const Point &left, const Point &right)
+{
+    return left.x == right.x ? left.y < right.y : left.x < right.x;
+}
+
+int main()
+{
+    std::default_random_engine engine{39};
+    const int size = 20;
+    const int b_size = 50;
+    std::uniform_int_distribution<> distribution(0, size - 1);
+    std::cout << size << ' ' << size << ' ' << b_size << '\n';
+
+    std::set<Point> b;
+
+    while (b.size() < b_size)
+    {
+        int x = distribution(engine);
+        int y = distribution(engine);
+
+        if (x == 0 && y == 0)
+            continue;
+        if (x == size - 1 && y == size - 1)
+            continue;
+
+        b.insert({x, y});
+    }
+
+    std::vector<Point> bb(b.cbegin(), b.cend());
+
+    std::shuffle(bb.begin(), bb.end(), engine);
+
+    for (const auto &p : bb)
+    {
+        std::cout << p.x << ' ' << p.y << '\n';
+    }
+
+    return 0;
+}
diff --git a/works/life/2020-algorithm-contest/test-data/5/1.in b/works/life/2020-algorithm-contest/test-data/5/1.in
new file mode 100644
index 0000000..250b0ad
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/5/1.in
@@ -0,0 +1 @@
+( + 1 2 5 )
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/5/2.in b/works/life/2020-algorithm-contest/test-data/5/2.in
new file mode 100644
index 0000000..3119560
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/5/2.in
@@ -0,0 +1 @@
+( - 6 3 )
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/test-data/5/3.in b/works/life/2020-algorithm-contest/test-data/5/3.in
new file mode 100644
index 0000000..92969bb
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/5/3.in
@@ -0,0 +1 @@
+( * 1 2 5 )
diff --git a/works/life/2020-algorithm-contest/test-data/5/4.in b/works/life/2020-algorithm-contest/test-data/5/4.in
new file mode 100644
index 0000000..232d166
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/5/4.in
@@ -0,0 +1 @@
+( / 8 3 )
diff --git a/works/life/2020-algorithm-contest/test-data/5/5.in b/works/life/2020-algorithm-contest/test-data/5/5.in
new file mode 100644
index 0000000..1db11b7
--- /dev/null
+++ b/works/life/2020-algorithm-contest/test-data/5/5.in
@@ -0,0 +1 @@
+( * 3 ( - 4 ( - 4 1 ) ) ( + ( + 9 5 ) 5 4 3 ( / 6 ( + 2 4 ) ) ) 5 6 )
\ No newline at end of file
diff --git a/works/life/2020-algorithm-contest/v1.1-output.zip b/works/life/2020-algorithm-contest/v1.1-output.zip
new file mode 100644
index 0000000..0a63eec
--- /dev/null
+++ b/works/life/2020-algorithm-contest/v1.1-output.zip
diff --git a/works/life/2020-algorithm-contest/zip.bash b/works/life/2020-algorithm-contest/zip.bash
new file mode 100644
index 0000000..519dd45
--- /dev/null
+++ b/works/life/2020-algorithm-contest/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