Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Использование сортировки#23590

Известны значения роста всех учащихся класса. Определите рост учащегося, который при построении учащихся по росту, в порядке возрастания, занимал бы 10-е место при счете от самого высокого ученика.

Нельзя использовать встроенную сортировку.

Входные данные
В первой строке вводится натуральное число N - количество учащихся класса (11 <= N <= 35).
Во второй строке вводятся N целых чисел - рост учащихся.

Выходные данные
Необходимо вывести на экран значение роста учащегося, который бы занимал 10-е место по росту в порядке убывания, при счете от самого высого ученика.

Пример

№	Входные данные	Выходные данные
1	12 148 144 154 145 155 130 157 136 152 130 177 166	136

Квадратичные сортировки

✓ 2 088✗ 2 168300лёгкаяВойти и решать

Сливаемся!#23375

Слияние двух упорядоченных последовательностей чисел в одну упорядоченную основная идея сортировки слиянием. Эта сортировка работает быстро, а слияние двух упорядоченных после-

довательностей легко выполняется в том числе и человеком вручную.

В этой задаче по полученной в результате слияния неубывающей последовательности чисел вам предстоит восстановить две исходных неубывающих последовательности одинакового размера.

Некоторые числа в исходных последовательностях известны, а некоторые заменены знаком "?".

Результат слияния известен полностью. Вам необходимо подставить на место знаков вопроса числа так, чтобы исходные последовательности были неубывающими и при слиянии образовывали заданную результирующую последовательность.

Входные данные

В первой входного файла строке содержится число N количество элементов в каждой из исходных последовательностей. Во второй и третьей строках записано по N чисел и знаков вопроса

содержимое первой и второй последовательности соответственно. В четвертой строке записано 2хN чисел - результат слияния.

Выходные данные

Вывод должен содержать 2 строки по N чисел в каждой: какой-нибудь из вариантов восстановления исходных последовательностей, которые при слиянии дадут тот же результат. Если

в исходных данных в последовательности стояло число, то в выходных данных на том же месте должно стоять то же число.

Ввод	Вывод
2 ? 4 3 ? 1 3 4 5	1 4 3 5

Разбор случаев Сортировка слиянием

—Войти и решать

Гирлянда#22022

Все мы знаем и соблюдаем старую новогоднюю традицию - ставить дома хвойное дерево и украшать его разными предметами.

В семье Бонесов подрастает юный ДжонниБой. Мама учит его различать цвета и считать. Для этого она показывает ДжонниБою гирлянду на елочке и называет цвет лампочки, на которую показывает. Когда все лампочки перечислены, вместо цвета мама говорит “ноль”, чтобы ДжонниБой не запутался.

Юный Бонес еще не очень разобрался, и поэтому вам необходимо помочь ДжонниБою посчитать количество лампочек каждого цвета( цветом называется любая непустая последовательность символов).

Входные данные

Входной файл содержит последовательность строк, оканчивающаяся символом ‘0’(ASCII 48).

Выходные данные

Выходной файл должен содержать какое-то количество строк, отделенных переходом на новую строку. Каждая строка содержит в себе название цвета, символ ‘-‘ , отделенный пробелами с обеих сторон и число повторений его в последовательности. Строки должны выводиться в алфавитном порядке цветов.

Пример 1

Input

red blue red orange red green blue 0

Output

blue - 2

green - 1

orange - 1

red - 3

Пример 2

Input

Red red RED 0

Output

RED - 1

Red - 1

red - 1

Использование сортировки Словари

✓ 8✗ 8900средняяВойти и решать

Результаты олимпиады#22009

N участников олимпиады получили уникальные номера от 1 до N. В результате решения задач на олимпиаде, каждый участник получил некоторое количество баллов (целое число от 0 до 600). Известно, кто сколько баллов набрал. Требуется перечислить участников олимпиады в порядке невозрастания набранных ими баллов.

Входные данные

Вводится сначала число N (\(1<=N<=100\)) - количество участников олимпиады. Далее вводится N чисел - количества набранных участниками баллов (1-е число - это баллы, набранные участником номер 1, 2-е - участником номер 2 и т.д.).

Выходные данные

Выведите N чисел - номера участников в порядке невозрастания набранных ими баллов (участники, набравшие одинаковое количество баллов, могут быть выведены в любом порядке).

Пример

№	Входные данные	Выходные данные
1	5 100 312 0 312 500	5 2 4 1 3

Квадратичные сортировки

✓ 1 668✗ 1 712400лёгкаяВойти и решать

Большая сортировка#22008

Дано число N (\(1<=N<=100000\)), а затем N натуральных чисел из диапазона от 1 до 100.

Выведите N чисел в неубывающем порядке.

Входные данные
В первой строке задается число N - количество элементов массива (\(1<=N<=100000\)).
Далее идет N строк, по одному числу в строке - элементы массива.

Выходные данные
Выведите на экран отсортированный массив в одну строку.

Примеры

№	Входные данные	Выходные данные
1	5 3 1 2 4 2	1 2 2 3 4

Быстрая сортировка

✓ 917✗ 1 784500лёгкаяВойти и решать

Урок физкультуры#21998

Феоктист Всеволодович — преподаватель физкультуры старой закалки, глубоко убеждённый, что в начале каждого урока школьников необходимо построить по росту. Для этого он сначала просит школьников построиться самостоятельно, после чего последовательно меняет местами про- извольную пару стоящих рядом учеников, пока шеренга не примет желанный вид.

Всего на урок пришло N детей, изначально построившихся таким образом, что рост стоящего на позиции i равен hi (используется нумерация c 1). Можно считать, что все числа hi различны и лежат в диапазоне от 1 до N. Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьни- ков, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях i и j, если hi < h_j . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

Староста Саша очень любит играть в волейбол и прекрасно понимает, что чем дольше препо- даватель будет расставлять всех по местам, тем меньше времени останется для игры. Ученики уже построились некоторым образом, а Феоктист Всеволодович вышел поговорить по телефону, так что Саша может успеть поменять местами ровно двух школьников, необязательно стоящих рядом в ше- ренге. Разумеется, он хочет сделать это таким образом, чтобы преподаватель как можно быстрее закончил упорядочивать шеренгу (Саша давно уже раскусил, как именно действует Феоктист Всево- лодович). С информатикой у старосты всегда были определённые проблемы, поэтому ему требуется ваша помощь.

Формат входных данных
В первой строке ввода содержится единственное число N — количество школьников на уроке (1 <= N <= 1 000 000). Во второй строке записано N различных целых чисел h_i (1 <= h_i <= N). i-е число соответствует росту школьника стоящего на i-й позиции.

Формат выходных данных
Выведите два числа — номера позиций школьников, которым необходимо поменяться местами, чтобы минимизировать количество действий преподавателя. Если таких пар несколько, то выведите любую из них. Если никому меняться местами не нужно, выведите -1 -1.

Ввод	Вывод
5 2 4 3 5 1	2 5
4 1 2 3 4	-1 -1
10 2 3 7 1 5 10 4 6 9 8	3 7

Дерево отрезков, RSQ, RMQ Сканирующая прямая Словари Структуры данных

✓ 1✗ 391 200средняяВойти и решать

Регистрация на олимпиаду#21818

Петя и Вася проводят олимпиаду по программированию. На нее пришло так много участников,

что для того, чтобы их всех зарегистрировать, Пете и Васе пришлось работать вдвоем.

Для того, чтобы зарегистрироваться, каждый участник называет свои имя, фамилию и отчество,

а Петя и Вася заносят эту информацию в общую электронную таблицу. Так как участников много,

а времени на организацию так мало, Петя и Вася не успели договориться о формате записи данных

участника в таблицу и им пришлось импровизировать. Петя решил писать для каждого участника

сначала его фамилию, затем имя, а затем — отчество, а Вася — сначала имя, затем отчество, а

затем — фамилию.

По окончании регистрации стало понятно, что для подведения итогов олимпиады использовать

данную таблицу невозможно: участнику будет неудобно себя искать. Было решено привести таблицу

к следующему виду:

• для всех участников сначала написана фамилия, затем имя, а затем — отчество;

• участники в таблице упорядочены лексикографически по фамилии.

Петя и Вася заметили, что фамилии у всех участников различны, а вот каждое имя встречается

хотя бы два раза. При этом никакое имя не является ни фамилией, ни отчеством никакого из

участников, аналогично никакие фамилия и отчество не совпадают.

Пользуясь этой информацией, помогите им привести таблицу к желаемому виду.

Формат входных данных

В первой строке задано число n (2 ≤ n ≤ 1000) — общее число записей в электронной таблице.

Далее, в n строках записано по три слова s_1,i, s_2,i, s_3,i. Каждое из слов содержит от 1 до 20 латинских

букв, первая буква является заглавной, а все остальные — строчными. Каждая строка соответствует

одной из записей, сделанных Петей или Васей. Слова разделены одним пробелом.

Формат выходных данных

Выведите n строк — электронную таблицу, в которой для каждого участника идет сначала

фамилия, потом имя, потом отчество, причем все записи отсортированы лексикографически.

Лексикографический порядок соответствует порядку в словарях: слова сначала сравниваются

по первой букве, затем по второй и т.д. Если очередная буква в одном из слов идет раньше в

алфавите, то это слово лексикографически меньше другого. Если же расхождение так и не найдено,

то есть одно из слов является префиксом другого, то считается, что слово, являющееся префиксом,

лексикографически меньше.

Пример
Ввод

Ivanov Ivan Ivanovich

Ivan Borisovich Petrov

Sergey Ivanovich Sidorov

Pavlov Sergey Borisovich

Вывод

Ivanov Ivan Ivanovich

Pavlov Sergey Borisovich

Petrov Ivan Borisovich

Sidorov Sergey Ivanovich

Использование сортировки Строки

✓ 10✗ 241 100средняяВойти и решать

Мерлин#21817

Однажды, вернувшись в свою башню, Мерлин обнаружил, что Моргана наложила проклятие на

все его сосуды с эликсиром мудрости.

Мерлин знает, как снять проклятие, но соответствующее заклинание требует, чтобы во всех

сосудах, к которым оно применяется, было равное количество эликсира.

Чтобы добиться этого, Мерлин решил действовать следующим образом. Он выбирает несколько

сосудов и переливает весь эликсир из выбранных сосудов в оставшиеся. Он может распределить

переливаемый эликсир между оставшимися сосудами произвольным образом. После того, как весь

эликсир из выбранных сосудов перелит, Мерлин разбивает опустошенные сосуды (с них проклятие

уже не снять), выбрасывает осколки и применяет заклинание снятия проклятия к оставшимся

сосудам.

Помогите волшебнику узнать, какое наименьшее количество сосудов ему придется разбить,

чтобы снять проклятие Морганы.

Формат входных данных

В первой строке входного файла находится число n (2 ≤ n ≤ 10⁵) — количество сосудов. Во

второй строке содержатся n чисел a₁, a₂, . . . , a_n (1 ≤ a_i ≤ 10⁹) — количество литров эликсира

мудрости в каждом сосуде.

Формат выходных данных

Выведите в выходной файл минимальное количество сосудов, которые Мерлину придется

разбить.

Пример
Ввод

2 3 2
Вывод
1

Ввод:

4 4 4 4
Вывод
0

Ввод

1 2 3 4 5
Вывод
2

В первом примере можно, например, перелить 0.5 литра эликсира из первого сосуда во второй

и 1.5 литра в третий, после чего разбить первый сосуд.

Во втором сосуды исходно содержат равное количество эликсира, можно ничего не переливать.

В третьем примере можно, например, перелить 1 литр эликсира из первого сосуда во второй, по

2 литра из пятого во второй и третий, 1 литр из пятого в четвертый, после чего разбить первый и

пятый сосуды.

Использование сортировки Отрезки реализация

✓ 11✗ 191 000средняяВойти и решать

Количество операций#18780

Количество операций

Дана программа сортировки (p141.pas). Требуется узнать, сколько раз

при сортировке конкретного массива с помощью этой программы

выполняется операция сравнения двух элементов массива (строка 25 программы).

Входные данные

Задано сначала число N (1≤N≤100), а затем N целых чисел, по модулю не превышающих 1000.

Выходные данные

Ваша программа должна печатать одно число - сколько

раз в процессе сортировки этого массива программой p141.pas выполнится

команда сравнения двух элементов массива.

Пример входного файла

3 1 2 4 2

Пример выходного файла

Текст программы p141.pas

const nmax=100;

var a:array[1..nmax] of integer;
    n:integer;
    i,j,g:integer;

    f1,f2:text;

begin
assign(f1,'input.txt');
reset(f1);
assign(f2,'output.txt');
rewrite(f2);
                                  {Чтение входных данных}
read(f1,n);
for i:=1 to n do read(f1,a[i]);
                                  {Сортировка массива}

for i:=1 to n do begin            {Подбираем число на i-ое место}

  g:=i;                           {Считаем, что самое маленькое число,
                                   которое нам встретилось, стоит на месте i}

  for j:=i+1 to n do              {Перебираем все числа с i+1 до конца массива}
    if a[j]<a[g] then g:=j;       {Если нашли число, которое меньше,
                                   чем то, что уже найдено, запоминаем его}

                                  {Меняем местами числа, стоящие на i-ом и
                                   на g-ом местах }
                                  {Если a[i]=x, a[g]=y, то после выполнения
                                   команды: }
  if i<>g then begin
    a[i]:=a[i]+a[g];                {a[i]=x+y, a[g]=y}
    a[g]:=a[i]-a[g];                {a[i]=x+y, a[g]=(x+y)-y=x}
    a[i]:=a[i]-a[g];                {a[i]=(x+y)-x=y}
                                  {То есть после этого a[i]=y, a[g]=x
                                   обмен значений произошел}
    end;

  end;

                                  {Выводим результат}
for i:=1 to n do
  write(f2,a[i],' ');
close(f1);
close(f2);
end.

Вывод формулы Использование сортировки

✓ 22✗ 46900средняяВойти и решать

Сортировка#18730

Сортировка

Во входном файле задано сначала число N (1<=N<=100), а затем N целых

чисел, по модулю не превышающих 1000.

Выведите N чисел в порядке неубывания.

Пример входного файла

3 1 2 4 2

Пример выходного файла

1 2 2 3 4

Использование сортировки

✓ 140✗ 130400лёгкаяВойти и решать

Частоты букв#15824

На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке.

Сортировка подсчетом

✓ 968✗ 1 926500лёгкаяВойти и решать

Телефоны сотрудников#15680

На вход программе подаются сведения о телефонах всех сотрудников некоторого учреждения. В первой строке сообщается количество сотрудников N, каждая из следующих N строк имеет следующий формат:

<Фамилия> <Инициалы> <телефон>

где <Фамилия> – строка, состоящая не более чем из 20 символов, <Инициалы> - строка, состоящая не более чем из 4-х символов (буква, точка, буква, точка), <телефон> – семизначный номер, 3-я и 4, я, а также 5-я и 6-я цифры которого разделены символом «–». <Фамилия> и <Инициалы>, а также <Инициалы> и <телефон> разделены одним пробелом.

Пример входной строки:

Иванов П.С. 555-66-77

Сотрудники одного подразделения имеют один и тот же номер телефона. Номера телефонов в учреждении отличаются только двумя последними цифрами.
Требуется написать как можно более эффективную программу, которая будет выводить на экран информацию, сколько в среднем сотрудников работает в одном подразделении данного учреждения.
Ответ выводить с точностью 6 знаков после запятой.

Сортировка подсчетом

✓ 592✗ 1 397600лёгкаяВойти и решать

Средний балл по предметам#15581

Годовые оценки по девяти предметам за 9-й класс каждого из N учеников класса напечатаны в виде таблицы (в первой строке - оценки первого ученика, во второй - второго и т.д.). Фамилия ученика записана в первом столбце. Необходимо вывести данную таблицу в порядке убывания среднего балла. В случае равенства среднего балла, фамилии выводить в порядке их следования в исходных данных.

Входные данные
На вход программе подаются:
- в первой строке число N - количество учеников (1<=N<=25);
- далее идут N строк, в формате <фамилия (последовательность латинских символов)> <оценка за 1й предмет> <оценка за 2й предмет> ... <оценка за 9й предмет>.

Выходные данные
Вывести на экран таблицу, записанную в порядке убывания среднего балла по всем предметам в формате:
<Фамилия> <Средний балл (с точностью 6 знаков после запятой)>
В случае равенства среднего балла, фамилии выводить в порядке их следования в исходных данных.

Примеры

№	Входные данные	Выходные данные
1	3 Sidorov 1 1 1 1 1 1 1 1 1 Ivanov 5 5 5 5 5 5 5 5 5 Petrov 4 4 4 4 4 4 4 4 4	Ivanov 5.000000 Petrov 4.000000 Sidorov 1.000000

Алгоритмы обработки Использование сортировки

✓ 161✗ 687700средняяВойти и решать

15580#15580

Годовые оценки по девяти предметам за 9й класс каждого из N учеников класса напечатаны в виде таблицы (в первой строке - оценки первого ученика, во второй - второго и т.д.) Фамилия ученика записана в первом столбце. Необходимо вывести данную таблицу в алфавитном порядке (по возрастанию, начиная с A заканчивая Z)

Входные данные: на вход программе подаются
в первой число N - количество учеников, 1<=N<=25
далее идут N строк, в формате <фамилия-последовательность латинских символов> <оценка за 1й предмет> <оценка за 2й предмет>... <оценка за 9й предмет>

Выходные данные: вывести на экран исходную таблицу, записанную в алфавитном порядке от A до Z

Примеры

входные данные

Sidorov 1 1 1 1 1 1 1 1 1 
Ivanov 5 5 5 5 5 5 5 5 5
Petrov 4 4 4 5 4 5 5 5 5

выходные данные

Ivanov 5 5 5 5 5 5 5 5 5

Petrov 4 4 4 5 4 5 5 5 5

Sidorov 1 1 1 1 1 1 1 1 1

Алгоритмы обработки Использование сортировки

✓ 41✗ 104800средняяВойти и решать