03/04/2025 13:54:28

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2724. Функции и подпрограммы 39

Ограничения: время – 200ms/500ms, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Напишите функции CountingSort и , псевдокод для которых написан ниже.

int n;
...
int a[n],b[n];
...
CountingSort(a,n,-100,100,b);
...

В качестве решения необходимо отправлять файл, содержащий только определение функции!

Алгоритм CountingSort( $A, l, u$ )
// Входные данные: Массив $A[0...n-1]$ целых чисел от $l$ до $u$
// Выходные данные: Массив $B[0...n-1]$ элементов $A$
// отсортированных в неубывающем порядке
for $i in [0...u-l]$ do
$quad C[i] larr 0$
for $i in [0...n-1]$ do
$quad C[A[i]-l] larr C[A[i]-l]+1$
$S larr "PartialSum"(C)$
for $i in [n-1...0]$ do
$quad j larr A[i]-l$
$quad S[j] larr S[j]-1$
$quad B[S[j]] larr A[i]$
return $B$

Алгоритм PartialSum( $A$ )
// Входные данные: Массив $A[0...n-1]$
// Выходные данные: Массив частичных сумм $S[0...n-1]$
$S[0] larr A[0]$
for $i in [1..n-1]$ do
$quad S[i] larr S[i-1]+A[i]$