Disciplina: ACH2107 - Desafios de Programação I
1º Semestre de 2019
Além de submeter a solução no sistema acima, cada grupo deverá mostrar o resultado da submissão ao professor e enviar um e-mail ao docente (digiampietri@usp.br) durante a aula contendo:
|
| ID | Problema | Enunciado em Português | Entradas | Saídas | Aproveitamento do Problema | Simplista // Solução_Submetida | Discussão/Dicas | ||
| 100 [UVa] | O problema do 3*n + 1 | entrada.txt entrada2.txt |
saida.txt saida2.txt |
Desconhecida | Desconhecida | Cuidado com o caso em que o primeiro número da entrada for maior que o segundo. Se desejar use o arquivo Main.java ou Main.c ou Main.py para implementar sua solução. |  |
||
| 1001 [URI] | Extremamente Básico | A entrada é composta por apenas um par de números inteiros. Se desejar, use o arquivo Main.java para implementar sua solução. | |||||||
| 639 | Colocando Torres de Xadrez | entrada.txt | saida.txt | O(2^n) | O(2^n) | Complete o arquivo Main.java. O problema pode ser resolvido com uma tentativa e erro onde em cada casa pode-se colocar ou não uma torre de xadrez. | |||
| 146 | Códigos de Identificação | entrada.txt
entrada2.txt |
saida.txt
saida2.txt |
O(n^2) | O(n), O(n*log(n)) e O(n^2) | Arquivo Main.java para a leitura do arquivo de entrada (implemente o método executar para resolver este problema). Dica: divida o problema em três partes: (i) identificar o ponto onde a sequência será mudada; (ii) identificar qual valor irá para esse lugar; (iii) ordenar de maneira crescente o resto da sequência (após o ponto de mudança). | |||
| 352 | Guerras Sazonais | entrada.txt | saida.txt | O(n^3) | O(n^2) | Arquivo Main.java para a leitura do arquivo de entrada (implemente o método executar para resolver este problema). Dica: para cada caça identificado, apague-o totalmente da imagem. | |||
| 580 | Massa Crítica | entrada.txt | saida.txt | O(n!) ou O(2^n) | O(n) | Complete o arquivo Main.java. Use long para armazenar a resposta (o tipo int pode ser pequeno demais). Para otimizar o sistema basta usar um arranjo "global/estático" com os valores parciais já calculados. | |||
| 337 | Interpretando Sequências de Controle | entrada.txt | saida.txt | O(n) | O(n) | Arquivo Main.java para a leitura do arquivo de entrada (implemente o método executar para resolver este problema). O algoritmo é ad hoc, basta manter o terminal atualizado e executar os comandos solicitados. | |||
| 151 | Crise Elétrica | entrada.txt
entrada2.txt |
saida.txt
saida2.txt |
O(n^6) | O(n^3) | Arquivo Main.java para a leitura do arquivo de entrada (implemente o método executar para resolver este problema). Dica1: não é necessário utilizar um arranjo. As informações relevantes são: quantas cidades estão acesas antes da cidade 13; o total de cidades e a posição da última cidade apagada. | |||
| 1112 | Os Ratos e o Labirinto | entrada.txt | saida.txt | O(n^3) | O(n^3),O(n^2) | Arquivo Main.java para a leitura do arquivo de entrada (implemente o método executar para resolver este problema). Dica: trata-se de um problema da distância mínima (caminho mínimo) de um ponto para todos os demais. | |||
| 167 | Os Sucessores do Sultão | entrada.txt | saida.txt | O(k*((m^(m+1))) = O(134.217.728*k) | O(744*k) | Arquivo Main.java para a leitura do arquivo de entrada (implemente o método executar para resolver este problema). Trata-se de um problema de tentativa e erro, mas é importante otimizá-lo para não executar operações desnecessárias. Por exemplo, nunca é possível colocar duas rainhas numa mesma linha ou coluna (a cada chamada recursiva do algoritmo, você pode, por exemplo, ir para a próxima coluna). | |||
| 442 | 442 - Multiplicacao de Matrizes | entrada1.txt | saida1.txt | Complete o arquivo Main.java. Dicas: verifique como armazenar as matrizes da melhor forma para fazer os cálculos, bem como o que fazer com as matrizes resultantes. | |||||
| 882 | 882 - O Problema do Fabricante de Caixas Postais | entrada1.txt | saida1.txt | Complete o arquivo Main.java. Dica: não há uma fórmula mágica para resolver o problema, isto é, é necessário testar diferentes situações e verificar qual necessitará de mais bombinhas. Duas maneiras pensar na solução: decomposição do problema em problemas menores ou composição da solução a partir dos problemas menores. | |||||
| 439 | 439 - Movimentos do Cavalo | entrada1.txt | saida1.txt | Complete o arquivo Main.java. Trata-se de um problema típico de busca em largura. Porém, pode ser utilizado um algoritmo Tentativa e erro clássico, para isso vocês provavelmente precisão usar variáveis/atributos globais e deverão limitar a profundidade da busca. | |||||
| 377 | Matemática das Vacas | entrada.txt | saida.txt | O(n) | O(n) | Complete o arquivo Main.java. Dica: assim como existe a matemática binária e decimal, pode existir uma matemática quaternária. Que tal converter o "vacanes" para essa matemática base 4? | |||