Semifinales de NOIP2010 (Grupo de Mejoramiento Pascal)
Grupo de Mejoramiento de Semifinales de la Liga Olimpiada Nacional de Informática (NOIP2010)
Página 1*** Página 7
Semifinales de la Liga Olimpiada Nacional de Informática (NOIP2010)
Grupo de mejora (Los jugadores deben leer atentamente el contenido de esta página)
1. Descripción general del tema
Título en chino: traducción automática: Turtle Chess encarceló a criminales y desvió agua a la ciudad
Título en inglés y nombre del subdirectorio traducen el flujo de la prisión de tortugas
Nombre del archivo ejecutable traducir flujo prisión tortuga
Nombre del archivo de entrada traducir.in tortoise.in prisión.en flujo.in
Nombre del archivo de salida traducir.out tortuga.fuera prisión.flujo salida. out
El límite de tiempo de cada punto de prueba es 1 segundo 1 segundo 1 segundo 1 segundo
El número de puntos de prueba es 10 10 10 10
La puntuación de cada punto de prueba es 10 10 10 10
Hay archivos de muestra adjuntos disponibles
Método de comparación de resultados comparación de texto completo (filtrado de espacios al final de las líneas y retornos de carro al final de el texto)
Tipo de pregunta tradicional tradicional tradicional tradicional
2. Envíe el nombre del archivo del programa fuente
Para lenguaje Pascal traducir.pas tortoise.pas prision.pas flow.pas
Para lenguaje C traducir.c tortoise.c prision.c flow.c
Para lenguaje C++ traducir.cpp tortuga.cpp prisión.cpp flujo.cpp
3. Comando de compilación (sin ningún modificador de optimización)
Para lenguaje Pascal fpc traducir.pasfpc tortoise.pasfpc prision.pas fpc flow.pas
Para lenguaje C
gcc -o traducir
translate.c -lm
gcc -o tortuga
tortuga.c -lm
gcc -o prisión
prison.c -lm
gcc -o flow
flow.c -lm
Para lenguaje C++ g++ -o traducir< / p>
translate.cpp -lm
g++ -o tortuga
tortoise.cpp -lm
g++ -o prisión
prison.cpp -lm
g++ -o flow
flow.cpp -lm
Cuatro. Límite de memoria en ejecución Límite superior de memoria 128M 128M 128M 128M
Notas:
1. Los nombres de los archivos (nombres de programas y nombres de archivos de entrada y salida) deben estar en minúsculas inglesas.
2. El tipo de valor de retorno de la función main() en C/C++ debe ser int, y el valor de retorno cuando el programa finaliza normalmente debe ser 0.
3. La configuración de la máquina utilizada en la evaluación unificada nacional es: CPU P4 3,0 GHz, memoria 1G. El límite de tiempo anterior está sujeto a esta configuración.
Cada provincia puede ajustar el límite de tiempo según su configuración específica durante el autotest.
Cambio de página
Grupo de mejora semifinal de la Liga Olimpiada Nacional de Informática (NOIP2010)
Página 2*** 7 páginas
1 ． Traducción automática
(translate.pas/c/cpp)
Descripción del problema
Xiaochen tiene un software de traducción automática instalado en su computadora, que usa con frecuencia. para traducir artículos en inglés.
El principio de este software de traducción es muy simple: simplemente reemplaza cada palabra en inglés con su correspondiente significado en chino de principio a fin.
Para cada palabra en inglés, el software primero buscará el significado chino de la palabra en la memoria. Si existe en la memoria, el software lo usará para traducir; si no existe en la memoria, el software lo almacenará. en la memoria externa busque en el diccionario, averigüe el significado chino de la palabra y luego tradúzcala, y guarde la palabra y la traducción en la memoria para su posterior búsqueda y traducción.
Supongamos que hay M unidades en la memoria y que cada unidad puede almacenar una palabra y su traducción. Siempre que el software almacene una nueva palabra en la memoria
si el número de palabras actualmente almacenadas en la memoria no excede M?1, el software almacenará la nueva palabra en un espacio no utilizado
Unidad de memoria; si se han almacenado M palabras en la memoria, el software borrará la primera palabra que ingrese a la memoria y liberará la unidad para almacenar nuevas palabras.
Supongamos que la extensión de un artículo en inglés es de N palabras. Dado que este artículo debe traducirse, ¿cuántas veces necesita el software de traducción buscar diccionarios externos? Supongamos que no hay palabras en la memoria antes de que comience la traducción.
Entrada
El nombre del archivo de entrada es Translate.in y el archivo de entrada contiene ***2 líneas. Separe dos números en cada línea con un espacio.
La primera línea contiene dos números enteros positivos M y N, que representan la capacidad de memoria y la longitud del artículo.
La segunda línea contiene N números enteros no negativos. Según el orden del artículo, cada número (el tamaño no supera los 1000) representa una palabra en inglés.
Dos palabras de un artículo son la misma palabra si y sólo si sus correspondientes números enteros no negativos son iguales.
La línea del archivo de salida Translate.out***1 contiene un número entero, que es el número de veces que el software necesita buscar el diccionario.
Muestra de entrada y salida 1
translate.in Translate.out
3 7
1 2 1 5 4 4 1
p>
5
Descripción de la muestra 1 de entrada y salida
Todo el proceso de búsqueda en el diccionario es el siguiente: cada línea representa la traducción de una palabra y el estado de la memoria después de esta traducción está antes de los dos puntos:
Vacío: el estado inicial de la memoria está vacío.
1． 1: Encuentra la palabra 1 y cárgala en la memoria.
2. 1 2: Encuentra la palabra 2 y cárgala en la memoria.
3. 1 2: Palabra 1 encontrada en la memoria.
4. 1 2 5: Encuentra la palabra 5 y cárgala en la memoria.
5. 2 5 4: Busque la palabra 4 y cárguela en la memoria para reemplazar la palabra 1.
6. 2 5 4: La palabra 4 se encuentra en la memoria.
7. 5 4 1: Busque la palabra 1 y cárguela en la memoria para reemplazar la palabra 2.
***Revisé el diccionario 5 veces.
Cambio de página
Grupo de mejora semifinal de la Liga Olimpiada Nacional de Informática (NOIP2010)
Página 3*** 7 páginas
Entrada Muestra de salida 2
translate.in Translate.out
2 10
8 824 11 78 11 78 11 78 8 264
6
Rango de datos
Para el 10% de los datos, M=1 y N≤5.
Para el 100% de los datos, 0≤100, 0≤1000.
2. Ajedrez de tortuga
(tortoise.pas/c/cpp)
Descripción del problema
En el cumpleaños de Xiao Ming, su padre le regaló un ajedrez de tortuga. .
El tablero de ajedrez de las tortugas es una fila de N cuadrículas, con una puntuación (entero no negativo) en cada cuadrícula. El primer cuadrado del tablero de ajedrez es el único punto de partida y el enésimo cuadrado es el punto final. El juego requiere que los jugadores controlen una pieza de ajedrez de tortuga desde el punto inicial hasta el final.
……
1 2 3 4 5……N
Las cartas rastreras M en Turtle Chess se dividen en 4 tipos diferentes (entre las cartas M se no incluye necesariamente los cuatro tipos de tarjetas
, ver ejemplos). Cada tipo de tarjeta está marcado con uno de los cuatro números 1, 2, 3 o 4, que indican el uso de esta tarjeta
Después de la pieza, la pieza de la tortuga avanzará el número correspondiente de cuadrados. En el juego, los jugadores deben seleccionar una carta de rastreo que no se haya usado antes de todas las cartas de rastreo cada vez y controlar las piezas de la tortuga para avanzar el número correspondiente de cuadrículas. Cada carta solo se puede usar una vez.
En el juego, la pieza de ajedrez de la tortuga obtiene automáticamente la puntuación de la cuadrícula inicial, y cada vez que llega a una cuadrícula en el siguiente rastreo, obtiene la puntuación correspondiente a esa cuadrícula.
La puntuación final del juego del jugador es la suma de las puntuaciones de todas las casillas que ha visitado la pieza de ajedrez tortuga desde el punto inicial hasta el final.
Obviamente, el uso de diferentes órdenes de uso de cartas de rastreo dará como resultado diferentes puntuaciones en el juego final. Xiao Ming quiere encontrar un orden de uso de cartas que haga que el juego final obtenga la mayor puntuación.
Ahora, te diré la puntuación de cada cuadrícula en el tablero y todas las cartas de rastreo. ¿Puedes decirle a Xiao Ming cuántos puntos puede obtener como máximo?
Entrada
Ingrese el nombre del archivo tortoise.in. Separe dos números en cada línea del archivo de entrada con un espacio.
Los dos números enteros positivos N y M en la primera línea representan el número de cuadrículas de tablero de ajedrez y el número de cartas que se arrastran, respectivamente.
La línea 2 contiene N enteros no negativos, a1a2
...aN
, donde ai representa la puntuación en la i-ésima cuadrícula del tablero de ajedrez. . Hay M enteros en la tercera línea, b1b2
...bM
, que representan los números en M tarjetas de rastreo.
Ingrese los datos para garantizar que M tarjetas de rastreo se agoten al llegar al punto final, es decir, N?1=∑
M
ib
1
Salida
El nombre del archivo de salida es tortoise.out.
Cambio de página
Grupo de mejora semifinal de la Liga Olimpiada Nacional de Informática (NOIP2010)
Página 4*** 7 páginas
Salida Solo hay 1 línea, 1 número entero, que indica la puntuación máxima que Xiao Ming puede obtener.
Muestra de entrada y salida 1
tortoise.in tortoise.out
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
73
Descripción de la muestra 1 de entrada y salida
Xiao Ming usa tarjetas de rastreo en orden 1, 1 , 3, 1, 2, la puntuación obtenida es 6+114+8+18+17=73. Tenga en cuenta que
Dado que el punto de partida es 1, la puntuación de la primera cuadrícula es 6 automáticamente.
Muestra de entrada y salida 2
tortoise.in tortoise.out
13 8
4 96 10 64 55 13 94 53 5 24 89 8 30
1 1 1 1 1 2 4 1
455
Rango de datos
Para el 30% de los datos allí es 1
≤
N
≤
30, 1
≤
M
≤
12.
Para el 50% de los datos, 1≤N≤120, 1
≤
M
≤
50, y entre los 4 tipos de cartas rastreras, el número de cada tipo de carta no superará
20.
Para el 100% de los datos, 1≤N≤350, 1≤M≤120, y hay 4 tipos de tarjetas de rastreo, el número de cada tipo de tarjeta no
exceder 40; 0 ≤ai≤100, 1≤i≤N; 1≤bi≤4, 1≤i≤M. Los datos de entrada garantizan N?1=
∑
M
ib
1
3. Encarcelar criminales
(prison.pas/c/cpp)
Descripción del problema
La ciudad S tiene actualmente dos cárceles, una prisión tiene a N personas Los criminales están numerados 1 ~N respectivamente. La relación entre ellos es, naturalmente, extremadamente discordante. Muchos delincuentes incluso tienen rencores de larga data entre ellos y los conflictos pueden estallar en cualquier momento si se cumplen condiciones objetivas. Usamos "valor de resentimiento" (un valor entero positivo) para representar el grado de odio entre dos criminales. Cuanto mayor es el valor del resentimiento, mayor es el odio entre los dos criminales y más rencores. Si dos criminales con un valor de agravio de c están encarcelados en la misma prisión, se producirá fricción entre ellos y provocará un conflicto con un impacto de c.
Al final de cada año, la comisaría hará una lista de todos los conflictos ocurridos en la prisión durante el año en orden descendente de impacto,
y luego los reportará al alcalde. de la ciudad S Z. . El alcalde Z, que está ocupado con deberes oficiales, sólo considerará el impacto del primer evento de la lista.
Si el impacto es muy malo, considerará reemplazar al jefe de policía.
Después de un examen detallado de las relaciones conflictivas entre los delincuentes N, el jefe de policía sintió una tremenda presión. Planea redistribuir a los criminales entre las dos prisiones para que cualquier conflicto tenga menos impacto y así mantener su posición. Suponiendo que haya odio entre dos criminales en la misma prisión, definitivamente tendrán fricciones en algún momento cada año. Entonces
¿Cómo se deben distribuir los delincuentes para que el conflicto visto por el alcalde Z tenga el menor impacto? ¿A cuánto asciende este valor mínimo?
Cambio de página
Grupo de mejora semifinal de la Liga Olimpiada Nacional de Informática (NOIP2010)
Página 5*** Página 7
¿Menos?
Entrada
El nombre del archivo de entrada es prision.in. Separe dos números en cada línea del archivo de entrada con un espacio.
La primera línea contiene dos números enteros positivos N y M, que representan respectivamente el número de delincuentes y el número de pares de delincuentes con odio.
Cada una de las siguientes M líneas contiene tres números enteros positivos aj, bj, cj, lo que indica que existe odio entre los criminales aj y bj, y su valor de resentimiento es cj. Los datos garantizan Nba
jj
≤1,0000000001
0≤
jc
, y cada par La combinación criminal aparece sólo una vez
.
Salida
La línea del archivo de salida jail.out***1 es la influencia del evento de conflicto visto por el alcalde Z. Si no ocurrieron conflictos en la prisión durante este año, envíe 0.
Muestras de entrada y salida
prison.in prison.out
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
3512
Descripción de muestra de entrada y salida
El valor del agravio entre delincuentes se muestra en la imagen de la izquierda a continuación. La imagen de la derecha muestra el método de asignación de delincuentes y los eventos de conflicto vistos por el alcalde.
La influencia es 3512 (provocada por los criminales nº 2 y nº 3). Ningún otro método de división será mejor que este método de división.
Rango de datos
Para el 30% de los datos, N≤15.
Para el 70% de los datos, N≤2000 y M≤50000.
Para el 100% de los datos, N≤20000 y M≤100000.
2 1
3 4
1805 6618
2534 3512
12884
28351 2 1
3 4
2534 3512
Cambio de página
Grupo de mejora semifinal de la Liga Olimpiada Nacional de Informática (NOIP2010)
Página 6*** Página 7
4. Desviar agua a la ciudad
(flow.pas/c/cpp)
Descripción del problema
Lago
Desierto
En un país lejano, hay un hermoso lago a un lado y un desierto interminable al otro. Las divisiones administrativas del país son muy especiales. Simplemente forman un rectángulo con N filas y M columnas, como se muestra en la imagen de arriba. Cada cuadrícula representa una ciudad. Todas tienen una altitud.
Para que los residentes puedan beber el agua del lago lo más clara posible, en algunas ciudades se están construyendo instalaciones de conservación de agua. Hay dos tipos de instalaciones de conservación de agua: plantas de almacenamiento de agua y estaciones de suministro de agua. La función de la planta de almacenamiento de agua es utilizar bombas de agua para bombear agua desde el lago hasta el embalse de la ciudad. Por lo tanto, sólo las ciudades de la fila 1 que estén adyacentes a lagos pueden construir plantas de almacenamiento de agua. La función de la estación de suministro de agua es transportar el agua del lago de arriba a abajo a través de tuberías de suministro de agua utilizando diferencias de altura. Por lo tanto, el requisito previo para que una ciudad construya una estación de transmisión de agua es que haya una ciudad adyacente con una altitud mayor que ella y adyacente a la vía pública, y que ya haya construido instalaciones de conservación de agua.
Dado que las ciudades de la enésima fila están cerca del desierto y son zonas áridas del país, cada ciudad debe tener instalaciones de conservación de agua
. Entonces, ¿se puede cumplir este requisito? Si es posible, calcule el número mínimo de plantas de almacenamiento de agua que se construirán; de lo contrario, calcule el número de ciudades en zonas áridas donde es imposible construir instalaciones de conservación de agua.
Entrada
El nombre del archivo de entrada es flow.in. Separe dos números en cada línea del archivo de entrada con un espacio.
La primera línea de entrada son dos números enteros positivos N y M, que representan el tamaño del rectángulo.
Las siguientes N líneas contienen M enteros positivos en cada línea, que representan la altitud de cada ciudad por turno.
Salida
El nombre del archivo de salida es flow.out.
La salida tiene dos líneas. Si se pueden cumplir los requisitos, la primera línea de salida es un número entero 1, y la segunda línea es un número entero, que representa el número mínimo de plantas de almacenamiento de agua que se construirán; si no se pueden cumplir los requisitos, la primera línea de salida es; un número entero 0, la segunda línea es un número entero, que representa cuántas ciudades en áreas áridas no pueden tener instalaciones de conservación de agua.
Muestra de entrada y salida 1
flow.in flow.out
2 5
9 1 5 4 3
8 7 6 1 2
11
Cambio de página
Grupo de mejora semifinal de la Liga Olimpiada Nacional de Informática (NOIP2010)
Página 7*** Página 7
Explicación del Ejemplo 1
Solo necesitas construir una planta de almacenamiento de agua en la ciudad con una altitud de 9 para cumplir con los requisitos.
Muestra de entrada y salida 2
flow.in flow.out
3 6
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
13
Descripción de la muestra 2
Lago
8 4 5 6 4 4
7 3 4 3 3 3
3 2 2 1 1 2
Desierto
En la imagen de arriba, la construcción de plantas de almacenamiento de agua en las tres ciudades marcadas con líneas gruesas puede cumplir con los requisitos. Tomando como fuentes estas tres plantas de almacenamiento de agua
Las estaciones de suministro de agua construidas en zonas áridas están marcadas en tres colores. Por supuesto, el método de construcción puede no ser único.
Rango de datos
Esta pregunta*** tiene 10 datos de prueba. El rango de cada dato se muestra en la siguiente tabla:
¿Pueden los datos de prueba? número cumple los requisitos N M
1 No puede ≤ 10 ≤ 10
2 No puede ≤ 100 ≤ 100
3 No puede ≤ 500 ≤ 500
4 Can= 1 ≤ 10
5 Neng ≤ 10 ≤ 10
6 Neng ≤ 100 ≤ 20
7 Neng ≤ 100 ≤ 50
8 Neng ≤ 100 ≤ 100
9 Neng ≤ 200 ≤ 200
10 Neng ≤ 500 ≤ 500
Para los 10 datos, la altitud de cada ciudad La altura no supera los 10
6
Cambio de página