5 files changed, 230 insertions, 0 deletions
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;
+}