This repository contains a competitive programming problem designed for a university programming contest setting, including the official solution, alternative correct solutions, incorrect/inefficient solutions for judging, and tooling for test generation and stress testing.

• Alejandro Parreño Minaya — @aparreno14
• Daniel Casquero Palencia

The full statement is available in: enunciado.pdf

Goal (high-level): pay an exact amount C using an unlimited supply of N coin denominations, minimizing the number of coins, under the additional constraint that the total number of coins used must be divisible by K.

Input consists of multiple test cases. Each case is described in two lines:

• Line 1: C K N
• Line 2: N distinct coin values

The input ends with: 0 0 0

Output (one line per test case):

• the minimum number of coins, if possible
• or the word: Imposible

• 0 ≤ C ≤ 10,000
• 1 ≤ K ≤ 50
• 1 ≤ N ≤ 20
• 1 ≤ coin value ≤ 1,000 (all distinct)

• enunciado.pdf — problem statement
• oficial.cpp — reference (“official”) solution
• assert.cpp — same logic with asserts to validate input constraints
• generador.cpp — test generation utilities (special, large, random)
• Ejemplos de casos de prueba/ — sample test sets
• Otras soluciones correctas/ — alternative correct approaches
• Soluciones malas/ — wrong answers / inefficient approaches for judging
• prueba/ — local stress-testing workspace (includes scripts and variants)

The official approach models the problem as a shortest-path / dynamic programming over states:

• state = (current_sum, current_mod) where current_mod = (#coins used) mod K
• transitions: add one coin of any type
• objective: reach (C, 0) with minimum steps (coins)

A standard DP formulation is dp[sum][mod] = minimum coins to reach that state, updating transitions by adding a coin and advancing mod by +1 (mod K).

Note: The repository also includes a graph/BFS-style alternative correct solution.

Requirements: a C++17 compiler (g++/clang++/MSVC).

Compile the official solution: g++ -std=c++17 -O2 -Wall -Wextra oficial.cpp -o oficial

Run: ./oficial < input.txt

Compile the generator (optional): g++ -std=c++17 -O2 -Wall -Wextra generador.cpp -o generador

• Use assert.cpp to ensure generated cases respect constraints.
• Use the provided “wrong” solutions to confirm the judge data rejects naive strategies (e.g., greedy WA).
• Use the sample / large / random datasets under Ejemplos de casos de prueba/.

MIT (see LICENSE).