CacheDB: 2026-05-08 13:06:58

1034-problema-do-troco

problema-do-troco

C Difficulty

README.md Preview

# 1034 - Problema do Troco | **Version**: 1.0
`problema-do-troco` | Difficulty: **C** | **Updated**: 2026-04-15 22:52:29

**Sync Status:** ✅ Local: OK | ✅ Maratona: OK | ✅ API: OK (15/04/26 22:41)

## Overview
Otimização combinatória equivalente ao 'Unbounded Knapsack Problem' e 'Coin Change'. O algoritmo exige modelagem iterativa Bottom-Up via Programação Dinâmica para minimizar agregação em um target exato M, provando que abordagens puramente Gulosas colapsam sob alocações assimétricas.

## Metadata
- **Author**: wanderley-guimaraes
- **Editorial Author**: alessio
- **Editorial**: A heurística Gulosa falhará contra os casos de teste complexos. É preciso estruturar a solução com Programação Dinâmica, tabulando a menor quantidade de itens para cada sub-valor de 0 a M para encontrar o mínimo global alcançável iterativamente.
- **Success Msg**: Processamento TDD validado. A transição de estado tabular O(M) mitigou falhas heurísticas (False Positives Gulosos) e assegurou robustez O(NM) contra Limits Severos sem provocar stack overflows recursivos.

| Time Limit | Memory Limit | Time Complexity | Space Complexity |
| :--- | :--- | :--- | :--- |
| 3s | 128MB | O(N) | O(N) |

## Stats
| Metric | Count |
| :--- | :--- |
| Test Scenarios | 15 |
| Solutions | 3 |

## Statements
| ID | Status | Level | Natural Languages | Skills |
| :--- | :--- | :--- | :--- | :--- |
| `a-problema-do-troco` | ✅ | A | pt | commerce |
| `a-estatuas-de-gelo` | ✅ | A | pt | daily-life |

## Test Scenarios
| Name | Description | Count | Type | Level | Skills | DB Sync |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| **Submissões de Fuzzing** | Casos gigantescos (T=1000, M=1000000) forçando o uso de Programação Dinâmica tabulada bottom-up prevenida contra stack overflow. | 3 | Performance | A | dynamic-programming, coin-change | ✅ 3/3 |
| **Falso Positivo Guloso** | Sistemas de moedas com valores irregulares onde a lógica Gulosa encontra caminhos sub-ótimos, caindo na armadilha perfeitamente sem erros de sintaxe (Wrong Answer limpo). | 3 | False-Green | B | greedy-algorithms, dynamic-programming | ✅ 3/3 |
| **Programação Dinâmica Clássica** | Casos de programação dinâmica medianos. Sem restrições rígidas de tempo para validar a lógica canônica recursiva ou tabulada com memoização. | 3 | TDD | B | dynamic-programming, coin-change | ✅ 3/3 |
| **Gulosos Extensos** | Entradas com grande quantidade de denominadores, mas onde a heurística Gulosa continua alcançando o ótimo local. | 3 | TDD | C | greedy-algorithms, basic-programming | ✅ 3/3 |
| **Sample** | Instâncias simples retiradas do enunciado principal. Algoritmos Gulosos tendem a passar nesta subtask por serem casos básicos amigáveis. | 3 | TDD | D | basic-programming | ✅ 3/3 |

## Solutions
- **Solução Ótima (Programação Dinâmica)** (`a-otima`)
  - Languages: `cpp, py, java`
- **Solução Sub-ótima (Gulosa)** (`c-gulosa`)
  - Languages: `py`
- **Solução Força Bruta (Recursiva)** (`d-forca-bruta`)
  - Languages: `cpp`

## Components
- ✅ Statements
- ✅ Solutions
- ✅ Test Cases

Actions

Workflow do Problema

Local Workspace

Pasta criada no disco
Metadados

Informações básicas preenchidas
Validação

Soluções passam nos testes
4

Sincronização

Enviado para DB e GitLab

Components

Statements ✅
Solutions 3 ✅
Test Cases 15 ✅

Database Info

DB ID 1034

Name Problema do Troco

Time Limit 3.0s

Mem Limit 138 MB

Version 1.0

Difficulty Level C

Test Cases 15

🚀 Quick Prompts

Structure Scaffolding

Generate metadata & folder structure

ID: 1.1

Context & Description

Draft description & editorial

ID: 1.2

Statements List

ID	Level	Natural Languages	Skills	Status	Action
a-problema-do-troco	A	a b c d	commerce	⚠️
a-estatuas-de-gelo	A	a b	daily-life	⚠️

Statement Details

Select a statement above to view details.

Actions

Statistics

2 Total Statements

By Type (ID)

a-problema-do-troco 1
a-estatuas-de-gelo 1

By Level

Level A 2

🚀 Quick Prompts

Statement Analysis

Analyze ambiguity & clarity

ID: 2.1

WOK Statement Generation

Rewrite in WOK Universe theme

ID: 2.2

Statement Expansion

Expand to 4 difficulty levels

ID: 2.3

Database Test Cases 15 cases

ID	Rank	Status	Scenario	Filename	MD5	Description	Image	Disk Sync
14921	10	Sample	`d-sample` TDD	`sample-01`	I `28e9fb75aa4df5f29100b325abb8c2aa`	-	-	✅ Linked
14921	10	Sample	`d-sample` TDD	-	O `e6e9cab964cde7bf69025955bd790de8`	-	-	✅ Linked
14922	20	Sample	`d-sample` TDD	`sample-02`	I `b730864539d2db690f0241ea719a6f5e`	-	-	✅ Linked
14922	20	Sample	`d-sample` TDD	-	O `6ddb4095eb719e2a9f0a3f95677d24e0`	-	-	✅ Linked
14923	30	Sample	`d-sample` TDD	`sample-03`	I `c8cbfaca450774b3808b991d2971a3e4`	-	-	✅ Linked
14923	30	Sample	`d-sample` TDD	-	O `b026324c6904b2a9cb4b88d6d61c81d1`	-	-	✅ Linked
14924	40		`c-greedy-friendly` TDD	`greedy-friendly-01`	I `f110e288a1f46a2e3dcf741a92a3f6f6`	-	-	✅ Linked
14924	40		`c-greedy-friendly` TDD	-	O `aab7e347f9aa1c3cf3c14ae4f87c2488`	-	-	✅ Linked
14925	50		`c-greedy-friendly` TDD	`greedy-friendly-02`	I `2f55c1b776783326a21435055f0a06fb`	-	-	✅ Linked
14925	50		`c-greedy-friendly` TDD	-	O `c40982ec8f1a0e5b28fedf80d271ffd5`	-	-	✅ Linked
14926	60		`c-greedy-friendly` TDD	`greedy-friendly-03`	I `9c769a2739b497f5c8dbe190eb357602`	-	-	✅ Linked
14926	60		`c-greedy-friendly` TDD	-	O `a5308d5c3f10c07b68ddb3b9d2301792`	-	-	✅ Linked
14927	70		`b-dp-basico` TDD	`dp-basico-01`	I `ab45b5b59865d7a4bde6232a05c7912a`	-	-	✅ Linked
14927	70		`b-dp-basico` TDD	-	O `be34787b7197b91b2cf2477ac17f75c0`	-	-	✅ Linked
14928	80		`b-dp-basico` TDD	`dp-basico-02`	I `ec24d6955b2612158a74e4a4d8dae3c1`	-	-	✅ Linked
14928	80		`b-dp-basico` TDD	-	O `5ff5346abe3eaef0fda42cbb18efd8c5`	-	-	✅ Linked
14929	90		`b-dp-basico` TDD	`dp-basico-03`	I `9f74956e06487251558b6585c41ae47a`	-	-	✅ Linked
14929	90		`b-dp-basico` TDD	-	O `0b80bda548efa881c513cacd13a61d6c`	-	-	✅ Linked
14930	100		`b-greedy-breaker` False-Green	`falso-green-01`	I `961b1389ebbfad62bc04cde6e0294bbb`	-	-	✅ Linked
14930	100		`b-greedy-breaker` False-Green	-	O `6d7fce9fee471194aa8b5b6e47267f03`	-	-	✅ Linked
14931	110		`b-greedy-breaker` False-Green	`falso-green-02`	I `663b6f5ae5a578ef665df1832fb82eef`	-	-	✅ Linked
14931	110		`b-greedy-breaker` False-Green	-	O `9ae0ea9e3c9c6e1b9b6252c8395efdc1`	-	-	✅ Linked
14932	120		`b-greedy-breaker` False-Green	`falso-green-03`	I `6269c451110079c4f5a6d2e44ae97297`	-	-	✅ Linked
14932	120		`b-greedy-breaker` False-Green	-	O `9ae0ea9e3c9c6e1b9b6252c8395efdc1`	-	-	✅ Linked
14933	130		`a-performance` Performance	`performance-01`	I `f6905660aa451871d53f1c3d1ba50dc8`	-	-	✅ Linked
14933	130		`a-performance` Performance	-	O `ff5f74bc8111dfcf69e2e7944210114a`	-	-	✅ Linked
14934	140		`a-performance` Performance	`performance-02`	I `3f3074f8e872cd6a94d306ca6a5170c2`	-	-	✅ Linked
14934	140		`a-performance` Performance	-	O `ff5f74bc8111dfcf69e2e7944210114a`	-	-	✅ Linked
14935	150		`a-performance` Performance	`performance-03`	I `5a322b8b52ab4eaa7309ab8f06a2a34b`	-	-	✅ Linked
14935	150		`a-performance` Performance	-	O `8e75327432c2af82a45993a27190aa89`	-	-	✅ Linked

📊 Sync Statistics

Total (Disk) 15

Total (Database) 15

✓ Synchronized 15

⚠ Desynchronized 0

Duplicates (MD5)

Duplicates in (MD5) 0

Desync = (DB missing on Disk) + (Disk missing on DB)

Actions

Testcase Scenarios Sync

YAML Source vs Database

Slug	Level	Name	Type	Skills	Status
`a-performance`	A	Submissões de Fuzzing Casos gigantescos (T=1000, M=1000000) forçando...	PERFORMANCE	dynamic-programming 2pts coin-change 1pts	Synced
`b-greedy-breaker`	B	Falso Positivo Guloso Sistemas de moedas com valores irregulares...	TDD_FALSE_GREEN	greedy-algorithms 1pts dynamic-programming 1pts	Synced
`b-dp-basico`	B	Programação Dinâmica Clássica Casos de programação dinâmica medianos. Sem...	TDD	dynamic-programming 1pts coin-change 1pts	Synced
`c-greedy-friendly`	C	Gulosos Extensos Entradas com grande quantidade de...	TDD	greedy-algorithms 1pts basic-programming 1pts	Synced
`d-sample`	D	Sample Instâncias simples retiradas do enunciado...	TDD	basic-programming 1pts	Synced

Local Test Cases (Disk)

Scenario: a-performance 3 cases

Name	Files (Input / Output)	Status	Actions
performance-01 #14933 📄 📷	Input `performance-01.in` f6905660aa451871d53f1c3d1ba50dc8 Output `performance-01.out` ff5f74bc8111dfcf69e2e7944210114a	✅ Synced (ID: 14933)	🔍 Details
performance-02 #14934 📄 📷	Input `performance-02.in` 3f3074f8e872cd6a94d306ca6a5170c2 Output `performance-02.out` ff5f74bc8111dfcf69e2e7944210114a	✅ Synced (ID: 14934)	🔍 Details
performance-03 #14935 📄 📷	Input `performance-03.in` 5a322b8b52ab4eaa7309ab8f06a2a34b Output `performance-03.out` 8e75327432c2af82a45993a27190aa89	✅ Synced (ID: 14935)	🔍 Details

Scenario: b-dp-basico 3 cases

Name	Files (Input / Output)	Status	Actions
dp-basico-01 #14927 📄 📷	Input `dp-basico-01.in` ab45b5b59865d7a4bde6232a05c7912a Output `dp-basico-01.out` be34787b7197b91b2cf2477ac17f75c0	✅ Synced (ID: 14927)	🔍 Details
dp-basico-02 #14928 📄 📷	Input `dp-basico-02.in` ec24d6955b2612158a74e4a4d8dae3c1 Output `dp-basico-02.out` 5ff5346abe3eaef0fda42cbb18efd8c5	✅ Synced (ID: 14928)	🔍 Details
dp-basico-03 #14929 📄 📷	Input `dp-basico-03.in` 9f74956e06487251558b6585c41ae47a Output `dp-basico-03.out` 0b80bda548efa881c513cacd13a61d6c	✅ Synced (ID: 14929)	🔍 Details

Scenario: b-greedy-breaker 3 cases

Name	Files (Input / Output)	Status	Actions
greedy-breaker-01 #14930 📄 📷	Input `greedy-breaker-01.in` 961b1389ebbfad62bc04cde6e0294bbb Output `greedy-breaker-01.out` 6d7fce9fee471194aa8b5b6e47267f03	✅ Synced (ID: 14930)	🔍 Details
greedy-breaker-02 #14931 📄 📷	Input `greedy-breaker-02.in` 663b6f5ae5a578ef665df1832fb82eef Output `greedy-breaker-02.out` 9ae0ea9e3c9c6e1b9b6252c8395efdc1	✅ Synced (ID: 14931)	🔍 Details
greedy-breaker-03 #14932 📄 📷	Input `greedy-breaker-03.in` 6269c451110079c4f5a6d2e44ae97297 Output `greedy-breaker-03.out` 9ae0ea9e3c9c6e1b9b6252c8395efdc1	✅ Synced (ID: 14932)	🔍 Details

Scenario: c-greedy-friendly 3 cases

Name	Files (Input / Output)	Status	Actions
greedy-friendly-01 #14924 📄 📷	Input `greedy-friendly-01.in` f110e288a1f46a2e3dcf741a92a3f6f6 Output `greedy-friendly-01.out` aab7e347f9aa1c3cf3c14ae4f87c2488	✅ Synced (ID: 14924)	🔍 Details
greedy-friendly-02 #14925 📄 📷	Input `greedy-friendly-02.in` 2f55c1b776783326a21435055f0a06fb Output `greedy-friendly-02.out` c40982ec8f1a0e5b28fedf80d271ffd5	✅ Synced (ID: 14925)	🔍 Details
greedy-friendly-03 #14926 📄 📷	Input `greedy-friendly-03.in` 9c769a2739b497f5c8dbe190eb357602 Output `greedy-friendly-03.out` a5308d5c3f10c07b68ddb3b9d2301792	✅ Synced (ID: 14926)	🔍 Details

Scenario: d-sample 3 cases

Name	Files (Input / Output)	Status	Actions
sample-01 #14921 📄 📷	Input `sample-01.in` 28e9fb75aa4df5f29100b325abb8c2aa Output `sample-01.out` e6e9cab964cde7bf69025955bd790de8	✅ Synced (ID: 14921)	🔍 Details
sample-02 #14922 📄 📷	Input `sample-02.in` b730864539d2db690f0241ea719a6f5e Output `sample-02.out` 6ddb4095eb719e2a9f0a3f95677d24e0	✅ Synced (ID: 14922)	🔍 Details
sample-03 #14923 📄 📷	Input `sample-03.in` c8cbfaca450774b3808b991d2971a3e4 Output `sample-03.out` b026324c6904b2a9cb4b88d6d61c81d1	✅ Synced (ID: 14923)	🔍 Details

📊 Sync Statistics

Total (Disk) 15

Total (Database) 15

✓ Synchronized 15

⚠ Desynchronized 0

Duplicates (MD5)

Duplicates in (MD5) 0

Desync = (DB missing on Disk) + (Disk missing on DB)

Actions

Solução Ótima (Programação Dinâmica)

ID: a-otima

Solução ótima do Exercício usando PD paralela (Bottom-Up)

Implementations

Solução Sub-ótima (Gulosa)

ID: c-gulosa

Algoritmo guloso O(N log N) que falha em certos conjuntos de moedas (Wrong Answer)

Implementations

py Imperative

✅ guloso.py

Solução Força Bruta (Recursiva)

ID: d-forca-bruta

Busca completa Exponencial que gera Time Limit Exceeded (TLE)

Implementations

cpp Imperative

✅ bruta.cpp

Solutions Check Report

## Solutions Check Report (Detalhado / Debug)
**Generated**: 2026-06-01T12:09:46.974316
**Solution**: `solutions/a-otima/troco.cpp`

### Compilation
✅ /home/ubuntu/apps/pack-tecnicas/workspace/1034-problema-do-troco/solutions/a-otima/troco.out

### Resultados

<table class="results-table"><thead><tr><th>Test Case</th><th>Result</th><th>Time (s)</th></tr></thead><tbody>
<tr class="scenario-row"><td colspan="3"><strong>a-performance - Performance</strong></td></tr>
<tr id="row-a-performance-performance-01-in"><td>performance-01.in</td><td>✅ PASS</td><td>0.016</td></tr>
<tr id="row-a-performance-performance-02-in"><td>performance-02.in</td><td>✅ PASS</td><td>0.016</td></tr>
<tr id="row-a-performance-performance-03-in"><td>performance-03.in</td><td>✅ PASS</td><td>0.016</td></tr>
<tr class="scenario-row"><td colspan="3"><strong>b-dp-basico - TDD</strong></td></tr>
<tr id="row-b-dp-basico-dp-basico-01-in"><td>dp-basico-01.in</td><td>✅ PASS</td><td>0.001</td></tr>
<tr id="row-b-dp-basico-dp-basico-02-in"><td>dp-basico-02.in</td><td>✅ PASS</td><td>0.001</td></tr>
<tr id="row-b-dp-basico-dp-basico-03-in"><td>dp-basico-03.in</td><td>✅ PASS</td><td>0.001</td></tr>
<tr class="scenario-row"><td colspan="3"><strong>b-greedy-breaker - False-Green</strong></td></tr>
<tr id="row-b-greedy-breaker-greedy-breaker-01-in"><td><a href="#detail-b-greedy-breaker-greedy-breaker-01-in" class="tc-link">greedy-breaker-01.in</a></td><td>✅ WA (expected)</td><td>0.001</td></tr>
<tr id="row-b-greedy-breaker-greedy-breaker-02-in"><td><a href="#detail-b-greedy-breaker-greedy-breaker-02-in" class="tc-link">greedy-breaker-02.in</a></td><td>✅ WA (expected)</td><td>0.001</td></tr>
<tr id="row-b-greedy-breaker-greedy-breaker-03-in"><td><a href="#detail-b-greedy-breaker-greedy-breaker-03-in" class="tc-link">greedy-breaker-03.in</a></td><td>✅ WA (expected)</td><td>0.001</td></tr>
<tr class="scenario-row"><td colspan="3"><strong>c-greedy-friendly - TDD</strong></td></tr>
<tr id="row-c-greedy-friendly-greedy-friendly-01-in"><td>greedy-friendly-01.in</td><td>✅ PASS</td><td>0.000</td></tr>
<tr id="row-c-greedy-friendly-greedy-friendly-02-in"><td>greedy-friendly-02.in</td><td>✅ PASS</td><td>0.003</td></tr>
<tr id="row-c-greedy-friendly-greedy-friendly-03-in"><td>greedy-friendly-03.in</td><td>✅ PASS</td><td>0.003</td></tr>
<tr class="scenario-row"><td colspan="3"><strong>d-sample - TDD</strong></td></tr>
<tr id="row-d-sample-sample-01-in"><td>sample-01.in</td><td>✅ PASS</td><td>0.001</td></tr>
<tr id="row-d-sample-sample-02-in"><td>sample-02.in</td><td>✅ PASS</td><td>0.000</td></tr>
<tr id="row-d-sample-sample-03-in"><td>sample-03.in</td><td>✅ PASS</td><td>0.000</td></tr>
</tbody></table>

### Detalhes (WA) — Expected vs Actual

<p id="detail-b-greedy-breaker-greedy-breaker-01-in"><strong>b-greedy-breaker/greedy-breaker-01.in</strong> <a href="#row-b-greedy-breaker-greedy-breaker-01-in" class="back-to-table" title="Voltar à tabela">↑ voltar</a></p>

<div class="wa-diff-wrap"><table class="diff" id="difflib_chg_to6__top"
           cellspacing="0" cellpadding="0" rules="groups" >
        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
        <thead><tr><th class="diff_next"><br /></th><th colspan="2" class="diff_header">Expected</th><th class="diff_next"><br /></th><th colspan="2" class="diff_header">Actual</th></tr></thead>
        <tbody>
            <tr><td class="diff_next" id="difflib_chg_to6__0"><a href="#difflib_chg_to6__top">t</a></td><td class="diff_header" id="from6_1">1</td><td nowrap="nowrap"><span class="diff_sub">3</span></td><td class="diff_next"><a href="#difflib_chg_to6__top">t</a></td><td class="diff_header" id="to6_1">1</td><td nowrap="nowrap"><span class="diff_add">2</span></td></tr>
        </tbody>
    </table></div>

<p id="detail-b-greedy-breaker-greedy-breaker-02-in"><strong>b-greedy-breaker/greedy-breaker-02.in</strong> <a href="#row-b-greedy-breaker-greedy-breaker-02-in" class="back-to-table" title="Voltar à tabela">↑ voltar</a></p>

<div class="wa-diff-wrap"><table class="diff" id="difflib_chg_to7__top"
           cellspacing="0" cellpadding="0" rules="groups" >
        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
        <thead><tr><th class="diff_next"><br /></th><th colspan="2" class="diff_header">Expected</th><th class="diff_next"><br /></th><th colspan="2" class="diff_header">Actual</th></tr></thead>
        <tbody>
            <tr><td class="diff_next" id="difflib_chg_to7__0"><a href="#difflib_chg_to7__top">t</a></td><td class="diff_header" id="from7_1">1</td><td nowrap="nowrap"><span class="diff_sub">6</span></td><td class="diff_next"><a href="#difflib_chg_to7__top">t</a></td><td class="diff_header" id="to7_1">1</td><td nowrap="nowrap"><span class="diff_add">2</span></td></tr>
        </tbody>
    </table></div>

<p id="detail-b-greedy-breaker-greedy-breaker-03-in"><strong>b-greedy-breaker/greedy-breaker-03.in</strong> <a href="#row-b-greedy-breaker-greedy-breaker-03-in" class="back-to-table" title="Voltar à tabela">↑ voltar</a></p>

<div class="wa-diff-wrap"><table class="diff" id="difflib_chg_to8__top"
           cellspacing="0" cellpadding="0" rules="groups" >
        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
        <thead><tr><th class="diff_next"><br /></th><th colspan="2" class="diff_header">Expected</th><th class="diff_next"><br /></th><th colspan="2" class="diff_header">Actual</th></tr></thead>
        <tbody>
            <tr><td class="diff_next" id="difflib_chg_to8__0"><a href="#difflib_chg_to8__top">t</a></td><td class="diff_header" id="from8_1">1</td><td nowrap="nowrap"><span class="diff_sub">6</span></td><td class="diff_next"><a href="#difflib_chg_to8__top">t</a></td><td class="diff_header" id="to8_1">1</td><td nowrap="nowrap"><span class="diff_add">3</span></td></tr>
        </tbody>
    </table></div>

✅ Verification

Validate your solutions against test cases using the metadata rules.

🚀 Quick Prompts

Solution Generation

Create Optimal/Sub-optimal code

ID: 3.1

📄 Enunciados

A 2

Idiomas: pt

💡 Soluções

cpp: 2 py: 2 java: 1

✅ 0 ❌ 0

🧪 Casos de Teste

5 Scen.

Total no Disco 15

Total no Banco 15

Sincronização 100.0%

Metadata (form)

Version

Name

Slug

ID Beecrowd

Difficulty

Time Complexity

Space Complexity

Time Limit (s)

Memory Limit (MB)

Origin

Author (Problem)

Author (Editorial)

Default Statement

Topics

Skills

Description

Editorial

Success message

metadata.yaml

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 1034 idBeecrowd: 1034 name: Problema do Troco origin: beecrowd topics: - introducao-cpp slug: problema-do-troco authorSlugEditorial: alessio authorSlugProblem: wanderley-guimaraes description: Otimização combinatória equivalente ao 'Unbounded Knapsack Problem' e 'Coin Change'. O algoritmo exige modelagem iterativa Bottom-Up via Programação Dinâmica para minimizar agregação em um target exato M, provando que abordagens puramente Gulosas colapsam sob alocações assimétricas. editorial: A heurística Gulosa falhará contra os casos de teste complexos. É preciso estruturar a solução com Programação Dinâmica, tabulando a menor quantidade de itens para cada sub-valor de 0 a M para encontrar o mínimo global alcançável iterativamente. successmsg: Processamento TDD validado. A transição de estado tabular O(M) mitigou falhas heurísticas (False Positives Gulosos) e assegurou robustez O(NM) contra Limits Severos sem provocar stack overflows recursivos. difficultyLevelId: C timeComplexity: O(N) spaceComplexity: O(N) timeLimitSegs: 3 memoryLimitMb: 128 defaultStatement: b_pt_estatuas-de-gelo.pdf skills: - basic-programming - coin-change - dynamic-programming - greedy-algorithms statements: - id: a-problema-do-troco testScenarioLevel: A thematicSkills: - points: 1 skill: commerce - id: a-estatuas-de-gelo testScenarioLevel: A thematicSkills: - points: 1 skill: daily-life testScenarios: - id: d-sample name: Sample description: Instâncias simples retiradas do enunciado principal. Algoritmos Gulosos tendem a passar nesta subtask por serem casos básicos amigáveis. helpTip: I/O Sanity Check. O caso atesta validação morfológica e limites primitivos da entrada, confirmando que a sintaxe base não estoura a conversão estrutural linear do seu vetor. level: D testType: TDD skills: - points: 1 skill: basic-programming - id: c-greedy-friendly name: Gulosos Extensos description: Entradas com grande quantidade de denominadores, mas onde a heurística Gulosa continua alcançando o ótimo local. helpTip: Heurística Sub-Ótima Resiliente. Sub-grafos perfeitamente harmonizados (múltiplos exatos) toleram relaxamentos simplificados onde o processamento denso natural via Guloso se iguala ao ótimo local. level: C testType: TDD skills: - points: 1 skill: greedy-algorithms - points: 1 skill: basic-programming - id: b-greedy-breaker name: Falso Positivo Guloso description: Sistemas de moedas com valores irregulares onde a lógica Gulosa encontra caminhos sub-ótimos, caindo na armadilha perfeitamente sem erros de sintaxe (Wrong Answer limpo). helpTip: 'Trap State Guloso O(N log N). Na ausência de modulações perfeitas (ex: Array {1, 15, 25} para Target 30), a extração agressiva do maior componente bloqueia o algoritmo num Sub-Ótimo global irreversível.' level: B testType: TDD_FALSE_GREEN skills: - points: 1 skill: greedy-algorithms - points: 1 skill: dynamic-programming - id: b-dp-basico name: Programação Dinâmica Clássica description: Casos de programação dinâmica medianos. Sem restrições rígidas de tempo para validar a lógica canônica recursiva ou tabulada com memoização. helpTip: Topological Map (Memoization). Instâncias neutras exigem modelagem da transição DP(i) = min(DP(i), DP(i-Weight) + 1). O processador valida estabilidade sob Bottom-Up e Top-Down canônicos. level: B testType: TDD skills: - points: 1 skill: dynamic-programming - points: 1 skill: coin-change - id: a-performance name: Submissões de Fuzzing description: Casos gigantescos (T=1000, M=1000000) forçando o uso de Programação Dinâmica tabulada bottom-up prevenida contra stack overflow. helpTip: DP Stress-Test O(NM). Testes massivos (M=1M) causam letalidade direta de 'Stack Overflow' nas DFS Top-Down. Imponha purgação Bottom-Up para alavancar estabilidade em cache linear O(1) de saltos em memória estrita. level: A testType: PERFORMANCE skills: - points: 2 skill: dynamic-programming - points: 1 skill: coin-change solutions: - id: a-otima name: Solução Ótima (Programação Dinâmica) description: Solução ótima do Exercício usando PD paralela (Bottom-Up) level: A implementations: - filenames: - troco.cpp language: cpp paradigm: Imperative - filenames: - troco_pd.py language: py paradigm: Imperative - filenames: - Troco.java language: java paradigm: Imperative main: Troco - id: c-gulosa name: Solução Sub-ótima (Gulosa) description: Algoritmo guloso O(N log N) que falha em certos conjuntos de moedas (Wrong Answer) level: C implementations: - filenames: - guloso.py language: py paradigm: Imperative - id: d-forca-bruta name: Solução Força Bruta (Recursiva) description: Busca completa Exponencial que gera Time Limit Exceeded (TLE) level: D implementations: - filenames: - bruta.cpp language: cpp paradigm: Imperative

1034-problema-do-troco

README.md Preview

Actions

Workflow do Problema

Local Workspace

Metadados

Validação

Sincronização

Components

Database Info

🚀 Quick Prompts

Statements List

Statement Details

Actions

Statistics

By Type (ID)

By Level

🚀 Quick Prompts

Database Test Cases 15 cases

📊 Sync Statistics

Actions

Test Case Details

Testcase Scenarios Sync

Local Test Cases (Disk)

Scenario: a-performance 3 cases

Scenario: b-dp-basico 3 cases

Scenario: b-greedy-breaker 3 cases

Scenario: c-greedy-friendly 3 cases

Scenario: d-sample 3 cases

📊 Sync Statistics

Actions

Solução Ótima (Programação Dinâmica)

Implementations

Solução Sub-ótima (Gulosa)

Implementations

Solução Força Bruta (Recursiva)

Implementations

Solutions Check Report

✅ Verification

🚀 Quick Prompts

📄 Enunciados

💡 Soluções

🧪 Casos de Teste

Metadata (form)

Git Status

Git Workflow

Problem Analysis Report

🛠️ Validation Tools

✅ Synced with API

✅ Synced with Database

Actions

📋 Processo de Criação

Select a Prompt

📤 API Synchronization

📄 Recreating README.md...

💻 Git Action Output

Running Verification...

Ajuda

📄 Sync Statements to DB

🚀 Batch Auto-Link Process

⬇️ Repo Sync Output

📝 Update Manifest Output

Ajuda