e-olymp 6901. Shuffling Strings

12/05/2019 by Владислав Шеванов

Task

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 [latex] 0 \le n \le 100 [/latex] 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

Program code

#include <iostream>
using namespace std;
 
string shuffle (string &s1, string &s2) {
    string s;
    for (int i = 0; i < s1.length(); i++) {
        s += s2[i];
        s += s1[i];
    }
    s1 = s.substr(0, s1.length());
    s2 = s.substr(s2.length(), s2.length());
    return s;
} 
 
int main() {
    string s1, s2, s;
    int n;
    while (cin >> n && n) {
        cin >> s1 >> s2 >> s;
        string s12 = s1; s12 += s2;
        string fixS = s12;
        bool flag = true;
        int nofs = 0;           // number of steps
        do {
            nofs++;
            s12 = shuffle(s1, s2);
            if (s == s12)
                flag = false;
        } while (s12 != fixS && flag && nofs <= 50);
        cout << (flag ? -1 : nofs) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

string shuffle (string &s1, string &s2) {

string s;

for (int i = 0; i < s1.length(); i++) {

s += s2[i];

s += s1[i];

}

s1 = s.substr(0, s1.length());

s2 = s.substr(s2.length(), s2.length());

return s;

}

int main() {

string s1, s2, s;

int n;

while (cin >> n && n) {

cin >> s1 >> s2 >> s;

string s12 = s1; s12 += s2;

string fixS = s12;

bool flag = true;

int nofs = 0; // number of steps

do {

nofs++;

s12 = shuffle(s1, s2);

if (s == s12)

flag = false;

} while (s12 != fixS && flag && nofs <= 50);

cout << (flag ? -1 : nofs) << endl;

}

return 0;

}

Program code V2.

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    int n;
    while( cin >> n && n){
        int count = 0;
        char *first = new char[n+1];
        char *second = new char[n+1];
        char *third = new char[2 * n+1];
        char *result = new char[2 * n+1];
        cin >> first;
        cin >> second;
        cin >> third;
        while(strcmp(result, third) && (count < 51)){
            for(int i = 0; i < n; i++){
                result[2 * i] = second[i];
                result[2 * i + 1] = first[i];
            }
            strncpy(first, &result[0], n);
            strncpy(second, &result[n], n);
            count++;
        }
        cout << ((count < 51) ? count : -1) << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

int n;

while( cin >> n && n){

int count = 0;

char *first = new char[n+1];

char *second = new char[n+1];

char *third = new char[2 * n+1];

char *result = new char[2 * n+1];

cin >> first;

cin >> second;

cin >> third;

while(strcmp(result, third) && (count < 51)){

for(int i = 0; i < n; i++){

result[2 * i] = second[i];

result[2 * i + 1] = first[i];

}

strncpy(first, &result[0], n);

strncpy(second, &result[n], n);

count++;

}

cout << ((count < 51) ? count : -1) << endl;

}

return 0;

}

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.

Related Images:

e-olymp 7261. Трудный путь

20/02/2019 by Владислав Шеванов

Задача

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

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

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

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

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

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

Тесты

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

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

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    double** x = new double* [n+1];
    for (int i = 0; i < n+1; i++) {
        x[i] = new double [2*n+1];
    }
    x[0][n] = 1;
    double a, b;
    for(int i = 1; i <= n; i++) {
      for(int j = n - i; j <= n + i; j++) {
        a = (j - 1 < 0)? 0 : x[i-1][j-1];
        b = (j + 1 > 2*n)? 0 : x[i-1][j+1];
        x[i][j] = (a + b) / 2;
      }
    }
    double h = (n + m > 2*n)? 0 : x[n][n+m];
    cout << fixed << setprecision(9) << h;
    for (int i = 0; i < n+1; i++) {
        delete []x[n-i];
    }
    delete []x;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

double** x = new double* [n+1];

for (int i = 0; i < n+1; i++) {

x[i] = new double [2*n+1];

}

x[0][n] = 1;

double a, b;

for(int i = 1; i <= n; i++) {

for(int j = n - i; j <= n + i; j++) {

a = (j - 1 < 0)? 0 : x[i-1][j-1];

b = (j + 1 > 2*n)? 0 : x[i-1][j+1];

x[i][j] = (a + b) / 2;

}

double h = (n + m > 2*n)? 0 : x[n][n+m];

cout << fixed << setprecision(9) << h;

for (int i = 0; i < n+1; i++) {

delete []x[n-i];

}

delete []x;

return 0;

}

Решение

Закодируем путь Васи последовательностью из 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$ четно.

Ссылки

Related Images:

e-olymp 407. Обмін

26/12/2018 by Владислав Шеванов

Задача

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

Вхідні дані

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

Вихідні дані

Вивести $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

Код програми

#include <iostream>
using namespace std;

int main() {
    int n, day;
    cin >> n;
    while (n--) {
        cin >> day;
        if (day % 3 == 1)
            cout<<"VGC"<<endl;
        else if (day % 3 == 2)
            cout<<"CVG"<<endl;
        else
            cout<<"GCV"<<endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, day;

cin >> n;

while (n--) {

cin >> day;

if (day % 3 == 1)

cout<<"VGC"<<endl;

else if (day % 3 == 2)

cout<<"CVG"<<endl;

else

cout<<"GCV"<<endl;

}

return 0;

}

Розв’язок

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

Посилання

e-olymp
ideone.com

Related Images:

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

05/12/2018 by Владислав Шеванов

Задача

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

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

В первой строке заданы три числа: [latex]n (3 \le n \le 10^5)[/latex] и координаты точки. Далее в $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

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

#include <iostream>
using namespace std;

struct point {
    int x;
    int y;
};

int f (point *p, int N, int x, int y) {
    int i1, i2, n, S, S1, S2, S3, flag;
    for (n = 0; n < N; n++) {
        flag = 0;
        i1 = n < N-1 ? n + 1 : 0;
        while (flag == 0) {
            i2 = i1 + 1;
            if (i2 >= N)
                i2 = 0;
            if (i2 == (n < N-1 ? n + 1 : 0))
                break;
            S = abs (p[i1].x * (p[i2].y - p[n].y) +
                p[i2].x * (p[n].y - p[i1].y) +
                p[n].x  * (p[i1].y - p[i2].y));
            S1 = abs (p[i1].x * (p[i2].y - y) +
                p[i2].x * (y - p[i1].y) +
                x * (p[i1].y - p[i2].y));
            S2 = abs (p[n ].x * (p[i2].y - y) +
                p[i2].x * (y - p[n].y) +
                x * (p[n].y - p[i2].y));
            S3 = abs (p[i1].x * (p[n].y - y) +
                p[n].x * (y - p[i1].y) +
                x * (p[i1].y - p[n].y));
            if (S == S1 + S2 + S3) {
                flag = 1;
                break;
            }
            i1++;
            if (i1 >= N)
                i1 = 0;
            }
        if (flag == 0)
            break;
    }
    return flag;
}

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    point* p = new point[n];
    for (int i = 0; i < n; i++)
        cin >> p[i].x >> p[i].y;
    cout << (f(p, n, x, y) ? "YES" : "NO");
    return 0;
}

#include <iostream>

using namespace std;

struct point {

int x;

int y;

};

int f (point *p, int N, int x, int y) {

int i1, i2, n, S, S1, S2, S3, flag;

for (n = 0; n < N; n++) {

flag = 0;

i1 = n < N-1 ? n + 1 : 0;

while (flag == 0) {

i2 = i1 + 1;

if (i2 >= N)

i2 = 0;

if (i2 == (n < N-1 ? n + 1 : 0))

break;

S = abs (p[i1].x * (p[i2].y - p[n].y) +

p[i2].x * (p[n].y - p[i1].y) +

p[n].x * (p[i1].y - p[i2].y));

S1 = abs (p[i1].x * (p[i2].y - y) +

p[i2].x * (y - p[i1].y) +

x * (p[i1].y - p[i2].y));

S2 = abs (p[n ].x * (p[i2].y - y) +

p[i2].x * (y - p[n].y) +

x * (p[n].y - p[i2].y));

S3 = abs (p[i1].x * (p[n].y - y) +

p[n].x * (y - p[i1].y) +

x * (p[i1].y - p[n].y));

if (S == S1 + S2 + S3) {

flag = 1;

break;

}

i1++;

if (i1 >= N)

i1 = 0;

}

if (flag == 0)

break;

}

return flag;

}

int main() {

int n, x, y;

cin >> n >> x >> y;

point* p = new point[n];

for (int i = 0; i < n; i++)

cin >> p[i].x >> p[i].y;

cout << (f(p, n, x, y) ? "YES" : "NO");

return 0;

}

Решение

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

Ссылки

Related Images:

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

11/11/2018 by Владислав Шеванов

Задача

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

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

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

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

В первой строке выведите квадраты всех целых чисел от $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

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

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    for (long long int i = a; i <= b; i++)
        cout << i * i << ' ';
    cout << endl;
    for (long long int j = b; j >= a; j--)
        cout << j * j * j << ' ';
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b;

cin >> a >> b;

for (long long int i = a; i <= b; i++)

cout << i * i << ' ';

cout << endl;

for (long long int j = b; j >= a; j--)

cout << j * j * j << ' ';

return 0;

}

Решение

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

Ссылки

Ideone

e-olymp

Related Images:

e-olymp 2. Цифры

03/10/2018 by Владислав Шеванов

Задача

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

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

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

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

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

Тесты

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

Код программы (с использованием условных операторов)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    if( n <= 9 ) cout << 1;
    else if( n <= 99 ) cout << 2;
    else if( n <= 999 ) cout << 3;
    else if( n <= 9999 ) cout << 4;
    else if( n <= 99999 ) cout << 5;
    else if( n <= 999999 ) cout << 6;
    else if( n <= 9999999 ) cout << 7;
    else if( n <= 99999999 ) cout << 8;
    else if( n <= 999999999 ) cout << 9;
    else if( n <= 2000000000 ) cout << 10;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

if( n <= 9 ) cout << 1;

else if( n <= 99 ) cout << 2;

else if( n <= 999 ) cout << 3;

else if( n <= 9999 ) cout << 4;

else if( n <= 99999 ) cout << 5;

else if( n <= 999999 ) cout << 6;

else if( n <= 9999999 ) cout << 7;

else if( n <= 99999999 ) cout << 8;

else if( n <= 999999999 ) cout << 9;

else if( n <= 2000000000 ) cout << 10;

return 0;

}

Код программы (без использования условных операторов)

#include <iostream>
#include <string>
using namespace std;

int main() {
    string n;
    cin >> n;
    cout << n.length();
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string n;

cin >> n;

cout << n.length();

return 0;

}

Решение

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