diff options
Diffstat (limited to 'store/works/life/2020-algorithm-contest')
27 files changed, 474 insertions, 0 deletions
diff --git a/store/works/life/2020-algorithm-contest/.gitignore b/store/works/life/2020-algorithm-contest/.gitignore new file mode 100644 index 0000000..9d58650 --- /dev/null +++ b/store/works/life/2020-algorithm-contest/.gitignore @@ -0,0 +1,4 @@ +.vscode +temp +output +arc
\ No newline at end of file diff --git a/store/works/life/2020-algorithm-contest/README.md b/store/works/life/2020-algorithm-contest/README.md new file mode 100644 index 0000000..babf984 --- /dev/null +++ b/store/works/life/2020-algorithm-contest/README.md @@ -0,0 +1,5 @@ +这是在武汉轻工大学举办2020年数计学院算法大赛时候，我出题时用于生成测试数据的相关代码和脚本。
+
+其中`v1.1-output.zip`就是比赛时的测试数据，如果我没记错的话。
+
+当然，这是一个很***water***的比赛！
diff --git a/store/works/life/2020-algorithm-contest/code/1.cpp b/store/works/life/2020-algorithm-contest/code/1.cpp new file mode 100644 index 0000000..1ae1783 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/code/2.cpp b/store/works/life/2020-algorithm-contest/code/2.cpp new file mode 100644 index 0000000..2d5fded --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/code/3.cpp b/store/works/life/2020-algorithm-contest/code/3.cpp new file mode 100644 index 0000000..088cc5e --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/code/4.cpp b/store/works/life/2020-algorithm-contest/code/4.cpp new file mode 100644 index 0000000..4ee94cb --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/code/5.cpp b/store/works/life/2020-algorithm-contest/code/5.cpp new file mode 100644 index 0000000..24d3fd6 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/gen.bash b/store/works/life/2020-algorithm-contest/gen.bash new file mode 100644 index 0000000..08a4897 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/1/1.in b/store/works/life/2020-algorithm-contest/test-data/1/1.in new file mode 100644 index 0000000..0caae7c --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/1/2.cpp b/store/works/life/2020-algorithm-contest/test-data/1/2.cpp new file mode 100644 index 0000000..3bdaf19 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/2/1.in b/store/works/life/2020-algorithm-contest/test-data/2/1.in new file mode 100644 index 0000000..2c27ec3 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/2/2.in b/store/works/life/2020-algorithm-contest/test-data/2/2.in new file mode 100644 index 0000000..129c127 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/2/3.cpp b/store/works/life/2020-algorithm-contest/test-data/2/3.cpp new file mode 100644 index 0000000..c19d9e3 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/3/1.in b/store/works/life/2020-algorithm-contest/test-data/3/1.in new file mode 100644 index 0000000..83884b9 --- /dev/null +++ b/store/works/life/2020-algorithm-contest/test-data/3/1.in @@ -0,0 +1 @@ +10 1
\ No newline at end of file diff --git a/store/works/life/2020-algorithm-contest/test-data/3/2.in b/store/works/life/2020-algorithm-contest/test-data/3/2.in new file mode 100644 index 0000000..0355e8d --- /dev/null +++ b/store/works/life/2020-algorithm-contest/test-data/3/2.in @@ -0,0 +1 @@ +5 8
\ No newline at end of file diff --git a/store/works/life/2020-algorithm-contest/test-data/3/3.in b/store/works/life/2020-algorithm-contest/test-data/3/3.in new file mode 100644 index 0000000..86f1abd --- /dev/null +++ b/store/works/life/2020-algorithm-contest/test-data/3/3.in @@ -0,0 +1 @@ +12 4
\ No newline at end of file diff --git a/store/works/life/2020-algorithm-contest/test-data/3/4.in b/store/works/life/2020-algorithm-contest/test-data/3/4.in new file mode 100644 index 0000000..20085c7 --- /dev/null +++ b/store/works/life/2020-algorithm-contest/test-data/3/4.in @@ -0,0 +1 @@ +10000 1234
\ No newline at end of file diff --git a/store/works/life/2020-algorithm-contest/test-data/4/1.in b/store/works/life/2020-algorithm-contest/test-data/4/1.in new file mode 100644 index 0000000..d9d2898 --- /dev/null +++ b/store/works/life/2020-algorithm-contest/test-data/4/1.in @@ -0,0 +1,3 @@ +3 4 2 +0 3 +1 0 diff --git a/store/works/life/2020-algorithm-contest/test-data/4/2.in b/store/works/life/2020-algorithm-contest/test-data/4/2.in new file mode 100644 index 0000000..afe3aef --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/4/3.cpp b/store/works/life/2020-algorithm-contest/test-data/4/3.cpp new file mode 100644 index 0000000..20428a6 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/5/1.in b/store/works/life/2020-algorithm-contest/test-data/5/1.in new file mode 100644 index 0000000..250b0ad --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/test-data/5/2.in b/store/works/life/2020-algorithm-contest/test-data/5/2.in new file mode 100644 index 0000000..3119560 --- /dev/null +++ b/store/works/life/2020-algorithm-contest/test-data/5/2.in @@ -0,0 +1 @@ +( - 6 3 )
\ No newline at end of file diff --git a/store/works/life/2020-algorithm-contest/test-data/5/3.in b/store/works/life/2020-algorithm-contest/test-data/5/3.in new file mode 100644 index 0000000..92969bb --- /dev/null +++ b/store/works/life/2020-algorithm-contest/test-data/5/3.in @@ -0,0 +1 @@ +( * 1 2 5 ) diff --git a/store/works/life/2020-algorithm-contest/test-data/5/4.in b/store/works/life/2020-algorithm-contest/test-data/5/4.in new file mode 100644 index 0000000..232d166 --- /dev/null +++ b/store/works/life/2020-algorithm-contest/test-data/5/4.in @@ -0,0 +1 @@ +( / 8 3 ) diff --git a/store/works/life/2020-algorithm-contest/test-data/5/5.in b/store/works/life/2020-algorithm-contest/test-data/5/5.in new file mode 100644 index 0000000..1db11b7 --- /dev/null +++ b/store/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/store/works/life/2020-algorithm-contest/v1.1-output.zip b/store/works/life/2020-algorithm-contest/v1.1-output.zip Binary files differnew file mode 100644 index 0000000..0a63eec --- /dev/null +++ b/store/works/life/2020-algorithm-contest/v1.1-output.zip diff --git a/store/works/life/2020-algorithm-contest/zip.bash b/store/works/life/2020-algorithm-contest/zip.bash new file mode 100644 index 0000000..519dd45 --- /dev/null +++ b/store/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 |