The Chicken McNugget Theorem

A classic problem in number theory asks for the largest monetary amount that cannot be obtained using any combination of coins of specified denominations. For two positive integers $a$ and $b$ that are coprime, this largest unobtainable value is given by $ab - a - b$. This problem requires implementing this formula to find the maximum number of candy items that cannot be purchased given two package sizes.

Problem Specification:
Input: Two integers representing the package sizes.
Output: The single largest integer that cannot be formed by a linear combination of the input sizes.

#include <iostream>

int main() {
    int packSizeA, packSizeB;
    std::cin >> packSizeA >> packSizeB;
    
    // Formula for the largest number that cannot be expressed 
    // as ax + by for coprime a and b
    int maxUnobtainable = (packSizeA * packSizeB) - packSizeA - packSizeB;
    
    std::cout << maxUnobtainable << std::endl;
    return 0;
}

Infection Propagation on a Line

This problem involves ants moving on a stick. When an infected ant meets another ant, the infection spreads, and they reverse direction. Since ants are indistinguishable and move at constant speed, we can model the interaction as them passing through each other without reversing. The solution involves counting ants moving towards the initial ant and those moving away that might be 'hit' by rebounding ants.

Logic:
If the first ant moves right, it will infect ants to its right moving left. If such collisions occur, ants rebounding to the left (originally to the right of the first ant moving left) will effectively collide with ants to the left of the start moving right.

#include <iostream>
#include <vector>
#include <cmath>

int main() {
    int count;
    std::cin >> count;
    std::vector<int> ants(count);
    
    for (auto& pos : ants) {
        std::cin >> pos;
    }

    int targetHeadOn = 0; // Ants moving towards the initial ant
    int targetChase = 0;  // Ants moving away that might be hit
    int initialAnt = ants[0];

    for (int i = 1; i < count; ++i) {
        int current = ants[i];
        
        if (initialAnt > 0) {
            // Initial ant moves right
            if (current < 0 && std::abs(current) > initialAnt) targetHeadOn++;
            if (current > 0 && std::abs(current) < initialAnt) targetChase++;
        } else {
            // Initial ant moves left
            if (current > 0 && std::abs(current) < std::abs(initialAnt)) targetHeadOn++;
            if (current < 0 && std::abs(current) > std::abs(initialAnt)) targetChase++;
        }
    }

    if (targetHeadOn == 0) {
        // No collision will occur
        std::cout << 1 << std::endl;
    } else {
        // All relevant ants get infected
        std::cout << targetHeadOn + targetChase + 1 << std::endl;
    }
    
    return 0;
}

Simulating Bottle Recycling

This simulation problem tracks the total number of beverages consumed given an exchange policy. For every specific number of empty bottles (bottle caps), a new drink can be obtained. The loop continues until the remaining caps are insufficient for a trade.

#include <iostream>

int main() {
    int initialBottles;
    std::cin >> initialBottles;
    
    int totalConsumed = initialBottles;
    int currentCaps = initialBottles;
    const int exchangeRate = 3;

    while (currentCaps >= exchangeRate) {
        int newDrinks = currentCaps / exchangeRate;
        totalConsumed += newDrinks;
        // Remaining caps are the unused ones plus the caps from new drinks
        currentCaps = (currentCaps % exchangeRate) + newDrinks;
    }

    std::cout << totalConsumed << std::endl;
    return 0;
}