Упражнения

В задачах этого (и всех последующих листков) данные можно читать как со стандартного ввода, так и из файла (input.txt), результат можно выводить как на стандартный вывод, так и в файл (output.txt).

A: Сортировка цифр

Программа получает на вход строку, в которой записаны цифры (то есть символы от 0 до 9) через пробел. Упорядочите эти цифры в порядке неубывания.

В этой задаче количество чисел на входе может достигать 1 миллиона, а ограничение по памяти для вашей программы 2 мегабайта. Это означает, что сохранить все данные числа в памяти не получится.

Ввод Вывод
1 2 3 1 2 3
1 1 2 2 3 3

B: Сортировка строк

А теперь программа получает на вход строку, состоящую из непробельных ASCII-символов. Упорядочите символы этой строки. Ограничения такие же — в строке может быть до миллиона символов и 2 мегабайта доступной памяти.

Ввод Вывод
Hello,World!
!,HWdellloor

C: Сортировка чисел

Вам дано \(N\) целых чисел, где \(N\le 10^6\). Вам по-прежнем нужно их отсортировать, но их всё еще нельзя все сохранить в памяти. Вам поможет дополнительная информация о том, что любые два из этих чисел отличаются не более, чем на \(10^5\).

Ввод Вывод
1000000179 1000000000 999999990 1000000010
999999990 1000000000 1000000010 1000000179

D: Палиндром (ЕГЭ-2010)

Задача такого рода предлагалась на ЕГЭ по информатике в 2010 году. Решение должно использовать \(O(1)\) памяти, в частности, это означает, что чтение данных должно быть посимвольным.

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

Ввод Вывод
PARALLELOGRAM
ALRARLA
ONE
E

E: Анаграммы

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

Программа получает на вход две строки, содержащие только ASCII-символы, не содержащие пробелы.

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

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

  1. Установить до начала считывания манипулятор noskipws. Пример: cin >> noskipws. Это приведет к тому, что при посимвольном считывании не будут пропускаться пробельные символы.
  2. Сравнить считанный символ со специальным символом конца строки, который в исходном коде программе на C++ можно задать, как '\n'.
Ввод Вывод
eleven_plus_two
twelve_plus_one
YES
Eleven_plus_two
Twelve_plus_one
NO

F: Числа

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

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

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

Ввод Вывод
280138
798081
8810
123
456
-1