Prazo de submissão: 15 de março (submeter no Mooshak de DAA)
Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem. Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relembre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.
Exercício 1) O meu primeiro problema aceite... no Mooshak de DAA!
Nesta unidade curricular vamos usar o sistema Mooshak para avaliar automaticamente os programas feitos (mesmo já tendo usado, veja com cuidado todos os passos aqui descritos).
O Mooshak está em "modo feedback detalhado", ou seja, é possível visualizar o resultado obtido em cada um dos testes ao código submetido. É também possível aceder aos testes públicos onde o programa submetido não responde correctamente. Para isso basta carregar no resultado da submissão, que aparece a sublinhado na listagem.
O Mooshak estará sempre em "modo IOI" (de pontos), ou seja, cada teste vale um determinado conjunto de pontos e apenas quando se tem 100 se acertou completamente no problema.
Para aceder ao sistema use o login e password que recebeu num email enviado a 23 de fevereiro. (se tiver problemas em aceder contacte o regente Pedro Ribeiro no Slack de DAA)
Leia o enunciado do problema [DAA 001] O sentido da vida (que é trivial)
Familiarize-se com as secções típicas de um enunciado em DAA:
Uma introdução no início com motivação e contexto
Secção Problema descreve resumidamente o problema e as variáveis envolvidas
Seccão Input descreve em detalhe como é dado o input (que deve ser sempre lido do stdin)
Seccão Output descreve em detalhe como deve ser escrito o output (que deve ser sempre escrito para o stdout, sendo que todas as linhas devem terminar com o caracter de mudança de linha)
Secção Restrições descreve os limites de todas as variáveis envolvidas (é garantido que os testes respeitam e não precisa de verificar no código; o intuito desta secção é ajudar a perceber a complexidade necessária)
Pelo menos um exemplo de input e output, tipicamente com uma secção que o explica.
Em DAA será possível usar qualquer uma das seguintes linguagens de programação: C, C++ ou Java
Pode sempre submeter na sua linguagem favorita e em qualquer altura pode modificar a sua escolha, sendo que daremos suporte ativo a cada uma das linguagens.
Para iniciar a sua "viagem" e como pode estar enferrujado, aqui fica um exemplo de solução para este problema em cada uma das 3 linguagens suportadas: daa001.c
| daa001.cpp
| daa001.java
Deve começar por compilar o seu programa na sua máquina (o Mooshak não é para ser usado como um compilador!). Para saber o comando exacto com que o seu programa será compilado, carregue no botão help.
Espreite tudo o que está disponível na página de ajuda: não apenas os comandos de compilação, mas também as versões do compiladores, os limites (memória, tempo, tamanho do código) e o que significa cada um dos resultados possíveis.
Para testar deve sempre colocar o exemplo num ficheiro (ex: daa001.txt) e fazer redirecionamento de input (executavel < daa001.txt). Se estiver numa shell de Linux, pode até compilar e executar num mesmo comando. Por exemplo:
Depois de ter testado na sua máquina, submeta então o código no Mooshak para o problema [DAA 001] O sentido da vida Procure sempre ler o guião e fazer o que ele lhe pede antes! A ideia não é partir logo para o Mooshak sem ler o contexto e perceber o que é suposto ser o objectivo da aula.
Para ficar familiarizado com os erros e confortável com a maneira como o Mooshak funciona, o objectivo deste exercício é provocar alguns erros ao submeter o problema [DAA 001] O sentido da vida. Use como base o seu código aceite.
Provoque um erro de apresentação (Presentation Error) (ex: retire o caracter de mudança de linha na impressão) e submeta para ver o feedback detalhado que é dado nesse caso.
Provoque um erro de compilação (Compile Time Error) (ex: retirar um ';') e verifique o feedback detalhado dado nesse caso.
Provoque uma resposta errada (Wrong Answer) (ex: mude a impressão para ser sempre 3). Note no feedback detalhado como consegue ver agora em que testes falha, e como tem acesso ao primeiro teste onde falha (sendo o que regente controla os testes que ficam "disponíveis": tipicamente o último é sempre secreto para evitar que façam "reverse engineering" a todos os testes e manter-vos "honestos").
Provoque um excesso de tempo de execução (Time Limit Exceedeed) (ex: faça com que o ciclo nunca termine) e verifique qual o feedback detalhado (cada problema pode ter um tempo limite diferente: por exemplo este [DAA 001] tem configurado 1 segundo como tempo limite de execução)
Como isto já deve ficar com uma ideia de alguns dos princiais erros, e do comportamento do Mooshak nesses casos. Lidar com isto no futuro será um skill importante, não apenas neste cadeira.
Exercício 3) Resolvendo um problema
Agora que já desenferrujou, passemos para um primeiro problema um pouco mais "a sério". Estes problema envolve apenas instruções básicas como ciclos:
Resolva e submeta o problema [DAA 002] Números arranjadinhos
Pode optar por tentar resolver completamente de forma autónoma, ou consultar dicas, que estão "escondidas" para não serem spoilers para todos (mesmo que faça "sozinho", não deixe no final de vir espreitar as dicas).
Os limites são pequenos e por isso é exequível fazer um ciclo a começar em Ni e ir iterando sobre todos os inteiros consecutivos até chegar a um cujos dígitos tenham soma Ki. (consegue estimar a complexidade? e se os limites fossem maiores isto chegaria?)
Faça uma função separada para receber um inteiro e devolver a soma dos seus dígitos, para o código ficar minimamente organizado.
Para obter a soma dos dígitos, pode por exemplo fazer um ciclo onde vai repetidamente extraindo o resto da divisão por 10 (instrução '%') para saber o último dígito, seguido de uma divisão por 10 para retirar esse mesmo dígito.
Exercício 4) Dificuldade++
Para terminar esta primeira aula, aqui fica um problema um pouco mais "giro" para que possam usar um pouco a cabeça a pensar num algoritmo, ao invés de ser logo "imediata" uma ideia de solução.
Era mais fácil se em vez de matrículas fosse só comparar números não? Porque não converter então a matrícula num número?
Para converter pensem na matrícula como um número
escrito numa "base" diferente e na maneira como convertem
um qualquer base para decimal. Por exemplo, se a matrícula
fosse apenas XN1N2, o seu número de
ordem era igual a
valor(X)*100+N1*10+N2
Cuidado com as letras 'K', 'W' e 'Y' que não devem ser
consideradas
Quando estamos numa dada geração, com avançar todas as matrículas anteriores? Por exemplo, a matrícula 00-00-AA não é a primeira, mas sim qual?
Se tiverem mais dúvidas podem e devem usar o Slack (usando por exemplo o canal #praticas ou enviando mensagem directa a um dos docentes).
Exercício de Desafio
Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.
Para esta semana o desafio tem a ver com a eficiência algorítmica e como desenhar um algoritmo mais eficiente para um problema que já deve ter resolvido. Para isso, deve tentar resolver o seguinte problema, que está disponível para submissão no Mooshak:
Notem a diferença nas restrições e como os limites impedem uma solução naive que itere sobre todos os inteiros consecutivos até descobrir a resposta.
Como este é um problema de desafio, não vou para já dar nenhuma dica, ficando à espera de ver os vossos programas :)
Se já tiverem feito tudo e estiverem "presos" neste, e quiserem mesmo fazer o desafio, podem contactar-me para eu "dosear" as dicas, sabendo que este problema é substancialmente mais difícil que a versão "fácil" original.
