| ID | Problema | Enunciado em
Português | Entradas | Saídas | Aproveitamento
do Problema | Complexidade Assintótica
Simplista // Solução_Submetida | Discussão/Dicas |
| 102 | Mochila Binária Ecológia |
[pdf] |
entrada.txt |
saida.txt |
85,7% | O(1) | O(1) |
Complete o arquivo Main.java ou Main.c |
| 1001 [URI] | Extremamente Básico |
[html] |
| | | O(1) | O(1) |
A entrada é composta por apenas um par de números inteiros. Se desejar, use o arquivo Main.java para implementar sua solução. |
| 108 | Soma Máxima |
[pdf] |
entrada.txt
entrada2.txt
entrada3.txt
|
saida.txt
saida2.txt
saida3.txt
|
75,0% | O(n^6) | O(n^3) e O(n^4) |
Arquivo Main.java para a leitura da matriz (implemente o método executar para resolver este problema).
Dica1: Para a solução n^4 use uma matriz auxiliar (calculada utilizando programação dinâmica) e contendo, para cada posição (i,j) a soma dos elmentos da sub-matriz de (0,0) até (i,j).
Dica2: Para a solução n^3 calcule a soma máxima (SM) das (n+1)*n/2 linhas correspondentes a soma de linhas consecutivas da matriz original (por exemplo, SM da linha 1, SM da soma das linhas 1 e 2, SM das linhas 1, 2 e 3, sm das linhas 2 e 3 ...). |
 |
| 532 | Mestre da Masmorra |
[pdf] |
entrada.txt
entrada2.txt
entrada3.txt
|
saida.txt
saida2.txt
saida3.txt
|
87,61% | O(6^(n^3)) | O(6^30) |
Complete o arquivo Main.java. O problema é, naturalmente, resolvido por uma busca em largura mas pode ser resolvido com tentativa e erro tomando-se cuidado para não usar caminhos maiores do que o maior já encontrado [ou do que o máximo definido pelo enunciado]. |
| 147 | Dólares |
[pdf] |
entrada1.txt
entrada2.txt
entrada2_br.txt |
saida1.txt
saida2.txt |
91,7% | O(m^n) | O(m*n) |
Complete o arquivo Main.java. Dica: é necessário usar programação dinâmica. Sugestão: use um arranjo com todos os valores possíveis de entrada e preencha utilizando programação dinâmica considerando os diferentes valores de notas/modedas. Dica2: as respostas podem ser números bastante grandes, sugere-se usar double; os valores de entrada são decimais múltiplos de 0,05, sugere-se multiplicar por 20 para utilizar inteiros. |
| Minimaratona 1 |
| 297 | QuadTree |
[pdf] |
entrada.txt |
saida.txt |
91% | O(n^2) | O(n) |
Complete o arquivo Main.java |
| 12487 | Perdido na Noite |
[pdf] |
entrada1.txt
entrada2.txt |
saida1.txt
saida2.txt |
87% | O(n^3) | O(n^3), O(n^2) e O(n) |
Complete o arquivo Main.java. A resposta do problema é igual a relação entre a distância da bifurcação do caminho até o hotel mais caro dividida pela soma das distâncias dos caminhos da bifurcação até o hotel mais barato e da bifurcação até o hotel mais caro.
|
| 572 | 572 - Depósito de Petróleo |
[pdf] |
entrada1.txt |
saida1.txt |
94,87% |
O(n^4) |
O(n^2) |
Complete o arquivo Main.java. Dica: para cada novo depósito que você encontrar, o mais fácil é marcar/remover todos os pontos daquele depósito da matriz. |
| 12648 | Chefe |
[pdf] |
entrada1.txt
entradas.zip |
saida1.txt
saidas.zip |
85,9% | n^2 | n |
Complete o arquivo Main.java. Dica: se você montar em memória a estrutura como um grafo onde os nós possuem os dados de cada pessoa, a troca de duas pessoas no grafo pode ser feita apenas trocando os valores dos atributos dos nós, sem nenhuma outra alteração na rede.
|
| Minimaratona 2 |
| 170 | 170 - Paciência de Relógio |
[pdf] |
entrada1.txt |
saida1.txt |
89% |
O(52*n) |
O(52*n) |
Complete o arquivo Main.java. Dicas: observe a ordem das cartas (invertida em relação à entrada); lembre-se de colocar um zero a esquerda na saída caso o contador de cartas seja menor que 10; pensem em uma maneira simples de armazenar as cartas e de fazer uma conversão fácil de carta para valor. Se quiser, adapte a leitura de cartas de forma a ficar mais eficiente (já organizando as cartas na estrutura que vocês forem utilizar). |
| 1291 | Dance, Dance, Revolution! |
[pdf] |
entrada.txt |
saida.txt |
90,9% | O(2^n) | O(n*(m^2)) |
Complete o arquivo Main.java. Uma implementação simplista usando tentativa e erro não irá satisfazer o limite de tempo imposto pelo sistema. Sugere-se o uso de programação dinâmica de forma semelhante à utilizada para o cálculo da distância de edição [1] [2]. |
| 417 | Índice da Palavra |
[pdf] |
entrada.txt |
saida.txt |
93,8% | O(n!) | O(n^2) |
Complete o arquivo Main.java. Dica: você pode dividir o problema em, dada uma palavra com x letras, contar quantas palavras existem com menos de x letra e adicionar a posição da palavra atual entre as palavras que têm x letras. |
| Minimaratona 3 |
| 1235 | 1235 - Cadeado anti força bruta |
[pdf] |
entrada.txt |
saida.txt |
90,9% |
O(2^m) |
O(n^2), O(m log n) |
Complete o arquivo Main.java. Dicas: a distância (ou custo) entre duas chaves é calculada de maneira bastante simples, bem como da combinação inicial para qualquer chave. A partir dessas distâncias, o problema se torna o de encontrar o custo da árvore geradora mínima (ou árvore geradora de custo mínimo). |
| 12485 | Coral Perfeito |
[pdf] |
entrada.txt |
saida.txt |
96% | n | n |
Complete o arquivo Main.java.
|