From 58e4c77b1d5f8241af91c55e1a8efaba3115dc6b Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Sun, 25 Oct 2020 17:16:31 +0800
Subject: import(life): Add algorithm contest 2.

---
 works/life/algorithm-contest-2/README.md         |   9 +++
 works/life/algorithm-contest-2/gen.ps1           |  39 ++++++++++++
 works/life/algorithm-contest-2/generator/1/1.in  |   1 +
 works/life/algorithm-contest-2/generator/1/2.in  |   1 +
 works/life/algorithm-contest-2/generator/1/3.in  |   1 +
 works/life/algorithm-contest-2/generator/1/4.in  |   1 +
 works/life/algorithm-contest-2/generator/1/5.in  |   1 +
 works/life/algorithm-contest-2/generator/2/1.in  |   2 +
 works/life/algorithm-contest-2/generator/2/2.in  |   2 +
 works/life/algorithm-contest-2/generator/2/3.cpp |  15 +++++
 works/life/algorithm-contest-2/generator/2/4.cpp |  15 +++++
 works/life/algorithm-contest-2/generator/2/5.cpp |  15 +++++
 works/life/algorithm-contest-2/generator/3/1.in  |   4 ++
 works/life/algorithm-contest-2/generator/3/2.in  |   5 ++
 works/life/algorithm-contest-2/generator/3/3.in  |   6 ++
 works/life/algorithm-contest-2/generator/3/4.cpp |  18 ++++++
 works/life/algorithm-contest-2/generator/3/5.cpp |  18 ++++++
 works/life/algorithm-contest-2/generator/4/1.in  |   3 +
 works/life/algorithm-contest-2/generator/4/2.in  |   4 ++
 works/life/algorithm-contest-2/generator/4/3.in  |   4 ++
 works/life/algorithm-contest-2/generator/4/4.cpp |  29 +++++++++
 works/life/algorithm-contest-2/generator/4/5.cpp |  29 +++++++++
 works/life/algorithm-contest-2/generator/4/6.cpp |  29 +++++++++
 works/life/algorithm-contest-2/generator/5/1.in  |   2 +
 works/life/algorithm-contest-2/generator/5/2.in  |   2 +
 works/life/algorithm-contest-2/generator/5/3.cpp |  47 ++++++++++++++
 works/life/algorithm-contest-2/output.zip        | Bin 0 -> 68853 bytes
 works/life/algorithm-contest-2/pack.ps1          |   6 ++
 works/life/algorithm-contest-2/problems.pdf      | Bin 0 -> 157726 bytes
 works/life/algorithm-contest-2/solution/1.cpp    |  34 ++++++++++
 works/life/algorithm-contest-2/solution/2.cpp    |  41 ++++++++++++
 works/life/algorithm-contest-2/solution/3.cpp    |  77 +++++++++++++++++++++++
 works/life/algorithm-contest-2/solution/4.cpp    |  48 ++++++++++++++
 works/life/algorithm-contest-2/solution/5-bf.cpp |  34 ++++++++++
 works/life/algorithm-contest-2/solution/5.cpp    |  49 +++++++++++++++
 35 files changed, 591 insertions(+)
 create mode 100644 works/life/algorithm-contest-2/README.md
 create mode 100644 works/life/algorithm-contest-2/gen.ps1
 create mode 100644 works/life/algorithm-contest-2/generator/1/1.in
 create mode 100644 works/life/algorithm-contest-2/generator/1/2.in
 create mode 100644 works/life/algorithm-contest-2/generator/1/3.in
 create mode 100644 works/life/algorithm-contest-2/generator/1/4.in
 create mode 100644 works/life/algorithm-contest-2/generator/1/5.in
 create mode 100644 works/life/algorithm-contest-2/generator/2/1.in
 create mode 100644 works/life/algorithm-contest-2/generator/2/2.in
 create mode 100644 works/life/algorithm-contest-2/generator/2/3.cpp
 create mode 100644 works/life/algorithm-contest-2/generator/2/4.cpp
 create mode 100644 works/life/algorithm-contest-2/generator/2/5.cpp
 create mode 100644 works/life/algorithm-contest-2/generator/3/1.in
 create mode 100644 works/life/algorithm-contest-2/generator/3/2.in
 create mode 100644 works/life/algorithm-contest-2/generator/3/3.in
 create mode 100644 works/life/algorithm-contest-2/generator/3/4.cpp
 create mode 100644 works/life/algorithm-contest-2/generator/3/5.cpp
 create mode 100644 works/life/algorithm-contest-2/generator/4/1.in
 create mode 100644 works/life/algorithm-contest-2/generator/4/2.in
 create mode 100644 works/life/algorithm-contest-2/generator/4/3.in
 create mode 100644 works/life/algorithm-contest-2/generator/4/4.cpp
 create mode 100644 works/life/algorithm-contest-2/generator/4/5.cpp
 create mode 100644 works/life/algorithm-contest-2/generator/4/6.cpp
 create mode 100644 works/life/algorithm-contest-2/generator/5/1.in
 create mode 100644 works/life/algorithm-contest-2/generator/5/2.in
 create mode 100644 works/life/algorithm-contest-2/generator/5/3.cpp
 create mode 100644 works/life/algorithm-contest-2/output.zip
 create mode 100644 works/life/algorithm-contest-2/pack.ps1
 create mode 100644 works/life/algorithm-contest-2/problems.pdf
 create mode 100644 works/life/algorithm-contest-2/solution/1.cpp
 create mode 100644 works/life/algorithm-contest-2/solution/2.cpp
 create mode 100644 works/life/algorithm-contest-2/solution/3.cpp
 create mode 100644 works/life/algorithm-contest-2/solution/4.cpp
 create mode 100644 works/life/algorithm-contest-2/solution/5-bf.cpp
 create mode 100644 works/life/algorithm-contest-2/solution/5.cpp

diff --git a/works/life/algorithm-contest-2/README.md b/works/life/algorithm-contest-2/README.md
new file mode 100644
index 0000000..ce3292d
--- /dev/null
+++ b/works/life/algorithm-contest-2/README.md
@@ -0,0 +1,9 @@
+2020.10.25
+
+此文件夹包含第二届数计学院算法大赛相关的文件。
+
+- `solution`里是参考答案。
+- `generator`里是测试数据生成器。
+- `gen.ps1`和`pack.ps1`为生成测试数据用的便捷脚本。
+- `output.zip`为最终的测试数据。
+- `problems.pdf`为本次比赛的题目。
diff --git a/works/life/algorithm-contest-2/gen.ps1 b/works/life/algorithm-contest-2/gen.ps1
new file mode 100644
index 0000000..60b88b2
--- /dev/null
+++ b/works/life/algorithm-contest-2/gen.ps1
@@ -0,0 +1,39 @@
+Push-Location solution
+
+foreach ($problem in 1..5) {
+    clang-cl "$problem.cpp" /O2 "-fsanitize=address,undefined"
+}
+
+Pop-Location
+
+Remove-Item -Recurse output
+
+mkdir .\output
+
+$time_output = @()
+
+foreach ($problem in 1..5) {
+    mkdir output/$problem
+    foreach ($genfile in Get-ChildItem "generator/$problem") {
+        if ($genfile.Name -match "(.+)\.in") {
+            $genfile_id = $Matches[1]
+            Copy-Item $genfile output/$problem
+        }
+        elseif ($genfile.Name -match "(.+)\.cpp") {
+            $genfile_id = $Matches[1]
+            Push-Location "generator/$problem"
+            clang-cl $genfile.Name /O2 "-fsanitize=address,undefined"
+            Pop-Location
+            & "./generator/$problem/$genfile_id.exe" > "./output/$problem/$genfile_id.in"
+        }
+        $time = (Measure-Command {
+                Get-Content "./output/$problem/$genfile_id.in" | & "./solution/$problem.exe"  > "./output/$problem/$genfile_id.out"
+            }).TotalSeconds
+
+        $time_output += "Problem $problem test point $genfile_id time: $time s."
+    }
+}
+
+foreach ($line in $time_output) {
+    Write-Output $line
+}
diff --git a/works/life/algorithm-contest-2/generator/1/1.in b/works/life/algorithm-contest-2/generator/1/1.in
new file mode 100644
index 0000000..38f8fd6
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/1/1.in
@@ -0,0 +1 @@
+8 3
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/1/2.in b/works/life/algorithm-contest-2/generator/1/2.in
new file mode 100644
index 0000000..f4eea7b
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/1/2.in
@@ -0,0 +1 @@
+4 4
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/1/3.in b/works/life/algorithm-contest-2/generator/1/3.in
new file mode 100644
index 0000000..11ab954
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/1/3.in
@@ -0,0 +1 @@
+4 6
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/1/4.in b/works/life/algorithm-contest-2/generator/1/4.in
new file mode 100644
index 0000000..11c3433
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/1/4.in
@@ -0,0 +1 @@
+8 2
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/1/5.in b/works/life/algorithm-contest-2/generator/1/5.in
new file mode 100644
index 0000000..fda96a5
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/1/5.in
@@ -0,0 +1 @@
+88888 5
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/2/1.in b/works/life/algorithm-contest-2/generator/2/1.in
new file mode 100644
index 0000000..37ba146
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/2/1.in
@@ -0,0 +1,2 @@
+4
+6 2 9 1
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/2/2.in b/works/life/algorithm-contest-2/generator/2/2.in
new file mode 100644
index 0000000..01faa33
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/2/2.in
@@ -0,0 +1,2 @@
+3
+13 22 11
diff --git a/works/life/algorithm-contest-2/generator/2/3.cpp b/works/life/algorithm-contest-2/generator/2/3.cpp
new file mode 100644
index 0000000..0eeadd1
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/2/3.cpp
@@ -0,0 +1,15 @@
+#include <iostream>
+#include <random>
+
+using std::cout;
+
+int main() {
+    std::default_random_engine engine(std::random_device{}());
+    std::uniform_int_distribution<int> distribution(1, 5000);
+    const int SIZE = 5000;
+    cout << SIZE << '\n';
+    for (int i = 0; i < SIZE; i++) {
+        cout << distribution(engine) << ' ';
+    }
+    return 0;
+}
diff --git a/works/life/algorithm-contest-2/generator/2/4.cpp b/works/life/algorithm-contest-2/generator/2/4.cpp
new file mode 100644
index 0000000..08d5c14
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/2/4.cpp
@@ -0,0 +1,15 @@
+#include <iostream>
+#include <random>
+
+using std::cout;
+
+int main() {
+    std::default_random_engine engine(std::random_device{}());
+    std::uniform_int_distribution<int> distribution(1, 9999);
+    const int SIZE = 9999;
+    cout << SIZE << '\n';
+    for (int i = 0; i < SIZE; i++) {
+        cout << distribution(engine) << ' ';
+    }
+    return 0;
+}
diff --git a/works/life/algorithm-contest-2/generator/2/5.cpp b/works/life/algorithm-contest-2/generator/2/5.cpp
new file mode 100644
index 0000000..bae2a90
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/2/5.cpp
@@ -0,0 +1,15 @@
+#include <iostream>
+#include <random>
+
+using std::cout;
+
+int main() {
+    std::default_random_engine engine(std::random_device{}());
+    std::uniform_int_distribution<int> distribution(1, 9999);
+    const int SIZE = 9998;
+    cout << SIZE << '\n';
+    for (int i = 0; i < SIZE; i++) {
+        cout << distribution(engine) << ' ';
+    }
+    return 0;
+}
diff --git a/works/life/algorithm-contest-2/generator/3/1.in b/works/life/algorithm-contest-2/generator/3/1.in
new file mode 100644
index 0000000..170d639
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/3/1.in
@@ -0,0 +1,4 @@
+3
+#..
+...
+#.#
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/3/2.in b/works/life/algorithm-contest-2/generator/3/2.in
new file mode 100644
index 0000000..7cefeb0
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/3/2.in
@@ -0,0 +1,5 @@
+4
+#...
+....
+#.#.
+....
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/3/3.in b/works/life/algorithm-contest-2/generator/3/3.in
new file mode 100644
index 0000000..51fff91
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/3/3.in
@@ -0,0 +1,6 @@
+5
+#....
+.....
+.....
+.....
+.....
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/3/4.cpp b/works/life/algorithm-contest-2/generator/3/4.cpp
new file mode 100644
index 0000000..ed2fbb6
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/3/4.cpp
@@ -0,0 +1,18 @@
+#include <iostream>
+#include <random>
+
+using std::cout;
+
+int main() {
+  std::default_random_engine engine(std::random_device{}());
+  std::uniform_int_distribution<int> distribution(1, 100);
+  const int SIZE = 100;
+  cout << SIZE << '\n';
+  for (int i = 0; i < SIZE; i++) {
+    for (int j = 0; j < SIZE; j++) {
+      cout << (distribution(engine) > 90 ? '#' : '.');
+    }
+    cout << '\n';
+  }
+  return 0;
+}
diff --git a/works/life/algorithm-contest-2/generator/3/5.cpp b/works/life/algorithm-contest-2/generator/3/5.cpp
new file mode 100644
index 0000000..bf1d14c
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/3/5.cpp
@@ -0,0 +1,18 @@
+#include <iostream>
+#include <random>
+
+using std::cout;
+
+int main() {
+  std::default_random_engine engine(std::random_device{}());
+  std::uniform_int_distribution<int> distribution(1, 100);
+  const int SIZE = 100;
+  cout << SIZE << '\n';
+  for (int i = 0; i < SIZE; i++) {
+    for (int j = 0; j < SIZE; j++) {
+      cout << (distribution(engine) < 75 ? '#' : '.');
+    }
+    cout << '\n';
+  }
+  return 0;
+}
diff --git a/works/life/algorithm-contest-2/generator/4/1.in b/works/life/algorithm-contest-2/generator/4/1.in
new file mode 100644
index 0000000..feef14b
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/4/1.in
@@ -0,0 +1,3 @@
+2 10
+6 5
+5 6
diff --git a/works/life/algorithm-contest-2/generator/4/2.in b/works/life/algorithm-contest-2/generator/4/2.in
new file mode 100644
index 0000000..d72e475
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/4/2.in
@@ -0,0 +1,4 @@
+3 20
+1 2
+2 1
+3 4
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/4/3.in b/works/life/algorithm-contest-2/generator/4/3.in
new file mode 100644
index 0000000..60d56de
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/4/3.in
@@ -0,0 +1,4 @@
+3 1
+4 5
+8 6
+7 7
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/4/4.cpp b/works/life/algorithm-contest-2/generator/4/4.cpp
new file mode 100644
index 0000000..fc0de0b
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/4/4.cpp
@@ -0,0 +1,29 @@
+#include <iostream>
+#include <random>
+#include <vector>
+
+using std::cout;
+
+int main() {
+  std::default_random_engine engine(std::random_device{}());
+  std::uniform_int_distribution<int> distribution(1, 1000);
+  const int SIZE = 100;
+  std::vector<int> b;
+
+  for (int i = 0; i < SIZE * 2; i++) {
+    b.push_back(distribution(engine));
+  }
+
+  long long sum = 0;
+  for (int i = 0; i < SIZE; i++) {
+    sum += b[i * 2] * b[i * 2 + 1];
+  }
+
+  cout << SIZE << ' ' << (sum + 10) << '\n';
+
+  for (int i = 0; i < SIZE; i++) {
+    cout << b[i * 2] << ' ' << b[i * 2 + 1] << '\n';
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-2/generator/4/5.cpp b/works/life/algorithm-contest-2/generator/4/5.cpp
new file mode 100644
index 0000000..518a4aa
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/4/5.cpp
@@ -0,0 +1,29 @@
+#include <iostream>
+#include <random>
+#include <vector>
+
+using std::cout;
+
+int main() {
+  std::default_random_engine engine(std::random_device{}());
+  std::uniform_int_distribution<int> distribution(1, 10000);
+  const int SIZE = 600;
+  std::vector<int> b;
+
+  for (int i = 0; i < SIZE * 2; i++) {
+    b.push_back(distribution(engine));
+  }
+
+  long long sum = 0;
+  for (int i = 0; i < SIZE; i++) {
+    sum += b[i * 2] * b[i * 2 + 1];
+  }
+
+  cout << SIZE << ' ' << 5000 << '\n';
+
+  for (int i = 0; i < SIZE; i++) {
+    cout << b[i * 2] << ' ' << b[i * 2 + 1] << '\n';
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-2/generator/4/6.cpp b/works/life/algorithm-contest-2/generator/4/6.cpp
new file mode 100644
index 0000000..b4bdb00
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/4/6.cpp
@@ -0,0 +1,29 @@
+#include <iostream>
+#include <random>
+#include <vector>
+
+using std::cout;
+
+int main() {
+  std::default_random_engine engine(std::random_device{}());
+  std::uniform_int_distribution<int> distribution(1, 10000);
+  const int SIZE = 100;
+  std::vector<int> b;
+
+  for (int i = 0; i < SIZE * 2; i++) {
+    b.push_back(distribution(engine));
+  }
+
+  long long sum = 0;
+  for (int i = 0; i < SIZE; i++) {
+    sum += b[i * 2] * b[i * 2 + 1];
+  }
+
+  cout << SIZE << ' ' << 5000 << '\n';
+
+  for (int i = 0; i < SIZE; i++) {
+    cout << b[i * 2] << ' ' << b[i * 2 + 1] << '\n';
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-2/generator/5/1.in b/works/life/algorithm-contest-2/generator/5/1.in
new file mode 100644
index 0000000..a1dfd91
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/5/1.in
@@ -0,0 +1,2 @@
+5 3
+6 1 2 3 4
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/5/2.in b/works/life/algorithm-contest-2/generator/5/2.in
new file mode 100644
index 0000000..7c0d388
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/5/2.in
@@ -0,0 +1,2 @@
+6 8
+1 9 5 4 3 6
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/generator/5/3.cpp b/works/life/algorithm-contest-2/generator/5/3.cpp
new file mode 100644
index 0000000..62d18c4
--- /dev/null
+++ b/works/life/algorithm-contest-2/generator/5/3.cpp
@@ -0,0 +1,47 @@
+#include <iostream>
+#include <random>
+#include <vector>
+
+using std::cout;
+
+int main() {
+  std::default_random_engine engine(std::random_device{}());
+  std::uniform_int_distribution<int> insert_distribution(0, 997);
+  std::uniform_int_distribution<int> distribution(1, 100000);
+  const int SIZE = 1000;
+  std::vector<int> v;
+
+  for (int i = 0; i < SIZE - 1; i++) {
+    v.push_back(distribution(engine));
+  }
+
+  int K = 320;
+
+  int a_index = insert_distribution(engine);
+  int a = v[a_index];
+  int b_index = insert_distribution(engine);
+  while (b_index == a_index) {
+    b_index = insert_distribution(engine);
+  }
+  int b = v[b_index];
+
+  int c_index = insert_distribution(engine);
+  while (c_index == a_index && c_index == b_index) {
+    c_index = insert_distribution(engine);
+  }
+  int c = v[c_index];
+
+  int d = (((-a - b - c) % K + K) % K) + 20 * K;
+
+  int d_index = insert_distribution(engine);
+
+  v.insert(v.cbegin() + d_index, c);
+
+  cout << SIZE << ' ' << K << '\n';
+
+  for (int i = 0; i < SIZE; i++) {
+    cout << v[i] << ' ';
+  }
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-2/output.zip b/works/life/algorithm-contest-2/output.zip
new file mode 100644
index 0000000..9ef7e40
Binary files /dev/null and b/works/life/algorithm-contest-2/output.zip differ
diff --git a/works/life/algorithm-contest-2/pack.ps1 b/works/life/algorithm-contest-2/pack.ps1
new file mode 100644
index 0000000..6d77d81
--- /dev/null
+++ b/works/life/algorithm-contest-2/pack.ps1
@@ -0,0 +1,6 @@
+foreach ($problem in 1..5) {
+    Push-Location "output/$problem"
+    7z a -tzip "$problem.zip" *
+    Move-Item "$problem.zip" ..
+    Pop-Location
+}
diff --git a/works/life/algorithm-contest-2/problems.pdf b/works/life/algorithm-contest-2/problems.pdf
new file mode 100644
index 0000000..dfb7df1
Binary files /dev/null and b/works/life/algorithm-contest-2/problems.pdf differ
diff --git a/works/life/algorithm-contest-2/solution/1.cpp b/works/life/algorithm-contest-2/solution/1.cpp
new file mode 100644
index 0000000..2689f9d
--- /dev/null
+++ b/works/life/algorithm-contest-2/solution/1.cpp
@@ -0,0 +1,34 @@
+#include <iostream>
+#include <cstdio>
+#include <cstring>
+#include <algorithm>
+#include <vector>
+#include <queue>
+#include <stack>
+#include <set>
+#include <map>
+#include <cmath>
+#include <unordered_map>
+#include <unordered_set>
+#include <string>
+#include <sstream>
+#include <climits>
+#define x first
+#define y second
+#define pub push_back
+#define mp make_pair
+#define ll long long
+using namespace std;
+
+int x, y;
+
+int main(void) {
+    cin >> x >> y;
+    int ans = x;
+    while (x >= y) {
+        ans += x / y;
+        x = x / y + x % y;
+    }
+    cout << ans;
+    return 0;
+}
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/solution/2.cpp b/works/life/algorithm-contest-2/solution/2.cpp
new file mode 100644
index 0000000..4410da0
--- /dev/null
+++ b/works/life/algorithm-contest-2/solution/2.cpp
@@ -0,0 +1,41 @@
+#define _CRT_SECURE_NO_WARNINGS
+#include <iostream>
+#include <cstdio>
+#include <cstring>
+#include <algorithm>
+#include <vector>
+#include <queue>
+#include <stack>
+#include <set>
+#include <map>
+#include <cmath>
+#include <unordered_map>
+#include <unordered_set>
+#include <string>
+#include <sstream>
+#include <climits>
+#define x first
+#define y second
+#define pub push_back
+#define mp make_pair
+#define ll long long
+using namespace std;
+typedef pair<int, int> PII;
+
+const int MAXN = 1e5 + 5;
+int n, a[MAXN];
+
+int main(void) {
+    cin >> n;
+    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
+    sort(a + 1, a + 1 + n);
+    
+    int l = 1, r = n;
+    ll ans = 0;
+    
+    while (l < r) {
+        ans += (a[r--] - a[l++]);
+    }
+    cout << ans;
+    return 0;
+}
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/solution/3.cpp b/works/life/algorithm-contest-2/solution/3.cpp
new file mode 100644
index 0000000..a97e351
--- /dev/null
+++ b/works/life/algorithm-contest-2/solution/3.cpp
@@ -0,0 +1,77 @@
+#include <iostream>
+#include <cstdio>
+#include <cstring>
+#include <algorithm>
+#include <vector>
+#include <queue>
+#include <stack>
+#include <set>
+#include <map>
+#include <cmath>
+#include <unordered_map>
+#include <unordered_set>
+#include <string>
+#include <sstream>
+#include <climits>
+#define x first
+#define y second
+#define pub push_back
+#define mp make_pair
+#define ll long long
+using namespace std;
+typedef pair<int, int> PII;
+
+struct node{
+    int x, y;
+    node(){}
+    node(int _x = 0,int _y = 0): x(_x), y(_y){}
+};
+
+int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
+int n;
+vector<string> graph;
+vector<vector<int>> vis;
+
+int solve() {
+    queue<node> Q;
+    for(int i = 0;i < n;++i){
+        for(int j = 0;j < n;++j){
+            if(graph[i][j] == '#') Q.push(node(i,j));
+            vis[i][j] = 0;
+        }
+    }
+    
+    if(Q.size() == n * n || Q.empty()) return -1;
+
+    int dis = 0;
+    while(!Q.empty()){
+        int size = Q.size();
+        while(size-- > 0){
+            node cur = Q.front();
+            Q.pop();
+            for(int i = 0;i < 4;i++){
+                int nextX = cur.x + dir[i][0];
+                int nextY = cur.y + dir[i][1];
+                if(nextX > -1 && nextX < n && nextY > -1 && nextY < n && graph[nextX][nextY] == '.' && !vis[nextX][nextY]){
+                    vis[nextX][nextY] = 1;
+                    Q.push(node(nextX,nextY));
+                }
+            }
+        }
+        if(!Q.empty()) dis += 1;
+    }
+    return dis;
+}
+
+int main(void) {
+    cin >> n;
+    string line;
+    vis.resize(n + 1, vector<int>(n + 1));
+    for (int i = 0; i < n; i++) {
+        cin >> line;
+        graph.push_back(line);
+    }
+
+    cout << solve();
+    return 0;
+}
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/solution/4.cpp b/works/life/algorithm-contest-2/solution/4.cpp
new file mode 100644
index 0000000..93c9190
--- /dev/null
+++ b/works/life/algorithm-contest-2/solution/4.cpp
@@ -0,0 +1,48 @@
+#define _CRT_SECURE_NO_WARNINGS
+#include <iostream>
+#include <cstdio>
+#include <cstring>
+#include <algorithm>
+#include <vector>
+#include <set>
+#include <map>
+#include <cmath>
+#include <unordered_map>
+#define x first
+#define y second
+#define pub push_back
+#define MP make_pair
+#define LL long long
+using namespace std;
+typedef pair<int, int> PII;
+
+const int MAXN = 1e5 + 5;
+int n, k, h[MAXN], w[MAXN];
+
+bool check(int m) {
+    if (m == 0) return true;
+    int cnt = 0;
+    for (int i = 0; i < n; i++) {
+        cnt += (h[i] / m) * (w[i] / m);
+    }
+    return cnt >= k;
+}
+
+int main(void) {
+    cin >> n >> k;
+    int mx = 0;
+    for (int i = 0; i < n; i++) {
+        scanf("%d", &h[i]);
+        scanf("%d", &w[i]);
+        mx = max(mx, max(h[i], w[i]));
+    }
+
+    int l = 0, r = mx;
+    while (l < r) {
+        int m = (l + r + 1) >> 1;
+        if (check(m)) l = m;
+        else r = m - 1;
+    }
+    cout << r;
+    return 0;
+}
\ No newline at end of file
diff --git a/works/life/algorithm-contest-2/solution/5-bf.cpp b/works/life/algorithm-contest-2/solution/5-bf.cpp
new file mode 100644
index 0000000..f197e6b
--- /dev/null
+++ b/works/life/algorithm-contest-2/solution/5-bf.cpp
@@ -0,0 +1,34 @@
+#include <iostream>
+
+int batteries[1000];
+
+int main(void) {
+  int N, K;
+  std::cin >> N >> K;
+  for (int i = 0; i < N; i++)
+    std::cin >> batteries[i];
+
+  int max = 0;
+  int max_index[4];
+
+  for (int i = 0; i < N; i++) {
+    for (int j = i + 1; j < N; j++) {
+      for (int k = j + 1; k < N; k++) {
+        for (int l = k + 1; l < N; l++) {
+          int sum = batteries[i] + batteries[j] + batteries[k] + batteries[l];
+          if (sum % K == 0 && sum > max) {
+            max = sum;
+            max_index[0] = i;
+            max_index[1] = j;
+            max_index[2] = k;
+            max_index[3] = l;
+          }
+        }
+      }
+    }
+  }
+
+  std::cout << max;
+
+  return 0;
+}
diff --git a/works/life/algorithm-contest-2/solution/5.cpp b/works/life/algorithm-contest-2/solution/5.cpp
new file mode 100644
index 0000000..b668f95
--- /dev/null
+++ b/works/life/algorithm-contest-2/solution/5.cpp
@@ -0,0 +1,49 @@
+#include <iostream>
+#include <cstdio>
+#include <cstring>
+#include <algorithm>
+#include <vector>
+#include <queue>
+#include <stack>
+#include <set>
+#include <map>
+#include <cmath>
+#include <unordered_map>
+#include <unordered_set>
+#include <string>
+#include <sstream>
+#include <climits>
+#define x first
+#define y second
+#define pub push_back
+#define mp make_pair
+#define ll long long
+using namespace std;
+typedef pair<int, int> PII;
+
+int dp[1005][5][1005];
+int n, K, a[1005];
+
+int main(void) {
+    // freopen("3.in", "r", stdin);
+    cin >> n >> K;
+    for (int i = 1; i <= n; i++) cin >> a[i];
+
+    for (int i = 0; i < 1005; i++)
+        for (int j = 0; j < 4; j++)
+            for (int k = 0; k < 1005; k++)
+                dp[i][j][k] = INT_MIN;
+
+    dp[0][0][0] = 0;
+    
+    for (int i = 1; i <= n; i++)
+        for (int j = 0; j <= 4; j++)
+            for (int k = 0; k < K; k++) {
+                if (j == 0) dp[i][j][k] = dp[i - 1][j][k];
+                else dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][((k - a[i]) % K + K) % K] + a[i]);
+            }
+                
+
+    cout << dp[n][4][0];
+    return 0;
+}
\ No newline at end of file
-- 
cgit v1.2.3