# 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.

# Задача

Вася хорошо выпил и теперь, когда он добрался до своей улицы, он полностью потерял чувство направления. Поскольку он не помнит, с какой стороны его дом, он выбирает направление наобум. Более того, на каждом перекрёстке он с вероятностью $50\%$ продолжает идти вперёд, а иначе разворачивается и идёт назад. Он настолько потерял связь с реальностью, что может даже пройти мимо своего дома и не заметить этого!

Пройдя $n$ кварталов, Вася засыпает прямо на улице. Проснувшись, он задаётся вопросом: какой у него был шанс заснуть рядом с домом? Ведь от перекрёстка, от которого он начал свой путь, до перекрёстка рядом с домом Васи всего $m$ кварталов. Помогите ему.

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

В одной строке содержатся два целых числа $n$ и $m$ $(0 \le n , m \le 1000)$.

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

Выведите одно число — вероятность Васи заснуть на перекрёстке рядом со своим домом. Выведите ответ с абсолютной погрешностью не более $10^{-7}$.

#### Тесты

 Входные данные Выходные данные 1 1 0.500000000 10 20 0.000000000 1000 100 0.000169397 16 2 0.174560547 90 44 0.000001273

#### Решение

Закодируем путь Васи последовательностью из 0 и 1. Пусть 1 соответствует движению вправо, а 0 влево. Пусть из $n$ шагов, которые совершил Вася, $k$ шагов он сделал вправо. Тогда $n-k$ шагов он сделал влево.Нас интересует вероятность того, что Вася переместился в одну из сторон (например вправо) на $m$ кварталов. Тогда должно выполняться: $m+n-k=k$откуда $k=\frac{m+n}{2}$.Количество последовательностей длины $n$ с $k$ единицами равно $C_n^k$. Поскольку Вася совершил $n$ перемещений, то у него имеется $2^n$ вариантов выбора различных путей. Следовательно вероятность того что Вася пройдет вправо m кварталов, равна $\frac{C_n^k}{2^n}$, где $k=\frac{m+n}{2}$. Отметим, что искомая вероятность равна 0, если $m+n$ нечетно. В этом случае Вася просто не сможет попасть домой, то есть $m+n=2k$ четно.

Ссылки

# e-olymp 407. Обмін

## Задача

У різдвяний вечір у віконці стояло три квіточки, зліва на право: герань, крокус та фіалка. Кожен ранок Маша витирала віконце і міняла містами стоявшу праворуч квіточку з центральною кввточкою. А Таня кожен вечір поливала квіточки і міняла місцями ліву та центральну квіточку. Потрібно визначити порядок квітів вночі після того, як пройде $k$ днів.

#### Вхідні дані

Перший рядок містить кількість тестів $t$ $(1 \leq t \leq 12)$. В кожному з наступних $t$ рядків знаходиться кількість днів $k$ $(k \leq 1000)$.

#### Вихідні дані

Вивести $t$ рядків, що містять по три латинських літери: «G», «C» и «V» (великі літери без пропусків), які описують порядок квітів на вікні по закінченню $k$ днів (зліва направо). Позначення: G – герань, C – крокус, V – фіалка.

#### Тести

 № Вхідні дані Вихідні дані 1 2 1 5 VGC CVG 2 6 1 2 3 4 5 6 VGC CVG GCV VGC CVG GCV 3 3 3 6 9 GCV GCV GCV

#### Розв’язок

Якщо кожного вечора звертати увагу на те, як Маша і Таня міняють місцями квіти, то можна помітити, що їх перестановки періодично повторюються кожні три дні. Цим я скористався для розв’язку задачі. Достатньо лише задати ці три перестановки і брати залишок від ділення на три для визначення конкретної.

# e-olymp 8357. Точка в многоугольнике

## Задача Как известно, простой многоугольник — это фигура, состоящая из не пересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.

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

В первой строке заданы три числа: $n (3 \le n \le 10^5)$ и координаты точки. Далее в $n$ строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

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

Вывести строку «YES», если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

#### Тесты

 Входные данные Выходные данные 3 0 0 1 0 0 1 1 1 NO 4 3 2 0 0 1 5 5 5 6 0 YES 3 5 6 2 3 8 0 -1 -3 NO 4 -2 3 0 0 5 0 0 6 3 3 NO 5 3 1 9 2 3 0 -2 -4 -4 0 -4 5 YES

#### Решение

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

# e-olymp 8532. Печать квадратов и кубов

### Задача

Заданы два целых числа $a$ и $b$. Выведите квадраты и кубы всех целых чисел от $a$ до $b$ включительно.

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

Два целых числа $a$ и $b$ $(0 \le a \le b \le 10000)$.

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

В первой строке выведите квадраты всех целых чисел от $a$ до $b$ включительно по возрастанию. Во второй строке выведите кубы всех целых чисел от $a$ до $b$ включительно по убыванию.

#### Тесты

 Входные данные Выходные данные 5 10 25 36 49 64 81 100 1000 729 512 343 216 125 120 123 14400 14641 14884 15129 1860867 1815848 1771561 1728000 9995 10000 99900025 99920016 99940009 99960004 99980001 100000000 1000000000000 999700029999 999400119992 999100269973 998800479936 998500749875 0 3 0 1 4 9 27 8 1 0 25 27 625 676 729 19683 17576 15625

Код программы

#### Решение

Ввожу $a$ и $b$, создаю цикл вывода по возрастанию квадратов чисел из промежутка, и с новой строки — кубы по убыванию.

Ideone

e-olymp

# Задача

Вычислить количество цифр целого неотрицательного числа $n$.

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

Одно целое неотрицательное число $n$ $(0 \ge n \ge 2\cdot10^9)$.

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

Количество цифр в числе $n$.

#### Тесты

 Входные данные Выходные данные 12345 5 1 1 353628 6 5454 4 0 1

#### Решение

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

#### Ссылки

E-Olymp

Ideone (с условными операторами)

Ideone (без условных операторов)