MAC0327
Desafios de Programação
2006

Essa disciplina tem suas aulas num laboratório do CEC. O ambiente é semelhante aos concursos de programação ACM International Collegiate Programming Contest (http://icpc.baylor.edu/icpc/) e Maratona de Programação (http://maratona.ime.usp.br/).

O objetivo é criar condições para que o aluno de computação desenvolva suas habilidades de resolução de problemas computacionais. Os problemas de programação dessas competições são uma excelente oportunidade para aprender técnicas de criação e análise de algoritmos.

A cada aula o aluno recebe uma coleção de problemas (dois ou três) para os quais ele deve implementar um algoritmo, preferivelmente durante o período da aula. Caso não consiga terminar, ele deve fazê-lo até a aula seguinte. Assim sendo, é exigida uma boa quantidade de programação nesta disciplina. Parte de algumas das aulas são expositivas, abordando alguma técnica de programação que seja relevante para a resolução dos problemas selecionados.

Acreditamos que ela pode ser cursada mesmo por alunos de segundo ano, se bem ajuda bastante se o aluno já cursou as disciplinas de MAC338 - Análise de Algoritmos e MAC328 - Algoritmos em Grafos.

Livro

Juízes

Outros links

Lista de problemas

A maioria dos problemas vem do livro "Programming Challenges".  Legenda para  "P/s/l":  P = popularity (A, B, C),  s = success rate (low, average, high),  l = level (1, 2, 3, 4).

  1. #1.6.1 p.15 A/l/1
    "The 3n+1 Problem" PC=110101 UVa=100
    chapter: Getting Started
    para 22/8/2006
  2. #7.6.1 p.157 A/a/1
    "Light, More Light" PC=110701 UVa=10110
    chapter: Number Theory
    para 22/8/2006
  3. #1.6.2 p.16 A/h/1
    "Minesweeper" PC=110102 UVa=10189
    chapter: Getting Started
    para xxxxx
  4. #1.6.8 p.25 B/l/1
    "Australian Voting" PC=110108 UVa=10142
    chapter: Getting Started
    para 22/8/2006
  5. #2.8.3 p.45 B/h/2
    "Hartals" PC=110203 UVa=10050
    chapter: Data Structures
    para ???????
  6. #1.6.3 p.17 B/a/1
    "The Trip" PC=110103 UVa=10137
    chapter: Getting Started
    para ???????
  7. Não está no PC nem UVa
    "Medianas"
    para 15/8/2006
  8. #4.6.2 p.89 B/h/2
    "Stack of Flapjacks" PC=110402 UVa=120
    chapter: Sorting
    para 24/8/2006
  9. #5.9.2 p.120 A/l/1
    "Reverse and Add" PC=110502 UVa=10018
    chapter: Arithmetic and Algebra
    para 24/8/2006
  10. #5.9.3 p.121 A/l/1
    "The Archeologist's Dilemma" PC=110503 UVa=701
    chapter: Arithmetic and Algebra
    para 24/8/2006
  11. #2.8.4 p.47 B/l/2
    "Crypt Kicker" PC=110204 UVa=843
    chapter: Data Structures
    para 24/8/2006
  12. #4.6.4 B/a/1
    "Longest Nap" PC=110404 UVa=10191
    chap: Sorting
  13. #4.6.7 p.97 B/a/2
    "ShellSort" PC=110407 UVa=10152
    chapter: Sorting
    para 29/8/2006
  14. #5.9.6 B/h/1
    "Polynomial Coefficients" PC=110506 UVa=10105
    chap: Arithmetic and Algebra
  15. #5.9.5 A/h/3
    "A Multiplication Game" PC=110505 UVa=847
    chap: Arithmetic and Algebra
  16. Problema A da X Maratona
  17. Problema H da X Maratona
  18. #6.6.3 B/h/2
    "Counting" PC=110603 UVa=10198
    chap: Combinatorics
  19. #6.6.6 C/h/2
    "The Priest Mathematician" PC=110606 UVa=10254
    chap: Combinatorics
  20. Problema C da X Maratona
  21. #7.6.6 B/a/1
    "Smith Numbers" PC=110706 UVa=10042
    chap: Number Theory
  22. #6.6.8 A/h/2
    "Steps" PC=110608 UVa=846
    chap: Combinatorics
  23. #7.6.4 A/a/2
    "Factovisors" PC=110704 UVa=10139
    chap: Number Theory
  24. #8.6.1 C/h/2
    "Little Bishops" PC=110801 UVa=861
    chap: Backtracking
  25. #8.6.3 B/h/2
    "Queue" PC=110803 UVa=10128
    chap: Backtracking
  26. #8.6.8 C/h/3
    "Bigger Square Please…" PC=110808 UVa=10270
    chap: Backtracking
  27. #3304 Sudoku
  28. #9.6.1 A/h/1
    "Bicoloring" PC=110901 UVa=10004
    chap: Graph Traversal
  29. #10.5.1 B/a/2
    "Freckles" PC=111001 UVa=10034
    chap: Graph Algorithms
  30. #10.5.2 B/l/3
    "The Necklace" PC=111002 UVa=10054
    chap: Graph Algorithms
  31. #10.5.3 B/l/2
    "Fire Station" PC=111003 UVa=10278
    chap: Graph Algorithms
  32. #9.6.2 C/a/2
    "Playing With Wheels" PC=110902 UVa=10067
    chap: Graph Traversal
  33. "The Mailbox Manufacturers Problem" UVa=882 (não está no livro)
    Prog Dyn
  34. #12.6.1 B/h/1
    "Ant on a Chessboard" PC=111201 UVa=10161
    chap: Grids

Possíveis respostas do juiz

PE Presentation Error The output is correct but it produces some extra space or blank line
WA Wrong Answer The output of the program does not match the correct output
TL Time Limit Exceeded The program does not terminate within the specified time limit
CE Compile Error The program does not compile with the specified language s compiler
RE Runtime Error The program has crashed
ML Memory Limit Exceeded The program requires more memory to run than what the judge allows
OL Output Limit Exceeded The program produces more than 4 MB output within the time limit
RF Restricted Function The program uses some system function call or tries to access files
Others Uncommon verdicts Some rare verdicts produced by the judge

Exemplo de Makefile

Para facilitar o teste de programas em C, eu uso um arquivo Makefile semelhante ao seguinte (o arquivo fica no meu diretório de trabalho):

PROG  = xxx
ENTRA = yyy
SAI   = zzz

CFLAGS = -Wall -ansi -pedantic -g -O2 -I.

LDLIBS = -lm
# para o caso de usar sqrt, sin, cos, etc.


default : 
	@echo ""
	gcc $(CFLAGS) $(PROG).c $(LDLIBS) -o $(PROG)
	@echo ""
	@echo "-----------------------------------"
	@echo "Teste:"
	-$(PROG) <$(ENTRA) >$(SAI)
	cat $(SAI)

(As linhas precedidas por "#" são comentários.)  Para compilar e testar um programa xxx.c com arquivo de dados yyy, basta digitar "make".  A saída é gravada no arquivo zzz e em seguida exibida no monitor.

Função qsort

A função qsort, presente nos sistemas UNIX e GNU/Linux, é muito útil.  Veja em ~pf/algoritmos/apend/util.html#qsort como usá-la.

 


URL: http://www.ime.usp.br/~pf/challenges/
Responsável:  Cristina Gomes Fernandes
Ajudantes:  Carlos Eduardo Ferreira,  José Coelho de Pina Jr.,  Paulo Feofiloff

Valid HTML 4.0!