diff options
Diffstat (limited to 'works/solutions/acwing')
39 files changed, 0 insertions, 1699 deletions
diff --git a/works/solutions/acwing/1204.cpp b/works/solutions/acwing/1204.cpp deleted file mode 100644 index e3e5395..0000000 --- a/works/solutions/acwing/1204.cpp +++ /dev/null @@ -1,31 +0,0 @@ -#include <ios>
-#include <iostream>
-#include <set>
-
-int main() {
- std::ios_base::sync_with_stdio(false);
-
- int repeat;
-
- int n;
- std::cin >> n;
-
- std::set<int> 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/works/solutions/acwing/1208.cpp b/works/solutions/acwing/1208.cpp deleted file mode 100644 index 84f60f1..0000000 --- a/works/solutions/acwing/1208.cpp +++ /dev/null @@ -1,24 +0,0 @@ -#include <iostream>
-#include <string>
-
-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/works/solutions/acwing/1209.cpp b/works/solutions/acwing/1209.cpp deleted file mode 100644 index 3f3ff7a..0000000 --- a/works/solutions/acwing/1209.cpp +++ /dev/null @@ -1,48 +0,0 @@ -#include <array>
-#include <iostream>
-#include <vector>
-
-int number;
-int count = 0;
-std::array<bool, 10> used{false};
-std::array<int, 9> 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/works/solutions/acwing/1210.cpp b/works/solutions/acwing/1210.cpp deleted file mode 100644 index 4c9c0ba..0000000 --- a/works/solutions/acwing/1210.cpp +++ /dev/null @@ -1,37 +0,0 @@ -#include <iostream>
-
-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/works/solutions/acwing/1211.cpp b/works/solutions/acwing/1211.cpp deleted file mode 100644 index 18c564e..0000000 --- a/works/solutions/acwing/1211.cpp +++ /dev/null @@ -1,38 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-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/works/solutions/acwing/1212.cpp b/works/solutions/acwing/1212.cpp deleted file mode 100644 index e60e993..0000000 --- a/works/solutions/acwing/1212.cpp +++ /dev/null @@ -1,46 +0,0 @@ -#include <iostream>
-
-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/works/solutions/acwing/1215.cpp b/works/solutions/acwing/1215.cpp deleted file mode 100644 index d6832b3..0000000 --- a/works/solutions/acwing/1215.cpp +++ /dev/null @@ -1,59 +0,0 @@ -#include <cstring>
-#include <iostream>
-
-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/works/solutions/acwing/1216.cpp b/works/solutions/acwing/1216.cpp deleted file mode 100644 index 61d1848..0000000 --- a/works/solutions/acwing/1216.cpp +++ /dev/null @@ -1,19 +0,0 @@ -#include <iostream>
-
-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/works/solutions/acwing/1217.cpp b/works/solutions/acwing/1217.cpp deleted file mode 100644 index e729547..0000000 --- a/works/solutions/acwing/1217.cpp +++ /dev/null @@ -1,67 +0,0 @@ -#include <cstring>
-#include <iostream>
-
-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/works/solutions/acwing/1219.cpp b/works/solutions/acwing/1219.cpp deleted file mode 100644 index 9538e94..0000000 --- a/works/solutions/acwing/1219.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-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/works/solutions/acwing/1220.cpp b/works/solutions/acwing/1220.cpp deleted file mode 100644 index 443ed43..0000000 --- a/works/solutions/acwing/1220.cpp +++ /dev/null @@ -1,65 +0,0 @@ -#include <iostream>
-#include <vector>
-
-const int N = 100010;
-
-struct Node {
- int w;
- std::vector<int> 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/works/solutions/acwing/1221.cpp b/works/solutions/acwing/1221.cpp deleted file mode 100644 index 9ba4229..0000000 --- a/works/solutions/acwing/1221.cpp +++ /dev/null @@ -1,45 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-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/works/solutions/acwing/1224.cpp b/works/solutions/acwing/1224.cpp deleted file mode 100644 index 8cdd9f0..0000000 --- a/works/solutions/acwing/1224.cpp +++ /dev/null @@ -1,33 +0,0 @@ -#include <iostream> -#include <utility> - -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/works/solutions/acwing/1226.cpp b/works/solutions/acwing/1226.cpp deleted file mode 100644 index cbfea98..0000000 --- a/works/solutions/acwing/1226.cpp +++ /dev/null @@ -1,55 +0,0 @@ -#include <iostream> - -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/works/solutions/acwing/1227.cpp b/works/solutions/acwing/1227.cpp deleted file mode 100644 index ff14be2..0000000 --- a/works/solutions/acwing/1227.cpp +++ /dev/null @@ -1,50 +0,0 @@ -#include <iostream> - -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/works/solutions/acwing/1229.cpp b/works/solutions/acwing/1229.cpp deleted file mode 100644 index e3b16ba..0000000 --- a/works/solutions/acwing/1229.cpp +++ /dev/null @@ -1,106 +0,0 @@ -#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/solutions/acwing/1230.cpp b/works/solutions/acwing/1230.cpp deleted file mode 100644 index 958cbdd..0000000 --- a/works/solutions/acwing/1230.cpp +++ /dev/null @@ -1,36 +0,0 @@ -#include <iostream>
-
-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/works/solutions/acwing/1233.cpp b/works/solutions/acwing/1233.cpp deleted file mode 100644 index 117b2fb..0000000 --- a/works/solutions/acwing/1233.cpp +++ /dev/null @@ -1,69 +0,0 @@ -#include <iostream>
-#include <utility>
-
-const int M = 1010;
-
-int N;
-char map[M][M];
-bool visited[M][M];
-
-int not_sink_count;
-
-const std::pair<int, int> 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/works/solutions/acwing/1236.cpp b/works/solutions/acwing/1236.cpp deleted file mode 100644 index a89a890..0000000 --- a/works/solutions/acwing/1236.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include <iostream>
-
-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/works/solutions/acwing/1237.cpp b/works/solutions/acwing/1237.cpp deleted file mode 100644 index a3b8810..0000000 --- a/works/solutions/acwing/1237.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-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/works/solutions/acwing/1238.cpp b/works/solutions/acwing/1238.cpp deleted file mode 100644 index 2c9d899..0000000 --- a/works/solutions/acwing/1238.cpp +++ /dev/null @@ -1,56 +0,0 @@ -#include <iostream>
-#include <map>
-#include <set>
-
-const int M = 100010;
-
-int N, D, K;
-
-std::map<int, std::multiset<int>> vote_map;
-
-bool check(const std::multiset<int> &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/works/solutions/acwing/1239.cpp b/works/solutions/acwing/1239.cpp deleted file mode 100644 index c670cd4..0000000 --- a/works/solutions/acwing/1239.cpp +++ /dev/null @@ -1,52 +0,0 @@ -#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;
-}
diff --git a/works/solutions/acwing/1240.cpp b/works/solutions/acwing/1240.cpp deleted file mode 100644 index 8ebae33..0000000 --- a/works/solutions/acwing/1240.cpp +++ /dev/null @@ -1,42 +0,0 @@ -#include <iostream>
-
-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/works/solutions/acwing/1245.cpp b/works/solutions/acwing/1245.cpp deleted file mode 100644 index ba51a8f..0000000 --- a/works/solutions/acwing/1245.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <iostream>
-
-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/works/solutions/acwing/1246.cpp b/works/solutions/acwing/1246.cpp deleted file mode 100644 index 5c0454c..0000000 --- a/works/solutions/acwing/1246.cpp +++ /dev/null @@ -1,34 +0,0 @@ -#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;
-}
\ No newline at end of file diff --git a/works/solutions/acwing/1247.cpp b/works/solutions/acwing/1247.cpp deleted file mode 100644 index 1fd4412..0000000 --- a/works/solutions/acwing/1247.cpp +++ /dev/null @@ -1,39 +0,0 @@ -#include <cmath>
-#include <iostream>
-
-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/works/solutions/acwing/2-2.cpp b/works/solutions/acwing/2-2.cpp deleted file mode 100644 index fb0fb3b..0000000 --- a/works/solutions/acwing/2-2.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-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/works/solutions/acwing/2.cpp b/works/solutions/acwing/2.cpp deleted file mode 100644 index 1a75c19..0000000 --- a/works/solutions/acwing/2.cpp +++ /dev/null @@ -1,30 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-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/works/solutions/acwing/2065.cpp b/works/solutions/acwing/2065.cpp deleted file mode 100644 index a0c47c2..0000000 --- a/works/solutions/acwing/2065.cpp +++ /dev/null @@ -1,16 +0,0 @@ -#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 /= 2;
- }
-
- return 0;
-}
\ No newline at end of file diff --git a/works/solutions/acwing/2066.cpp b/works/solutions/acwing/2066.cpp deleted file mode 100644 index 7a6132b..0000000 --- a/works/solutions/acwing/2066.cpp +++ /dev/null @@ -1,21 +0,0 @@ -#include <cctype>
-#include <iostream>
-
-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/works/solutions/acwing/2067.cpp b/works/solutions/acwing/2067.cpp deleted file mode 100644 index 3ebd61d..0000000 --- a/works/solutions/acwing/2067.cpp +++ /dev/null @@ -1,22 +0,0 @@ -#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/solutions/acwing/2068.cpp b/works/solutions/acwing/2068.cpp deleted file mode 100644 index 592f43f..0000000 --- a/works/solutions/acwing/2068.cpp +++ /dev/null @@ -1,57 +0,0 @@ -#include <algorithm>
-#include <cmath>
-#include <cstring>
-#include <iostream>
-
-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/works/solutions/acwing/2069.cpp b/works/solutions/acwing/2069.cpp deleted file mode 100644 index fbfa6d2..0000000 --- a/works/solutions/acwing/2069.cpp +++ /dev/null @@ -1,82 +0,0 @@ -#include <iostream>
-#include <vector>
-
-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/works/solutions/acwing/3-2.cpp b/works/solutions/acwing/3-2.cpp deleted file mode 100644 index c099838..0000000 --- a/works/solutions/acwing/3-2.cpp +++ /dev/null @@ -1,25 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-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/works/solutions/acwing/3.cpp b/works/solutions/acwing/3.cpp deleted file mode 100644 index 21bd8dc..0000000 --- a/works/solutions/acwing/3.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-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/works/solutions/acwing/4.cpp b/works/solutions/acwing/4.cpp deleted file mode 100644 index 3270402..0000000 --- a/works/solutions/acwing/4.cpp +++ /dev/null @@ -1,51 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-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/works/solutions/acwing/5.cpp b/works/solutions/acwing/5.cpp deleted file mode 100644 index a88fba6..0000000 --- a/works/solutions/acwing/5.cpp +++ /dev/null @@ -1,49 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-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/works/solutions/acwing/7.cpp b/works/solutions/acwing/7.cpp deleted file mode 100644 index fcc0fb1..0000000 --- a/works/solutions/acwing/7.cpp +++ /dev/null @@ -1,54 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-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/works/solutions/acwing/8.cpp b/works/solutions/acwing/8.cpp deleted file mode 100644 index f62d21e..0000000 --- a/works/solutions/acwing/8.cpp +++ /dev/null @@ -1,29 +0,0 @@ -#include <algorithm>
-#include <iostream>
-
-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 |