# e-olymp 6901. Shuffling Strings

Suppose $S_1$ and $S_2$  are two strings of size $n$ consisting of characters $A$ through $H$ (capital letters). We plan to perform the following step several times to produce a given string $S$. In each step we shuffle $S_1$ and $S_2$ to get string $S_{12}$ Indeed, $S_{12}$ is obtained by scanning $S_1$ and $S_2$ from left to right and putting their characters alternatively in $S_{12}$ from left to right.

The shuffling operation always starts with the leftmost character of $S_2$. After this operation, we set $S_1$ and $S_2$ to be the first half and the second half of $S_{12}$, respectively. For instance, if $S_1 = ABCHAD$ and $S_2 = DEFDAC$, then $S_12 = DAEBFCDHAACD$, and for the next step $S_1 = DAEBFC$ and $S_2 = DHAACD$. For the given string $S$ of size $2n$, the goal is to determine whether $S_{12} = S$ at some step.

#### Input

There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers $0 \le n \le 100$ which is the length of $S_1$ and $S_2$. The remainder of each test case consists of three lines. The first and the second lines contain strings $S_1$ and $S_2$ with size $n$, respectively, and the last line contains string $S$ with size $2n$. The input terminates with «$0$» which should not be processed.

#### Output

For each test case, output $-1$ if $S$ is not reachable. Otherwise, output the minimum number of steps to reach $S$ . To make your life easier, we inform you that the output is not greater than $50$ for the given input.

#### Tests

 Input Output 4 AHAH HAHA HHAAAAHH 3 CDE CDE EEDDCC 0 2 -1 3 DBC BCD CDBCBD 0 -1 3 DABC ABCD CADBCBAD 1 A B AB 0 -1 2 3 AAA AAA AAAAAA 0 1 5 ABACD ACABB AAAACCBBBD 0 -1

#### Solution

Repeating the shuffling of the two strings a sufficient number of times, it becomes clear that the variations of the lines repeat with a certain periodicity. In order not to continue the cycle of shuffling if strings began to repeat, we fix the first concatenation of the strings $S_1$ and $S_2$, and if we meet it again, we assume that the string $S$ cannot be obtained. Also a sign of this is that the number of steps exceeded $50$ — from the condition of the problem.

# Задача. Длина слов

Задан текст — последовательность слов. Найдите длину каждого слова.

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

Текст содержит последовательность слов. Длина каждого слова не более $20$.

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

Для каждого слова в одной строке выведите его длину.

# Тесты

 № Ввод Вывод 1 Programming Principles 1 11 10 1 2 I like C very much 1 4 1 4 4 3 12345678901234567890 20 4 ;-\ 3 9 5 5^2-7*4/2 = 11 9 1 2 6 Veeeeeeery bIg LeTteR! 10 3 7 7 1,               25. 10! 2 3 3

# Решение

Считываем в потоке и выводим длину каждого слова через пробел.

# Анаграммы

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

После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

## Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

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

## Тесты

 № Ввод Вывод 1 2500 слов английского языка trace react crate dear dare read post stop spot

# Условие задачи

«Курс валюты Зимбабве опустился накануне до рекордно низкого уровня — $1,2$ млрд. зимбабвийских долларов за один доллар США»
(Новости от $7.06.2009$)

В некоторой стране инфляция достигла таких размеров, что доходы граждан стали выражаться числами, количество знаков в десятичной записи которых доходит до $200.$ Это сильно усложнило задачу взимания налогов.

Один из налогов на доходы составляет $1%.$ Напишите программу, которая по введенному числу $D$ (величине дохода гражданина) вычислит этот налог.

При этом применяются следующие правила округления:

1. Если налог выражается целым числом, то он не округляется.
2. Если налог выражается дробным числом, то он округляется в сторону большего целого (в пользу государства).

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

Вводится одно число $D$ (натуральное, $10^{5} \leqslant D < 10^{200}$) – величина дохода гражданина.

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

Выведите одно натуральное число – величину налога.

# e-olymp 2197. Антипалиндром

## Антипалиндром

#### Условие задачи:

Палиндромом называют строку, читающуюся одинаково с обеих сторон. Задана строка s. Найдите её наибольшую по длине подстроку, не являющуюся палиндромом.

Входные данные
Входной файл содержит строку s. Она состоит только из строчных букв латинского алфавита, не пуста, её длина не превышает 100000 символов.

Выходные данные
В выходной файл выведите ответ на задачу, если ответов несколько — выберите лексикографически минимальный. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.

Тесты

 № Входные данные Выходные данные 1 abba abb 2 aaaaaaa NO SOLUTION 3 abcghgcba abcghgcb 4 abaaabbb abaaabbb

Код на языке C++:

Код на языке Java:

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

Условие задачи на e-olymp
Засчитанная задача на e-olymp: на языке C++
Засчитанная задача на e-olymp: на языке Java
Код задачи на C++: Ideone
Код задачи на Java: Ideone