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

Подсчет пар#50778

Вам дан массив A из N чисел. Найдите количество различных пар (i, j), таких, что j>=i и A[i] = A[j].

Формат входных данных
Первая строка входных данных содержит количество тестовых случаев T. Каждый тестовый случай состоит из двух строк, первая строка - число N, за ней следует строка, состоящая из N целых чисел, которые являются элементами массива A.

Ограничения

1 <= T <= 10

1 <= N <= 10⁶ 

-10⁶ <= A[i] <= 10⁶

0 <= i < N

Формат выходных данных
Для каждого тестового случая выведите количество различных пар.

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

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

Первый уникальный#46033

Символ называется уникальным, если он встречается в строке один раз. Первый уникальный символ - это уникальный символ с наименьшим индексом.
Дана строка s. Найдите первый уникальный символ в данной строке. Выведите его индекс. Если в строке нет уникальных символов, выведите -1.

Входные данные
Программа получает на вход последовательность непробельных символов s.

Ограничения
'a' <= s[i] <= 'z'
0 <= i <= 255

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	silvertests	1
2	sstt	-1

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

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

Относительная сортировка#45263

Даны два массива arr1 и arr2. Элементы массива arr2 различны, и при этом все элементы arr2 содержатся в arr1.

Отсортируйте элементы массива arr1 таким образом, чтобы относительный порядок элементов в массиве arr1 был таким же, как в массиве arr2. Элементы, которых нет в массиве arr2 должны располагаться в конце массива arr1 в порядке возрастания.

Входные данные
Первая строка входных данных содержит целое число n - количество элементов в массиве arr1, вторая строка содержит n целых чисел - элементы массива arr1. Третья строка содержит целое число m - количество элементов в массиве arr2, четвертая строка содержит m целых чисел - элементы массива arr2.

Ограничения на входные данные

1 <= n, m <= 10⁶
0 <= arr1[i], arr2[i] <= 1000
Все элементы массива arr2 различны.
Каждый элемент массива arr2[i] содержится в массиве arr1.

Выходные данные
Выведите, отсортированный по условию задачи, массив arr1.

Примеры

№	Входные данные	Выходные данные
1	11 2 3 1 3 2 4 6 7 9 2 19 6 2 1 4 3 9 6	2 2 2 1 4 3 3 9 6 7 19
2	6 28 6 22 8 44 17 4 22 28 8 6	22 28 8 6 17 44

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

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

Мегавзлом#34825

У Егора очень старый телефон. Слава отправил Егору кодовую фразу от Серёжиного банковского счёта, чтоб его ограбить, но телефон Егора настолько стар, что не умеет принимать длинные сообщения. Он разбивает их на несколько маленьких случайной длины, и приходят они ему в случайном порядке.

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

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

Единственная строка входных данных содержит строку s — сообщение в телефоне Егора (1 ≤ |s| ≤ 10⁵). Гарантируется, что s содержит только маленькие латинские буквы.

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

Выведите кодовую фразу от Серёжиного банковского счёта.

Примеры

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

qwerty

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

ywtrqe

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

onehundredseventynine

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

yvutsronnnnniheeeeedd

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

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

Списки по классам#34824

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

В каждой строке сначала записан номер класса (число, равное 9, 10 или 11), затем (через пробел) — фамилия ученика.

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

Необходимо вывести список школьников по классам: сначала всех учеников 9 класса, затем — 10, затем — 11. Внутри одного класса порядок вывода фамилий должен быть таким же, как на входе.

Примеры

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

9 Ivanov
10 Petrov
11 Sidorov
9 Grigoryev
9 Sergeev
10 Yakovlev

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

9 Ivanov
9 Grigoryev
9 Sergeev
10 Petrov
10 Yakovlev
11 Sidorov

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

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

Арифметика Саши и Кати#34822

Саша и Катя учатся в начальной школе. Для изучения арифметики при этом используются карточки, на которых написаны цифры (на каждой карточке написана ровно одна цифра). Однажды они пришли на урок математики, и Саша, используя все свои карточки, показал число A, а Катя показала число B. Учитель тогда захотел дать им такую задачу, чтобы ответ на нее смогли показать и Саша, и Катя, каждый используя только свои карточки. При этом учитель хочет, чтобы искомое число было максимально возможным.

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

Вводятся два целых неотрицательных числа A и B (каждое число в одной строке). Длина каждого из чисел не превосходит 100 000 цифр.

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

Выведите одно число — максимальное целое число, которое можно составить используя как цифры первого числа, так и цифры второго числа. Если же ни одного такого числа составить нельзя, выведите -1.

Примеры тестов

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

280138
798081

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

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

123
456

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

-1

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

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

Головоломка#34819

Петя разгадывает головоломку, которая устроена следующим образом. Дана квадратная таблица размера NxN, в каждой клетке которой записана какая-нибудь латинская буква. Кроме того, дан список ключевых слов. Пете нужно, взяв очередное ключевое слово, найти его в таблице. То есть найти в таблице все буквы этого слова, причем они должны быть расположены так, чтобы клетка, в которой расположена каждая последующая буква слова, была соседней с клеткой, в которой записана предыдущая буква (клетки называются соседними, если они имеют общую сторону — то есть соседствуют по вертикали или по горизонтали). Например, на рисунке ниже показано, как может быть расположено в таблице слово olympiad.

P	O	L	T	E
R	W	Y	M	S
O	A	I	P	T
B	D	A	N	R
L	E	M	E	S

Когда Петя находит слово, он вычеркивает его из таблицы. Использовать уже вычеркнутые буквы в других ключевых словах нельзя.
После того, как найдены и вычеркнуты все ключевые слова, в таблице остаются еще несколько букв, из которых Петя должен составить слово, зашифрованное в головоломке.
Помогите Пете в решении этой головоломки, написав программу, которая по данной таблице и списку ключевых слов выпишет, из каких букв Петя должен сложить слово, то есть какие буквы останутся в таблице после вычеркивания ключевых слов.

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

В первой строке записаны два числа N (1 ≤ N ≤ 10) и M ( 0 ≤ M ≤ 200). Следующие N строк по N заглавных латинских букв описывают ребус. Следующие M строк содержат слова. Слова состоят только из заглавных латинских букв, каждое слово не длиннее 200 символов. Гарантируется, что в таблице можно найти и вычеркнуть по описанным выше правилам все ключевые слова.

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

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

Примеры

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

5 3
POLTE
RWYMS
OAIPT
BDANR
LEMES
OLYMPIAD
PROBLEM
TEST

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

AENRSW

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

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

Самая частая сумма#33480

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

Напишите эффективную по времени и по памяти программу для решения этой задачи.

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

Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.

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

В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.

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

Выведите одно число - искомый ответ.

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

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

Клавиатура#29472

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

При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.

Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.

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

В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.

Ввод	Вывод
5 1 50 3 4 3 16 1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5	yes no no no yes

Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 2 день, Задача A

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

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

Разброс#29470

Дано N целых чисел, которые требуется отсортировать в порядке неубывания. В связи с нормами СЭС среди чисел не будет двух, разница между которыми превышает 10⁷.

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

Первая строка входного файла содержит целое число N. (1 <= N <= 100000), вторая строка – N целых чисел, не превышающих по модулю 2*10⁹. Никакие два не различаются более, чем на 10⁷.

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

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

Ввод	Вывод
1 863961129	863961129
5 1866455200 1866455199 1866455198 1866455197 1866455196	1866455196 1866455197 1866455198 1866455199 1866455200

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

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

Носки#29468

Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.

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

Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки.

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

Выведите M чисел – толщину носкового покрытия в каждой точке.

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

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

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

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

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

На вход программе сначала подается значение n <= 100000 – количество элементов массива. В следующей строке расположены сами элементы – целые числа, по модулю не превосходящие 10000.

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

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

Примеры

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

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

✓ 1 265✗ 4 097500лёгкаяВойти и решать

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

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

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

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

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

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

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

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

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

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

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

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

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