From dc1f0c4c0096013799416664894c5194dc7e1f52 Mon Sep 17 00:00:00 2001 From: Yuqian Yang Date: Fri, 28 Feb 2025 23:13:39 +0800 Subject: chore(store): move everything to store. --- store/works/solutions/acwing/1204.cpp | 31 ++++++++++ store/works/solutions/acwing/1208.cpp | 24 ++++++++ store/works/solutions/acwing/1209.cpp | 48 +++++++++++++++ store/works/solutions/acwing/1210.cpp | 37 ++++++++++++ store/works/solutions/acwing/1211.cpp | 38 ++++++++++++ store/works/solutions/acwing/1212.cpp | 46 +++++++++++++++ store/works/solutions/acwing/1215.cpp | 59 +++++++++++++++++++ store/works/solutions/acwing/1216.cpp | 19 ++++++ store/works/solutions/acwing/1217.cpp | 67 +++++++++++++++++++++ store/works/solutions/acwing/1219.cpp | 26 +++++++++ store/works/solutions/acwing/1220.cpp | 65 +++++++++++++++++++++ store/works/solutions/acwing/1221.cpp | 45 +++++++++++++++ store/works/solutions/acwing/1224.cpp | 33 +++++++++++ store/works/solutions/acwing/1226.cpp | 55 ++++++++++++++++++ store/works/solutions/acwing/1227.cpp | 50 ++++++++++++++++ store/works/solutions/acwing/1229.cpp | 106 ++++++++++++++++++++++++++++++++++ store/works/solutions/acwing/1230.cpp | 36 ++++++++++++ store/works/solutions/acwing/1233.cpp | 69 ++++++++++++++++++++++ store/works/solutions/acwing/1236.cpp | 54 +++++++++++++++++ store/works/solutions/acwing/1237.cpp | 49 ++++++++++++++++ store/works/solutions/acwing/1238.cpp | 56 ++++++++++++++++++ store/works/solutions/acwing/1239.cpp | 52 +++++++++++++++++ store/works/solutions/acwing/1240.cpp | 42 ++++++++++++++ store/works/solutions/acwing/1245.cpp | 29 ++++++++++ store/works/solutions/acwing/1246.cpp | 34 +++++++++++ store/works/solutions/acwing/1247.cpp | 39 +++++++++++++ store/works/solutions/acwing/2-2.cpp | 25 ++++++++ store/works/solutions/acwing/2.cpp | 30 ++++++++++ store/works/solutions/acwing/2065.cpp | 16 +++++ store/works/solutions/acwing/2066.cpp | 21 +++++++ store/works/solutions/acwing/2067.cpp | 22 +++++++ store/works/solutions/acwing/2068.cpp | 57 ++++++++++++++++++ store/works/solutions/acwing/2069.cpp | 82 ++++++++++++++++++++++++++ store/works/solutions/acwing/3-2.cpp | 25 ++++++++ store/works/solutions/acwing/3.cpp | 29 ++++++++++ store/works/solutions/acwing/4.cpp | 51 ++++++++++++++++ store/works/solutions/acwing/5.cpp | 49 ++++++++++++++++ store/works/solutions/acwing/7.cpp | 54 +++++++++++++++++ store/works/solutions/acwing/8.cpp | 29 ++++++++++ 39 files changed, 1699 insertions(+) create mode 100644 store/works/solutions/acwing/1204.cpp create mode 100644 store/works/solutions/acwing/1208.cpp create mode 100644 store/works/solutions/acwing/1209.cpp create mode 100644 store/works/solutions/acwing/1210.cpp create mode 100644 store/works/solutions/acwing/1211.cpp create mode 100644 store/works/solutions/acwing/1212.cpp create mode 100644 store/works/solutions/acwing/1215.cpp create mode 100644 store/works/solutions/acwing/1216.cpp create mode 100644 store/works/solutions/acwing/1217.cpp create mode 100644 store/works/solutions/acwing/1219.cpp create mode 100644 store/works/solutions/acwing/1220.cpp create mode 100644 store/works/solutions/acwing/1221.cpp create mode 100644 store/works/solutions/acwing/1224.cpp create mode 100644 store/works/solutions/acwing/1226.cpp create mode 100644 store/works/solutions/acwing/1227.cpp create mode 100644 store/works/solutions/acwing/1229.cpp create mode 100644 store/works/solutions/acwing/1230.cpp create mode 100644 store/works/solutions/acwing/1233.cpp create mode 100644 store/works/solutions/acwing/1236.cpp create mode 100644 store/works/solutions/acwing/1237.cpp create mode 100644 store/works/solutions/acwing/1238.cpp create mode 100644 store/works/solutions/acwing/1239.cpp create mode 100644 store/works/solutions/acwing/1240.cpp create mode 100644 store/works/solutions/acwing/1245.cpp create mode 100644 store/works/solutions/acwing/1246.cpp create mode 100644 store/works/solutions/acwing/1247.cpp create mode 100644 store/works/solutions/acwing/2-2.cpp create mode 100644 store/works/solutions/acwing/2.cpp create mode 100644 store/works/solutions/acwing/2065.cpp create mode 100644 store/works/solutions/acwing/2066.cpp create mode 100644 store/works/solutions/acwing/2067.cpp create mode 100644 store/works/solutions/acwing/2068.cpp create mode 100644 store/works/solutions/acwing/2069.cpp create mode 100644 store/works/solutions/acwing/3-2.cpp create mode 100644 store/works/solutions/acwing/3.cpp create mode 100644 store/works/solutions/acwing/4.cpp create mode 100644 store/works/solutions/acwing/5.cpp create mode 100644 store/works/solutions/acwing/7.cpp create mode 100644 store/works/solutions/acwing/8.cpp (limited to 'store/works/solutions/acwing') diff --git a/store/works/solutions/acwing/1204.cpp b/store/works/solutions/acwing/1204.cpp new file mode 100644 index 0000000..e3e5395 --- /dev/null +++ b/store/works/solutions/acwing/1204.cpp @@ -0,0 +1,31 @@ +#include +#include +#include + +int main() { + std::ios_base::sync_with_stdio(false); + + int repeat; + + int n; + std::cin >> n; + + std::set ids; + + while (std::cin >> n) { + auto result = ids.insert(n); + if (!result.second) + repeat = n; + } + + auto iter = ids.cbegin(); + + int last = *iter++; + + while (++last == *iter++) + ; + + std::cout << last << ' ' << repeat; + + return 0; +} diff --git a/store/works/solutions/acwing/1208.cpp b/store/works/solutions/acwing/1208.cpp new file mode 100644 index 0000000..84f60f1 --- /dev/null +++ b/store/works/solutions/acwing/1208.cpp @@ -0,0 +1,24 @@ +#include +#include + +inline void toggle(char &c) { c = c == '*' ? 'o' : '*'; } + +int main() { + std::string original, expected; + std::cin >> original >> expected; + + int size = original.size(); + + int count = 0; + + for (int i = 0; i < size - 1; i++) { + if (original[i] != expected[i]) { + count++; + toggle(original[i + 1]); + } + } + + std::cout << count; + + return 0; +} diff --git a/store/works/solutions/acwing/1209.cpp b/store/works/solutions/acwing/1209.cpp new file mode 100644 index 0000000..3f3ff7a --- /dev/null +++ b/store/works/solutions/acwing/1209.cpp @@ -0,0 +1,48 @@ +#include +#include +#include + +int number; +int count = 0; +std::array used{false}; +std::array current; + +int calc(int start, int end) { + int n = 0; + for (int i = start; i < end; i++) { + n *= 10; + n += current[i]; + } + return n; +} + +void dfs(int n) { + if (n == 9) { + for (int i = 1; i <= 7; i++) + for (int j = i + 1; j <= 8; j++) { + int a = calc(0, i); + int b = calc(i, j); + int c = calc(j, 9); + if ((number - a) * b == c) { + count++; + } + } + return; + } + + for (int i = 1; i <= 9; i++) { + if (!used[i]) { + used[i] = true; + current[n] = i; + dfs(n + 1); + used[i] = false; + } + } +} + +int main() { + std::cin >> number; + dfs(0); + std::cout << count; + return 0; +} diff --git a/store/works/solutions/acwing/1210.cpp b/store/works/solutions/acwing/1210.cpp new file mode 100644 index 0000000..4c9c0ba --- /dev/null +++ b/store/works/solutions/acwing/1210.cpp @@ -0,0 +1,37 @@ +#include + +int N; +int seq[10000]; + +int main() { + std::cin >> N; + for (int i = 0; i < N; i++) { + std::cin >> seq[i]; + } + + int count = N; + + for (int start = 0; start < N; start++) { + int min = seq[start], max = seq[start]; + + for (int end = start + 1; end < N; end++) { + int current = seq[end]; + + if (current > max) { + max = current; + } + + if (current < min) { + min = current; + } + + if (max - min == end - start) { + count++; + } + } + } + + std::cout << count; + + return 0; +} diff --git a/store/works/solutions/acwing/1211.cpp b/store/works/solutions/acwing/1211.cpp new file mode 100644 index 0000000..18c564e --- /dev/null +++ b/store/works/solutions/acwing/1211.cpp @@ -0,0 +1,38 @@ +#include +#include + +int main() { + std::ios_base::sync_with_stdio(false); + + int n; + std::cin >> n; + + int fever_ant; + std::cin >> fever_ant; + + int fever_position = std::abs(fever_ant); + + int left = 0, right = 0; + + for (int i = 1; i < n; i++) { + int ant; + std::cin >> ant; + int position = std::abs(ant); + if (position < fever_position && ant > 0) { + left++; + } + if (position > fever_position && ant < 0) { + right++; + } + } + + if (fever_ant < 0 && left == 0) { + std::cout << 1; + } else if (fever_ant > 0 && right == 0) { + std::cout << 1; + } else { + std::cout << left + right + 1; + } + + return 0; +} diff --git a/store/works/solutions/acwing/1212.cpp b/store/works/solutions/acwing/1212.cpp new file mode 100644 index 0000000..e60e993 --- /dev/null +++ b/store/works/solutions/acwing/1212.cpp @@ -0,0 +1,46 @@ +#include + +int n, m, k; +int v[51][51]; +int f[51][51][14][14]; // row col count max +const int MOD = 1000000007; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin >> n >> m >> k; + + for (int i = 1; i <= n; i++) + for (int j = 1; j <= m; j++) { + std::cin >> v[i][j]; + v[i][j]++; + } + + f[1][1][0][0] = 1; + f[1][1][1][v[1][1]] = 1; + + for (int i = 1; i <= n; i++) { + for (int j = 1; j <= m; j++) { + for (int c = 0; c <= k; c++) { + for (int m = 0; m <= 13; m++) { + f[i][j][c][m] = (f[i][j][c][m] + f[i][j - 1][c][m]) % MOD; + f[i][j][c][m] = (f[i][j][c][m] + f[i - 1][j][c][m]) % MOD; + + if (c && v[i][j] == m) { + for (int max = 0; max < v[i][j]; max++) { + f[i][j][c][m] = (f[i][j][c][m] + f[i][j - 1][c - 1][max]) % MOD; + f[i][j][c][m] = (f[i][j][c][m] + f[i - 1][j][c - 1][max]) % MOD; + } + } + } + } + } + } + + int result = 0; + for (int i = 1; i <= 13; i++) + result = (result + f[n][m][k][i]) % MOD; + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1215.cpp b/store/works/solutions/acwing/1215.cpp new file mode 100644 index 0000000..d6832b3 --- /dev/null +++ b/store/works/solutions/acwing/1215.cpp @@ -0,0 +1,59 @@ +#include +#include + +const int MAX = 1000010; // Why 1000001 is not ok!? + +int n; +int H[100001]; +int bit[MAX]; +int reverse_pairs[100001]; + +int lowbit(int x) { return x & -x; } + +void add(int x, int y) { + for (int i = x; i < MAX; i += lowbit(i)) { + bit[i] += y; + } +} + +int query(int x) { + int result = 0; + for (int i = x; i != 0; i -= lowbit(i)) { + result += bit[i]; + } + return result; +} + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> n; + + for (int i = 1; i <= n; i++) { + std::cin >> H[i]; + H[i]++; + } + + for (int i = 1; i <= n; i++) { + add(H[i], 1); + reverse_pairs[i] = i - query(H[i]); + } + + std::memset(bit, 0, sizeof bit); + + for (int i = n; i >= 1; i--) { + add(H[i], 1); + reverse_pairs[i] += query(H[i] - 1); + } + + long long result = 0; + + for (int i = 1; i <= n; i++) { + result += (1LL + reverse_pairs[i]) * reverse_pairs[i] / 2; + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1216.cpp b/store/works/solutions/acwing/1216.cpp new file mode 100644 index 0000000..61d1848 --- /dev/null +++ b/store/works/solutions/acwing/1216.cpp @@ -0,0 +1,19 @@ +#include + +int main() { + int n; + std::cin >> n; + + int result = n; + + while (n >= 3) { + int exchange = n / 3; + int rest = n % 3; + result += exchange; + n = exchange + rest; + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1217.cpp b/store/works/solutions/acwing/1217.cpp new file mode 100644 index 0000000..e729547 --- /dev/null +++ b/store/works/solutions/acwing/1217.cpp @@ -0,0 +1,67 @@ +#include +#include + +const int MOD = 1e9 + 7; + +int n, m; +bool conflict_matrix[7][7]; + +long long f[7]; +long long temp[7]; + +int back(int x) { + switch (x) { + case 1: + return 4; + case 2: + return 5; + case 3: + return 6; + case 4: + return 1; + case 5: + return 2; + case 6: + return 3; + default: + return 0; + } +} + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> n >> m; + + for (int i = 0; i < m; i++) { + int a, b; + std::cin >> a >> b; + conflict_matrix[a][b] = true; + conflict_matrix[b][a] = true; + } + + for (int i = 1; i <= 6; i++) + f[i] = 4; + + for (int c = 2; c <= n; c++) { + for (int up = 1; up <= 6; up++) { + for (int down = 1; down <= 6; down++) { + if (!conflict_matrix[back(down)][up]) { + temp[up] = (temp[up] + f[down] * 4) % MOD; + } + } + } + std::memcpy(f, temp, sizeof f); + std::memset(temp, 0, sizeof temp); + } + + long long result = 0; + for (int i = 1; i <= 6; i++) { + result = (result + f[i]) % MOD; + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1219.cpp b/store/works/solutions/acwing/1219.cpp new file mode 100644 index 0000000..9538e94 --- /dev/null +++ b/store/works/solutions/acwing/1219.cpp @@ -0,0 +1,26 @@ +#include +#include + +int w, m, n; + +int row(int x) { return (x - 1) / w; } + +int col(int x, int r) { + int result = (x - 1) % w; + if (r % 2) { + result = w - 1 - result; + } + return result; +} + +int main() { + std::cin >> w >> m >> n; + int m_r = row(m); + int m_c = col(m, m_r); + int n_r = row(n); + int n_c = col(n, n_r); + + std::cout << std::abs(m_r - n_r) + std::abs(m_c - n_c); + + return 0; +} diff --git a/store/works/solutions/acwing/1220.cpp b/store/works/solutions/acwing/1220.cpp new file mode 100644 index 0000000..443ed43 --- /dev/null +++ b/store/works/solutions/acwing/1220.cpp @@ -0,0 +1,65 @@ +#include +#include + +const int N = 100010; + +struct Node { + int w; + std::vector children; +}; + +int n; +Node nodes[N]; +bool visited[N]; +long long contain_root[N]; +long long contain_or_not_contain_root[N]; + +void dfs(int i) { + visited[i] = true; + long long this_contain_root = nodes[i].w; + long long this_contain_or_not_contain_root = nodes[i].w; + + for (auto next : nodes[i].children) { + if (!visited[next]) { + dfs(next); + if (contain_root[next] > 0) { + this_contain_root += contain_root[next]; + } + if (contain_or_not_contain_root[next] > + this_contain_or_not_contain_root) { + this_contain_or_not_contain_root = contain_or_not_contain_root[next]; + } + } + } + + if (this_contain_root > this_contain_or_not_contain_root) { + this_contain_or_not_contain_root = this_contain_root; + } + + contain_root[i] = this_contain_root; + contain_or_not_contain_root[i] = this_contain_or_not_contain_root; +} + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> n; + + for (int i = 1; i <= n; i++) { + std::cin >> nodes[i].w; + } + + for (int i = 1; i < n; i++) { + int a, b; + std::cin >> a >> b; + nodes[a].children.push_back(b); + nodes[b].children.push_back(a); + } + + dfs(1); + + std::cout << contain_or_not_contain_root[1]; + + return 0; +} diff --git a/store/works/solutions/acwing/1221.cpp b/store/works/solutions/acwing/1221.cpp new file mode 100644 index 0000000..9ba4229 --- /dev/null +++ b/store/works/solutions/acwing/1221.cpp @@ -0,0 +1,45 @@ +#include +#include + +const int M = 5000010; +const int SM = std::sqrt(M / 2); + +int s[M]; + +int main() { + int n; + std::cin >> n; + + for (int i = 0; i <= SM; i++) { + const int i2 = i * i; + const int SMB = M - i2; + for (int j = i; j * j < SMB; j++) { + const int a = i2 + j * j; + + if (s[a] == 0) { + s[a] = i + 1; + } + } + } + + int sm = std::sqrt(n); + + for (int a = 0; a <= sm; a++) { + int as = a * a; + int bsm = n - 3 * a * a; + for (int b = a; b * b <= bsm; b++) { + int bs = b * b + as; + + int c = s[n - bs]; + + if (c != 0) { + c = c - 1; + std::cout << a << ' ' << b << ' ' << c << ' ' + << std::sqrt(n - bs - c * c); + return 0; + } + } + } + + return 0; +} diff --git a/store/works/solutions/acwing/1224.cpp b/store/works/solutions/acwing/1224.cpp new file mode 100644 index 0000000..8cdd9f0 --- /dev/null +++ b/store/works/solutions/acwing/1224.cpp @@ -0,0 +1,33 @@ +#include +#include + +int N; +int x[10010]; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N; + for (int i = 1; i <= N; i++) { + std::cin >> x[i]; + } + + int result = 0; + + for (int i = 1; i <= N - 1; i++) { + if (x[i] != i) { + for (int j = i + 1; j <= N; j++) { + if (x[j] == i) { + x[j] = x[i]; + result++; + break; + } + } + } + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1226.cpp b/store/works/solutions/acwing/1226.cpp new file mode 100644 index 0000000..cbfea98 --- /dev/null +++ b/store/works/solutions/acwing/1226.cpp @@ -0,0 +1,55 @@ +#include + +int gcd(int a, int b) { + if (b == 0) + return a; + return gcd(b, a % b); +} + +int N; +int A[110]; + +const int M = 10000; + +bool f[M + 10]; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N; + + for (int i = 1; i <= N; i++) { + std::cin >> A[i]; + } + + int a = A[1]; + + for (int i = 2; i <= N; i++) { + a = gcd(a, A[i]); + } + + if (a != 1) { + std::cout << "INF"; + return 0; + } + + f[0] = true; + + for (int i = 1; i <= N; i++) { + for (int w = A[i]; w <= M; w++) { + f[w] = f[w] || f[w - A[i]]; + } + } + + int count = 0; + + for (int i = 1; i <= M; i++) { + if (f[i] == false) + count++; + } + + std::cout << count; + + return 0; +} diff --git a/store/works/solutions/acwing/1227.cpp b/store/works/solutions/acwing/1227.cpp new file mode 100644 index 0000000..ff14be2 --- /dev/null +++ b/store/works/solutions/acwing/1227.cpp @@ -0,0 +1,50 @@ +#include + +const int M = 1e5 + 10; + +int N, K; +int H[M]; +int W[M]; + +bool check(int l) { + if (l == 0) + return true; + + int count = 0; + + for (int i = 1; i <= N; i++) { + count += (H[i] / l) * (W[i] / l); + if (K <= count) { + return true; + } + } + + return false; +} + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N >> K; + + for (int i = 1; i <= N; i++) { + std::cin >> H[i] >> W[i]; + } + + int l = 0, r = M; + + while (l != r) { + int m = l + ((r - l + 1) / 2); + + if (check(m)) { + l = m; + } else { + r = m - 1; + } + } + + std::cout << l; + + return 0; +} diff --git a/store/works/solutions/acwing/1229.cpp b/store/works/solutions/acwing/1229.cpp new file mode 100644 index 0000000..e3b16ba --- /dev/null +++ b/store/works/solutions/acwing/1229.cpp @@ -0,0 +1,106 @@ +#include +#include +#include + +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 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/store/works/solutions/acwing/1230.cpp b/store/works/solutions/acwing/1230.cpp new file mode 100644 index 0000000..958cbdd --- /dev/null +++ b/store/works/solutions/acwing/1230.cpp @@ -0,0 +1,36 @@ +#include + +using ll = long long; + +const int M = 100010; + +int N, K; +ll p; +int c[M]; +ll result; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N >> K; + + c[0] = 1; + + for (int i = 1; i <= N; i++) { + int a; + std::cin >> a; + + p += a; + + int r = p % K; + + result += c[r]; + + c[r]++; + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1233.cpp b/store/works/solutions/acwing/1233.cpp new file mode 100644 index 0000000..117b2fb --- /dev/null +++ b/store/works/solutions/acwing/1233.cpp @@ -0,0 +1,69 @@ +#include +#include + +const int M = 1010; + +int N; +char map[M][M]; +bool visited[M][M]; + +int not_sink_count; + +const std::pair moves[]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; + +void dfs(int r, int c) { + if (visited[r][c]) + return; + if (map[r][c] != '#') + return; + + visited[r][c] = true; + + bool sink = false; + + for (const auto &move : moves) { + if (map[r + move.first][c + move.second] == '.') { + sink = true; + break; + } + } + + if (!sink) { + not_sink_count++; + } + + for (const auto &move : moves) { + dfs(r + move.first, c + move.second); + } +} + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N; + + for (int i = 1; i <= N; i++) { + for (int j = 1; j <= N; j++) { + std::cin >> map[i][j]; + } + } + + int result = 0; + + for (int i = 1; i <= N; i++) { + for (int j = 1; j <= N; j++) { + if (map[i][j] == '#' && !visited[i][j]) { + dfs(i, j); + if (not_sink_count == 0) { + result++; + } + not_sink_count = 0; + } + } + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1236.cpp b/store/works/solutions/acwing/1236.cpp new file mode 100644 index 0000000..a89a890 --- /dev/null +++ b/store/works/solutions/acwing/1236.cpp @@ -0,0 +1,54 @@ +#include + +const int MAX = 100000; +const int MM = 100010; + +int N; + +long long ca[MM]; +long long cb[MM]; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N; + + for (int i = 0; i < N; i++) { + int a; + std::cin >> a; + ca[a]++; + } + + for (int n = 1; n <= MAX; n++) { + ca[n] = ca[n - 1] + ca[n]; + } + + for (int i = 0; i < N; i++) { + int b; + std::cin >> b; + cb[b]++; + } + + for (int n = 1; n <= MAX; n++) { + cb[n] *= ca[n - 1]; + } + + for (int n = 2; n <= MAX; n++) { + cb[n] = cb[n - 1] + cb[n]; + } + + long long result = 0; + + for (int i = 0; i < N; i++) { + int c; + std::cin >> c; + if (c >= 2) { + result += cb[c - 1]; + } + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1237.cpp b/store/works/solutions/acwing/1237.cpp new file mode 100644 index 0000000..a3b8810 --- /dev/null +++ b/store/works/solutions/acwing/1237.cpp @@ -0,0 +1,49 @@ +#include +#include + +using ll = long long; + +int main() { + ll X, Y; + std::cin >> X >> Y; + + ll result = 0; + + if (X == 0 && Y == 0) { + return 0; + } + + if (std::abs(X) > std::abs(Y) || + (std::abs(X) == std::abs(Y) && !(X < 0 && Y < 0))) { + ll c = std::abs(X); + + result += ((c - 1) * 4 + 2) * (c - 1); + + if (X > 0) { + result += (c * 2 - 1) * 2; + result += c * 2; + result += (c - Y); + } else { + result += (c * 2 - 1); + result += (Y - (-c + 1)); + } + + } else { + ll c = std::abs(Y); + + result += ((c - 1) * 4 + 2) * (c - 1); + + if (Y > 0) { + result += (c * 2 - 1) * 2; + result += (X - (-c)); + } else { + result += (c * 2 - 1) * 2; + result += c * 2 * 2; + result += c - X; + } + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1238.cpp b/store/works/solutions/acwing/1238.cpp new file mode 100644 index 0000000..2c9d899 --- /dev/null +++ b/store/works/solutions/acwing/1238.cpp @@ -0,0 +1,56 @@ +#include +#include +#include + +const int M = 100010; + +int N, D, K; + +std::map> vote_map; + +bool check(const std::multiset &v) { + auto iter1 = v.cbegin(); + auto iter2 = v.cbegin(); + + const auto end = v.cend(); + + int count = 1; + + while (iter2 != end) { + while (*iter2 - *iter1 >= D) { + ++iter1; + count--; + } + + if (count >= K) + return true; + + ++iter2; + count++; + } + + return false; +} + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + std::cin >> N >> D >> K; + + for (int i = 1; i <= N; i++) { + int ts, id; + std::cin >> ts >> id; + vote_map[id].insert(ts); + } + + int result; + + for (const auto &vote : vote_map) { + if (check(vote.second)) { + std::cout << vote.first << "\n"; + } + } + + return 0; +} diff --git a/store/works/solutions/acwing/1239.cpp b/store/works/solutions/acwing/1239.cpp new file mode 100644 index 0000000..c670cd4 --- /dev/null +++ b/store/works/solutions/acwing/1239.cpp @@ -0,0 +1,52 @@ +#include +#include + +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; +} diff --git a/store/works/solutions/acwing/1240.cpp b/store/works/solutions/acwing/1240.cpp new file mode 100644 index 0000000..8ebae33 --- /dev/null +++ b/store/works/solutions/acwing/1240.cpp @@ -0,0 +1,42 @@ +#include + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + int n; + std::cin >> n; + + int current_count = 0; + int current_level_count = 1; + int current_level = 1; + long long current_sum = 0; + long long max_sum = -1000000; + int result = 1; + + for (int i = 0; i < n; i++) { + long long a; + std::cin >> a; + current_sum += a; + current_count++; + + if (current_count == current_level_count) { + if (current_sum > max_sum) { + max_sum = current_sum; + result = current_level; + } + current_count = 0; + current_level_count *= 2; + current_sum = 0; + current_level++; + } + } + + if (current_count && current_sum > max_sum) { + result = current_level; + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/1245.cpp b/store/works/solutions/acwing/1245.cpp new file mode 100644 index 0000000..ba51a8f --- /dev/null +++ b/store/works/solutions/acwing/1245.cpp @@ -0,0 +1,29 @@ +#include + +bool check(int n) { + while (n != 0) { + int k = n % 10; + if (k == 2 || k == 0 || k == 1 || k == 9) { + return true; + } + n /= 10; + } + return false; +} + +int main() { + int n; + std::cin >> n; + + long long sum; + + for (int i = 1; i <= n; i++) { + if (check(i)) { + sum += i; + } + } + + std::cout << sum; + + return 0; +} diff --git a/store/works/solutions/acwing/1246.cpp b/store/works/solutions/acwing/1246.cpp new file mode 100644 index 0000000..5c0454c --- /dev/null +++ b/store/works/solutions/acwing/1246.cpp @@ -0,0 +1,34 @@ +#include +#include +#include + +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; +} \ No newline at end of file diff --git a/store/works/solutions/acwing/1247.cpp b/store/works/solutions/acwing/1247.cpp new file mode 100644 index 0000000..1fd4412 --- /dev/null +++ b/store/works/solutions/acwing/1247.cpp @@ -0,0 +1,39 @@ +#include +#include + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + int N, M; + std::cin >> N >> M; + + long long result = 0; + + long long min = 1e9 + 1; + long long max = -1e9 - 1; + + for (int i = 0; i < N + M + 1; i++) { + long long a; + std::cin >> a; + max = std::max(a, max); + min = std::min(a, min); + if (M == 0) { + result += a; + } else { + result += std::abs(a); + } + } + + if (M != 0 && max < 0) { + result += 2 * max; + } + + if (M != 0 && min > 0) { + result -= 2 * min; + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/2-2.cpp b/store/works/solutions/acwing/2-2.cpp new file mode 100644 index 0000000..fb0fb3b --- /dev/null +++ b/store/works/solutions/acwing/2-2.cpp @@ -0,0 +1,25 @@ +#include +#include + +int N, V; +int v[1001]; +int w[1001]; +int states[1001]; + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i]; + } + + for (int i = 1; i <= N; i++) { + for (int j = V; j >= v[i]; j--) { + states[j] = std::max(states[j], states[j - v[i]] + w[i]); + } + } + + std::cout << states[V]; + + return 0; +} diff --git a/store/works/solutions/acwing/2.cpp b/store/works/solutions/acwing/2.cpp new file mode 100644 index 0000000..1a75c19 --- /dev/null +++ b/store/works/solutions/acwing/2.cpp @@ -0,0 +1,30 @@ +#include +#include + +int N, V; +int v[1001]; +int w[1001]; +int states[1001][1001]; + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i]; + } + + for (int i = 1; i <= N; i++) { + for (int j = V; j >= 0; j--) { + if (j >= v[i]) { + states[i][j] = + std::max(states[i - 1][j], states[i - 1][j - v[i]] + w[i]); + } else { + states[i][j] = states[i - 1][j]; + } + } + } + + std::cout << states[N][V]; + + return 0; +} diff --git a/store/works/solutions/acwing/2065.cpp b/store/works/solutions/acwing/2065.cpp new file mode 100644 index 0000000..a0c47c2 --- /dev/null +++ b/store/works/solutions/acwing/2065.cpp @@ -0,0 +1,16 @@ +#include + +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 /= 2; + } + + return 0; +} \ No newline at end of file diff --git a/store/works/solutions/acwing/2066.cpp b/store/works/solutions/acwing/2066.cpp new file mode 100644 index 0000000..7a6132b --- /dev/null +++ b/store/works/solutions/acwing/2066.cpp @@ -0,0 +1,21 @@ +#include +#include + +int main() { + std::string input; + std::cin >> input; + std::string result; + + for (int i = 0; i < input.size(); i++) { + if (std::isalpha(input[i])) { + result.push_back(input[i]); + } else { + int c = input[i] - '1'; + result.append(c, input[i - 1]); + } + } + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/2067.cpp b/store/works/solutions/acwing/2067.cpp new file mode 100644 index 0000000..3ebd61d --- /dev/null +++ b/store/works/solutions/acwing/2067.cpp @@ -0,0 +1,22 @@ +#include + +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/store/works/solutions/acwing/2068.cpp b/store/works/solutions/acwing/2068.cpp new file mode 100644 index 0000000..592f43f --- /dev/null +++ b/store/works/solutions/acwing/2068.cpp @@ -0,0 +1,57 @@ +#include +#include +#include +#include + +int n, K; +int A[100010]; +int c[11][100010]; +long long result; + +int CalcDigitCount(int n) { + int c = 0; + while (n != 0) { + c++; + n /= 10; + } + return c; +} + +void work() { + for (int i = 0; i < n; i++) { + result += c[CalcDigitCount(A[i])][(K - A[i] % K) % K]; + // Wrong Code I don't know why! + // int a = A[i]; + // for (int j = 1; j < 11; j++) { + // a *= 10; + // a %= K; + // c[j][a]++; + // } + for (int j = 0, power = 1; j < 11; j++) { + c[j][power * 1ll * A[i] % K]++; + power = power * 10 % K; + } + } +} + +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]; + } + + work(); + + std::reverse(A, A + n); + std::memset(c, 0, sizeof c); + + work(); + + std::cout << result; + + return 0; +} diff --git a/store/works/solutions/acwing/2069.cpp b/store/works/solutions/acwing/2069.cpp new file mode 100644 index 0000000..fbfa6d2 --- /dev/null +++ b/store/works/solutions/acwing/2069.cpp @@ -0,0 +1,82 @@ +#include +#include + +struct Node { + int m = 0; + Node *set; + Node *left = nullptr; + Node *right = nullptr; + + Node() : set(this) {} + + void SetParent(Node *parent, bool l) { + set = parent; + l ? parent->left = this : parent->right = this; + } + + Node *GetSetRepresentative() { + Node *r = this; + while (r->set != r) { + r = r->set; + } + set = r; + return set; + } + + bool has_dfs = false; + + void Dfs() { + if (has_dfs) + return; + has_dfs = true; + if (left != nullptr) + left->Dfs(m); + if (right != nullptr) + right->Dfs(m); + } + + void Dfs(int c) { + m += c; + if (left != nullptr) + left->Dfs(m); + if (right != nullptr) + right->Dfs(m); + } +}; + +Node nodes[10010]; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + int n, m; + + std::cin >> n >> m; + + for (int i = 0; i < m; i++) { + int operation, a, b; + std::cin >> operation >> a >> b; + + if (operation == 1) { + auto ra = nodes[a].GetSetRepresentative(), + rb = nodes[b].GetSetRepresentative(); + + if (ra != rb) { + auto node = new Node; + ra->SetParent(node, true); + rb->SetParent(node, false); + } + } else { + nodes[a].GetSetRepresentative()->m += b; + } + } + + for (int i = 1; i <= n; i++) { + auto &node = nodes[i]; + node.GetSetRepresentative()->Dfs(); + std::cout << node.m << ' '; + } + + return 0; +} diff --git a/store/works/solutions/acwing/3-2.cpp b/store/works/solutions/acwing/3-2.cpp new file mode 100644 index 0000000..c099838 --- /dev/null +++ b/store/works/solutions/acwing/3-2.cpp @@ -0,0 +1,25 @@ +#include +#include + +int N, V; +int v[1001]; +int w[1001]; +int states[1001]; + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i]; + } + + for (int i = 1; i <= N; i++) { + for (int j = v[i]; j <= V; j++) { + states[j] = std::max(states[j], states[j - v[i]] + w[i]); + } + } + + std::cout << states[V]; + + return 0; +} diff --git a/store/works/solutions/acwing/3.cpp b/store/works/solutions/acwing/3.cpp new file mode 100644 index 0000000..21bd8dc --- /dev/null +++ b/store/works/solutions/acwing/3.cpp @@ -0,0 +1,29 @@ +#include +#include + +int N, V; +int v[1001]; +int w[1001]; +int states[1001][1001]; + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i]; + } + + for (int i = 1; i <= N; i++) { + for (int j = 0; j <= V; j++) { + if (j >= v[i]) { + states[i][j] = std::max(states[i - 1][j], states[i][j - v[i]] + w[i]); + } else { + states[i][j] = states[i - 1][j]; + } + } + } + + std::cout << states[N][V]; + + return 0; +} diff --git a/store/works/solutions/acwing/4.cpp b/store/works/solutions/acwing/4.cpp new file mode 100644 index 0000000..3270402 --- /dev/null +++ b/store/works/solutions/acwing/4.cpp @@ -0,0 +1,51 @@ +#include +#include + +int N, V; +int v[101]; +int w[101]; +int s[101]; +int states[101]; + +void CompletePack(int v, int w) { + for (int j = v; j <= V; j++) { + states[j] = std::max(states[j], states[j - v] + w); + } +} + +void ZeroOnePack(int v, int w) { + for (int j = V; j >= v; j--) { + states[j] = std::max(states[j], states[j - v] + w); + } +} + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i] >> s[i]; + } + + for (int i = 1; i <= N; i++) { + if (v[i] * s[i] >= V) { + CompletePack(v[i], w[i]); + } else { + int k = 1; + int amount = s[i]; + + while (k < amount) { + ZeroOnePack(k * v[i], k * w[i]); + amount -= k; + k *= 2; + } + + if (amount != 0) { + ZeroOnePack(amount * v[i], amount * w[i]); + } + } + } + + std::cout << states[V]; + + return 0; +} diff --git a/store/works/solutions/acwing/5.cpp b/store/works/solutions/acwing/5.cpp new file mode 100644 index 0000000..a88fba6 --- /dev/null +++ b/store/works/solutions/acwing/5.cpp @@ -0,0 +1,49 @@ +#include +#include + +int N, V; +int v[1001]; +int w[1001]; +int s[1001]; +int states[2001]; + +void CompletePack(int v, int w) { + for (int j = v; j <= V; j++) { + states[j] = std::max(states[j], states[j - v] + w); + } +} + +void ZeroOnePack(int v, int w) { + for (int j = V; j >= v; j--) { + states[j] = std::max(states[j], states[j - v] + w); + } +} + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i] >> s[i]; + } + + for (int i = 1; i <= N; i++) { + if (v[i] * s[i] >= V) { + CompletePack(v[i], w[i]); + } else { + int k = 1; + int amount = s[i]; + + while (k < amount) { + ZeroOnePack(k * v[i], k * w[i]); + amount -= k; + k *= 2; + } + + ZeroOnePack(amount * v[i], amount * w[i]); + } + } + + std::cout << states[V]; + + return 0; +} diff --git a/store/works/solutions/acwing/7.cpp b/store/works/solutions/acwing/7.cpp new file mode 100644 index 0000000..fcc0fb1 --- /dev/null +++ b/store/works/solutions/acwing/7.cpp @@ -0,0 +1,54 @@ +#include +#include + +int N, V; +int v[1001]; +int w[1001]; +int s[1001]; +int states[1001]; + +void CompletePack(int v, int w) { + for (int j = v; j <= V; j++) { + states[j] = std::max(states[j], states[j - v] + w); + } +} + +void ZeroOnePack(int v, int w) { + for (int j = V; j >= v; j--) { + states[j] = std::max(states[j], states[j - v] + w); + } +} + +void MultiplePack(int v, int w, int s) { + int k = 1; + + while (k < s) { + ZeroOnePack(k * v, k * w); + s -= k; + k *= 2; + } + + ZeroOnePack(s * v, s * w); +} + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i] >> s[i]; + } + + for (int i = 1; i <= N; i++) { + if (s[i] < 0) { + ZeroOnePack(v[i], w[i]); + } else if (s[i] == 0) { + CompletePack(v[i], w[i]); + } else { + MultiplePack(v[i], w[i], s[i]); + } + } + + std::cout << states[V]; + + return 0; +} diff --git a/store/works/solutions/acwing/8.cpp b/store/works/solutions/acwing/8.cpp new file mode 100644 index 0000000..f62d21e --- /dev/null +++ b/store/works/solutions/acwing/8.cpp @@ -0,0 +1,29 @@ +#include +#include + +int N, V, M; +int v[1001]; +int w[1001]; +int m[1001]; +int states[101][101]; + +int main() { + std::cin >> N >> V >> M; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> m[i] >> w[i]; + } + + for (int i = 1; i <= N; i++) { + for (int j = V; j >= v[i]; j--) { + for (int k = M; k >= m[i]; k--) { + states[j][k] = + std::max(states[j][k], states[j - v[i]][k - m[i]] + w[i]); + } + } + } + + std::cout << states[V][M]; + + return 0; +} \ No newline at end of file -- cgit v1.2.3