Given three strings A, B, and C, determine whether the last character of A matches the first character of B, and the last character of B matches the first character of C. Each string consists of lowercase letters and is provided on a single line separated by spaces.
Solution Approach:
Extract the relevant characters and perform two comparisons. The key insight is to identify the boundary characters at the positions where strings are separated by spaces. We need to verify both conditions simultaneously - if either condition fails, the answer is "NO".
Implementation:
The solution parses the input line character by character, tracking the last character of each string and comparing it with the first character of the subsequant string. A boolean flag maintains the verification status throughout the iteration.
#include <bits/stdc++.h>
using namespace std;
int main() {
string input;
getline(cin, input);
char previous_last = '?';
bool valid = true;
for (size_t idx = 0; idx < input.length(); ++idx) {
char current = input[idx];
char next = (idx + 1 < input.length()) ? input[idx + 1] : ' ';
char prev = (idx > 0) ? input[idx - 1] : ' ';
if (next == ' ') {
previous_last = current;
}
if (prev == ' ') {
valid = valid && (current == previous_last);
}
}
cout << (valid ? "YES" : "NO") << endl;
return 0;
}
Problem B: Modular Sum Verification
Given positive integers A and B, along with an integer C (where 0 ≤ C < B), determine whether it is possible to select at least one multiple of A such that the sum of selected multiples has a remainder of C when divided by B.
Solution Approach:
The sum of any collection of multiples of A remains a multiple of A. Therefore, the problem reduces to finding whether there exists some integer k such that k·A ≡ C (mod B). This is equivalent to solving the linear Diophantine equation x·A + y·B = C for integers x and y.
By Bézout's identity, the equation has integer solutions if and only if gcd(A, B) divides C. This provides a simple O(log min(A, B)) solution using the Euclidean algorithm for computing the greatest common divisor.
Implementation:
Compute the greatest common divisor of A and B using the Euclidean algorithm. If C is divisible by this gcd, the answer is "YES"; otherwise, it is "NO".
#include <bits/stdc++.h>
using namespace std;
long long gcd_extended(long long a, long long b) {
while (b != 0) {
long long temp = b;
b = a % b;
a = temp;
}
return a;
}
int main() {
long long A, B, C;
cin >> A >> B >> C;
long long divisor = gcd_extended(A, B);
cout << (C % divisor == 0 ? "YES" : "NO") << endl;
return 0;
}
Problem C: Sprinkler Duration Calculation
A sprinkler activates for T seconds whenever its switch is pressed. If pressed at second t, it sprays water until second t + T - 1. N people pass by the sprinkler at times t₁, t₂, ..., t_N (in strictly increasing order), and each person presses the switch when passing. Calculate the total duration the sprinkler is spraying water.
Solution Approach:
Track the time when the current watering session ends. When a new person arrives, determine how much additional watering time is contributed. If the new activation starts before the previous session ends, only the non-overlapping portion adds to the total. Otherwise, the full duration T is added.
The formula for additional time is: add min(T, max(0, (t_i + T - 1) - end)). This ensures we only count the new coverage beyond the current end time, capped at the full spray duration T.
Implementation:
Maintain a running total and the endpoint of the current watering session. Process each arrival time in order, updating both values according to the overlap calculation.
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
int N;
int64 T;
cin >> N >> T;
int64 total_time = 0;
int64 current_end = -1;
for (int i = 0; i < N; ++i) {
int64 arrival;
cin >> arrival;
int64 spray_end = arrival + T - 1;
if (current_end == -1) {
total_time += T;
} else {
int64 new_coverage = max(static_cast<int64>(0), spray_end - current_end);
total_time += min(T, new_coverage);
}
current_end = spray_end;
}
cout << total_time << endl;
return 0;
}
Problem D: 0/1 Knapsack with Limited Weight Variance
Given N items where item i has weight w_i and value v_i, and a knapsack with capacity W, select a subset of items to maximize total value. The weight constraint is 1 ≤ w_i ≤ 10^9, N ≤ 100, and W ≤ 10^9. An additional constranit states that all weights satisfy w₁ ≤ w_i ≤ w₁ + 3 for i ≥ 2.
Solution Approach:
The weight constraint implies that all items fall into at most four distinct weight categories: w₁, w₁+1, w₁+2, and w₁+3. This bounded weight variance allows a combinatorial enumeration approach that would otherwise be impractical.
Group items by their weight category relative to w₁. Within each category, sort items by value in descending order. Enumerate the count of items taken from the first three weight categories (A, B, C), compute the remaining capacity, and greedi fill the remaining space with items from the fourth category (D) sorted by value.
The enumeration complexity is O(|A| × |B| × |C|), which is feasible given N ≤ 100 and each group containing at most 100 items.
Implementation:
Group items by weight offset, sort each group by value, then systematically enumerate combinations from the first three groups while greedily selecting from the fourth group within remaining capacity constraints.
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
int N;
int64 capacity;
cin >> N >> capacity;
vector<vector<int>> value_groups(4);
int64 base_weight = 0;
for (int i = 0; i < N; ++i) {
int64 weight, value;
cin >> weight >> value;
if (i == 0) base_weight = weight;
int offset = static_cast<int>(weight - base_weight);
value_groups[offset].push_back(static_cast<int>(value));
}
for (auto& group : value_groups) {
sort(group.begin(), group.end(), greater<int>());
}
int64 max_value = 0;
for (int count_A = 0; count_A <= static_cast<int>(value_groups[0].size()); ++count_A) {
for (int count_B = 0; count_B <= static_cast<int>(value_groups[1].size()); ++count_B) {
for (int count_C = 0; count_C <= static_cast<int>(value_groups[2].size()); ++count_C) {
int64 current_weight = 0;
int64 current_value = 0;
bool feasible = true;
// Process group A (weight = base_weight)
for (int i = 0; i < count_A && feasible; ++i) {
current_weight += base_weight;
if (current_weight > capacity) {
feasible = false;
break;
}
current_value += value_groups[0][i];
}
// Process group B (weight = base_weight + 1)
for (int i = 0; i < count_B && feasible; ++i) {
current_weight += base_weight + 1;
if (current_weight > capacity) {
feasible = false;
break;
}
current_value += value_groups[1][i];
}
// Process group C (weight = base_weight + 2)
for (int i = 0; i < count_C && feasible; ++i) {
current_weight += base_weight + 2;
if (current_weight > capacity) {
feasible = false;
break;
}
current_value += value_groups[2][i];
}
if (!feasible) continue;
int64 remaining = capacity - current_weight;
int max_D = min(
static_cast<int>(remaining / (base_weight + 3)),
static_cast<int>(value_groups[3].size())
);
// Process group D (weight = base_weight + 3)
for (int i = 0; i < max_D; ++i) {
current_weight += base_weight + 3;
if (current_weight > capacity) break;
current_value += value_groups[3][i];
}
if (current_weight <= capacity) {
max_value = max(max_value, current_value);
}
}
}
}
cout << max_value << endl;
return 0;
}