A - Welcome to AtCoder Land
This problem is a straightforward string comparison. We need to check if the first input string is "AtCoder" and the second input string is "Land". If both conditions are met, we output "Yes"; otherwise, we output "No".
#include <iostream>
#include <string>
#include <vector>
int main() {
std::string s, t;
std::cin >> s >> t;
if (s == "AtCoder" && t == "Land") {
std::cout << "Yes" << std::endl;
} else {
std::cout << "No" << std::endl;
}
return 0;
}
</vector></string></iostream>
B - Ticket Counter
We are given the number of tickets n and a time duration t. We then receive n ticket purchase times. For each purchase, we need to calculate the earliest time the ticket can be issued. If a ticket is purchased at time a\[i\], and the previous ticket was issued at time issued\_time, the new ticket can be issued at max(a\[i\], issued\_time) + t. We maintain a running issued\_time and print it after each purchase.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n, t;
std::cin >> n >> t;
int current_issue_time = 0;
for (int i = 0; i < n; ++i) {
int purchase_time;
std::cin >> purchase_time;
current_issue_time = std::max(purchase_time, current_issue_time) + t;
std::cout << current_issue_time << std::endl;
}
return 0;
}
</algorithm></vector></iostream>
C - Popcorn
This problem can be solved using bitmask dynamic programming or brute force with bitmasks. We have n items, each with m properties. An item can either have a property or not. We want to select a subset of items such that all m properties are covered. The state can be represented by a bitmask where the j-th bit is set if the j-th property is covered. We iterate through all possible subsets of items (2^n possibilities) and for each subset, we calculate the combined bitmask of properties covered. If the final bitmask covers all m properties (i.e., equals (1 << m) - 1), we update the minimum number of items selected.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main() {
int n, m;
std::cin >> n >> m;
std::vector<int> item_properties(n, 0);
for (int i = 0; i < n; ++i) {
std::string s;
std::cin >> s;
for (int j = 0; j < m; ++j) {
if (s[j] == 'o') {
item_properties[i] |= (1 << j);
}
}
}
int min_items = n + 1;
for (int i = 0; i < (1 << n); ++i) {
int combined_mask = 0;
int items_count = 0;
for (int j = 0; j < n; ++j) {
if ((i >> j) & 1) {
combined_mask |= item_properties[j];
items_count++;
}
}
if (combined_mask == (1 << m) - 1) {
min_items = std::min(min_items, items_count);
}
}
std::cout << min_items << std::endl;
return 0;
}
</int></algorithm></string></vector></iostream>
D - Souvenirs
This problem can be solved using a greedy approach with binary search. We have two arrays, a and b. For each element b\_i in array b, we want to find the smallest element a\_j in array a such that a\_j >= b\_i and a\_j has not been used yet. To efficiently find a\_j, we first sort array a. Then, for each b\_i, we use std::lower\_bound on the sorted array a to find the first element greater than or equal to b\_i. If such an element exists, we add it to our total sum and mark it as used (e.g., by setting it to 0 or removing it). If no such element can be found for any b\_i, then no solution exists, and we output -1. Sorting b is not strictly necessary for correctness but can sometimes help in reasoning about the greedy choice.
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n, m;
std::cin >> n >> m;
std::vector<long long=""> a(n);
std::vector<long long=""> b(m);
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
}
for (int i = 0; i < m; ++i) {
std::cin >> b[i];
}
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
long long total_cost = 0;
std::vector<bool> used_a(n, false);
bool possible = true;
for (long long val_b : b) {
int best_idx = -1;
for (int i = 0; i < n; ++i) {
if (!used_a[i] && a[i] >= val_b) {
if (best_idx == -1 || a[i] < a[best_idx]) {
best_idx = i;
}
}
}
if (best_idx != -1) {
total_cost += a[best_idx];
used_a[best_idx] = true;
} else {
possible = false;
break;
}
}
if (possible) {
std::cout << total_cost << std::endl;
} else {
std::cout << -1 << std::endl;
}
return 0;
}
</bool></long></long></algorithm></vector></iostream>
E - Alphabet Tiles
This problem requires dynamic programming with combinations. We need to form strings of length n using characters 'A' through 'Z', where each character c can be used at most c\_val times. The problem asks for the number of distinct strings of length n that can be formed. Let dp\[i\]\[j\] be the number of ways to form a string of length j using the first i characters of the alphabet. To compute dp\[i\]\[j\], we can consider using k occurrences of the i-th character, where 0 <= k <= min(j, count\[i\]). The number of ways to choose k positions for the i-th character out of j positions is given by the binomial coefficient C(j, k). The remaining j-k positions must be filled using the first i-1 characters, which can be done in dp\[i-1\]\[j-k\] ways. Thus, the transition is: dp\[i\]\[j\] = sum(C(j, k) \* dp\[i-1\]\[j-k\]) for 0 <= k <= min(j, count\[i\]). The base case is dp\[0\]\[0\] = 1. The final answer is the sum of dp\[26\]\[j\] for 1 <= j <= n. We need to precompute binomial coefficients modulo 998244353.
#include <iostream>
#include <vector>
#include <algorithm>
long long power(long long base, long long exp) {
long long res = 1;
base %= 998244353;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % 998244353;
base = (base * base) % 998244353;
exp /= 2;
}
return res;
}
long long modInverse(long long n) {
return power(n, 998244353 - 2);
}
std::vector<:vector long="">> nCr_table;
void precompute_ncr(int max_n) {
nCr_table.assign(max_n + 1, std::vector<long long="">(max_n + 1, 0));
for (int i = 0; i <= max_n; ++i) {
nCr_table[i][0] = 1;
for (int j = 1; j <= i; ++j) {
nCr_table[i][j] = (nCr_table[i - 1][j - 1] + nCr_table[i - 1][j]) % 998244353;
}
}
}
long long nCr(int n_val, int r_val) {
if (r_val < 0 || r_val > n_val) return 0;
return nCr_table[n_val][r_val];
}
int main() {
int n;
std::cin >> n;
std::vector<int> counts(27);
for (int i = 1; i <= 26; ++i) {
std::cin >> counts[i];
}
precompute_ncr(n);
std::vector<:vector long="">> dp(27, std::vector<long long="">(n + 1, 0));
dp[0][0] = 1;
for (int i = 1; i <= 26; ++i) {
for (int j = 0; j <= n; ++j) {
for (int k = 0; k <= std::min(j, counts[i]); ++k) {
dp[i][j] = (dp[i][j] + nCr(j, k) * dp[i - 1][j - k]) % 998244353;
}
}
}
long long total_ways = 0;
for (int j = 1; j <= n; ++j) {
total_ways = (total_ways + dp[26][j]) % 998244353;
}
std::cout << total_ways << std::endl;
return 0;
}
</long></:vector></int></long></:vector></algorithm></vector></iostream>
F - Easiest Maze
This problem involves constructing a maze. The constraints suggest that we need to generate a specific maze pattern. The core idea is to first create a path from the start to the end. This can be a simple straight line or a slightly winding path. Then, we can expand this path by adding dead ends and corridors to satisfy the required path length k. The solution involves carefully placing walls ('+') and paths ('.') to form the maze structure. The construction can be done by first defining a sequence of moves (Up, Down, Left, Right) to create the primary path, and then using this sequence to fill in the grid. It's crucial to check the feasibility conditions for k based on the dimensions n and m. If k is too large or too small, a valid maze cannot be constructed.
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
int main() {
int n, m, k;
std::cin >> n >> m >> k;
auto is_possible = [&]() {
if ((n % 2) != (k % 2)) return false;
int max_len = n * m;
if ((n % 2) == 1 && (m % 2) == 0) max_len--;
if (k < n || k > max_len) return false;
return true;
};
if (!is_possible()) {
std::cout << "No" << std::endl;
return 0;
}
std::cout << "Yes" << std::endl;
std::vector<:string> maze(n * 2 + 1, std::string(m * 2 + 1, '#'));
auto fill_path = [&](int r, int c, char dir) {
if (dir == 'R') {
for (int i = 0; i < m; ++i) {
maze[r][c + i * 2] = '+';
maze[r + 1][c + i * 2] = '.';
}
} else if (dir == 'D') {
for (int i = 0; i < n; ++i) {
maze[r + i * 2][c] = '+';
maze[r + i * 2][c + 1] = '.';
}
}
};
int current_k = n;
// Initial path downwards
fill_path(1, 1, 'D');
// Horizontal paths
for (int r = 1; r <= n && current_k < k; r += 2) {
for (int c = 1; c < m && current_k < k; ++c) {
if (current_k + 2 <= k) {
maze[r][c * 2] = '.';
maze[r][c * 2 + 1] = '.';
current_k += 2;
} else {
break;
}
}
}
// More downwards paths if needed
for (int c = 1; c <= m && current_k < k; c += 2) {
for (int r = 1; r < n && current_k < k; ++r) {
if (current_k + 2 <= k) {
maze[r * 2][c] = '.';
maze[r * 2 + 1][c] = '.';
current_k += 2;
} else {
break;
}
}
}
maze[1][1] = 'S';
maze[n * 2 - 1][m * 2 - 1] = 'G';
for (int i = 0; i < maze.size(); ++i) {
for (int j = 0; j < maze[i].size(); ++j) {
if (maze[i][j] == '#') {
if (i % 2 == 0 && j % 2 == 0) maze[i][j] = '+';
else if (i % 2 == 0) maze[i][j] = '|';
else if (j % 2 == 0) maze[i][j] = '-';
else maze[i][j] = '#'; // Should not happen if logic is correct
}
}
}
// Ensure start and end are correctly placed and path exists
maze[1][0] = maze[1][2] = '.';
maze[n*2-1][m*2] = maze[n*2-1][m*2-2] = '.';
// Fill remaining empty cells appropriately if any '#' remain
for (size_t r = 0; r < maze.size(); ++r) {
for (size_t c = 0; c < maze[r].size(); ++c) {
if (maze[r][c] == '#') {
if (r % 2 == 0 && c % 2 == 0) maze[r][c] = '+';
else if (r % 2 == 0) maze[r][c] = '|';
else if (c % 2 == 0) maze[r][c] = '-';
else maze[r][c] = '.';
}
}
}
for (const auto& row : maze) {
std::cout << row << std::endl;
}
return 0;
}
</:string></algorithm></string></vector></iostream>
G - AtCoder Tour
This problem involves finding the maximum score path in a grid over a fixed number of steps k. The optimal strategy is to move to a cell and stay there until the end of k steps. This suggests a dynamic prgoramming approach on the number of steps. Let dp\[t\]\[r\]\[c\] be the maximum score achievable at step t ending at cell (r, c). The transitions involve moving from a cell (pr, pc) at step t-1 to cell (r, c) at step t. The score accumulated at step t is dp\[t-1\]\[pr\]\[pc\] + value\[r\]\[c\]. However, since the strategy is to move and then stay, a more direct DP formulation is to consider the number of moves made. Let dp\[t\]\[r\]\[c\] be the maximum score obtained after exactly t *moves*, ending at (r, c). The score at step t is then dp\[t\]\[r\]\[c\] + (k - t) \* value\[r\]\[c\]. We need to initialize dp values to a very small number (negative infinity) to correctly handle paths. The base case would be after the first step from the start position. The final answer is the maximum over all t from 1 to k and all cells (r, c) of dp\[t\]\[r\]\[c\] + (k - t) \* value\[r\]\[c\].
#include <iostream>
#include <vector>
#include <algorithm>
const long long INF = -1e18; // Represents negative infinity
int main() {
int n, m, k;
std::cin >> n >> m >> k;
int start_r, start_c;
std::cin >> start_r >> start_c;
std::vector<:vector long="">> values(n + 1, std::vector<long long="">(m + 1));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
std::cin >> values[i][j];
}
}
// dp[t][r][c]: max score after exactly t moves, ending at (r, c)
std::vector<:vector long="">>> dp(k + 1, std::vector<:vector long="">>(n + 1, std::vector<long long="">(m + 1, INF)));
// Base case: After 0 moves, we are at the start position. The score is 0.
// However, the problem implies we must make at least one move.
// Let's consider the first move from (start_r, start_c).
int dr[] = {0, 0, 0, 1, -1};
int dc[] = {0, 1, -1, 0, 0};
// Initialize dp for the first move (t=1)
dp[1][start_r][start_c] = values[start_r][start_c]; // This is wrong, should consider moves FROM start.
// Correct initialization: after 1 move from start
for (int i = 0; i < 5; ++i) {
int nr = start_r + dr[i];
int nc = start_c + dc[i];
if (nr >= 1 && nr <= n && nc >= 1 && nc <= m) {
dp[1][nr][nc] = values[nr][nc];
}
}
long long max_total_score = INF;
// Calculate scores for the first move directly
for(int r = 1; r <= n; ++r) {
for(int c = 1; c <= m; ++c) {
if (dp[1][r][c] != INF) {
max_total_score = std::max(max_total_score, dp[1][r][c] + (long long)(k - 1) * values[r][c]);
}
}
}
// DP transitions for subsequent moves
for (int t = 2; t <= k; ++t) {
for (int r = 1; r <= n; ++r) {
for (int c = 1; c <= m; ++c) {
// Consider all possible previous cells (pr, pc)
for (int i = 0; i < 5; ++i) {
int pr = r + dr[i];
int pc = c + dc[i];
if (pr >= 1 && pr <= n && pc >= 1 && pc <= m) {
if (dp[t - 1][pr][pc] != INF) {
dp[t][r][c] = std::max(dp[t][r][c], dp[t - 1][pr][pc] + values[r][c]);
}
}
}
// Update the overall maximum score
if (dp[t][r][c] != INF) {
max_total_score = std::max(max_total_score, dp[t][r][c] + (long long)(k - t) * values[r][c]);
}
}
}
}
// If k is small, the optimal might be staying at the start.
// This is implicitly handled if k=0 or k=1, but for larger k,
// staying at start means 0 moves, score k * values[start_r][start_c].
// The DP formulation above assumes at least one move.
// If k=0, answer is 0. If k > 0 and no moves are made, score is k * values[start_r][start_c].
// Let's ensure this case is covered if max_total_score is still INF or very small.
if (k > 0 && max_total_score == INF) {
max_total_score = (long long)k * values[start_r][start_c];
} else if (k > 0) {
max_total_score = std::max(max_total_score, (long long)k * values[start_r][start_c]);
} else if (k == 0) {
max_total_score = 0;
}
std::cout << max_total_score << std::endl;
return 0;
}
</long></:vector></:vector></long></:vector></algorithm></vector></iostream>