Nesse sábado dia 15/06 ocorreu a primeira etapa da Seletiva UFRN para a Maratona de Programação. Infelizmente, dos 29 inscritos para a seletiva apenas 12 compareceram, além de um competidor que não está concorrendo às vagas, porém a competição foi bem aproveitada por aqueles que lá estiveram. Como resultado final, tivemos Charles em primeiro lugar com 3 problemas resolvidos, Lucas Tomé em segundo com 2 problemas resolvidos e outros 8 com apenas 1 problema resolvido, diferenciando-se apenas pela penalidade de tempo (considerando que Argus não está concorrendo as vagas).
Os problemas da competição foram escolhidos dentre diversas competições passadas ao redor do mundo, tanto de fases regionais do ICPC quanto de outras competições como TopCoder e Google Code Jam. Os arquivos de entrada e saída de cada problema, bem como a nossa solução para eles podem ser baixados aqui (o código do Roleta Turca não está presente). Para aqueles que querem testar diretamente em juiz online, veja os links abaixo, bem como uma dica simples sobre cada problema.
A - Emoticons: pense em cada emoticon como um intervalo, então o que é preciso descobrir é o menor número de pontos que irão cobrir todos os intervalos.
B - Fraude Eleitoral: com os números dados, veja qual a menor e a maior soma que pode ter acontecido antes do arredondamento.
C - Recomposição de Pontuação Simples: podem ser testadas todas as permutações de pontuações possíveis.
D - Reorganização do Reino: árvore geradora mínima com os pesos das arestas existentes como negativos.
E - Roleta Turca: Programação Dinâmic.
F - Saudações Seguras: números de catalão (também pode ser feito recursivamente).
G - Tesouro: PD com bitmask, em que o estado é o bitmask dos baús já abertos.
H - TriFibonacci: ad hoc, porém precisa ser tomado cuidado com o fato de que o número a ser resposto tem que ser positivo.
Nenhum comentário:
Postar um comentário