Problem P1147: Consecutive Integer Sequences Summing to Target

Determine all sequences of consecutive positive integers that sum to a given target value. The solution leverages the arithmetic series formula, transforming the problem into solving a quadartic equation for valid integer endpoints.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    long long target;
    cin >> target;
    for (long long begin = 1; begin < target; ++begin) {
        long long discriminant = 1 + 8 * target + 4 * begin * begin - 4 * begin;
        long long root = sqrt(discriminant);
        if (root * root != discriminant) continue;
        long long end = (-1 + root) / 2;
        if (end > begin && (end * 2 + 1 == root)) {
            cout << begin << " " << end << "\n";
        }
    }
    return 0;
}

Problem P1125: Character Frequency Prime Check

Analyze character frequency distribution in a string to verify if the difference between the most and least frequent characters is a prime number. This involves counting occurrences and validating primality of the difference.

#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
using namespace std;

bool isPrime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    string input;
    cin >> input;
    int charFreq[26] = {0};
    for (char c : input) {
        if (c >= 'a' && c <= 'z') {
            charFreq[c - 'a']++;
        }
    }
    int maxFreq = 0, minFreq = INT_MAX;
    for (int count : charFreq) {
        if (count == 0) continue;
        maxFreq = max(maxFreq, count);
        minFreq = min(minFreq, count);
    }
    int diff = maxFreq - minFreq;
    if (isPrime(diff)) {
        cout << "Lucky Word\n" << diff << endl;
    } else {
        cout << "No Answer\n" << 0 << endl;
    }
    return 0;
}

Problem P1605: Maze Path Counting

Count all valid paths from start to end in a grid maze with obstacles using depth-first search. The solution tracks visited cells and explores four-directional movement while avoiding blocked positions.

#include <iostream>
#include <vector>
using namespace std;

int grid[10][10];
bool visited[10][10];
int pathCount = 0;
int rows, cols, obstacles;
int startX, startY, endX, endY;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y) {
    if (x == endX && y == endY) {
        pathCount++;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && nx <= rows && ny >= 1 && ny <= cols && !visited[nx][ny] && grid[nx][ny] == 1) {
            visited[x][y] = true;
            dfs(nx, ny);
            visited[x][y] = false;
        }
    }
}

int main() {
    cin >> rows >> cols >> obstacles >> startX >> startY >> endX >> endY;
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            grid[i][j] = 1;
        }
    }
    for (int i = 0; i < obstacles; i++) {
        int obstacleX, obstacleY;
        cin >> obstacleX >> obstacleY;
        grid[obstacleX][obstacleY] = 0;
    }
    dfs(startX, startY);
    cout << pathCount << endl;
    return 0;
}

Problem P1090: Optimal Fruit Merging

Minimize the total cost of merging items by repeatedly combining the two smallest elements using a min-heap priority queue. This greedy strategy ensures optimal cost calculation for the problem.

#include <queue>
#include <vector>
#include <iostream>
using namespace std;

int main() {
    int itemCount;
    cin >> itemCount;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int i = 0; i < itemCount; i++) {
        int value;
        cin >> value;
        minHeap.push(value);
    }
    long long totalCost = 0;
    while (minHeap.size() > 1) {
        int first = minHeap.top(); minHeap.pop();
        int second = minHeap.top(); minHeap.pop();
        int sum = first + second;
        totalCost += sum;
        minHeap.push(sum);
    }
    cout << totalCost << endl;
    return 0;
}

Problem P1037: Digit Transformation Counting

Calculate possible digit trensformations based on substitution rules using depth-first search and high-precision arithmetic. Each digit in the input number is processed to count reachable digits via the substitution graph, then multiply the counts for each digit.

#include <iostream>
#include <vector>
using namespace std;

void print(__int128 num) {
    if (num < 0) {
        cout << '-';
        num = -num;
    }
    if (num > 9) print(num / 10);
    cout << (char)(num % 10 + '0');
}

int main() {
    string number;
    int rulesCount;
    cin >> number >> rulesCount;
    vector<vector<int>> graph(10);
    for (int i = 0; i < rulesCount; i++) {
        int from, to;
        cin >> from >> to;
        graph[from].push_back(to);
    }
    __int128 total = 1;
    for (char c : number) {
        int digit = c - '0';
        vector<bool> visited(10, false);
        vector<int> stack;
        stack.push_back(digit);
        visited[digit] = true;
        int count = 0;
        while (!stack.empty()) {
            int current = stack.back();
            stack.pop_back();
            count++;
            for (int next : graph[current]) {
                if (!visited[next]) {
                    visited[next] = true;
                    stack.push_back(next);
                }
            }
        }
        total *= count;
    }
    print(total);
    cout << endl;
    return 0;
}