Potion-making Solution

This problem requires solving the equation i/(i+j) = k/100 to find the minimal total ingredients. The solution involves iterating through possiblle values of i and j.

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

void solvePotion() {
    int target_percentage;
    cin >> target_percentage;
    
    for(int numerator = 1; numerator <= 100; numerator++) {
        for(int denominator = 0; denominator < 100; denominator++) {
            if(numerator * 100 == target_percentage * (numerator + denominator)) {
                cout << numerator + denominator << endl;
                return;
            }
        }
    }
}

int main() {
    int test_cases;
    cin >> test_cases;
    while(test_cases--) {
        solvePotion();
    }
    return 0;
}

Permutation Sort Analysis

This problem determines the minimum operations needed to sort a permutation by analyzing the positions of the first and last elements.

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

void analyzePermutation() {
    int size;
    cin >> size;
    vector<int> arr(size);
    for(auto &element : arr) cin >> element;
    
    vector<int> sorted(size);
    iota(sorted.begin(), sorted.end(), 1);
    
    if(arr == sorted) {
        cout << 0 << endl;
    } else {
        if(arr[0] == 1 || arr.back() == size)
            cout << 1 << endl;
        else if(arr[0] == size && arr.back() == 1)
            cout << 3 << endl;
        else
            cout << 2 << endl;
    }
}

int main() {
    int test_count;
    cin >> test_count;
    while(test_count--) {
        analyzePermutation();
    }
    return 0;
}

Armchairs Placmeent Optimization

This solution uses dynamic programming to minimize the total movement distance when assigning people to empty chairs.

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

int main() {
    int chair_count;
    cin >> chair_count;
    vector<int> chairs(chair_count + 1);
    vector<int> person_positions{0};
    
    for(int i = 1; i <= chair_count; i++) {
        cin >> chairs[i];
        if(chairs[i] == 1)
            person_positions.push_back(i);
    }
    
    int person_count = person_positions.size() - 1;
    vector<vector<int>> dp(person_count + 1, 
                           vector<int>(chair_count + 1, INT_MAX));
    
    for(int i = 0; i <= chair_count; i++) 
        dp[0][i] = 0;
    
    for(int p = 1; p <= person_count; p++) {
        for(int c = 1; c <= chair_count; c++) {
            if(chairs[c] == 0) {
                dp[p][c] = min(dp[p][c-1], 
                              dp[p-1][c-1] + abs(person_positions[p] - c));
            } else {
                dp[p][c] = dp[p][c-1];
            }
        }
    }
    
    cout << dp[person_count][chair_count] << endl;
    return 0;
}