Prpgrmaing

Notas para el ACM ICPC
Octavio Alberto Agust´n Aquino
ı

Ricardo Omar Ch´ vez Garc´a
a
ı

Fernando Said Ram´rez Garc´a
ı
ı

17 de octubre de 2005

´
Indice

9. Programaci´ n din´ mica
o
a
9.1. Suma de subconjunto . . . . . . . . .
´
9.2. Estructuras de Catalan optimas . . . .
9.3. Mayor subsecuencia com´ n . . . . . .
u
9.4. Distancia de edici´ n . . . . . . . . . .
o9.5. Mayor subsecuencia creciente o decreciente . . . . . . . . . . . . . . . . .
9.6. Conteo de cambio . . . . . . . . . . .

1. Trigonometr´a
ı

1

2. Geometr´a anal´tica
ı
ı
2.1. Rectas, planos y c´rculos . . . . . . . .
ı
2.2. Transformaci´ n de coordenadas . . . .
o
2.3. Cuadr´ ticas . . . . . . . . . . . . . . .
a

2
2
2
2

3. Geometr´a computacional
ı
3.1.Triangulaci´ n de pol´gonos .
o
ı
3.2. Intersecci´ n de segmentos .
o
3.3. Envolvente convexa . . . . .
3.4. Punto en pol´gono . . . . . .
ı
3.5. M´nimo c´rculo encapsulador
ı
ı

a
3 10. Rastreo hacia atr´ s
3
3 11. Algoritmos voraces
4
12. Teor´a de grafos
ı
4
12.1. Circuitos eulerianos . . . . .
4
12.2. Recorridos . . . . . . . . . .
12.3. Caminos m´nimos . . . . . .
ı
4
12.3.1.Con una sola fuente .
4
12.3.2. Entre todos los pares
4
12.4. Ordenamiento topol´ gico . .
o
4
´
12.5. M´nimo arbol generador . .
ı
5
12.6. Grafos hamiltonianos . . . .
5
12.7. Flujo m´ ximo . . . . . . . .
a
6
6 13. Localizaci´ n de patrones
o
6
13.1. Algoritmo KMP . . . . . . .
13.2. Detecci´ n de periodicidades
o
6
6 14. Cuestiones miscel´ neas
a
7

.
.
.
.
.

..
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

´
4. Teor´a de numeros
ı
4.1. Factoriales . . . . . . . . . . . .
4.2. Ternas pitag´ ricas . . . . . . . .
o
4.3. Algoritmo de Euclides . . . . .
4.3.1. Ciclos en sucesiones . .
4.4. Divisores de un n´ mero . . . . .
u
4.5. N´ meros primos . . . . . . . . .
u
4.6. Potencias y logaritmos discretos
4.7.Teorema chino del residuo . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

5. Combinatoria
5.1. Objetos combinatorios . . . . . . . . .
5.2. N´ meros combinatorios . . . . . . . . .
u

.
.
.
.

10
10
10
11
11

. 11
. 12
12
12

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

..
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

12
13
13
13
13
14
14
14
15
15

15
. . . . . . 15
. . . . . . 15
16

8 1. Trigonometr´a
ı
8
Todo tri´ ngulo tiene un c´rculo inscrito tangente a sus
a
ı
8
´
8 lados e interior a el, cuyo centro es el punto de intersecci´ n de las bisectrices de los lados.
o
8
Todo tri´ ngulo tiene unc´rculo circunscrito que pasa
a
ı
9
por sus v´ rtices. El punto de intersecci´ n de las mediae
o
a
7. Probabilidad
9 nas del tri´ ngulo es su centro de masa.
´
Sea el tri´ ngulo A BC con angulos A, B y C y sean
a
´
8. Ordenamiento y busqueda
9 a, b y c los lados opuestos a dichos angulos, respecti´
8.1. Algoritmos basados en comparaciones . 9 vamente. Sean hc , tc y mc las longitudes dela altura, la
8.2. Algoritmos lineales . . . . . . . . . . . 10 bisectriz y la mediana que se originan en el v´ rtice C ,
e
8.3. B´ squeda binaria . . . . . . . . . . . . 10 y sean r y R los sendos radios de los c´rculos inscrito y
u
ı
´
6. M´ todos numericos
e
6.1. Interpolaci´ n . . . . . . . . . . .
o
6.2. Diferenciaci´ n . . . . . . . . . . .
o
6.3. Integraci´ n . . . . . . . . .. . .
o
6.4. Transformaci´ n r´ pida de Fourier
oa
´
6.5. Algebra lineal . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

1

circunscrito. Hagamos s = 1 (a + b + c). Se satisfacen
2
las siguientes relaciones.
c2 = a2 + b2 − 2ab cos C
a = b cos C + c cos B
a
b
c
= sen B = sen C
sen A
1
area = 2 chc = 1 ab sen C
2
= rs =

abc
4R

=
s( s − a)(...