Grupo de Promoción de Semifinales de la Liga Olimpiada Nacional de Informática (NOIP2007)
Beca
(scholar.pas/c/cpp). )
p>Descripción del problema
Una escuela primaria recibió recientemente una donación y planea usar parte de ella para otorgar becas a los cinco mejores estudiantes con desempeño académico sobresaliente. Al final del semestre, cada estudiante tiene tres cursos: chino, matemáticas e inglés. 1. Ordene por puntuación total de mayor a menor. Si dos estudiantes tienen la misma puntuación total, se ordenarán de mayor a menor en las puntuaciones del idioma chino. Si las puntuaciones totales y las puntuaciones en chino de dos estudiantes son iguales, entonces el estudiante con el menor número de estudiantes ocupará el primer lugar, de modo que la clasificación de cada estudiante sea única.
Tarea: primero, calcule la puntuación total en función de las puntuaciones de entrada de los tres cursos, luego ordene de acuerdo con las reglas anteriores y, finalmente, genere la identificación del estudiante y la puntuación total de los cinco mejores estudiantes en la clasificación. orden. Tenga en cuenta que entre los 5 mejores estudiantes, la beca de cada estudiante es diferente, por lo que debe clasificar estrictamente de acuerdo con las reglas anteriores. Por ejemplo, en una respuesta correcta, si los datos de salida de las dos primeras líneas (cada línea genera dos números: número de estudiante y puntuación total) es:
7 279
5 279
El significado de estas dos líneas de datos es que los números de estudiantes de los dos estudiantes con las puntuaciones totales más altas son el No. 7 y el No. 5. Los dos estudiantes obtuvieron una puntuación total de 279 (la puntuación total es igual a la suma de chino, matemáticas e inglés), pero el estudiante con el número 7 obtuvo una puntuación más alta en chino. Si sus dos primeros datos de salida son:
5 279
7 279
entonces se tratará como un error de salida y no se calificará.
Entrada
El archivo de entrada Scholar.in contiene n+1 líneas:
La primera línea es un número entero positivo n, que indica el número de personas que participan en la selección en la escuela.
Desde la línea 2 hasta la línea n+1, cada línea tiene tres números, separados por espacios, y cada número está entre 0 y 100. Los tres números seguidos de Z representan a su vez las puntuaciones de chino, matemáticas e inglés del estudiante. El número de estudiante de cada estudiante se numera l ~ n de acuerdo con la secuencia de entrada (que es exactamente el número de fila de los datos de entrada menos 1).
Todos los datos facilitados son correctos, por lo que no es necesario realizar ninguna comprobación.
Salida
El archivo de salida Scholar.out*** tiene cinco líneas. Cada línea tiene dos números enteros positivos separados por espacios, que a su vez representan los números de los estudiantes y el número total de estudiantes. punto de los cinco mejores estudiantes.
Muestra de entrada y salida 1
Académicos
Seis
90 67 80
87 66 91
p>
78 89 91
88 99 77
67 89 64
78 89 98
Académico completo
p>6 265
4 264
3 258
2 244
1 237.
Muestra de entradas y salidas 2
Académica. En
ocho
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
Erudito. Exterior
8 265
2 264
6 264
1 258
5 258
Restricciones
Cumple el 50% de los datos: la puntuación total de cada alumno es diferente. Se cumple el 100% de los datos: 6
2. Agrupación de souvenirs
(group.pas/c/cpp)
Descripción del título
Se acerca el día de Año Nuevo y el sindicato de estudiantes Lele será el encargado de distribuir souvenirs de la fiesta de Año Nuevo. Para equilibrar relativamente el valor de los souvenirs obtenidos por los estudiantes que asistieron a la fiesta, necesita agrupar los souvenirs comprados por precio, pero cada grupo solo puede incluir como máximo dos souvenirs, y la suma de los precios de cada grupo no puede exceder un número entero dado.
Para garantizar que todos los souvenirs se distribuyan en el menor tiempo posible, Lele espera que el número de personas en el grupo sea mínimo.
Su tarea es escribir un programa para encontrar el menor número de grupos entre todos los esquemas de agrupación y generar el menor número de grupos.
Entrada
El archivo de entrada group.in contiene n+2 líneas:
La primera línea contiene un número entero w, que es el límite superior de la suma de los precios de cada grupo de souvenirs. Ojo = La segunda línea es un número entero n, que representa el número total de souvenirs comprados g.
La línea 3-n+2 contiene un número entero positivo pi (5
Salida
El archivo de salida group.out tiene solo una línea → y contiene un número entero. El número mínimo de grupos en ep es igual
Muestra de entrada-salida
grupo en
100
Nueve
90
20
20
30
50
60
70
80
90
Exterior
Seis
Limitado
50. % de los datos satisface: 1
100% de los datos satisface: 1
3. La fuga del vigilante nocturno
(escape.pas/c/ cpp)
Descripción del problema
El cazador de demonios You Qiang'an es ambicioso. Traicionó a los elfos de la noche y llevó a los Nagas escondidos en las profundidades del mar a rebelarse. Asediados y asesinados, varados. En una isla desierta, para matar al Vigilante, Illidan comenzó a lanzar un hechizo en la isla desierta, que pronto se hundiría. Matar: La velocidad de carrera del Vigilante es de 17 m/s. Es imposible escapar de la isla desierta en este momento. Afortunadamente, el Vigilante tiene un hechizo de parpadeo que puede moverse 60 m en 1 segundo, pero cada uso del hechizo de parpadeo consume 10 maná. La tasa de recuperación de maná del Vigilante es de 4 puntos por segundo, que solo se puede restaurar en estado de reposo.
Ahora sabemos el valor inicial de la magia del Vigilante, m, y la distancia s desde su posición inicial hasta la salida de la isla y el tiempo t cuando la isla se hunde. ayude al observador a calcular cómo escapar de la isla desierta en el menor tiempo. De lo contrario, genere la distancia más larga que el observador puede recorrer en el tiempo restante. Nota: El observador corre, parpadea o descansa en segundos y la duración de cada actividad es. en metros.
El archivo de entrada escape.in tiene solo una línea. Contiene tres números enteros no negativos m, s, t, separados por espacios
Salida
1 línea La cadena es "Sí" o "No" (distingue entre mayúsculas y minúsculas), es decir, si el observador puede escapar de la isla desierta. /p>
La segunda línea contiene un número entero y la primera línea es "Sí" (distingue entre mayúsculas y minúsculas. Representa el tiempo más corto para escapar de la isla desierta).
El primer comportamiento es "No". " (distingue entre mayúsculas y minúsculas) indica la distancia más larga que puede viajar el observador.
Muestras de entrada y salida 1<. /p>
Escape. in
39 200 4
Escape
No
197
Muestra de entrada y salida 2
Escape en
. 36 255 10
Escape
Sí
Seis
Restricciones
El 30% de los datos cumple: 1
El 50% de los datos cumple: 1
El 100% de los datos cumple: 1
4. Problema de las Torres Gemelas de Hanoi
hanoi.pas/c/cpp
Descripción del problema
Dadas tres columnas delgadas A, B y C. Hay 2n discos en la columna A con espacios en el medio. * * * Hay n tamaños diferentes, cada uno con dos discos idénticos. Tenga en cuenta que los dos discos son indistinguibles (la imagen siguiente muestra el caso de n=3). Ahora necesitamos mover estos discos nacionales al pilar C y colocarlos en el pilar B para almacenamiento temporal mientras los movemos.
Requisitos:
(1) Solo se puede mover un disco a la vez;
(2) Los discos de las tres columnas delgadas A, B y C deben almacenarse en el orden de pequeño en la parte superior y grande en la parte inferior;
Tarea: suponga que An es el número mínimo de movimientos necesarios para que 2n discos completen la tarea anterior. Para la entrada n, salida uno.
Entrada
El archivo de entrada hanoi.in es un entero positivo n, lo que significa que hay 2n discos en la columna A.
Salida
El archivo de salida hAnoi.out tiene solo una línea, que contiene un número entero positivo, que es el número mínimo de movimientos necesarios para completar la tarea anterior.
Muestra de entrada y salida 1
Hanói
1
Hanói, completada
2
Muestras de entrada y salida 2
Hanói
2
Hanói, completado
Seis
Limitaciones
Para el 50% de los datos, 1
Para el 100% de los datos, 1
Señalar
Intentar establecer la relación entre An y An-1 relación recursiva entre.
Como no hay ningún informe de resolución de problemas en línea, yo mismo escribí uno. Consulte:
Informe de resolución de problemas de Noip2007
-por o0rqyoo (ese soy yo~ ~ ~ ~)
La primera pregunta: Académico
Esta pregunta no es nada especial. Principalmente pone a prueba la competencia de todos en programación. a:=x de la matriz bidimensional disponible a;
a:= x+y+z;
Fin;
Para i:=1 a n -1 hacer
para j:=i+1 a n hacer
si (a & lta) o ((a=a) y (a & lta)) o ( ( a[i, 1]> a[j, 1]) y (a=a) y (a=a)) luego
Iniciar
swap(a[i , 1], a[j, 1]);
Intercambiar (a, a
Intercambiar (a, a)
Fin ;
para i:=1 a 5 hacer
writeln(a[i, 1], '', a
Cerrar (entrada); p>
Cerrar(salida);
Fin.
Pregunta 2: Grupo
Esta pregunta tampoco es difícil. Mucha gente piensa que es DP, pero en realidad es una simulación simple. Ordene primero (las burbujas también son aceptables), luego use dos punteros para controlar los subíndices, agregando el primero (datos correspondientes al puntero de la cabeza) y el último (datos correspondientes al puntero de la cola) a la vez. Si es mayor que w, el contador se incrementa en 1 y el puntero principal se mueve hacia atrás; si la relación es menor o igual a w, el contador se incrementa en 1 y el puntero principal se mueve hacia atrás 1 bit; El puntero de cola se mueve hacia adelante 1 bit. Finalmente genera el resultado del contador.
El proceso es el siguiente:
Grupo de programas (entrada, salida);
Definir variables
Respuesta: Matriz [1. .30000 ] entero;
w, n, I, j, s: entero;
Procedimiento qsort(h, t: entero);
Definir variables
p, I, j: entero;
Inicio
I:= h
j:= t;
p:= a;
Repetir
mientras(a[j]& gt;p) y (j>I)hacen j:= j-1;
p>Si j & gt i entonces
Inicio
a:= a[j];
I:= I+1;
p>
mientras (a & lt; p) y (i & ltj)hacen I:= I+1;
Si i & ltentonces j
Inicio
p>a[j]:= a;
j:= j-1
Fin
Fin
Hasta I = j;
a:= p;
I:= I+1;
j:= j-1;
Si i & ltt entonces qsort(i, t);
Si j & gth entonces qsort(h, j);
Inicio
Asignación (entrada, 'grupo. en'
Asignación (salida, 'grupo. salida'); p>Restablecer (entrada);
Reescribir(salida);
readln(w);
readln(n); Para i:=1 an n haga readln(a);
qsort(1, n);
I:= 1;
j:= n ;
s:= 0;
Y i & lt=j hago
Empezar
Si i=j, entonces
Inicio
s:= s+1;
Interrupción
Fin
Si a+a[ j]<= w Luego
Iniciar
I:= I+1;
j:= j-1;
s:= s+ 1;
Fin;
Si a+a[j]& gt; entonces w
Inicio
s := s+ 1;
j:= j-1;
Fin;
Fin;
Escribir contenido;
Cerrar(entrada);
Cerrar(salida);
Fin.
Pregunta 3: Escape
No es necesario utilizar DP, utilice simulación. Debido a que cada movimiento consume 10 maná y 4 por segundo, cada movimiento también consume 1 segundo (algunas personas no prestan atención a esto). Después de la comparación, sabemos que usar magia para movernos es más rápido que correr, por lo que intentamos usar magia para determinar primero "sí" y "no", y luego encontrar los datos correspondientes.
El proceso es el siguiente:
Escape del programa (entrada, salida);
Definir variables
a, b: matriz [ 0 ..longint's 10000];
m, s, t, I, j: longint;
función max(a, b, c: longint): longint;
Definir variables
k:longint;
Inicio
Si a & gtb entonces k:=a en caso contrario k:= b;
Si k & ltc entonces k:= c;
max:= k;
Fin;
Inicio
Asignación (entrada, 'escape. in');
Asignación (salida, 'escape. out');
Restablecer (entrada). salida);
readln(m, s, t);
Para i:=0 a 10000,
Inicie
a [I]:= 0;
b[I]:= 0;
Fin;
para i:=1 para t hacer
Inicio
Para j:=0 a 9, haga
Inicio
b[j]:=max(a[j]+17, a [j+4], 0);
Si b[j]>=s entonces
Iniciar
writeln("Sí"); p>
writeln(1);
Cerrar (entrada);
Cerrar (salida);
Detener; Fin;
Fin;
Para j:=10 a m hacer
Inicio
b[j]:=max (a [j]+17, a[j+4], a[j-10]+60);
Si b[j]>=s entonces
Iniciar
writeln("sí");
writeln(uno);
Cerrar(entrada);
Cerrar(salida);
Detener;
Fin;
Fin;
a:= b;
Fin;
writeln("No");
writeln(a[m]);
Cerrar(entrada);
Cerrar(salida));
Fin.
Problema 4: Hanoi
Problema típico de la Torre de Hanoi. Simplemente multiplica por dos. No necesitamos deducir la relación recursiva entre An y An-1, solo necesitamos deducir la relación entre An y n. La relación de la torre única de Hanno es: an = 2 n-1. Multiplicar por 2 da: an = 2 * (2 n)-1. Simplificando, obtenemos: an = 2 (n+1)-2. Simplemente use uno de alta precisión.
El proceso es el siguiente:
Programar Hanoi (entrada, salida);
Definir variables
n, I, j: enteros;
Respuesta: Matriz [1..0 de 100]..9;
Procedimiento ppp (k: entero);
Definir variables
I, j, w, s: entero;
Inicio
a[1]:= 1;
w:= 0;
p>Para i:=1 a k hacer
Para j:=1 a 100 hacer
Inicio
s:= a[j] * 2+w;
a[j]:= s mod 10;
w:= s div 10;
Fin;
Fin;
Inicio
Asignación (entrada, ' Hanoi . in ');
Asignación (salida, ' Hanoi . out ');
p>Restablecer(entrada);
Reescribir(salida);
readln(n);
PPP(n); +1);
Si a[1]>entonces=2
a[1]:=a[1]-2
Otros
Inicio
a[1]:= a[1]+8
a[2]:= a[2]-1; p>Fin;
I:= 100;
Y a[I]= 0 hago I:= I-1;
para j:= I hasta 1 escribir (a[j]);
writeln
Cerrar (entrada
Cerrar