5201. К-ый минимум

Напишите программу, которая находит k-ое в возрастающем порядке число в массиве A = < a₁, a₂, ..., a_n >.

Массив A задается с помощью полинома P(x) = 132x³ + 77x² + 1345x + 1577: a_i = P(i) mod 1743.

Вход. Два натуральных числа n и k (1 ≤ k ≤ n ≤ 50000).

Выход. Выведите k-ое в число в отсортированном массиве А.

Пример входа	Пример выхода
10 1	402

РЕШЕНИЕ

поиск

Анализ алгоритма

Сгенерируем все числа a₁, a₂, ..., a_n в массиве a. Функция nth_element за линейное время переставляет числа массива a таким образом, чтобы на k-ом месте находился k-ый по возрастанию элемент. При этом все элементы, стоящие слева от a[k], будут не больше a[k], а элементы, стоящие справа от a[k], будут не меньше a[k].

Для нахождения ответа следует вывести значение a[k].

Реализация алгоритма

Значения полинома в точках храним в целочисленном массиве a длины MAX.

#define MOD 1743

#define MAX 50001

int a[MAX];

Вычисление полинома в точке.

long long P(long long x)

{

return (((132 * x) % MOD * (x * x) % MOD) % MOD +

((77 * x) % MOD * x) % MOD + (1345 * x) % MOD + 1577) % MOD;

}

Основная часть программы. Читаем входные данные. Генерируем значения массива А.

scanf("%d %d",&n,&k);

for(i = 1; i <= n; i++)

a[i] = P(i);

Разделяем элементы массива таким образом, что k - ый элемент становится на k - ое место. Элементы, меньшие k - ого, располагаются раньше его, а большие – позже.

nth_element(a+1, a+k, a+n+1);

Выводим ответ.

printf("%d\n",a[k]);

Реализация алгоритма – k-ый элемент O(n)

#include <cstdio>

#include <algorithm>

#define MOD 1743

#define MAX 50001

using namespace std;

int i, n, k;

int m[MAX];

long long P(long long x)

{

return (((132 * x) % MOD * (x * x) % MOD) % MOD +

((77 * x) % MOD * x) % MOD + (1345 * x) % MOD + 1577) % MOD;

}

int Partition(int left, int right)

{

int x = m[left], i = left - 1, j = right + 1;

while (1)

{

do j--; while (m[j] > x);

do i++; while (m[i] < x);

if (i < j) swap(m[i], m[j]); else return j;

}

}

int kth(int k, int left, int right)

{

if (left == right) return m[left];

int pos = Partition(left, right);

if (k <= pos) return kth(k, left, pos);

else return kth(k, pos + 1, right);

}

int main(void)

{

scanf("%d %d", &n, &k);

for (i = 1; i <= n; i++)

m[i] = P(i);

printf("%d\n", kth(k, 1, n));

return 0;

}

Java реализация

import java.util.*;

public class Main

{

public static final long MOD = 1743;

static long P(long x)

{

x = x % MOD;

return (((132 * x) % MOD * (x * x) % MOD) % MOD +

((77 * x) % MOD * x) % MOD + (1345 * x) % MOD + 1577) % MOD;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int k = con.nextInt();

long a[] = new long[n+1];

for(int i = 1; i <= n; i++)

a[i] = P(i);

Arrays.sort(a,1,n+1);

System.out.println(a[k]);

con.close();

}

}