Lucky Word Problem

A student with limited vocabulary discovered an interesting method for selecting correct answers in English multiple-choice questions. This approach has proven effective through experimentation.

The technique involves analyzing character frequencies within a word. Let's define max_freq as the highest occurrence of any letter in the word, and min_freq as the lowest occurrence of any letter. If the difference max_freq - min_freq results in a prime number, the word is considered "Lucky Word" and likely repersents the correct answer.

Input Format

A single line containing a lowercase word with length less than 100 characters.

Output Format

Two lines of output:

• First line: "Lucky Word" if the condition is met, otherwise "No Answer"
• Second line: The value of max_freq - min_freq if it's a lucky word, otherwise 0

Example

Input: error

Output:

Lucky Word
2

Explanation: In "error", letter 'r' appears 3 times (maximum), other letters appear once each (minimum). Difference is 2, which is prime.

Implementation

#include <stdio.h>
#include <string.h>

int is_prime(int value) {
    if (value < 2) return 1;
    for (int divisor = 2; divisor * divisor <= value; divisor++) {
        if (value % divisor == 0) return 1;
    }
    if (value == 0 || value == 1) return 1;
    return 0;
}

int main() {
    char input_word[100];
    int length, counter[100] = {0};
    int max_count = 0, min_count = 0;
    
    scanf("%s", input_word);
    length = strlen(input_word);
    
    for (int pos = 0; pos < length; pos++) {
        for (int scan = 0; scan < length; scan++) {
            if (input_word[pos] == input_word[scan]) {
                counter[pos]++;
            }
        }
    }
    
    min_count = counter[0];
    for (int idx = 0; idx < length; idx++) {
        if (counter[idx] < min_count) min_count = counter[idx];
        if (counter[idx] > max_count) max_count = counter[idx];
    }
    
    if (is_prime(max_count - min_count) == 0) {
        printf("Lucky Word\n%d", max_count - min_count);
    } else {
        printf("No Answer\n0");
    }
    
    return 0;
}

Matchstick Equation Problem

Given n matchsticks, determine how many equations of the form "A + B = C" can be formed. Each digit requires a specific number of matchsticks:

• Digit 0: 6 sticks
• Digit 1: 2 sticks
• Digit 2: 5 sticks
• Digit 3: 5 sticks
• Digit 4: 4 sticks
• Digit 5: 5 sticks
• Digit 6: 6 sticks
• Digit 7: 3 sticks
• Digit 8: 7 sticks
• Digit 9: 6 sticks

Additional constraints:

• Plus sign requires 2 matchsticks
• Equals sign requires 2 matchsticks
• Leading zeros are not allowed unless the number is zero itself
• All matchsticks must be used
• Different arrangements like A + B = C and B + A = C are considered distinct

Implemantation

#include <stdio.h>

int calculate_sticks(int number) {
    int mapping[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
    int total = 0;
    
    if (number == 0) return mapping[0];
    
    while (number > 0) {
        total += mapping[number % 10];
        number /= 10;
    }
    return total;
}

int main() {
    int n, count = 0;
    scanf("%d", &n);
    
    // Subtract 4 for + and = signs
    n -= 4;
    
    for (int operand_a = 0; operand_a <= 2000; operand_a++) {
        for (int operand_b = 0; operand_b <= 2000; operand_b++) {
            int result = operand_a + operand_b;
            
            int sticks_a = calculate_sticks(operand_a);
            int sticks_b = calculate_sticks(operand_b);
            int sticks_result = calculate_sticks(result);
            
            if (sticks_a + sticks_b + sticks_result == n) {
                count++;
            }
        }
    }
    
    printf("%d", count);
    return 0;
}

Passing Notes Problem

Two students, positioned at opposite corners of an m×n matrix, want to exchange notes via classmates. Student A sits at position (1,1) and Student B at position (m,n). The note from A to B can only move right or down, while the return note moves left or up.

Each classmate has a kindness score (0-100). The goal is to find two paths that maximize the sum of kindness scores along both routes, ensuring no student helps twice.

Implementation

#include <stdio.h>

int grid[55][55], dp[55][55][55][55];

int maximum(int first, int second) {
    return (first > second) ? first : second;
}

int main() {
    int rows, cols;
    scanf("%d %d", &rows, &cols);
    
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            scanf("%d", &grid[i][j]);
        }
    }
    
    for (int r1 = 1; r1 <= rows; r1++) {
        for (int c1 = 1; c1 <= cols; c1++) {
            for (int r2 = 1; r2 <= rows; r2++) {
                for (int c2 = 1; c2 <= cols; c2++) {
                    if ((r1 != r2 || c1 != c2) || (r1 == rows && r2 == rows && c1 == cols && c2 == cols)) {
                        dp[r1][c1][r2][c2] = maximum(
                            maximum(dp[r1-1][c1][r2-1][c2], dp[r1-1][c1][r2][c2-1]),
                            maximum(dp[r1][c1-1][r2-1][c2], dp[r1][c1-1][r2][c2-1])
                        ) + grid[r1][c1] + grid[r2][c2];
                    }
                }
            }
        }
    }
    
    printf("%d", dp[rows][cols][rows][cols]);
    return 0;
}

Double Stack Sorting Problem

This problem involves sorting a sequence using two stacks with four operations:

• Operation 'a': Push first element of input sequence to stack S1
• Operation 'b': Pop top element from S1 to output sequence
• Operation 'c': Push first element of input sequence to stack S2
• Operation 'd': Pop top element from S2 to output sequence

A permutation P is called "double-stack sortable" if these operations can produce the sorted sequence 1, 2, ..., n.

For example, (1,3,2,4) is double-stack sortable, while (2,3,4,1) is not.

Solution Strategy

For a single stack, if there exist indices i < j < k such that a[k] < a[i] < a[j], sorting is impossible.

For double stacks, elements that conflict must be placed in different stacks. This creates a graph where nodes represent positions, and edges connect conflicting positions.

If the resulting graph is bipartite, the sequence is double-stack sortable. Otherwise, it's not.

Implementation

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#define MAX_SIZE 1005

using namespace std;

int size, sequence[MAX_SIZE];
int start_pos[MAX_SIZE];
int edge_count;
int minimum_from_right[MAX_SIZE];
int visited[MAX_SIZE];
int group_assignment[MAX_SIZE];

class Stack {
private:
    int top_index;
    int storage[MAX_SIZE];
public:
    Stack() { top_index = -1; }
    
    int pop() {
        int value = storage[top_index--];
        return value;
    }
    
    void push(int value) {
        storage[++top_index] = value;
    }
    
    int peek() {
        return storage[top_index];
    }
    
    int get_size() {
        return top_index;
    }
} stacks[2];

struct Edge {
    int destination;
    int next_edge;
} edges[MAX_SIZE];

void add_connection(int source, int target) {
    edges[edge_count].destination = target;
    edges[edge_count].next_edge = start_pos[source];
    start_pos[source] = edge_count++;
    
    edges[edge_count].destination = source;
    edges[edge_count].next_edge = start_pos[target];
    start_pos[target] = edge_count++;
}

bool depth_first_search(int current, int depth) {
    if (group_assignment[current] != -1 && group_assignment[current] != depth % 2) {
        return false;
    }
    group_assignment[current] = depth % 2;
    
    for (int edge_idx = start_pos[current]; edge_idx != -1; edge_idx = edges[edge_idx].next_edge) {
        if (group_assignment[edges[edge_idx].destination] == (depth + 1) % 2) {
            continue;
        }
        if (!depth_first_search(edges[edge_idx].destination, depth + 1)) {
            return false;
        }
    }
    return true;
}

int main() {
    memset(start_pos, -1, sizeof(start_pos));
    scanf("%d", &size);
    
    for (int i = 0; i < size; i++) {
        scanf("%d", &sequence[i]);
    }
    
    minimum_from_right[size - 1] = sequence[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        minimum_from_right[i] = min(minimum_from_right[i + 1], sequence[i]);
    }
    
    for (int i = 0; i < size - 1; i++) {
        for (int j = i + 1; j < size - 1; j++) {
            if (minimum_from_right[j + 1] < sequence[i] && sequence[i] < sequence[j]) {
                add_connection(i, j);
            }
        }
    }
    
    memset(visited, -1, sizeof(visited));
    memset(group_assignment, -1, sizeof(group_assignment));
    
    for (int i = 0; i < size; i++) {
        if (visited[i] == -1) {
            if (!depth_first_search(i, 0)) {
                printf("0\n");
                return 0;
            }
            for (int j = 0; j < size; j++) {
                if (group_assignment[j] != -1) {
                    visited[j] = group_assignment[j];
                }
            }
            memset(group_assignment, -1, sizeof(group_assignment));
        }
    }
    
    int expected_output = 1;
    for (int i = 0; i < size; i++) {
        while (true) {
            bool processed = false;
            if (stacks[0].get_size() != -1 && stacks[0].peek() == expected_output) {
                stacks[0].pop();
                expected_output++;
                printf("b ");
                processed = true;
            }
            if (stacks[1].get_size() != -1 && stacks[1].peek() == expected_output) {
                stacks[1].pop();
                expected_output++;
                printf("d ");
                processed = true;
            }
            if (!processed) break;
        }
        
        stacks[visited[i]].push(sequence[i]);
        if (visited[i] == 0) {
            printf("a ");
        } else {
            printf("c ");
        }
    }
    
    while (true) {
        bool processed = false;
        if (stacks[0].get_size() != -1 && stacks[0].peek() == expected_output) {
            stacks[0].pop();
            expected_output++;
            printf("b ");
            processed = true;
        }
        if (stacks[1].get_size() != -1 && stacks[1].peek() == expected_output) {
            stacks[1].pop();
            expected_output++;
            printf("d ");
            processed = true;
        }
        if (!processed) break;
    }
    
    return 0;
}