commit 96254947699986c59f0dc63d69fd4b76bd3ed43e Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Mon, 6 Jul 2026 19:08:08 +0200 Initial commit Diffstat:
108 files changed, 2920 insertions(+), 0 deletions(-)
diff --git a/01_introductory_problems/a.out b/01_introductory_problems/a.out Binary files differ. diff --git a/01_introductory_problems/apple_division_1623.cpp b/01_introductory_problems/apple_division_1623.cpp @@ -0,0 +1,21 @@ +#include <iostream> +#include <numeric> +#include <vector> + +long long md(std::vector<long long>& a, long long p, long long t, size_t i) { + if (2*p >= t) + return 2*p - t; + if (i == a.size()) + return t; + return std::min(md(a, p, t, i+1), md(a, p+a[i], t, i+1)); +} + +int main() { + size_t n; + std::cin >> n; + std::vector<long long> a(n); + for (size_t i = 0; i < n; i++) + std::cin >> a[i]; + auto s = md(a, 0, std::accumulate(a.begin(), a.end(), (long long)0), 0); + std::cout << s << "\n"; +} diff --git a/01_introductory_problems/bit_strings_1617.cpp b/01_introductory_problems/bit_strings_1617.cpp @@ -0,0 +1,10 @@ +#include <iostream> + +int main() { + constexpr long long M = 1e9+7; + long long n, a{1}; + std::cin >> n; + while (--n >= 0) + a = (a * 2) % M; + std::cout << a << std::endl; +} diff --git a/01_introductory_problems/chessboard_and_queens_1624.cpp b/01_introductory_problems/chessboard_and_queens_1624.cpp @@ -0,0 +1,42 @@ +#include <bitset> +#include <iostream> +#include <string> + +void set_bit(std::bitset<64>& r, int i, int j) { + if (i >= 0 && i < 8 && j >= 0 && j < 8) + r |= 1ULL << (unsigned long long)(8*i + j); +} + +std::bitset<64> maskall(const std::bitset<64>& b, int i, int j) { + std::bitset<64> r{b}; + r |= 0x0101010101010101ULL << (unsigned long long)j; + for (int k = 0; k < 8; k++) { + set_bit(r, k, k+j-i); + set_bit(r, k, -k+j+i); + } + return r; +} + +long long f(std::bitset<64>& b, int i) { + if (i == 8) + return 1; + long long s{0}; + for (int j = 0; j < 8; j++) { + if (!b[8*i+j]) { + auto rr = maskall(b, i, j); + s += f(rr, i+1); + } + } + return s; +} + +int main() { + std::bitset<64> b{0}; + std::string s; + for (int i = 0; i < 8; i++) { + std::cin >> s; + for (int j = 0; j < 8; j++) + b[8*i+j] = s[j] == '*'; + } + std::cout << f(b, 0) << "\n"; +} diff --git a/01_introductory_problems/coin_piles_1754.cpp b/01_introductory_problems/coin_piles_1754.cpp @@ -0,0 +1,18 @@ +#include <algorithm> +#include <iostream> + +bool f(int a, int b) { + auto max = std::max(a, b); + auto min = std::min(a, b); + + return max <= 2*min && (2*min - max) % 3 == 0; +} + +int main() { + int t, a, b; + std::cin >> t; + for (int i = 0; i < t; i++) { + std::cin >> a >> b; + std::cout << (f(a, b) ? "YES" : "NO") << std::endl; + } +} diff --git a/01_introductory_problems/creating_strings_1622.cpp b/01_introductory_problems/creating_strings_1622.cpp @@ -0,0 +1,30 @@ +#include <iostream> +#include <string> +#include <map> +#include <vector> + +void gen(std::map<char, int>& a, int count, + std::string start, std::vector<std::string>& res) { + if (count == 0) + res.push_back(start); + for (auto [k, v] : a) { + if (v > 0) { + a[k]--; + gen(a, count - 1, start + k, res); + a[k]++; + } + } +} + +int main() { + std::string s; + std::map<char, int> a; + std::vector<std::string> sol; + std::cin >> s; + for (auto c : s) + a[c]++; + gen(a, s.size(), "", sol); + std::cout << sol.size() << "\n"; + for (auto x : sol) + std::cout << x << "\n"; +} diff --git a/01_introductory_problems/digit_queries_2431.cpp b/01_introductory_problems/digit_queries_2431.cpp @@ -0,0 +1,23 @@ +#include <iostream> + +int f(long long k) { + long long n{1}, p{1}, d{1}, q{9}; + while (p + d*q <= k) { + n += q; + p += d * q; + d++; + q *= 10; + } + long long x{(k-p) / d + n}; + long long m{(k-p) % d}; + for (long long j = 0; j < d-m-1; j++) + x /= (long long)10; + return x % (long long)10; +} + +int main() { + long long k; + std::cin >> k; + while (std::cin >> k) + std::cout << f(k) << "\n"; +} diff --git a/01_introductory_problems/gray_code_2205.cpp b/01_introductory_problems/gray_code_2205.cpp @@ -0,0 +1,22 @@ +#include <iostream> +#include <format> + +void print(int number, int ndigits) { + std::cout << std::format("{0:0{1}b}", number, ndigits) << "\n"; +} + +void print_all(int& start, int digit, int ndigits) { + if (digit == 0) { + print(start, ndigits); + } else { + print_all(start, digit-1, ndigits); + start ^= 1 << (digit-1); + print_all(start, digit-1, ndigits); + } +} + +int main() { + int n, start{0}; + std::cin >> n; + print_all(start, n, n); +} diff --git a/01_introductory_problems/grid_coloring_i_3311.cpp b/01_introductory_problems/grid_coloring_i_3311.cpp @@ -0,0 +1,17 @@ +#include <iostream> +#include <string> + +int main() { + int n, m; + std::cin >> n >> m; + for (int i = 0; i < n; i++) { + std::string s; + std::cin >> s; + for (int j = 0; j < m; j++) { + char c = 'A' + 2*((i+j)%2); + c += c == s[j]; + std::cout << c; + } + std::cout << "\n"; + } +} diff --git a/01_introductory_problems/grid_path_description_1625.cpp b/01_introductory_problems/grid_path_description_1625.cpp @@ -0,0 +1,150 @@ +#include <algorithm> +#include <bitset> +#include <iostream> +#include <queue> +#include <string> +#include <vector> + +/* +The official solution uses the heuristic: if both adjacent squares +in horizontal direction are visited or wall, and both in vertical direction +are not visited (or the other way round), then we stop because we borked +the square. I did not think of this criterion, so to check if the square +is borked I do a full visit from the bottom-left corner. This is too slow, +so I do this only at depths 10, 20, 30 and 40. This is good enough. +*/ + +class Tile { +public: + int i; + int j; + + bool valid() const { return i >= 0 && i < 7 && j >= 0 && j < 7; } + bool end() const { return i == 6 && j == 0; } + bool operator==(const Tile& t) const { return i == t.i && j == t.j; } + Tile u() const { return Tile{i-1, j}; } + Tile d() const { return Tile{i+1, j}; } + Tile l() const { return Tile{i, j-1}; } + Tile r() const { return Tile{i, j+1}; } + static Tile err() { return Tile{-1, -1}; } + + Tile move(char c) const { + if (c == 'U') return u(); + if (c == 'D') return d(); + if (c == 'L') return l(); + if (c == 'R') return r(); + return err(); + } + + std::vector<Tile> neighbors() const { + return std::vector { u(), d(), l(), r() }; + } +}; + +class Map { +public: + Map() : b(), v(49, 4) { + for (int i = 0; i < 7; i++) { + v[index(Tile{i, 0})]--; + v[index(Tile{i, 6})]--; + v[index(Tile{0, i})]--; + v[index(Tile{6, i})]--; + } + } + + bool visited(Tile t) const { + return !t.valid() || b.test(index(t)); + } + + void set(Tile t) { + if (!t.valid()) return; + b.set(index(t)); + for (auto u : t.neighbors()) + if (u.valid()) + v[index(u)]--; + } + + void reset(Tile t) { + if (!t.valid()) return; + b.reset(index(t)); + for (auto u : t.neighbors()) + if (u.valid()) + v[index(u)]++; + } + + std::vector<Tile> locked_neighbors(Tile t) const { + std::vector<Tile> r{}; + for (auto u : t.neighbors()) + if (locked(u)) + r.push_back(u); + return r; + } + + int count() const { return b.count(); } + + bool borked() const { + std::bitset<49> vv{}; + std::queue<Tile> q; + q.push(Tile{6, 0}); + vv.set(index(Tile{6, 0})); + int c{1}; + while (!q.empty()) { + Tile t = q.front(); + q.pop(); + for (auto u : t.neighbors()) { + if (!visited(u) && !vv.test(index(u))) { + vv.set(index(u)); + c++; + q.push(u); + } + } + } + + return c + count() < 49; + } + +private: + std::bitset<49> b; + std::vector<int> v; + static int index(Tile t) { return 7*t.i + t.j; } + + bool locked(Tile t) const { + return t.valid() && !visited(t) && !t.end() && v[index(t)] < 2; + } +}; + +int f(Map& m, const std::string& s, size_t n, Tile t) { + if (n == 48) return t.end(); + if (m.visited(t) || t.end()) return 0; + + m.set(t); + if (n % 10 == 0 && m.borked()) { + m.reset(t); + return 0; + } + + auto ln = m.locked_neighbors(t); + + int r{0}; + if (s[n] != '?') { + Tile nt = t.move(s[n]); + if (ln.size() == 0 || (ln.size() == 1 && ln[0] == nt)) + r = f(m, s, n+1, nt); + } else { + if (ln.size() == 0) + r = f(m, s, n+1, t.u()) + f(m, s, n+1, t.d()) + + f(m, s, n+1, t.l()) + f(m, s, n+1, t.r()); + if (ln.size() == 1) + r = f(m, s, n+1, ln[0]); + } + + m.reset(t); + return r; +} + +int main() { + Map m; + std::string s; + std::cin >> s; + std::cout << f(m, s, 0, Tile{0, 0}) << "\n"; +} diff --git a/01_introductory_problems/increasing_array_1094.cpp b/01_introductory_problems/increasing_array_1094.cpp @@ -0,0 +1,12 @@ +#include <algorithm> +#include <iostream> + +int main() { + long long n, prev{0}, sum{0}; + std::cin >> n; + while (std::cin >> n) { + sum += std::max<long long>(0, prev - n); + prev = std::max(prev, n); + } + std::cout << sum << std::endl; +} diff --git a/01_introductory_problems/knight_moves_grid_3217.cpp b/01_introductory_problems/knight_moves_grid_3217.cpp @@ -0,0 +1,40 @@ +#include <iostream> +#include <queue> +#include <tuple> +#include <vector> + +struct Node { + int i; + int j; + int d; +}; + +int main() { + int n; + std::cin >> n; + std::vector<std::vector<int>> a(n, std::vector<int>(n, 1e7)); + std::queue<Node> q; + + q.push(Node{0, 0, 0}); + while (!q.empty()) { + auto v = q.front(); + q.pop(); + if (v.i < 0 || v.j < 0 || v.i >= n || v.j >= n || a[v.i][v.j] <= v.d) + continue; + a[v.i][v.j] = v.d; + q.push(Node{v.i-2, v.j-1, v.d+1}); + q.push(Node{v.i-2, v.j+1, v.d+1}); + q.push(Node{v.i-1, v.j-2, v.d+1}); + q.push(Node{v.i-1, v.j+2, v.d+1}); + q.push(Node{v.i+2, v.j-1, v.d+1}); + q.push(Node{v.i+2, v.j+1, v.d+1}); + q.push(Node{v.i+1, v.j-2, v.d+1}); + q.push(Node{v.i+1, v.j+2, v.d+1}); + } + + for (auto& v : a) { + for (auto& x : v) + std::cout << x << " "; + std::cout << "\n"; + } +} diff --git a/01_introductory_problems/mex_grid_construction_3419.cpp b/01_introductory_problems/mex_grid_construction_3419.cpp @@ -0,0 +1,30 @@ +#include <algorithm> +#include <bitset> +#include <iostream> +#include <vector> + +int firstzero(const std::bitset<200>& b) { + for (int i = 0; i < 200; i++) + if (!b.test(i)) + return i; + return -1; +} + +int next(int i, int j, std::vector<std::bitset<200>>& col, + std::vector<std::bitset<200>>& row) { + int r = firstzero(row[i] | col[j]); + row[i][r] = col[j][r] = 1; + return r; +} + +int main() { + int n; + std::cin >> n; + std::vector<std::bitset<200>> col(n), row(n); + + for (int i = 0; i < n; i++) { + for (int j = 0; j < n; j++) + std::cout << next(i, j, col, row) << " "; + std::cout << "\n"; + } +} diff --git a/01_introductory_problems/missing_number_1083.cpp b/01_introductory_problems/missing_number_1083.cpp @@ -0,0 +1,9 @@ +#include <iostream> + +int main() { + long long n, m, sum{0}; + std::cin >> n; + while (std::cin >> m) + sum += m; + std::cout << n*(n+1)/2 - sum << std::endl; +} diff --git a/01_introductory_problems/number_spiral_1071.cpp b/01_introductory_problems/number_spiral_1071.cpp @@ -0,0 +1,27 @@ +#include <algorithm> +#include <iostream> + +long long f(long long x, long long y) { + long long c = std::max(x, y); + if (c % 2) { + if (y >= x) + return (c-1)*(c-1)+x; + else + return c*c-y+1; + } else { + if (y >= x) + return c*c-x+1; + else + return (c-1)*(c-1)+y; + } +} + +int main() { + int t; + std::cin >> t; + for (int i = 0; i < t; i++) { + long long x, y; + std::cin >> y >> x; + std:: cout << f(x, y) << std::endl; + } +} diff --git a/01_introductory_problems/palindrome_reorder_1755.cpp b/01_introductory_problems/palindrome_reorder_1755.cpp @@ -0,0 +1,35 @@ +#include <iostream> +#include <string> + +void printn(char c, int n) { + for (int i = 0; i < n; i++) + std::cout << c; +} + +int main() { + std::string s; + int odd{0}, a['Z'+1] = {0}; + char oddc{0}; + std::cin >> s; + for (auto c : s) + a[(size_t)c]++; + for (char c = 'A'; c <= 'Z'; c++) { + if (a[(size_t)c] % 2) { + odd++; + oddc = c; + } + } + if (odd > 1) { + std::cout << "NO SOLUTION\n"; + } else { + for (char c = 'A'; c <= 'Z'; c++) + if (c != oddc) + printn(c, a[(size_t)c]/2); + if (odd) + printn(oddc, a[(size_t)oddc]); + for (char c = 'Z'; c >= 'A'; c--) + if (c != oddc) + printn(c, a[(size_t)c]/2); + std::cout << std::endl; + } +} diff --git a/01_introductory_problems/permutations_1070.cpp b/01_introductory_problems/permutations_1070.cpp @@ -0,0 +1,15 @@ +#include <iostream> + +int main() { + int n; + std::cin >> n; + if (n == 2 || n == 3) { + std::cout << "NO SOLUTION" << std::endl; + } else { + for (int i = 2; i <= n; i += 2) + std::cout << i << " "; + for (int i = 1; i <= n; i += 2) + std::cout << i << " "; + std::cout << std::endl; + } +} diff --git a/01_introductory_problems/raab_game_i_3399.cpp b/01_introductory_problems/raab_game_i_3399.cpp @@ -0,0 +1,67 @@ +#include <iostream> +#include <utility> +#include <vector> + +class Game { +public: + bool y; + std::vector<int> a; + std::vector<int> b; + int apts = 0; + int bpts = 0; + + Game(int n, bool w) + : y{w}, a{std::vector<int>(n)}, b{std::vector<int>(n)} {} + + void play(int i, int j) { + this->a[this->next] = i; + this->b[this->next] = j; + this->apts += i > j; + this->bpts += j > i; + this->next++; + } + + friend std::ostream& operator<<(std::ostream& os, const Game g) { + if (!g.y) { + os << "NO\n"; + } else { + os << "YES\n"; + for (auto x : g.a) + os << x << " "; + os << "\n"; + for (auto x : g.b) + os << x << " "; + os << "\n"; + } + return os; + } +private: + int next = 0; +}; + +Game play(int n, int a, int b) { + if (a + b > n) + return Game(1, false); + + Game g(n, true); + for (int i = 0; i < n - (a+b); i++) + g.play(i+1, i+1); + for (int i = 0; i < a; i++) + g.play(n-a+i+1, n-(a+b)+i+1); + for (int i = 0; i < b; i++) + g.play(n-(a+b)+i+1, n-b+i+1); + + if (g.apts != a || g.bpts != b) + g.y = false; + + return g; +} + +int main() { + int n, a, b, t; + std::cin >> t; + for (int i = 0; i < t; i++) { + std::cin >> n >> a >> b; + std::cout << play(n, a, b); + } +} diff --git a/01_introductory_problems/repetitions_1069.cpp b/01_introductory_problems/repetitions_1069.cpp @@ -0,0 +1,20 @@ +#include <algorithm> +#include <iostream> +#include <string> + +int main() { + char cur{'x'}; + int n{0}, m{0}; + std::string str; + std::cin >> str; + for (auto c : str) { + if (c == cur) { + n++; + } else { + m = std::max(m, n); + n = 1; + cur = c; + } + } + std::cout << std::max(m, n) << std::endl; +} diff --git a/01_introductory_problems/string_reorder_1743.cpp b/01_introductory_problems/string_reorder_1743.cpp @@ -0,0 +1,38 @@ +#include <algorithm> +#include <array> +#include <iostream> +#include <iterator> +#include <sstream> +#include <string> + +int main() { + std::array<size_t, 26> a{}; + std::string s; + std::cin >> s; + for (auto c : s) a[c-'A']++; + + size_t i{0}, j{1}, tot{s.size()}, c{99}; + std::stringstream ss{}; + while (*std::max_element(a.begin(), a.end()) <= tot / 2) { + while (a[i] == 0) i++; + while (a[j] == 0 || j <= i) j++; + c = i == c ? j : i; + ss << (char)('A' + c); + a[c]--; + tot--; + } + + j = std::distance(a.begin(), std::max_element(a.begin(), a.end())); + while (a[j] > 1) { + if (tot == a[j]) { + std::cout << "-1\n"; + return 0; + } + while (a[i] == 0 || i == j) i++; + ss << (char)('A' + j) << (char)('A' + i); + a[i]--; + a[j]--; + tot -= 2; + } + std::cout << ss.str() << (char)('A' + j) << "\n"; +} diff --git a/01_introductory_problems/tower_of_hanoi_2165.cpp b/01_introductory_problems/tower_of_hanoi_2165.cpp @@ -0,0 +1,17 @@ +#include <iostream> + +void do_hanoi(int n, int l, int m, int r) { + if (n != 0) { + do_hanoi(n-1, l, r, m); + std::cout << l << " " << r << "\n"; + do_hanoi(n-1, m, l, r); + } +} + +int main() { + int n; + std::cin >> n; + + std::cout << (1 << n) - 1 << "\n"; + do_hanoi(n, 1, 2, 3); +} diff --git a/01_introductory_problems/trailing_zeros_1618.cpp b/01_introductory_problems/trailing_zeros_1618.cpp @@ -0,0 +1,9 @@ +#include <iostream> + +int main() { + int n, c{0}; + std::cin >> n; + while (n > 0) + c += (n /= 5); + std::cout << c << std::endl; +} diff --git a/01_introductory_problems/two_knights_1072.cpp b/01_introductory_problems/two_knights_1072.cpp @@ -0,0 +1,24 @@ +#include <iostream> +#include <vector> + +int main() { + long long n, a; + std::vector<long long> b = {0, 0, 6, 28, 96}; + std::cin >> n; + + for (long long k = 1; k <= n; k++) { + if (k <= 4) { + a = b[k]; + } else { + // Both knights in new strip + a += (2*k - 1)*(k - 1) - 2; + + // One knight in new strip, one in previous square + const long long s = (k-1)*(k-1); + a += 5*(s - 2); + a += 4*(s - 3); + a += (2*k - 10)*(s - 4); + } + std::cout << a << std::endl; + } +} diff --git a/01_introductory_problems/two_sets_1092.cpp b/01_introductory_problems/two_sets_1092.cpp @@ -0,0 +1,53 @@ +#include <iostream> +#include <vector> + +void printarr(const std::vector<int>& a) { + std::cout << a.size() << std::endl; + for (auto x : a) + std::cout << x << " "; + std::cout << std::endl; +} + +int main() { + int n; + std::cin >> n; + + switch (n % 4) { + case 1: + case 2: + std::cout << "NO\n"; + break; + case 0: + std::cout << "YES\n"; + { + std::vector<int> a(n/2), b(n/2); + for (int i = 0; i < n/4; i++) { + a[2*i] = 4*i+1; + a[2*i+1] = 4*i+4; + b[2*i] = 4*i+2; + b[2*i+1] = 4*i+3; + } + printarr(a); + printarr(b); + } + break; + case 3: + std::cout << "YES\n"; + if (n == 3) { + std::cout << "2\n1 2\n1\n3\n"; + } else { + std::vector<int> a(n/2+1), b(n/2); + a[0] = 1; a[1] = 2; a[2] = 4; a[3] = 7; + b[0] = 3; b[1] = 5; b[2] = 6; + for (int i = 1; i < n/4; i++) { + a[2*i+2] = 4*i+4; + a[2*i+3] = 4*i+7; + b[2*i+1] = 4*i+5; + b[2*i+2] = 4*i+6; + } + printarr(a); + printarr(b); + } + break; + } +} diff --git a/01_introductory_problems/weird_algorithm_1068.cpp b/01_introductory_problems/weird_algorithm_1068.cpp @@ -0,0 +1,12 @@ +#include <iostream> + +int main() { + long long n; + std::cin >> n; + + while (n != 1) { + std::cout << n << " "; + n = (n % 2) ? n * 3 + 1 : n / 2; + } + std::cout << 1 << std::endl; +} diff --git a/02_sorting_and_searching/a.out b/02_sorting_and_searching/a.out Binary files differ. diff --git a/02_sorting_and_searching/apartments_1084.cpp b/02_sorting_and_searching/apartments_1084.cpp @@ -0,0 +1,27 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +std::vector<int> readn(int n) { + std::vector<int> v(n); + for (int i = 0; i < n; i++) + std::cin >> v[i]; + return v; +} + +int main() { + int n, m, k; + std::cin >> n >> m >> k; + auto a = readn(n); + auto b = readn(m); + std::sort(a.begin(), a.end()); + std::sort(b.begin(), b.end()); + + size_t s{0}, i{0}, j{0}; + while (i < a.size() && j < b.size()) { + if (b[j] > a[i] + k) i++; + else if (b[j] < a[i] - k) j++; + else { s++; i++; j++; } + } + std::cout << s << "\n"; +} diff --git a/02_sorting_and_searching/collecting_numbers_2216.cpp b/02_sorting_and_searching/collecting_numbers_2216.cpp @@ -0,0 +1,46 @@ +#include <iostream> +#include <vector> + +int main() { + size_t n, x, s{1}, l{0}; + std::cin >> n; + std::vector<size_t> b(n); + for (size_t i = 0; i < n; i++) { + std::cin >> x; + b[x-1] = i; + } + for (size_t i = 0; i < n; i++) { + s += b[i] < l; + l = b[i]; + } + std::cout << s << "\n"; +} + + +// The code below solves a different problem: it finds the minimum number +// of ascending chains needed to partition the given list of numbers. + +#if 0 + +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + size_t n; + std::vector<size_t> s; + std::cin >> n; + for (size_t i = 0; i < n; i++) { + size_t x; + std::cin >> x; + auto it = std::lower_bound( + s.begin(), s.end(), x, std::greater<size_t>()); + if (it != s.end()) + *it = x; + else + s.push_back(x); + } + std::cout << s.size() << std::endl; +} + +#endif diff --git a/02_sorting_and_searching/concert_tickets_1091.cpp b/02_sorting_and_searching/concert_tickets_1091.cpp @@ -0,0 +1,25 @@ +#include <algorithm> +#include <iostream> +#include <set> +#include <vector> + +int main() { + size_t n, m; + std::cin >> n >> m; + std::vector<int> hv(n), t(m); + for (size_t i = 0; i < n; i++) + std::cin >> hv[i]; + for (size_t i = 0; i < m; i++) + std::cin >> t[i]; + + std::multiset<int, std::greater<int>> h(hv.begin(), hv.end()); + + for (auto c : t) { + if (auto x = h.lower_bound(c); x == h.end()) { + std::cout << "-1\n"; + } else { + std::cout << *x << "\n"; + h.erase(x); + } + } +} diff --git a/02_sorting_and_searching/distinct_numbers_1621.cpp b/02_sorting_and_searching/distinct_numbers_1621.cpp @@ -0,0 +1,13 @@ +#include <iostream> +#include <set> + +int main() { + int n, x; + std::set<int> s; + std::cin >> n; + for (int i = 0; i < n; i++) { + std::cin >> x; + s.insert(x); + } + std::cout << s.size() << "\n"; +} diff --git a/02_sorting_and_searching/ferris_wheel_1090.cpp b/02_sorting_and_searching/ferris_wheel_1090.cpp @@ -0,0 +1,17 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + int n, x; + std::cin >> n >> x; + std::vector<int> a(n); + for (int i = 0; i < n; i++) + std::cin >> a[i]; + std::sort(a.begin(), a.end()); + size_t i{0}, j{a.size()-1}, s{0}; + for (; j > i; j--, s++) + i += a[i] + a[j] <= x; + if (i == j) s++; + std::cout << s << "\n"; +} diff --git a/02_sorting_and_searching/maximum_subarray_sum_1643.cpp b/02_sorting_and_searching/maximum_subarray_sum_1643.cpp @@ -0,0 +1,19 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + size_t n; + std::cin >> n; + std::vector<long long> a(n); + for (size_t i = 0; i < n; i++) + std::cin >> a[i]; + + long long scur{0}, smax{0}; + for (size_t j = 0; j < n; j++) { + scur = std::max(0LL, scur + a[j]); + smax = std::max(smax, scur); + } + if (smax == 0) smax = *std::max_element(a.begin(), a.end()); + std::cout << smax << "\n"; +} diff --git a/02_sorting_and_searching/missing_coin_sum_2183.cpp b/02_sorting_and_searching/missing_coin_sum_2183.cpp @@ -0,0 +1,16 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + size_t n, s{1}; + std::cin >> n; + std::vector<size_t> a(n); + for (size_t i = 0; i < n; i++) + std::cin >> a[i]; + std::sort(a.begin(), a.end()); + for (auto c : a) + if (s < c) break; + else s+= c; + std::cout << s << std::endl; +} diff --git a/02_sorting_and_searching/movie_festival_1629.cpp b/02_sorting_and_searching/movie_festival_1629.cpp @@ -0,0 +1,21 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + size_t n; + std::cin >> n; + std::vector<std::pair<int, int>> v(n); + for (size_t i = 0; i < n; i++) + std::cin >> v[i].first >> v[i].second; + std::sort(v.begin(), v.end()); + int e{-1}, s{0}; + for (auto a : v) { + if (a.first >= e) { + e = a.second; + s++; + } + e = std::min(e, a.second); + } + std::cout << s << "\n"; +} diff --git a/02_sorting_and_searching/playlist_1141.cpp b/02_sorting_and_searching/playlist_1141.cpp @@ -0,0 +1,22 @@ +#include <algorithm> +#include <iostream> +#include <map> +#include <vector> + +int main() { + size_t n; + std::cin >> n; + std::vector<int> v(n); + for (size_t i = 0; i < n; i++) + std::cin >> v[i]; + + size_t l{0}, s{0}; + std::map<int, size_t> m; + for (size_t r = 0; r < n; r++) { + if (m.contains(v[r])) + l = std::max(l, m.at(v[r])+1); + m[v[r]] = r; + s = std::max(s, r-l+1); + } + std::cout << s << "\n"; +} diff --git a/02_sorting_and_searching/restaurant_customers_1619.cpp b/02_sorting_and_searching/restaurant_customers_1619.cpp @@ -0,0 +1,24 @@ +#include <algorithm> +#include <iostream> +#include <queue> +#include <vector> + +int main() { + size_t n; + std::cin >> n; + std::vector<std::pair<int, int>> c(n); + for (size_t i = 0; i < n; i++) { + int a, b; + std::cin >> a >> b; + c[i] = {a, b}; + } + std::sort(c.begin(), c.end()); + std::priority_queue<int, std::vector<int>, std::greater<int>> q; + size_t m{0}; + for (auto d : c) { + while (!q.empty() && q.top() < d.first) q.pop(); + q.push(d.second); + m = std::max(m, q.size()); + } + std::cout << m << "\n"; +} diff --git a/02_sorting_and_searching/room_allocation_1164.cpp b/02_sorting_and_searching/room_allocation_1164.cpp @@ -0,0 +1,38 @@ +#include <algorithm> +#include <iostream> +#include <queue> +#include <tuple> +#include <vector> + +int main() { + int n; + std::vector<std::tuple<int, int, int>> v; + std::cin >> n; + for (int i = 0; i < n; i++) { + int a, b; + std::cin >> a >> b; + v.push_back({a, b, i}); + } + std::sort(v.begin(), v.end()); + + using P = std::pair<int, int>; + std::priority_queue<P, std::vector<P>, std::greater<>> r; + std::vector<int> al(n); + for (auto [a, d, i] : v) { + int ind = r.size()+1; + if (!r.empty()) { + auto [x, j] = r.top(); + if (a > x) { + r.pop(); + ind = j; + } + } + r.push({d, ind}); + al[i] = ind; + } + + std::cout << r.size() << "\n"; + for (auto i : al) + std::cout << i << " "; + std::cout << "\n"; +} diff --git a/02_sorting_and_searching/stick_lengths_1074.cpp b/02_sorting_and_searching/stick_lengths_1074.cpp @@ -0,0 +1,16 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + long long n; + std::cin >> n; + std::vector<long long> a(n); + for (long long i = 0; i < n; i++) + std::cin >> a[i]; + std::sort(a.begin(), a.end()); + long long s{0}, t{a[n/2]}; + for (auto x : a) + s += std::abs(x-t); + std::cout << s << "\n"; +} diff --git a/02_sorting_and_searching/sum_of_two_values_1640.cpp b/02_sorting_and_searching/sum_of_two_values_1640.cpp @@ -0,0 +1,27 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + int n, x; + std::cin >> n >> x; + std::vector<std::pair<int, int>> a(n); + for (int i = 0; i < n; i++) { + std::cin >> a[i].first; + a[i].second = i; + } + std::sort(a.begin(), a.end()); + + int i{0}, j{n-1}; + while (i < j) { + auto [ai, ii] = a[i]; + auto [aj, ij] = a[j]; + if (ai + aj < x) i++; + else if (ai + aj > x) j--; + else { + std::cout << ii+1 << " " << ij+1 << "\n"; + return 0; + } + } + std::cout << "IMPOSSIBLE\n"; +} diff --git a/02_sorting_and_searching/towers_1063.cpp b/02_sorting_and_searching/towers_1063.cpp @@ -0,0 +1,17 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + size_t n; + std::cin >> n; + std::vector<int> v; + for (size_t i = 0; i < n; i++) { + int x; + std::cin >> x; + auto it = std::upper_bound(v.begin(), v.end(), x); + if (it == v.end()) v.push_back(x); + else *it = x; + } + std::cout << v.size() << "\n"; +} diff --git a/03_dynamic_programming/a.out b/03_dynamic_programming/a.out Binary files differ. diff --git a/03_dynamic_programming/coin_combinations_i_1635.cpp b/03_dynamic_programming/coin_combinations_i_1635.cpp @@ -0,0 +1,25 @@ +#include <iostream> +#include <vector> + +static constexpr int mod = 1000000007; +static constexpr int X = 1000001; + +int f(const std::vector<int>& c, std::vector<int>& a, int x) { + if (x < 0) return 0; + if (a[x] != -1) return a[x]; + if (x == 0) return a[x] = 1; + + a[x] = 0; + for (auto m : c) + a[x] = (a[x] + f(c, a, x-m)) % mod; + return a[x]; +} + +int main() { + int n, x; + std::cin >> n >> x; + std::vector<int> c(n), a(X, -1); + for (int i = 0; i < n; i++) + std::cin >> c[i]; + std::cout << f(c, a, x) << "\n"; +} diff --git a/03_dynamic_programming/coin_combinations_ii_1636.cpp b/03_dynamic_programming/coin_combinations_ii_1636.cpp @@ -0,0 +1,28 @@ +#include <iostream> +#include <map> +#include <vector> + +static constexpr int mod = 1000000007; +static constexpr int X = 1000001; + +int main() { + int n, x; + std::cin >> n >> x; + std::vector<int> c(n); + for (int i = 0; i < n; i++) + std::cin >> c[i]; + + std::vector<std::vector<int>> a(n, std::vector<int>(X, 0)); + for (int i = 0; i < (int)c.size(); i++) a[i][0] = 1; + for (int j = c.back(); j <= x; j += c.back()) a[c.size()-1][j] = 1; + for (int i = c.size()-2; i >= 0; i--) { + for (int j = 1; j <= x; j++) { + a[i][j] = a[i+1][j]; + if (j >= c[i]) { + a[i][j] += a[i][j-c[i]]; + a[i][j] %= mod; + } + } + } + std::cout << a[0][x] << "\n"; +} diff --git a/03_dynamic_programming/counting_towers_2413.cpp b/03_dynamic_programming/counting_towers_2413.cpp @@ -0,0 +1,38 @@ +#include <iostream> +#include <vector> + +// Recurrence relation: +// f(n) = sum over i from 0 to n-1 of f(i) * p(n-i) +// where p(n) is the number of indivisible towers of height n, +// which is easily seen to be 3^(n-1)+1. +// Then we can expand: +// f(n) = sum_{i=0}^{n-1} f(i)(3^{n-i-1}+1) = g(n) + h(n) +// where we define g(n) = sum f(i)3^{n-i-1} and h(n) = sum f(i). +// Then it's easy to see that: +// g(n+1) = f(n) + 3g(n) +// h(n+1) = f(n) + h(n) +// Initial values are h(1) = 1 and g(1) = 1. + +constexpr size_t mod{1000000007}; +constexpr size_t maxn{1000001}; +std::vector<size_t> f(maxn); +std::vector<size_t> g(maxn); +std::vector<size_t> h(maxn); + +int main() { + g[1] = h[1] = 1; + f[1] = 2; + for (size_t i = 2; i < maxn; i++) { + g[i] = (f[i-1] + 3*g[i-1]) % mod; + h[i] = (f[i-1] + h[i-1]) % mod; + f[i] = (g[i] + h[i]) % mod; + } + + size_t t; + std::cin >> t; + for (size_t i = 0; i < t; i++) { + size_t n; + std::cin >> n; + std::cout << f[n] << "\n"; + } +} diff --git a/03_dynamic_programming/dice_combinations_1633.cpp b/03_dynamic_programming/dice_combinations_1633.cpp @@ -0,0 +1,19 @@ +#include <algorithm> +#include <array> +#include <iostream> + +// We use a funny memory optimization: we only store the last 7 values. + +int main() { + constexpr unsigned mod = 1e9+7; + int n; + std::cin >> n; + std::array<int, 7> v{0}; + v[0] = 1; + for (int i = 1; i <= n; i++) { + v[i%7] = 0; + for (int j = std::max(0, i-6); j < i; j++) + v[i%7] = (v[i%7]+v[j%7]) % mod; + } + std::cout << v[n%7] << "\n"; +} diff --git a/03_dynamic_programming/edit_distance_1639.cpp b/03_dynamic_programming/edit_distance_1639.cpp @@ -0,0 +1,22 @@ +#include <algorithm> +#include <iostream> +#include <string> +#include <vector> + +int d(const std::string& a, const std::string& b, size_t i, size_t j, + std::vector<std::vector<int>>& t) { + if (t[i][j] != -1) return t[i][j]; + if (i == a.size()) return t[i][j] = b.size()-j; + if (j == b.size()) return t[i][j] = a.size()-i; + if (a[i] == b[j]) return t[i][j] = d(a, b, i+1, j+1, t); + return t[i][j] = 1+std::min(d(a, b, i+1, j+1, t), + std::min(d(a, b, i+1, j, t), d(a, b, i, j+1, t))); +} + +int main() { + std::string a, b; + std::cin >> a >> b; + std::vector<std::vector<int>> + t(a.size()+1, std::vector<int>(b.size()+1, -1)); + std::cout << d(a, b, 0, 0, t) << "\n"; +} diff --git a/03_dynamic_programming/longest_common_subsequence_3403.cpp b/03_dynamic_programming/longest_common_subsequence_3403.cpp @@ -0,0 +1,44 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int f(const std::vector<int>& a, const std::vector<int>& b, size_t i, size_t j, + std::vector<std::vector<int>>& t) { + if (i == a.size() || j == b.size()) return t[i][j] = 0; + if (t[i][j] != -1) return t[i][j]; + if (a[i] == b[j]) return t[i][j] = 1+f(a, b, i+1, j+1, t); + return t[i][j] = std::max(f(a, b, i+1, j, t), f(a, b, i, j+1, t)); +} + +std::vector<int> read(size_t n) { + std::vector<int> a(n); + for (size_t i = 0; i < n; i++) + std::cin >> a[i]; + return a; +} + +int main() { + std::size_t n, m; + std::cin >> n >> m; + std::vector<int> a = read(n); + std::vector<int> b = read(m); + std::vector<std::vector<int>> t(n+1, std::vector<int>(m+1, -1)); + int x = f(a, b, 0, 0, t); + std::cout << x << "\n"; + + std::vector<int> s; + size_t i{0}, j{0}; + while (x > 0) { + if (a[i] == b[j]) { + s.push_back(a[i]); + i++; j++; x--; + } else { + if (t[i+1][j] == x) i++; + else j++; + } + } + + for (auto x : s) + std::cout << x << " "; + std::cout << "\n"; +} diff --git a/03_dynamic_programming/minimizing_coins_1634.cpp b/03_dynamic_programming/minimizing_coins_1634.cpp @@ -0,0 +1,33 @@ +#include <algorithm> +#include <iostream> +#include <queue> +#include <vector> + +int f(const std::vector<int>& c, int x) { + static constexpr int max = 999999999; + std::vector<int> a(x+1, max); + std::queue<int> q; + a[0] = 0; + q.push(0); + while (!q.empty()) { + auto i = q.front(); + q.pop(); + for (auto k : c) { + if (i + k > x || a[i+k] <= a[i]+1) continue; + if (i + k == x) return a[i] + 1; + a[i+k] = a[i] + 1; + q.push(i + k); + } + } + return -1; +} + +int main() { + int n, x; + std::cin >> n >> x; + std::vector<int> c(n); + for (int i = 0; i < n; i++) + std::cin >> c[i]; + + std::cout << f(c, x) << "\n"; +} diff --git a/03_dynamic_programming/removing_digits_1637.cpp b/03_dynamic_programming/removing_digits_1637.cpp @@ -0,0 +1,28 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +static constexpr int inf = 1999999999; + +std::vector<int> digits(int n) { + std::vector<int> d; + for (int i = n; i != 0; i /= 10) + d.push_back(i % 10); + return d; +} + +int f(std::vector<int>& a, int n) { + if (a[n] != inf) return a[n]; + for (auto d : digits(n)) + if (d != 0) + a[n] = std::min(a[n], 1+f(a, n-d)); + return a[n]; +} + +int main() { + int n; + std::cin >> n; + std::vector<int> a(n+1, inf); + a[0] = 0; + std::cout << f(a, n) << "\n"; +} diff --git a/04_graph_algorithms/a.out b/04_graph_algorithms/a.out Binary files differ. diff --git a/04_graph_algorithms/building_roads_1666.cpp b/04_graph_algorithms/building_roads_1666.cpp @@ -0,0 +1,32 @@ +#include <iostream> +#include <vector> + +void visit(size_t i, const std::vector<std::vector<size_t>>& a, + std::vector<bool>& c) { + if (c[i]) return; + c[i] = true; + for (auto j : a[i]) + visit(j, a, c); +} + +int main() { + size_t n, m; + std::cin >> n >> m; + std::vector<std::vector<size_t>> a(n); + for (size_t i = 0; i < m; i++) { + size_t x, y; + std::cin >> x >> y; + a[x-1].push_back(y-1); + a[y-1].push_back(x-1); + } + + std::vector<bool> c(n, false); + std::vector<size_t> s; + for (size_t i = 0; i < n; i++) { + if (c[i]) continue; + if (i != 0) s.push_back(i); + visit(i, a, c); + } + std::cout << s.size() << "\n"; + for (auto x : s) std::cout << "1 " << x+1 << "\n"; +} diff --git a/04_graph_algorithms/building_teams_1668.cpp b/04_graph_algorithms/building_teams_1668.cpp @@ -0,0 +1,37 @@ +#include <iostream> +#include <vector> + +bool visit(size_t i, int c, const std::vector<std::vector<size_t>>& a, + std::vector<int>& t) { + if (t[i] != 0) return true; + t[i] = c; + for (auto j : a[i]) + if (t[j] == c) + return false; + else if (!visit(j, 3-c, a, t)) return false; + return true; +} + +int main() { + size_t n, m; + std::cin >> n >> m; + std::vector<std::vector<size_t>> a(n); + for (size_t i = 0; i < m; i++) { + size_t x, y; + std::cin >> x >> y; + a[x-1].push_back(y-1); + a[y-1].push_back(x-1); + } + + std::vector<int> t(n); + for (size_t i = 0; i < n; i++) { + if (t[i] == 0) { + if (!visit(i, 1, a, t)) { + std::cout << "IMPOSSIBLE\n"; + return 0; + } + } + } + for (auto x : t) std::cout << x << " "; + std::cout << "\n"; +} diff --git a/04_graph_algorithms/counting_rooms_1192.cpp b/04_graph_algorithms/counting_rooms_1192.cpp @@ -0,0 +1,62 @@ +#include <iostream> +#include <string> +#include <vector> + +class Tile { +public: + int i; + int j; + std::vector<Tile> neighbors() const { + return {Tile{i-1,j}, Tile{i+1,j}, Tile{i,j-1}, Tile{i,j+1}}; + } +}; + +class Map { +public: + int n; + int m; + + Map(int i, int j) : n{i}, m{j}, c(n*m, 0) {} + int color(Tile t) const { return inbound(t) ? c[ind(t)] : -1; } + void setcolor(Tile t, int k) { if (inbound(t)) c[ind(t)] = k; } + bool wall(Tile t) const { return !inbound(t) || c[ind(t)] == -1; } + void setwall(Tile t) { if (inbound(t)) setcolor(t, -1); } +private: + std::vector<int> c; + + size_t ind(Tile t) const { return m*t.i + t.j; } + bool inbound(Tile t) const { + return t.i >= 0 && t.i < n && t.j >= 0 && t.j < m; + } +}; + +Map readmap() { + int n, m; + std::string s; + std::cin >> n >> m; + Map map(n, m); + for (int i = 0; i < n; i++) { + std::cin >> s; + for (int j = 0; j < m; j++) + if (s[j] == '#') + map.setwall(Tile{i, j}); + } + return map; +} + +void visit(Map& m, Tile t, int c) { + m.setcolor(t, c); + for (auto u : t.neighbors()) + if (m.color(u) == 0) + visit(m, u, c); +} + +int main() { + auto m = readmap(); + int c{0}; + for (int i = 0; i < m.n; i++) + for (int j = 0; j < m.m; j++) + if (m.color(Tile{i, j}) == 0) + visit(m, Tile{i, j}, ++c); + std::cout << c << "\n"; +} diff --git a/04_graph_algorithms/high_score_1673.cpp b/04_graph_algorithms/high_score_1673.cpp @@ -0,0 +1,61 @@ +#include <algorithm> +#include <iostream> +#include <tuple> +#include <vector> + +constexpr long long inf = 999999999999999LL; + +size_t findcycle( + size_t v, + const std::vector<std::tuple<size_t, size_t, long long>>& a, + const std::vector<size_t>& p +) { + std::vector<bool> visited(p.size(), false); + visited[v] = true; + size_t u = p[v]; + while (!visited[u]) { + visited[u] = true; + u = p[u]; + } + return u; +} + +int main() { + size_t n, m; + std::cin >> n >> m; + std::vector<std::tuple<size_t, size_t, long long>> a(m); + for (size_t i = 0; i < m; i++) { + size_t x, y; + long long w; + std::cin >> x >> y >> w; + a[i] = {x-1, y-1, w}; + } + + std::vector<size_t> p(n, n); + std::vector<long long> d(n, -inf); + d[0] = 0; + std::vector<bool> reach_1(n, false), reach_n(n, false); + reach_1[0] = reach_n[n-1] = true; + for (size_t i = 0; i < n; i++) { + for (auto [v, u, w] : a) { + if (d[u] < d[v] + w) { + d[u] = d[v] + w; + p[u] = v; + } + reach_n[v] = reach_n[v] || reach_n[u]; + reach_1[u] = reach_1[u] || reach_1[v]; + } + } + + for (auto [v, u, w] : a) { + if (d[u] < d[v] + w) { + size_t x = findcycle(u, a, p); + if (reach_1[x] && reach_n[x]) { + std::cout << "-1\n"; + return 0; + } + } + } + + std::cout << d[n-1] << "\n"; +} diff --git a/04_graph_algorithms/labyrinth_1193.cpp b/04_graph_algorithms/labyrinth_1193.cpp @@ -0,0 +1,131 @@ +#include <iostream> +#include <queue> +#include <ranges> +#include <string> +#include <tuple> +#include <vector> + +struct Pos { + size_t i; + size_t j; + + Pos(size_t a = 0, size_t b = 0) : i{a}, j{b} {} + bool operator==(const Pos& p) const { return i == p.i && j == p.j; } + + std::vector<Pos> neighbors() const { + return {Pos(i+1, j), Pos(i-1, j), Pos(i, j+1), Pos(i, j-1)}; + } + + char dir(const Pos& p) const { + if (p.i == i+1 && p.j == j) return 'D'; + if (p.i == i-1 && p.j == j) return 'U'; + if (p.i == i && p.j == j+1) return 'R'; + if (p.i == i && p.j == j-1) return 'L'; + return 'X'; + } +}; + +class Map { +public: + Map(size_t i, size_t j) : n{i}, m{j}, v(n, std::vector<bool>(m)) {} + Pos start() const { return a; } + Pos finish() const { return b; } + bool operator[](Pos p) const { return inb(p) && v[p.i][p.j]; } + + friend std::istream& operator>>(std::istream& is, Map& map) { + std::string s; + is >> s; + for (size_t j = 0; j < map.m; j++) + map.readchar(s[j], map.l, j); + map.l++; + return is; + } + + friend std::ostream& operator<<(std::ostream& os, const Map& map) { + for (size_t i = 0; i < map.n; i++) { + for (size_t j = 0; j < map.m; j++) { + if (map.a == Pos(i, j)) os << 'A'; + else if (map.b == Pos(i, j)) os << 'B'; + else os << (map.v[i][j] ? '.' : '#'); + } + os << "\n"; + } + return os; + } + + template<typename T> + using Overlay = std::pair<T, std::vector<std::vector<T>>>; + + template<typename T> + Overlay<T> overlay(T t) const { + auto ov = std::vector<std::vector<T>>(n, std::vector(m, t)); + return {t, ov}; + } + + template<typename T> + T at(const Overlay<T>& ov, Pos p) const { + return inb(p) ? ov.second[p.i][p.j] : ov.first; + } + + template<typename T> + void set(Overlay<T>& ov, Pos p, T val) const { + if (inb(p)) ov.second[p.i][p.j] = val; + } +private: + size_t l{0}; + size_t n; + size_t m; + Pos a; + Pos b; + std::vector<std::vector<bool>> v; + + void readchar(char c, size_t i, size_t j) { + v[i][j] = c != '#'; + if (c == 'A') a = {i, j}; + if (c == 'B') b = {i, j}; + } + + bool inb(Pos p) const { return p.i < n && p.j < m; } +}; + +int main() { + size_t n, m; + std::cin >> n >> m; + Map map(n, m); + for (size_t i = 0; i < n; i++) + std::cin >> map; + + constexpr size_t inf{999999999}; + auto d = map.overlay<size_t>(inf); + std::queue<std::pair<Pos, size_t>> q; + q.push({map.start(), 0}); + while (!q.empty()) { + auto [p, w] = q.front(); + q.pop(); + if (!map[p] || map.at(d, p) != inf) continue; + map.set(d, p, w); + for (auto x : p.neighbors()) q.push({x, w+1}); + } + + if (map.at(d, map.finish()) == inf) { + std::cout << "NO\n"; + } else { + std::cout << "YES\n" << map.at(d, map.finish()) << "\n"; + + // Backtrack + Pos p = map.finish(); + std::vector<char> path; + do { + for (auto x : p.neighbors()) { + if (map.at(d, x) == map.at(d, p)-1) { + path.push_back(x.dir(p)); + p = x; + break; + } + } + } while (p != map.start()); + for (auto c : path | std::views::reverse) + std::cout << c; + std::cout << "\n"; + } +} diff --git a/04_graph_algorithms/message_route_1667.cpp b/04_graph_algorithms/message_route_1667.cpp @@ -0,0 +1,54 @@ +#include <iostream> +#include <queue> +#include <ranges> +#include <vector> + +constexpr size_t inf = 1999999999; + +int main() { + size_t n, m; + std::cin >> n >> m; + std::vector<std::vector<size_t>> a(n); + for (size_t i = 0; i < m; i++) { + size_t x, y; + std::cin >> x >> y; + a[x-1].push_back(y-1); + a[y-1].push_back(x-1); + } + + std::queue<size_t> q; + std::vector<size_t> d(n, inf); + d[0] = 0; + q.push(0); + while (!q.empty()) { + auto i = q.front(); + q.pop(); + if (i == n-1) break; + for (auto j : a[i]) { + if (d[j] > d[i]+1) { + d[j] = d[i] + 1; + q.push(j); + } + } + } + + if (d[n-1] == inf) { + std::cout << "IMPOSSIBLE\n"; + } else { + std::cout << d[n-1]+1 << "\n"; + // Backtracking + std::vector<size_t> v; + v.push_back(n-1); + while (v.back() != 0) { + for (auto j : a[v.back()]) { + if (d[j] == d[v.back()]-1) { + v.push_back(j); + break; + } + } + } + for (auto x : v | std::views::reverse) + std::cout << x+1 << " "; + std::cout << "\n"; + } +} diff --git a/04_graph_algorithms/round_trip_1669.cpp b/04_graph_algorithms/round_trip_1669.cpp @@ -0,0 +1,44 @@ +#include <iostream> +#include <vector> + +std::vector<int> cyc; + +int dfs(const std::vector<std::vector<int>>& a, + std::vector<bool>& v, int i, int p) { + v[i] = true; + for (auto x : a.at(i)) { + if (x == p) continue; + if (v.at(x)) { + cyc.push_back(x); + cyc.push_back(i); + return x; + } + if (int r = dfs(a, v, x, i); r != 0) { + cyc.push_back(i); + if (r == i) { + std::cout << cyc.size() << "\n"; + for (auto y : cyc) std::cout << y << " "; + std::cout << "\n"; + exit(0); + } else return r; + } + } + return 0; +} + +int main() { + int n, m; + std::cin >> n >> m; + std::vector<std::vector<int>> a(n+1); + for (int i = 0; i < m; i++) { + int x, y; + std::cin >> x >> y; + a[x].push_back(y); + a[y].push_back(x); + } + std::vector<bool> v(n+1); + for (int i = 1; i <= n; i++) + if (!v.at(i)) + dfs(a, v, i, 0); + std::cout << "IMPOSSIBLE\n"; +} diff --git a/04_graph_algorithms/shortest_routes_i_1671.cpp b/04_graph_algorithms/shortest_routes_i_1671.cpp @@ -0,0 +1,43 @@ +#include <iostream> +#include <queue> +#include <utility> +#include <vector> + +class dvpair { +public: + size_t d; + size_t v; + auto operator<=>(const dvpair& p) const { return p.d <=> d; } +}; + +int main() { + size_t n, m; + std::cin >> n >> m; + std::vector<std::vector<std::pair<size_t, size_t>>> a(n); + for (size_t i = 0; i < m; i++) { + size_t x, y, z; + std::cin >> x >> y >> z; + a[x-1].push_back({y-1, z}); + } + + constexpr size_t inf{999999999999999ULL}; + std::vector<size_t> d(n, inf); + std::priority_queue<dvpair> q; + d[0] = 0; + q.push({0, 0}); + while (!q.empty()) { + auto [dd, p] = q.top(); + q.pop(); + if (dd > d[p]) + continue; + for (auto [r, w] : a[p]) { + if (w + d[p] < d[r]) { + d[r] = d[p] + w; + q.push({d[r], r}); + } + } + } + for (auto x : d) + std::cout << x << " "; + std::cout << "\n"; +} diff --git a/04_graph_algorithms/shortest_routes_ii_1672.cpp b/04_graph_algorithms/shortest_routes_ii_1672.cpp @@ -0,0 +1,30 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +constexpr size_t inf{999999999999999ULL}; + +int main() { + size_t n, m, q; + std::cin >> n >> m >> q; + std::vector<std::vector<size_t>> d(n, std::vector(n, inf)); + for (size_t i = 0; i < n; i++) d[i][i] = 0; + for (size_t i = 0; i < m; i++) { + size_t x, y, z; + std::cin >> x >> y >> z; + d[x-1][y-1] = d[y-1][x-1] = std::min(d[x-1][y-1], z); + } + + for (size_t k = 0; k < n; k++) + for (size_t i = 0; i < n; i++) + for (size_t j = 0; j < n; j++) + d[j][i] = d[i][j] = + std::min(d[i][j], d[i][k] + d[k][j]); + + for (size_t i = 0; i < q; i++) { + size_t x, y; + std::cin >> x >> y; + long long int dd = d[x-1][y-1]; + std::cout << (dd == inf ? -1LL : dd) << "\n"; + } +} diff --git a/05_range_queries/a.out b/05_range_queries/a.out Binary files differ. diff --git a/05_range_queries/dynamic_range_minimum_queries_1649.cpp b/05_range_queries/dynamic_range_minimum_queries_1649.cpp @@ -0,0 +1,54 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +constexpr size_t inf = 1999999999; + +class SegmentTree { +public: + SegmentTree(size_t n) : m{pow2ceil(n)}, v(2*m, inf) {} + + void update(size_t i, size_t x) { + v[m+i-1] = x; + for (size_t p = (m+i-1)/2; p > 0; p /= 2) + v[p] = std::min(v[2*p], v[2*p+1]); + } + + size_t min(size_t a, size_t b) { return q(a-1, b, 1, 0, m); } + +private: + size_t m; + std::vector<size_t> v; + static constexpr size_t pow2ceil(size_t x) { + size_t c; + for (c = 1; c < x; c *= 2) ; + return c; + } + + size_t q(size_t a, size_t b, size_t i, size_t l, size_t r) { + if (a == l && b == r) return v[i]; + size_t p{(l+r)/2}, s{inf}; + if (a < p) s = std::min(s, q(a, std::min(b, p), 2*i, l, p)); + if (b > p) s = std::min(s, q(std::max(a, p), b, 2*i+1, p, r)); + return s; + } +}; + +int main() { + size_t n, q; + std::cin >> n >> q; + SegmentTree t(n); + for (size_t i = 0; i < n; i++) { + size_t x; + std::cin >> x; + t.update(i+1, x); + } + for (size_t i = 0; i < q; i++) { + int u, a, b; + std::cin >> u >> a >> b; + if (u == 1) + t.update(a, b); + else + std::cout << t.min(a, b) << "\n"; + } +} diff --git a/05_range_queries/dynamic_range_sum_queries_1648.cpp b/05_range_queries/dynamic_range_sum_queries_1648.cpp @@ -0,0 +1,50 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +class SumFenwickTree { +public: + SumFenwickTree(int n) : a(n+1) {} + long long sum(int l, int r) const { return psum(r) - psum(l-1); } + void update(int k, long long u) { add(k, u - sum(k, k));} + +private: + std::vector<long long> a; + + static int lsb(int i) { return i & -i; } + + long long psum(int i) const { + long long s = 0; + while (i > 0) { + s += a[i]; + i -= lsb(i); + } + return s; + } + + void add(int k, long long d) { + while (k < (int)a.size()) { + a[k] += d; + k += lsb(k); + } + } +}; + +int main() { + size_t n, q; + std::cin >> n >> q; + SumFenwickTree t(n); + for (size_t i = 0; i < n; i++) { + long long x; + std::cin >> x; + t.update(i+1, x); + } + for (size_t i = 0; i < q; i++) { + long long x, k, u; + std::cin >> x >> k >> u; + if (x == 1) + t.update(k, u); + else + std::cout << t.sum(k, u) << "\n"; + } +} diff --git a/05_range_queries/range_xor_queries_1650.cpp b/05_range_queries/range_xor_queries_1650.cpp @@ -0,0 +1,20 @@ +#include <algorithm> +#include <iostream> +#include <vector> + +int main() { + size_t n, q; + std::cin >> n >> q; + std::vector<int> p(n); + for (size_t i = 0; i < n; i++) + std::cin >> p[i]; + for (size_t i = 1; i < n; i++) + p[i] ^= p[i-1]; + for (size_t i = 0; i < q; i++) { + int x, k, s; + std::cin >> x >> k; + s = p[k-1]; + if (x > 1) s ^= p[x-2]; + std::cout << s << "\n"; + } +} diff --git a/05_range_queries/static_range_minimum_queries_1647.cpp b/05_range_queries/static_range_minimum_queries_1647.cpp @@ -0,0 +1,47 @@ +#include <iostream> +#include <limits> +#include <vector> + +int minrange(std::vector<int>& a, int x, int y, int i, int p, int l, int r) { + if (x == l && y == r) + return a[2*p-2-i]; + + if (x >= y) + return std::numeric_limits<int>::max(); + + int lr = (l+r)/2; + return std::min( + minrange(a, std::max(x, l), std::min(y, lr), 2*i+2, p, l, lr), + minrange(a, std::max(x, lr), std::min(y, r), 2*i+1, p, lr, r) + ); +} + +void compute_mins(std::vector<int>& a, int j, int n) { + for (int i = 0; i < n; i += 2) + a[j+n+i/2] = std::min(a[j+i], a[j+i+1]); +} + +int main() { + int n, q, x, y, p; + std::cin >> n >> q; + + // For simplicity, extend n to a power of 2 + for (p = 1; p < n; p <<= 1) ; + + std::vector<int> a(2*p-1, 0); + for (int i = 0; i < n; i++) + std::cin >> a[i]; + + // a[p], a[p+1] ... a[p+p/2-1] are min of pairs + // a[p+p/2], a[p+p/2+1], ... a[p+p/2+p/4] are min of quads + // etc... + for (int i = 1, j = 0; i < p; i <<= 1) { + compute_mins(a, j, p/i); + j += p/i; + } + + for (int i = 0; i < q; i++) { + std::cin >> x >> y; + std::cout << minrange(a, x-1, y, 0, p, 0, p) << "\n"; + } +} diff --git a/05_range_queries/static_range_sum_queries_1646.cpp b/05_range_queries/static_range_sum_queries_1646.cpp @@ -0,0 +1,17 @@ +#include <iostream> +#include <vector> + +int main() { + int n, q, x, y; + std::cin >> n >> q; + std::vector<long long> a(n+1, 0); + for (int i = 1; i <= n; i++) { + std::cin >> a[i]; + a[i] += a[i-1]; + } + + for (int i = 0; i < q; i++) { + std::cin >> x >> y; + std::cout << a[y]-a[x-1] << "\n"; + } +} diff --git a/06_tree_algorithms/a.out b/06_tree_algorithms/a.out Binary files differ. diff --git a/06_tree_algorithms/subordinates_1674.cpp b/06_tree_algorithms/subordinates_1674.cpp @@ -0,0 +1,23 @@ +#include <iostream> +#include <vector> + +int f(const std::vector<std::vector<int>>& a, std::vector<int>& b, int i) { + for (auto x : a[i]) + b[i] += f(a, b, x) + 1; + return b[i]; +} + +int main() { + int n, x; + std::cin >> n; + std::vector<std::vector<int>> a(n); + for (int i = 1; i < n; i++) { + std::cin >> x; + a[x-1].push_back(i); + } + std::vector<int> b(n, 0); + f(a, b, 0); + for (auto y : b) + std::cout << y << " "; + std::cout << std::endl; +} diff --git a/06_tree_algorithms/tree_matching_1130.cpp b/06_tree_algorithms/tree_matching_1130.cpp @@ -0,0 +1,41 @@ +#include <iostream> +#include <vector> + +int f(const std::vector<std::vector<int>>& a, + std::vector<std::vector<int>>& t, int v, int p, bool x) { + if (t[v][x] != -1) return t[v][x]; + if (p != -1 && a[v].size() == 1) return t[v][x] = 0; + + t[v][x] = 0; + for (auto u : a[v]) { + if (u == p) continue; + t[v][x] += f(a, t, u, v, false); + } + if (x) return t[v][x]; + + for (auto u : a[v]) { + if (u == p) continue; + if (f(a, t, u, v, true) == t[u][false]) { + t[v][x]++; + break; + } + } + return t[v][x]; +} + +int main() { + int n, x, y; + std::cin >> n; + std::vector<std::vector<int>> a(n); + for (int i = 0; i < n-1; i++) { + std::cin >> x >> y; + a[x-1].push_back(y-1); + a[y-1].push_back(x-1); + } + if (n == 1) { + std::cout << "0\n"; + return 0; + } + std::vector<std::vector<int>> t(n, {-1, -1}); + std::cout << f(a, t, 0, -1, false) << "\n"; +} diff --git a/07_mathematics/a.out b/07_mathematics/a.out Binary files differ. diff --git a/07_mathematics/common_divisors_1081.cpp b/07_mathematics/common_divisors_1081.cpp @@ -0,0 +1,53 @@ +#include <array> +#include <bitset> +#include <iostream> + +// This method is very different (and more complicated) than the one used +// in the official solution. +// First we save in spf[i] the smallest prime number that divides i. +// Then we initialize an array d with d[i] being 1 if i is in the input. +// Then we loop backwards and we search all divisors of the numbers marked +// in d. For each number we encounter, we look at its maximal divisors. +// If any of them was already found, we update our candidate solution. +// To avoid looking at a divisor more than once, we save in d[i] the +// smallest prime we want to continue diving i by to find more divisors. + +constexpr size_t max = 1000001; +std::array<size_t, max> spf; // Smallest prime factor of i +std::array<size_t, max> d; + +int main() { + for (size_t i = 2; i < max; i++) { + if (spf[i] != 0) continue; + spf[i] = i; + for (size_t j = 2; i*j < max; j++) + if (spf[i*j] == 0) + spf[i*j] = i; + } + + size_t n, sol{1}; + std::cin >> n; + for (size_t i = 0; i < n; i++) { + size_t x; + std::cin >> x; + if (d[x] != 0) sol = std::max(sol, x); + d[x] = 1; + } + + for (size_t i = max-1; i >= sol; i--) { + if (d[i] == 0) continue; + + // Loop over maximal divisors of i + size_t y{i}; + while (y != 1) { + size_t p = spf[y]; + if (i/p < sol) break; + if (p >= d[i]) { + if (d[i/p] != 0) sol = std::max(sol, i/p); + d[i/p] = p; + } + while (y % p == 0) y /= p; + } + } + std::cout << sol << "\n"; +} diff --git a/07_mathematics/counting_divisors_1713.cpp b/07_mathematics/counting_divisors_1713.cpp @@ -0,0 +1,34 @@ +#include <array> +#include <iostream> + +constexpr size_t max = 1000001; +std::array<size_t, max> spf; // Smallest prime factor of i + +size_t ndiv(size_t x) { + size_t n{1}, d{0}, e{0}; + for (size_t i = x; i > 1; i /= spf[i]) { + if (spf[i] != d) { + n *= e+1; + d = spf[i]; + e = 1; + } else e++; + } + return n * (e+1); +} + +int main() { + for (size_t i = 2; i < max; i++) { + if (spf[i] != 0) continue; + spf[i] = i; + for (size_t j = 2; i*j < max; j++) + if (spf[i*j] == 0) + spf[i*j] = i; + } + + size_t n, x; + std::cin >> n; + for (size_t i = 0; i < n; i++) { + std::cin >> x; + std::cout << ndiv(x) << "\n"; + } +} diff --git a/07_mathematics/exponentiation_1095.cpp b/07_mathematics/exponentiation_1095.cpp @@ -0,0 +1,19 @@ +#include <iostream> + +static constexpr unsigned long long MOD = 1000000007; + +unsigned long long pow(unsigned long long a, unsigned long long b) { + if (b == 0) return 1; + if (a == 0) return 0; + if (b % 2 == 0) return pow(a*a % MOD, b/2) % MOD; + return (a * pow(a, b-1)) % MOD; +} + +int main() { + unsigned long long n, a, b; + std::cin >> n; + for (unsigned long long i = 0; i < n; i++) { + std::cin >> a >> b; + std::cout << pow(a, b) << "\n"; + } +} diff --git a/07_mathematics/exponentiation_ii_1712.cpp b/07_mathematics/exponentiation_ii_1712.cpp @@ -0,0 +1,20 @@ +#include <iostream> + +static constexpr unsigned long long MOD = 1000000007; + +unsigned long long pow(unsigned long long a, unsigned long long b, + unsigned long long mod) { + if (b == 0) return 1; + if (a == 0) return 0; + if (b % 2 == 0) return pow(a*a % mod, b/2, mod) % mod; + return (a * pow(a, b-1, mod)) % mod; +} + +int main() { + unsigned long long n, a, b, c; + std::cin >> n; + for (unsigned long long i = 0; i < n; i++) { + std::cin >> a >> b >> c; + std::cout << pow(a, pow(b, c, MOD-1), MOD) << "\n"; + } +} diff --git a/07_mathematics/josephus_queries_2164.cpp b/07_mathematics/josephus_queries_2164.cpp @@ -0,0 +1,17 @@ +#include <iostream> + +int f(int n, int k, int m) { + int h = n/2 + m*(n%2); + if (n == 1) return 1; + if (k <= h) return 2*k-m; + return 2*f(n-h, k-h, m^(n%2))+m-1; +} + +int main() { + int q, n, k; + std::cin >> q; + for (int i = 0; i < q; i++) { + std::cin >> n >> k; + std::cout << f(n, k, 0) << "\n"; + } +} diff --git a/08_string_algorithms/a.out b/08_string_algorithms/a.out Binary files differ. diff --git a/08_string_algorithms/finding_borders_1732.cpp b/08_string_algorithms/finding_borders_1732.cpp @@ -0,0 +1,23 @@ +#include <algorithm> +#include <iostream> +#include <string> +#include <vector> + +int main() { + std::string s; + std::cin >> s; + std::vector<size_t> z(s.size(), 0), c; + z[0] = s.size(); + for (size_t i = 1, j = 0, k = 0; i < s.size(); i++) { + if (j < i || z[i-k] == j-i) { + for (j = std::max(i, j); j < s.size() && s[j] == s[j-i]; j++) ; + z[k=i] = j-i; + } else z[i] = std::min(z[i-k], j-i); + if (z[i] == s.size()-i) + c.push_back(z[i]); + } + std::sort(c.begin(), c.end()); + for (auto x : c) + std::cout << x << " "; + std::cout << "\n"; +} diff --git a/08_string_algorithms/finding_periods_1733.cpp b/08_string_algorithms/finding_periods_1733.cpp @@ -0,0 +1,29 @@ +#include <algorithm> +#include <iostream> +#include <string> +#include <vector> + +bool isp(const std::vector<size_t>& z, size_t k) { + for (size_t i = 0; i*k < z.size(); i++) + if (z[i*k] < std::min(k, z.size()-i*k)) + return false; + return true; +} + +int main() { + std::string s; + std::cin >> s; + std::vector<size_t> z(s.size(), 0); + z[0] = s.size(); + for (size_t i = 1, j = 0, k = 0; i < s.size(); i++) { + if (j < i || z[i-k] == j-i) { + for (j = std::max(i, j); j < s.size() && s[j] == s[j-i]; j++) ; + z[k=i] = j-i; + } else z[i] = std::min(z[i-k], j-i); + } + + for (size_t i = 1; i <= s.size(); i++) + if (isp(z, i)) + std::cout << i << " "; + std::cout << "\n"; +} diff --git a/08_string_algorithms/string_matching_1753.cpp b/08_string_algorithms/string_matching_1753.cpp @@ -0,0 +1,32 @@ +#include <iostream> +#include <string> +#include <vector> + +struct S { + std::string w; + std::string t; + + size_t size() const { return w.size() + 1 + t.size(); } + + char operator[](size_t i) const { + if (i < w.size()) return w.at(i); + if (i > w.size()) return t.at(i-w.size()-1); + return '$'; + } +}; + +int main() { + S s; + std::cin >> s.t >> s.w; + size_t c{0}; + std::vector<size_t> z(s.size(), 0); + z[0] = s.w.size(); + for (size_t i = 1, j = 0, k = 0; i < s.size(); i++) { + if (j < i || z[i-k] == j-i) { + for (j = std::max(i, j); j < s.size() && s[j] == s[j-i]; j++) ; + z[k=i] = j-i; + } else z[i] = std::min(z[i-k], j-i); + c += z[i] == s.w.size(); + } + std::cout << c << "\n"; +} diff --git a/08_string_algorithms/word_combinations_1731.cpp b/08_string_algorithms/word_combinations_1731.cpp @@ -0,0 +1,63 @@ +#include <iostream> +#include <queue> +#include <string> +#include <string_view> +#include <vector> + +struct TrieNode { + char c; + size_t d; + bool isend; + std::vector<TrieNode> next; + + TrieNode(char x, size_t y) : c{x}, d{y}, isend{false}, next() {} +}; + +void push(std::string_view s, TrieNode& t) { + if (s.empty()) { + t.isend = true; + return; + } + for (auto& u : t.next) { + if (s[0] == u.c) { + push(s.substr(1), u); + return; + } + } + t.next.push_back(TrieNode(s[0], t.d+1)); + push(s.substr(1), t.next.back()); +} + +const TrieNode* next(const TrieNode* w, char c) { + for (size_t i = 0; i < w->next.size(); i++) + if (w->next[i].c == c) + return &w->next[i]; + return nullptr; +} + +int f(std::vector<int>& t, std::string_view s, const TrieNode& d, size_t i) { + static constexpr long long mod = 1e9+7; + + if (t[i] != -1) return t[i]; + + t[i] = 0; + for (const TrieNode* w = &d; w != nullptr; w = next(w, s[w->d])) + if (w->isend) + t[i] = (t[i] + f(t, s.substr(w->d), d, i+w->d)) % mod; + return t[i]; +} + +int main() { + std::string s, u; + size_t k; + std::cin >> s >> k; + TrieNode d('\0', 0); + for (size_t i = 0; i < k; i++) { + std::cin >> u; + push(u, d); + } + + std::vector<int> t(s.size()+1, -1); + t[s.size()] = 1; + std::cout << f(t, s, d, 0) << "\n"; +} diff --git a/09_geometry/a.out b/09_geometry/a.out Binary files differ. diff --git a/09_geometry/line_segment_intersection_2190.cpp b/09_geometry/line_segment_intersection_2190.cpp @@ -0,0 +1,41 @@ +#include <algorithm> +#include <iostream> + +bool inran(long long int a, long long int b, long long int m) { + return m >= std::min(a, b) && m <= std::max(a, b); +} + +bool inseg(long long int d, long long int dt, long long int du) { + return dt >= 0 && dt <= d && du >= 0 && du <= d; +} + +bool f(long long int x1, long long int y1, long long int x2, long long int y2, + long long int x3, long long int y3, long long int x4, long long int y4) { + long long int xt = x2-x1, yt = y2-y1; + long long int xu = x4-x3, yu = y4-y3; + long long int d = xt * (-yu) - yt * (-xu); + long long int dt = (x3-x1) * (-yu) - (y3-y1) * (-xu); + long long int du = (xt) * (y3-y1) - (yt) * (x3-x1); + + if (d == 0) { + // Parallel on different lines + if (dt != 0 || du != 0) return false; + + // Parallel, same line + return xt == 0 ? + inran(y1,y2,y3) || inran(y1,y2,y4) || inran(y3,y4,y1) : + inran(x1,x2,x3) || inran(x1,x2,x4) || inran(x3,x4,x1); + } else { + // Not parallel + long long int m = d > 0 ? 1 : -1; + return inseg(m*d, m*dt, m*du); + } +} + +int main() { + long long int x1, y1, x2, y2, x3, y3, x4, y4; + int n; + std::cin >> n; + while (std::cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4) + std::cout << (f(x1,y1,x2,y2,x3,y3,x4,y4) ? "YES\n" : "NO\n"); +} diff --git a/09_geometry/point_location_test_2189.cpp b/09_geometry/point_location_test_2189.cpp @@ -0,0 +1,21 @@ +#include <iostream> + +struct Point { + long long x; + long long y; + Point operator-(const Point& p) const { return Point{x-p.x, y-p.y}; } + long long operator*(const Point& v) { return x * v.y - y * v.x; } +}; + +int main() { + int t; + Point a, b, c; + std::cin >> t; + for (int i = 0; i < t; i++) { + std::cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y; + auto v = (b-a)*(c-a); + if (v > 0) std::cout << "LEFT\n"; + else if (v < 0) std::cout << "RIGHT\n"; + else std::cout << "TOUCH\n"; + } +} diff --git a/10_advanced_techniques/a.out b/10_advanced_techniques/a.out Binary files differ. diff --git a/10_advanced_techniques/hamming_distance_2136.cpp b/10_advanced_techniques/hamming_distance_2136.cpp @@ -0,0 +1,22 @@ +#include <algorithm> +#include <bit> +#include <iostream> +#include <vector> + +int main() { + unsigned n, k; + std::cin >> n >> k; + std::vector<unsigned> a(n); + for (unsigned i = 0; i < n; i++) { + for (unsigned j = 0, p = 1; j < k; j++, p <<= 1) { + char c; + std::cin >> c; + if (c == '1') a[i] += p; + } + } + int s = k+1; + for (unsigned i = 0; i < n; i++) + for (unsigned j = i+1; j < n; j++) + s = std::min(s, std::popcount(a[i] ^ a[j])); + std::cout << s << "\n"; +} diff --git a/10_advanced_techniques/meet_in_the_middle_1628.cpp b/10_advanced_techniques/meet_in_the_middle_1628.cpp @@ -0,0 +1,42 @@ +#include <algorithm> +#include <iostream> +#include <numeric> +#include <unordered_map> +#include <vector> + +void add_to_map(size_t i, size_t e, long long s, + const std::vector<long long>& a, + std::unordered_map<long long, long long>& m) { + if (i == e) { m[s]++; return; } + add_to_map(i+1, e, s, a, m); + add_to_map(i+1, e, s+a[i], a, m); +} + +long long f(size_t i, size_t e, long long t, long long s, + const std::vector<long long>& a, + const std::unordered_map<long long, long long>& m) { + if (t < 0 || t > s) return 0; + if (i == e) return m.find(t) == m.end() ? 0 : m.at(t); + return f(i+1, e, t, s-a[i], a, m) + f(i+1, e, t-a[i], s-a[i], a, m); +} + +int main() { + size_t n, p; + long long x, s{0}; + std::cin >> n >> x; + std::vector<long long> a(n); + for (size_t i = 0; i < n; i++) + std::cin >> a[i]; + + std::sort(a.begin(), a.end(), std::greater<long long>()); + s = std::accumulate(a.begin(), a.end(), 0LL); + if (x > s) { + std::cout << "0\n"; + return 0; + } + + p = a.size()/2; + std::unordered_map<long long, long long> m; + add_to_map(p, a.size(), 0, a, m); + std::cout << f(0, p, x, s, a, m) << "\n"; +} diff --git a/11_sliding_window_problems/a.out b/11_sliding_window_problems/a.out Binary files differ. diff --git a/11_sliding_window_problems/sliding_window_minimum_3221.cpp b/11_sliding_window_problems/sliding_window_minimum_3221.cpp @@ -0,0 +1,29 @@ +#include <algorithm> +#include <deque> +#include <iostream> +#include <vector> + +int main() { + long long n, k, x, a, b, c; + std::cin >> n >> k >> x >> a >> b >> c; + + std::vector<long long> v(k); + std::deque<long long> q; + for (long long i = 0; i < k; i++) { + v[i] = x; + while (!q.empty() && q.back() >= x) q.pop_back(); + q.push_back(x); + x = (a*x + b) % c; + } + + long long sol = q.front(); + for (long long i = 0; i < n-k; i++) { + if (q.front() == v[i%k]) q.pop_front(); + v[i%k] = (a*v[(i-1+k)%k] + b) % c; + while (!q.empty() && q.back() >= v[i%k]) q.pop_back(); + q.push_back(v[i%k]); + sol ^= q.front(); + } + + std::cout << sol << "\n"; +} diff --git a/11_sliding_window_problems/sliding_window_or_3405.cpp b/11_sliding_window_problems/sliding_window_or_3405.cpp @@ -0,0 +1,28 @@ +#include <iostream> +#include <vector> + +// We pre-compute prefix and suffix or for non-overlapping windows of k +// elements, and we compute the sliding window or from those. +// https://codeforces.com/blog/entry/142846 + +int main() { + size_t n, k; + long long a, b, c, sol{0}; + std::cin >> n >> k; + std::vector<long long> v(n), pre(n), suf(n); + std::cin >> v[0] >> a >> b >> c; + + for (size_t i = 1; i < n; i++) + v[i] = (a*v[i-1] + b) % c; + + for (size_t i = 0; i < n; i++) + pre[i] = i % k == 0 ? v[i] : v[i] | pre[i-1]; + + for (size_t i = n; i > 0; i--) + suf[i-1] = i == n || (i-1) % k == 0 ? v[i-1] : v[i-1] | suf[i]; + + for (long long i = k-1; i < n; i++) + sol ^= pre[i] | suf[i-(k-1)]; + + std::cout << sol << "\n"; +} diff --git a/11_sliding_window_problems/sliding_window_sum_3220.cpp b/11_sliding_window_problems/sliding_window_sum_3220.cpp @@ -0,0 +1,25 @@ +#include <iostream> +#include <vector> + +int main() { + size_t n, k; + long long x, a, b, c, sum{0}, sol{0}; + std::cin >> n >> k >> x >> a >> b >> c; + + std::vector<long long> v(k); + for (size_t i = 0; i < k; i++) { + sum += x; + v[i] = x; + x = (a*x + b) % c; + } + + sol = sum; + for (size_t i = 0; i < n-k; i++) { + sum -= v[i%k]; + v[i%k] = (a*v[(i-1+k)%k] + b) % c; + sum += v[i%k]; + sol ^= sum; + } + + std::cout << sol << "\n"; +} diff --git a/11_sliding_window_problems/sliding_window_xor_3426.cpp b/11_sliding_window_problems/sliding_window_xor_3426.cpp @@ -0,0 +1,26 @@ +#include <algorithm> +#include <deque> +#include <iostream> +#include <vector> + +int main() { + long long n, k, x, a, b, c, m{0}; + std::cin >> n >> k >> x >> a >> b >> c; + + std::vector<long long> v(k); + for (long long i = 0; i < k; i++) { + v[i] = x; + m ^= x; + x = (a*x + b) % c; + } + + long long sol{m}; + for (long long i = 0; i < n-k; i++) { + m ^= v[i%k]; + v[i%k] = (a*v[(i-1+k)%k] + b) % c; + m ^= v[i%k]; + sol ^= m; + } + + std::cout << sol << "\n"; +} diff --git a/12_interactive_problems/a.out b/12_interactive_problems/a.out Binary files differ. diff --git a/12_interactive_problems/hidden_integer_3112.cpp b/12_interactive_problems/hidden_integer_3112.cpp @@ -0,0 +1,16 @@ +#include <iostream> +#include <string> + +int main() { + int m, l{0}, r{1000000000}; + std::string s; + while (l+1 != r) { + m = (l+r)/2; + std::cout << "? " << m << std::endl; + std::cin >> s; + if (s == "YES") l = m; + else r = m; + } + + std::cout << "! " << r << std::endl; +} diff --git a/12_interactive_problems/hidden_permutation_3139.cpp b/12_interactive_problems/hidden_permutation_3139.cpp @@ -0,0 +1,45 @@ +#include <iostream> +#include <iterator> +#include <string> +#include <vector> + +void print_sol(const std::vector<size_t>& v) { + std::cout << "! "; + for (size_t i = 0; i < v.size(); i++) { + for (size_t j = 0; j < v.size(); j++) { + if (v[j] == i) { + std::cout << (j+1) << " "; + break; + } + } + } + std::cout << std::endl; +} + +bool cmp(size_t i, size_t j) { + std::cout << "? " << (i+1) << " " << (j+1) << std::endl; + std::string s; + std::cin >> s; + return s == "YES"; +} + +size_t binsearch(size_t i, const std::vector<size_t>& v, size_t l, size_t r) { + if (r == l) return l; + size_t m = (l+r)/2; + return cmp(i, v[m]) ? binsearch(i, v, l, m) : binsearch(i, v, m+1, r); +} + +int main() { + size_t n; + std::vector<size_t> v; + std::cin >> n; + v.reserve(n); + + v.push_back(0); + for (size_t i = 1; i < n; i++) { + size_t pos = binsearch(i, v, 0, v.size()); + v.insert(std::next(v.begin(), pos), i); + } + + print_sol(v); +} diff --git a/13_bitwise_operations/a.out b/13_bitwise_operations/a.out Binary files differ. diff --git a/13_bitwise_operations/counting_bits_1146.cpp b/13_bitwise_operations/counting_bits_1146.cpp @@ -0,0 +1,14 @@ +#include <iostream> + +int main() { + unsigned long long n, f, p, s{0}; + std::cin >> n; + + for (unsigned long long i = 1, m = n; i <= n; i <<= 1, m >>= 1) { + f = i * (m / 2); + p = (n % (2*i)) + 1; + p = p > i ? p - i : 0; + s += f + p; + } + std::cout << s << "\n"; +} diff --git a/13_bitwise_operations/maximum_xor_subarray_1655.cpp b/13_bitwise_operations/maximum_xor_subarray_1655.cpp @@ -0,0 +1,53 @@ +#include <algorithm> +#include <iostream> +#include <unordered_set> +#include <vector> + +// First we compute the array a of cumulative xor starting from the +// first element (a[0] being set to 0 for convenience). Then we +// work bit by bit from the highest bit, building at each point +// an unordered set of the the available top-masked elements. We +// always try to find a full-mask, but when a bit is not available +// we store it in a the mask called "no". The reasoning is similar +// to finding a pair of elements in an array with a specified sum. +// The official solution uses a trie; it is more elegant and more +// efficient, but the idea is not too different. + +unsigned bit(unsigned i) { return 1U << (i-1); } + +bool no_bit(const std::vector<unsigned>& a, unsigned b) { + return std::ranges::none_of(a, [b](unsigned x){ return x & b; }); +} + +bool pair_match( + const std::unordered_set<unsigned>& s, unsigned m, unsigned no) { + for (auto x : s) + if (s.contains(((~x)&m)^no)) + return true; + return false; +} + +int main() { + size_t n; + std::cin >> n; + std::vector<unsigned> a(n+1); // Cumulative xor + a[0] = 0; + for (size_t i = 1; i <= n; i++) { + std::cin >> a[i]; + a[i] ^= a[i-1]; + } + unsigned i{32}, no{0}; + for ( ; i > 0 && no_bit(a, bit(i)); i--) + no |= bit(i); + i--; + std::unordered_set<unsigned> s; + for ( ; i > 0; i--) { + unsigned m = ~(bit(i) - 1); + s.clear(); + for (auto x : a) + s.insert(x & m); + if (!pair_match(s, m, no)) + no |= bit(i); + } + std::cout << ~no << "\n"; +} diff --git a/14_construction_problems/a.out b/14_construction_problems/a.out Binary files differ. diff --git a/14_construction_problems/inverse_inversions_2214.cpp b/14_construction_problems/inverse_inversions_2214.cpp @@ -0,0 +1,22 @@ +#include <iostream> +#include <utility> +#include <vector> + +// Observation: putting 1 at the n-th position (1-based) generates n-1 +// inversions; then, putting 2 at n-2 generates another n-2 inversions; +// and so on. +// The first step in our algorithm counts how many times we can do this, +// and leaves k pointing to the position where we should put the next +// element. All other elements are in increasing order. + +int main() { + long long n, k, p, l, m, j, i{0}; + std::cin >> n >> k; + std::vector<long long> a(n, 0); + + for (j = 1, p = 0; p < n-1 && k >= n-j; p++, j++) k -= n-j; + + for (m = p+1, l = p+2, i = 0; i < n; i++) + std::cout << ((n-i <= p || i == k) ? m-- : l++) << " "; + std::cout << "\n"; +} diff --git a/15_advanced_graph_problems/a.out b/15_advanced_graph_problems/a.out Binary files differ. diff --git a/15_advanced_graph_problems/nearest_shops_3303.cpp b/15_advanced_graph_problems/nearest_shops_3303.cpp @@ -0,0 +1,55 @@ +#include <algorithm> +#include <iostream> +#include <queue> +#include <tuple> +#include <vector> + +// The difficult part is finding for every city with an anime shop the +// closest other city with a shop. We do this via a "double BFS", where +// we reach each node twice from two different sources. + +struct V { int v1; int s1; int v2; int s2; }; + +int main() { + constexpr int max{99999999}; + int n, m, k, x, y; + std::queue<std::tuple<int, int, int>> q; + std::cin >> n >> m >> k; + std::vector<V> v(n, {max, -1, max, -1}); + for (int i = 0; i < k; i++) { + std::cin >> x; + v[x-1] = {0, x-1, max, -1}; + q.push({x-1, 0, x-1}); + } + std::vector<std::vector<int>> a(n); + for (int i = 0; i < m; i++) { + std::cin >> x >> y; + a[x-1].push_back(y-1); + a[y-1].push_back(x-1); + } + + while (!q.empty()) { + auto [u, w, s] = q.front(); + q.pop(); + for (auto z : a[u]) { + if (z == s) continue; + auto& [v1, s1, v2, s2] = v[z]; + if (v1 > w+1) { + v1 = w+1; + s1 = s; + q.push({z, w+1, s}); + } else if (s1 != s && v2 > w+1) { + v2 = w+1; + s2 = s; + q.push({z, w+1, s}); + } + } + } + + for (int i = 0; i < n; i++) { + auto [x, s, y, _] = v[i]; + auto w = s == i ? y : x; + std::cout << (w == max ? -1 : w) << " "; + } + std::cout << "\n"; +} diff --git a/16_counting_problems/a.out b/16_counting_problems/a.out Binary files differ. diff --git a/16_counting_problems/filled_subgrid_count_i_3413.cpp b/16_counting_problems/filled_subgrid_count_i_3413.cpp @@ -0,0 +1,38 @@ +#include <algorithm> +#include <iostream> +#include <string> +#include <vector> + +void fill(const std::vector<std::vector<char>>& a, + std::vector<std::vector<long long>>& t, int i, int j) { + if (a[i][j]==a[i][j+1] && a[i][j]==a[i+1][j] && a[i][j]==a[i+1][j+1]) + t[i][j] = 1+std::min({t[i+1][j], t[i][j+1], t[i+1][j+1]}); +} + +int main() { + int n, k; + std::string s; + std::cin >> n >> k; + std::vector<std::vector<char>> a(n, std::vector<char>(n)); + std::vector<std::vector<long long>> t(n, std::vector<long long>(n, 1)); + for (int i = 0; i < n; i++) { + std::cin >> s; + for (int j = 0; j < n; j++) + a[i][j] = s[j]; + } + + for (int d = n-2; d >= 0; d--) { + for (int i = d; i >= 0; i--) { + fill(a, t, i, d); + fill(a, t, d, i); + } + } + + std::vector<long long> sol(k, 0); + for (int i = 0; i < n; i++) + for (int j = 0; j < n; j++) + sol[a[i][j]-'A'] += t[i][j]; + + for (auto x : sol) + std::cout << x << "\n"; +} diff --git a/17_additional_problems_i/a.out b/17_additional_problems_i/a.out Binary files differ. diff --git a/17_additional_problems_i/shortest_subsequence_1087.cpp b/17_additional_problems_i/shortest_subsequence_1087.cpp @@ -0,0 +1,66 @@ +#include <algorithm> +#include <array> +#include <iostream> +#include <ranges> +#include <string> +#include <vector> + +// Idea: keep an array a[n][4] where a[i][x] denotes the shortest +// non-subsequence of s[:i] that ends with x. The recursive relation +// is the following: +// - For s[i] != x, a[i][x] = a[i-1][x] (easy to see). +// - For s[i] == x, we have a[i][x] = 1+min(a[i-1][y] over y): if +// the shortest non-subsequence ending with x becomes a subsequence, +// then this is realized by adding x to the any of the current 4 +// non-subsequences (including the one already ending in x); otherwise, +// the subsequence obtained by removing the x is still a valid +// non-subsequence, and it must be one of the other 3, so we get back +// the same (it can't end again in x, otherwise it would be a shorter +// non-subsequence ending in x). +// Then we have to backtrack to find an actual solution. + +size_t ind(char c) { + switch (c) { + case 'A': return 0; + case 'C': return 1; + case 'G': return 2; + case 'T': return 3; + default: return -1; + } +} + +char dni(size_t i) { + static constexpr char a[] = {'A', 'C', 'G', 'T'}; + return a[i]; +} + +size_t mi(const std::array<size_t, 4>& v) { + return *std::min_element(v.begin(), v.end()); +} + +int main() { + std::string s; + std::cin >> s; + std::vector<std::array<size_t, 4>> a(s.size(), {1, 1, 1, 1}); + + a[0][ind(s[0])] = 2; + for (size_t i = 1; i < s.size(); i++) + for (size_t j = 0; j < 4; j++) + a[i][j] = ind(s[i]) == j ? 1 + mi(a[i-1]) : a[i-1][j]; + + auto l = s.size()+2; + std::vector<char> sol; + for (size_t i = s.size(); i > 0; i--) { + auto m = mi(a[i-1]); + if (l != m) { + l = m; + auto in = std::distance(a[i-1].begin(), + std::min_element(a[i-1].begin(), a[i-1].end())); + sol.push_back(dni(in)); + } + } + + for (auto x : sol | std::views::reverse) + std::cout << x; + std::cout << "\n"; +} diff --git a/18_additional_problems_ii/a.out b/18_additional_problems_ii/a.out Binary files differ. diff --git a/18_additional_problems_ii/bouncing_ball_steps_3215.cpp b/18_additional_problems_ii/bouncing_ball_steps_3215.cpp @@ -0,0 +1,24 @@ +#include <algorithm> +#include <iostream> +#include <numeric> +#include <tuple> + +typedef long long ll; + +std::tuple<ll, ll, ll> f(ll n, ll m, ll k) { + n--; m--; + ll am{k % (2*n)}, ad{k / n}, bm{k % (2*m)}, bd{k / m}; + if (am > n) am = n - (am-n); + if (bm > m) bm = m - (bm-m); + return {am, bm, ad+bd-k/std::lcm(n, m)}; +} + +int main() { + ll t, n, m, k; + std::cin >> t; + for (ll i = 0; i < t; i++) { + std::cin >> n >> m >> k; + auto [a, b, c] = f(n, m, k); + std::cout << a+1 << " " << b+1 << " " << c << "\n"; + } +} diff --git a/README.md b/README.md @@ -0,0 +1,6 @@ +# Solutions for cses.fi + +In 2026 I felt a bit nostalgic of my competitive programming days, +and I wanted to play around with the same type of challenges. I found +out about [cses.fi](https://cses.fi), a practice website aimed at IOI +contestants, and I started doing some of the problems. diff --git a/notes.txt b/notes.txt @@ -0,0 +1,5 @@ +- Sparse tables: similar to range trees, but allows for O(1) queries for min. + t[i][j] = f([j, j+2^i)) + https://cp-algorithms.com/data_structures/sparse-table.html + +- Decent implementation of Map APIs in 04_graph_algorithms/labyrinth_1193.cpp