Semifinales de la Liga Olimpiada Nacional de Informática (NOIP2008)
Grupo de divulgación
1 Descripción general del tema
Nombre del tema en chino Número ISBN Clasificación. Vista tridimensional del juego de pases de silla
Nombre del título en inglés isbn asiento bola dibujo
Nombre del archivo ejecutable isbn asiento bola dibujo
Ingrese el nombre del archivo isbn. en asiento.en bola.en dibujo.en
El nombre del archivo de salida esbn.out asiento.fuera bola.fuera dibujo.fu
Límite de tiempo de cada punto de prueba 1 segundo 1 segundo 1 segundo 1 segundo
Número de puntos de prueba 10 10 10 10
La puntuación de cada punto de prueba es 10 10 10 10
Método de comparación Comparación de texto completo Comparación de texto completo Comparación de texto completo Comparación de texto completo
Tipo de pregunta tradicional tradicional tradicional tradicional
2. Enviar nombre del archivo del programa fuente
Para lenguaje pascal isbn.pas asiento.pas ball .pas dibujo.pas
Para lenguaje C isbn.c asiento.c bola.c dibujo.c
Para lenguaje C++ isbn.cpp asiento.cpp bola.cpp dibujo.cpp
3. Comando de compilación (no incluye ningún modificador de optimización)
Para lenguaje Pascal fpc isbn.pas fpc seat.pas fpc ball.pas fpc dibujo.pas
Para lenguaje C gcc –o isbn
isbn.c gcc –o asiento
seat.c gcc –o ball
ball.c gcc –o dibujo
drawing.c
Para lenguaje C++ g++ –o isbn
isbn.cpp g++ –o asiento
seat.cpp g++ – o ball
ball. cpp g++ –o
drawing
drawing.cpp
4. p>El límite superior de memoria en ejecución es 50M 50M 50M 50M
p>Notas:
1. Los nombres de los archivos (nombres de programas y nombres de archivos de entrada y salida) deben estar en minúsculas.
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 1,9 GHz, memoria 512 M. El límite de tiempo anterior prevalecerá según esta configuración.
Cada provincia puede ajustar el límite de tiempo según su configuración específica durante el autotest.
1. Número ISBN
(isbn.pas/c/cpp)
Descripción del problema
Cada libro publicado oficialmente tiene un Número ISBN que le corresponde El código ISBN incluye 9 dígitos, 1 código de identificación y 3 separadores. Su formato prescrito es "x-xxx-xxxxx-x", donde el símbolo "-" es el separador (signo menos del teclado). , el último dígito es el código de identificación, por ejemplo, 0-670-82162-4 es un código ISBN estándar. El primer dígito del código ISBN representa el idioma de publicación del libro, por ejemplo, 0 representa el inglés; los tres dígitos después del primer separador "-" representan la editorial; por ejemplo, 670 representa los cinco dígitos después del; segundo separador Representa el número de publicación del libro; el último dígito es el código de identificación.
El código de identificación se calcula de la siguiente manera:
El primer dígito se multiplica por 1 más el segundo dígito se multiplica por 2... y así sucesivamente, use el resultado mod 11, y el resto Ese es el código de identificación. Si el resto es 10, el código de identificación es la letra X mayúscula. Por ejemplo, el código de identificación 4 en el número ISBN 0-670-82162-4 se obtiene de la siguiente manera: multiplica los nueve números 067082162 de izquierda a derecha por 1, 2,...,9 respectivamente, y luego sumalos, es decir, 0×1+6×2+……+2×9=158, y luego toma el resultado 4 de 158 mod 11 como código de identificación.
Su tarea es escribir un programa para determinar si el código de identificación en el número ISBN ingresado es correcto. Si es correcto, simplemente escriba "Correcto"; si es incorrecto, envíe el número ISBN que usted. creo que es el correcto.
Entrada
El archivo de entrada isbn.in tiene solo una línea, que es una secuencia de caracteres que representa el número ISBN de un libro (asegúrese de que la entrada cumpla con los requisitos de formato del ISBN número).
Salida
Muestre el archivo isbn.out*** en una línea. Si el código de identificación del número ISBN ingresado es correcto, envíe "Derecho", en caso contrario, según el. formato especificado, la salida es el número ISBN correcto (incluido el separador "-").
Muestra de entrada y salida 1
isbn.in isbn.out
0-670-82162-4 Derecha
Entrada y salida Ejemplo de muestra 2
isbn.in isbn.out
0-670-82162-0 0-670-82162-4
2 Fila de asientos<. /p>
p>
（seat.pas/c/cpp）
Descripción del problema
Durante la clase, siempre hay algunos estudiantes susurrando con las personas que los rodean. Esto preocupa mucho a la maestra de primaria. Sin embargo, el maestro de la clase Xiaoxue descubrió algunos fenómenos interesantes. Después de que se determinaron los asientos de los estudiantes, solo un número limitado de pares D de estudiantes se susurraban entre sí durante la clase. Los estudiantes se sientan en M filas y N columnas en el aula. La posición del estudiante sentado en la i-ésima fila y j-ésima columna es (i, j). , a K canales horizontales y L canales verticales. Entonces, la inteligente Xiaoxue pensó en una manera de reducir el problema de los estudiantes que susurraban durante la clase: planeó reorganizar las mesas y sillas y cambiar la posición del pasillo entre los escritorios y las sillas de los estudiantes, porque si un pasillo separaba a dos estudiantes que se susurrarían entre sí, luego no se susurrarían entre sí.
Por favor, ayuda a escribir un programa para Xiaoxue y ofrece el mejor plan de división de canales. Según este esquema, el número de parejas de estudiantes que susurran entre sí durante la clase es el menor.
Entrada
La primera línea del archivo de entrada seat.in contiene 5 números enteros separados por espacios, a saber, M, N, K, L, D (2<= N, M< =1000, 0<=K La siguiente línea D, cada línea tiene 4 números enteros separados por espacios. Los 4 números enteros Xi, Yi, Pi, Qi en la línea i-ésima representan la posición sentada (Xi, Yi) y (Dos compañeros de clase. Pi, Qi) se susurrarán entre sí (ingrese para asegurarse de que estén uno al lado del otro por delante y por detrás o de izquierda a derecha). Los datos de entrada garantizan la unicidad de la solución óptima. Salida El archivo de salida seat.out*** tiene dos líneas. La primera línea contiene K enteros, a1a2...aK, lo que significa que entre la fila a1 y la fila a1+1, entre la fila a2 y la fila a2+1,..., la fila aK y los canales deben ser abierto entre líneas aK+1, donde ai< ai+1, y cada dos números enteros están separados por espacios (sin espacios al final de la línea). La segunda línea contiene L enteros, b1b2...bk, lo que significa entre la columna b1 y la columna b1+1, entre la columna b2 y la columna b2+1, ..., y la suma de la columna bL Se debe abrir un canal entre las columnas bL+1, donde bi Ejemplos de entrada y salida seat.in seat.out 4 5 1 2 3 4 2 4 3 2 3 3 3 2 5 2 4 2 2 4 Explicación de muestra de entrada y salida * * ※ ※ + + 1 2 3 4 5 Los símbolos *, ※, + están marcados en la imagen de arriba Las posiciones de tres pares de estudiantes que se susurran entre sí. Las posiciones de las tres líneas gruesas en la imagen representan los canales. El plan de división de canales que se muestra en la imagen es el único mejor plan. 3. Juego de pases (ball.pas/c/cpp) Descripción del problema En la clase de educación física, el profesor de Xiaoman. A menudo juega con sus compañeros de clase. Esta vez, la maestra llevó a los alumnos a jugar juntos un juego de pases. Las reglas del juego son las siguientes: n los alumnos se paran en círculo y uno de ellos sostiene una pelota en la mano. Cuando el profesor toca el silbato, comienza a pasar la pelota. Pasarse el balón a uno de los dos alumnos de izquierda y derecha (ya sea izquierda o derecha), cuando el profesor vuelve a tocar el silbato, el pase se detiene. En este momento, el alumno que sostiene el balón pero no lo pasa. out es el perdedor y tiene que realizar un espectáculo para todos. El inteligente Xiaoman planteó una pregunta interesante: ¿cuántos métodos de pase diferentes pueden hacer que el balón pasado de las manos de Xiaoman regrese a las manos de Xiaoman después de pasarlo m veces? Dos métodos de pase se consideran diferentes si y sólo si las secuencias de estudiantes que reciben el balón en los dos métodos son diferentes. Por ejemplo, hay tres compañeros de clase No. 1, No. 2 y No. 3, y asumiendo que Xiaoman es el No. 1. La pelota se pasa a Xiaoman tres veces de las siguientes maneras: 1->2->3- >1 y 1->3. ->2->1, ***2 tipos. Entrada Archivo de entrada ball.in*** una línea, hay dos números enteros n, m separados por espacios (3<=n<=30, 1<=m < =30). Salida El archivo de salida ball.out*** tiene una línea, con un número entero que representa el número de métodos que cumplen con el significado de la pregunta. Muestras de entrada y salida ball.in ball.out 3 3 2 Restricciones 40 % de los datos satisfacen: 3<=n<=30, 1<=m<=20 100% de los datos satisfacen: 3<=n<=30, 1<=m<=30 4. Dibujo tridimensional （drawing.pas/c/cpp） Descripción del problema Xiaoyuan es un niño inteligente , a menudo les dice a los niños que lo rodean algo que cree que es interesante. Recientemente, va a explicar diagramas tridimensionales a los niños y le pide que le ayude a dibujar diagramas tridimensionales. Xiaoyuan tiene un área rectangular con un área de m*n. Hay m*n cuadrículas con una longitud lateral de 1. Hay algunos Jims del mismo tamaño apilados en cada cuadrícula (la longitud). , ancho y alto de los bloques de construcción). Todos son 1), a Xiaoyuan le gustaría que imprimiera el diagrama tridimensional de estas cuadrículas. Definimos cada bloque de construcción con el siguiente formato, no volteamos ni rotamos y solo se colocaremos estrictamente en esta forma: +---+ / / | Alto +---+ | + |/ Ancho +---+ p > Longitud Cada vértice está representado por un signo más '+', la longitud está representada por 3 "-", el ancho está representado por 1 "/" y la altura está representada por dos " |" expresar. Los códigos ASCII de los caracteres '+' '-''/' '|' son 43, 45, 47 y 124 respectivamente. El carácter '.' (código ASCII 46) debe aparecer como fondo, es decir, la parte en blanco del estereograma debe reemplazarse con '.'. El método de dibujo del diagrama tridimensional es el siguiente: Si dos bloques de construcción son adyacentes a la izquierda y a la derecha, el diagrama es: ..+---+ ---+ ./ / /| +---+---+ | >| | |/. +---+---+.. Si dos bloques de construcción son adyacentes arriba y abajo, la imagen es: ..+---+ ./ /| +---+ | p>|/| +--+| -+.. Si dos bloques de construcción están adyacentes entre sí, como se muestra en la imagen: ….+---+ …/ /| ..+---+ ./ /| + +---+ |/. >| | +.. |/ … +---+…. En el diagrama tridimensional, la definición se encuentra en la cuadrícula (m, 1) (es decir, la cuadrícula en la m-ésima fila y columna 1) de abajo hacia arriba El vértice inferior izquierdo del primer bloque de construcción (es decir, el bloque de construcción inferior) es la esquina inferior izquierda punto de toda la imagen. Entrada La primera línea del archivo de entrada dibujo.in contiene dos números enteros myn separados por espacios, lo que indica que hay m*n cuadrículas (1<=m, n <=50). Las siguientes m filas son una matriz m*n. Cada fila tiene n números enteros separados por espacios. El número entero en la i-ésima fila y la j-ésima columna representa la i-ésima fila y la j-ésima. columna Cuántos bloques de construcción están apilados en la cuadrícula (1 <= el número de bloques de construcción en cada cuadrícula <= 100). Salida El archivo de salida dibujo.out contiene el diagrama tridimensional requerido por la pregunta, que es una matriz de caracteres con K filas y L columnas, donde K y L indican que Se requieren al menos K filas y L columnas para presionar. Especifica el estereograma de salida. Muestras de entrada y salida drawing.in drawings.out 3 4 2 2 1 2 2 2 1 1 3 2 1 2 ......+---+---+...+---+ ..+- --+ / /|../ /| ./ /|-+---+ |.+---+ +---+ |/ /| +-| | + | +---+ |/+---+ |/| +---+---+ |/+---+ |/| + | p>| |/ | |/| +.. +---+---+---+---+ |/... | | |... +---+---+ ...... Pregunta 1 Programa Gy Const Nombre='isbn'; p> Var A,B:Cadena; Entrada de procedimiento Comenzar Asignar(Entrada) ,Nombre+' .in');Reset(Entrada); Assign(Salida,Nombre+'.out');Reescritura(Salida); Readln(A); p> Fin; Procedimiento principal Var i,j,k:Longint Comenzar j: =0; k:=0; Para i:=1 a Longitud(A)-1 Si A:=1; :=1 a M hacer Para j:=1 a N hacer F Close(Input); Cerrar(Salida ); Fin Comenzar Entrada Principal Oup; /p> Fin. Pregunta 4 Programa Gy Const Trabajo='dibujo'; p> Tipo Rec=Registro X,Y:longint Fin Arr=Array[1; .. 20000] de Longint; Var A:Array[1..300,1..300] de Longint N,M, MaxN, MaxM:Longint; B:Array[1..1000,1..1000]de Char Entrada de procedimiento Var i, j: Entero largo; Comenzar Asignar(Entrada,Trabajo+'.in');Reset(Entrada Asignar(Salida,Trabajo+'.salida); ') ;Reescribir(Salida); Leer(n,m Para i:=1 a N p> Para j:=1 a M haga Read(a[n+1-i,j] MaxN:=0;MaxM:=0); Para i:=1 a N haga Para j:=1 a M haga Comenzar Si 2*i +4*j+1>MaxM entonces MaxM:=2*i+4*j+1; Si (2*i+3*a[i,j]+1>MaxN) entonces Maxn :=2*i+3*a[i,j]+1; Fin Para i:=1 a MaxN hacer Para j :=1 a MaxM hacer B[i,j]:='.'; Fin Procedimiento principal Comenzar Para i:=N hasta 1 hacer Para j:=1 a M hacer Para k:=1 a A[i,j] hacer Comenzar Y:=2*i+4*j-5; X:=2*i+3*k-4; B[x,y]:='+' B[x,y+1]:='; -'; B[x,y+2]:='-' B[x,y+3]:='-'; p>B[x,y+4]:='+'; B[x+1,y]:='|'; y+1]:=' '; B[x+1,y+2]:=' '; ' '; B[x+1,y+4]:='|'; B[x+1,y+5]:='/'; /p> B[x+2,y]:='|'; B[x+2,y+1]:=' '; [x+2,y+2]:=' '; B[x+2,y+3]:=' '; +4]:='|'; B[x+2,y+5]:=' '; B[x+2,y+6]:= '+'; B[x+3,y]:='+'; B[x+3,y+1]:='-'; p> p> B[x+3,y+2]:='-' B[x+3,y+3]:='-'; /p> B[x+3,y+4]:='+'; B[x+3,y+5]:=' B[x+ 3,y+6]:='|'; B[x+4,y+1]:='/'; 4,y+ 2]:=''; B[x+4,y+3]:='' B[x+4,y+4]: =' ' ; B[x+4,y+5]:='/' B[x+4,y+6]:='|'; B[x+5,y+2]:='+' B[x+5,y+3]:='-'; B[x+5,y+4]:='-'; B[x+5,y+5]:='-'; [x+ 5,y+6]:='+'; Fin; Fin Procedimiento arriba; i, j:Longint; Comenzar Para i:=MaxN hasta 1 hacer Comenzar Para j:=1 a MaxM haga Escribir(b[i,j]); p>Fin; Cerrar(Entrada); Cerrar(Salida); p>Inp; Principal; Oup; Fin Probado todos los pares (byte a byte)