Упражнения

В задачах этого (и всех последующих листков) данные можно читать как со стандартного ввода, так и из файла (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: Анаграммы

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

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

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

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

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

E: Числа

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

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

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

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

F: Покер

Даны 5 целых чисел, каждое от 1 до 13. Выведите одну из следующих строк:

Ввод Вывод
1 3 9 3 2
One Pair
1 5 5 4 4
Two Pairs
1 5 2 4 3
Straight
10 11 12 13 1
Nothing

G: Покер-2

Рассмотрим следующую разновидность покера. В игре участвуют карты \(N\) различных значений от 1 до \(N\), карт каждого из возможных значений бесконечно много. Каждый игрок получает \(N\) карт и смотрит, какое максимальное число карт одного значения у него есть на руках. Пусть у первого игрока на руках есть \(s\) одинаковых карт, а у второго игрока \(t\) одинаковых карт. Тогда если \(s\gt t\), то выиграл первый игрок, если \(s\lt t\), то выиграл второй игрок, иначе оба игрока отбрасывают равное наибольшее число одинаковых карт и процесс повторяется заново до тех пор, пока не будет определён победитель или пока у игроков не кончатся карты, что означает ничью.

По значениям карт двух игроков определите, кто выигрывает.

Первая строка входных данных содержит число \(N\), \(1\le N\le 10^5\). Вторая и третья строка содержат по \(N\) натуральных чисел от 1 до \(N\) каждое — значения карт первого и второго игрока.

Программа должна вывести номер выигрывающего игрока (1 или 2), или число 0 в случае ничьи.

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