Mejora del procedimiento de preguntas y respuestas preliminares de la Olimpiada de Informática de 2008

5. Mejorar el programa (3 puntos por los primeros 6 espacios, 2 puntos por los últimos 5 espacios, *** 28 puntos).

1. (Encuentra el k-ésimo número más grande) Dada una secuencia entera positiva desordenada de longitud 100000, otro número n (1

Var a:array[1 ..1000000];

n, m, ans: entero;

Intercambio de procesos (var a, b: entero);

var t: entero;

Iniciar

Si (a & lt& gtb) entonces iniciar

t:= a:= b:= t;

p><; p>Fin;

Fin;

Función FindKth(izquierda, derecha, n:entero):entero;

Var tmp, valor, I, j: entero;

Inicio

Si izquierda=derecha entonces salir(izquierda);

tmp:=random(derecha-izquierda)+izquierda;

intercambiar(a[tmp], a[izquierda]);

Valor:=____①_____

i:=izquierda; j:=derecha;

Y I & ltj hago

Empezar

mientras (I & ltj) y (_ _ _ _ _ _ _ _②_ _ _ _ _ _ _) hacen dec (j);

Si & lt entonces comienzo

a:= a[j]; inc(一);

Finalizar else break

while(I& ltj) y (_ _ _③_ _)hacen Inc(I);

Si I & ltentonces comencemos

a[j ]:= a[I]; session;

Fin else break

Fin;

____④_____

Si I& ltn entonces comienza inc(i); _ _ _ _ _ _ _⑤_ _ _ _ _); fin;

si & gtn entonces comienza dec(j); ; fin;

Salir (1);

Fin;

var i: entero; /p>

Aleatorizar;

ans:=-1;

m:= 5;

Para i :=1 to m do

Leer (a[I]);

Leer (n);

ans:=FindKth(1, m, n);

writeln(a[ans]);

Fin.

2. (Números en la matriz) Existe una matriz A de n*n (1≤n≤5000), para 1 ≤ I < n, 1≤j≤n, a[i, j ] <a[i+1,j] a[j,I]<a[j,i+1]. Es decir, para dos elementos adyacentes en la matriz, el elemento de la derecha debe ser mayor que el elemento. a la izquierda. Para dos elementos adyacentes, el elemento inferior debe ser más grande que el elemento superior. Dado un número K en la matriz A, encuentre la fila y la columna donde se encuentra K (nota: los datos de entrada garantizan que los números en la matriz sean diferentes).

Definir variables

n, k, respuestax, respuesta: entero

Respuesta: Entero en matriz [1..5000,1..5000];

Posición de búsqueda del proceso;

Var I, j: entero;

Inicio

I:= n;

mientras j>0 comienza

si a[n,j]<k entonces interrumpe;

décima sesión;

Fin;

______①_________

Y a[i, j]& lt;& gtk do

Iniciar

mientras ( ___②_____) y (i & gt1) hacer dec(一);

mientras (___③_____) y (j & lt= n)hacer Inc(j);

End;

p>

_______④________

_______⑤________

Fin;

var i, j: entero;

Inicio

Leer como (n);

Para i:=1 a n hacer

Para j:=1 a n hacer

leer(a[i , j]) ;

Leer (k);

BuscarKPosition

writeln(answerx, '', answery);