diff options
Diffstat (limited to 'works/life/2020-algorithm-contest')
27 files changed, 0 insertions, 474 deletions
diff --git a/works/life/2020-algorithm-contest/.gitignore b/works/life/2020-algorithm-contest/.gitignore deleted file mode 100644 index 9d58650..0000000 --- a/works/life/2020-algorithm-contest/.gitignore +++ /dev/null @@ -1,4 +0,0 @@ -.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 deleted file mode 100644 index babf984..0000000 --- a/works/life/2020-algorithm-contest/README.md +++ /dev/null @@ -1,5 +0,0 @@ -这是在武汉轻工大学举办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 deleted file mode 100644 index 1ae1783..0000000 --- a/works/life/2020-algorithm-contest/code/1.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#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 deleted file mode 100644 index 2d5fded..0000000 --- a/works/life/2020-algorithm-contest/code/2.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#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 deleted file mode 100644 index 088cc5e..0000000 --- a/works/life/2020-algorithm-contest/code/3.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#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 deleted file mode 100644 index 4ee94cb..0000000 --- a/works/life/2020-algorithm-contest/code/4.cpp +++ /dev/null @@ -1,71 +0,0 @@ -#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 deleted file mode 100644 index 24d3fd6..0000000 --- a/works/life/2020-algorithm-contest/code/5.cpp +++ /dev/null @@ -1,133 +0,0 @@ -#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 deleted file mode 100644 index 08a4897..0000000 --- a/works/life/2020-algorithm-contest/gen.bash +++ /dev/null @@ -1,31 +0,0 @@ -#!/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 deleted file mode 100644 index 0caae7c..0000000 --- a/works/life/2020-algorithm-contest/test-data/1/1.in +++ /dev/null @@ -1,2 +0,0 @@ -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 deleted file mode 100644 index 3bdaf19..0000000 --- a/works/life/2020-algorithm-contest/test-data/1/2.cpp +++ /dev/null @@ -1,15 +0,0 @@ -#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 deleted file mode 100644 index 2c27ec3..0000000 --- a/works/life/2020-algorithm-contest/test-data/2/1.in +++ /dev/null @@ -1,2 +0,0 @@ -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 deleted file mode 100644 index 129c127..0000000 --- a/works/life/2020-algorithm-contest/test-data/2/2.in +++ /dev/null @@ -1,2 +0,0 @@ -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 deleted file mode 100644 index c19d9e3..0000000 --- a/works/life/2020-algorithm-contest/test-data/2/3.cpp +++ /dev/null @@ -1,17 +0,0 @@ -#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 deleted file mode 100644 index 83884b9..0000000 --- a/works/life/2020-algorithm-contest/test-data/3/1.in +++ /dev/null @@ -1 +0,0 @@ -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 deleted file mode 100644 index 0355e8d..0000000 --- a/works/life/2020-algorithm-contest/test-data/3/2.in +++ /dev/null @@ -1 +0,0 @@ -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 deleted file mode 100644 index 86f1abd..0000000 --- a/works/life/2020-algorithm-contest/test-data/3/3.in +++ /dev/null @@ -1 +0,0 @@ -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 deleted file mode 100644 index 20085c7..0000000 --- a/works/life/2020-algorithm-contest/test-data/3/4.in +++ /dev/null @@ -1 +0,0 @@ -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 deleted file mode 100644 index d9d2898..0000000 --- a/works/life/2020-algorithm-contest/test-data/4/1.in +++ /dev/null @@ -1,3 +0,0 @@ -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 deleted file mode 100644 index afe3aef..0000000 --- a/works/life/2020-algorithm-contest/test-data/4/2.in +++ /dev/null @@ -1,5 +0,0 @@ -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 deleted file mode 100644 index 20428a6..0000000 --- a/works/life/2020-algorithm-contest/test-data/4/3.cpp +++ /dev/null @@ -1,50 +0,0 @@ -#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 deleted file mode 100644 index 250b0ad..0000000 --- a/works/life/2020-algorithm-contest/test-data/5/1.in +++ /dev/null @@ -1 +0,0 @@ -( + 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 deleted file mode 100644 index 3119560..0000000 --- a/works/life/2020-algorithm-contest/test-data/5/2.in +++ /dev/null @@ -1 +0,0 @@ -( - 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 deleted file mode 100644 index 92969bb..0000000 --- a/works/life/2020-algorithm-contest/test-data/5/3.in +++ /dev/null @@ -1 +0,0 @@ -( * 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 deleted file mode 100644 index 232d166..0000000 --- a/works/life/2020-algorithm-contest/test-data/5/4.in +++ /dev/null @@ -1 +0,0 @@ -( / 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 deleted file mode 100644 index 1db11b7..0000000 --- a/works/life/2020-algorithm-contest/test-data/5/5.in +++ /dev/null @@ -1 +0,0 @@ -( * 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 Binary files differdeleted file mode 100644 index 0a63eec..0000000 --- a/works/life/2020-algorithm-contest/v1.1-output.zip +++ /dev/null diff --git a/works/life/2020-algorithm-contest/zip.bash b/works/life/2020-algorithm-contest/zip.bash deleted file mode 100644 index 519dd45..0000000 --- a/works/life/2020-algorithm-contest/zip.bash +++ /dev/null @@ -1,11 +0,0 @@ -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 |