e-olymp 8379. Нулі та одиниці

24/06/2019 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Їжачок Аліна, переглядаючи свої старі зошити знайшла в одному з них неймовірно цікавий масив з нулів. Виявилось, що Аліна з цим масивом вміє робити кілька неймовірно цікавих операцій:

Присвоїти елементу в позиції $x$ значення $1.$
Присвоїти елементу в позиції $x$ значення $0.$
Замінити на відрізку від $l$ до $r$ всі нулі на одиниці і навпаки.
Повернути масив в стан, який був після $x$-ої операції.
Знайти кількість одиниць на підвідрізку масиву від $l$ до $r.$

Вхідні дані

В першому рядку задано два натуральні числа $N \leqslant 10^5$ i $M \leqslant 2 \cdot 10^5,$ що позначають розмір масива і кількість операцій відповідно. В наступних $M$ рядках задано інформацію про операції.

Вихідні дані

Для кожної операції типу $5$ вивести кількість одиниць на підвідрізку від $l$ до $r.$

Тести

#	Входные данные	Выходные данные
1	8 7 1 1 3 1 4 5 1 5 2 3 5 1 5 4 1 5 1 5	3 2 1
2	4 5 1 2 1 3 2 2 3 1 3 5 1 2	2
3	4 7 1 2 1 3 2 2 3 1 3 5 1 2 4 1 5 1 2	2 1

Код

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

struct node {
    int value = 0;
    node * right, * left;
    int l, r;
    int unPushed = 0;
    node(int l, int r) : left(nullptr), right(nullptr), l(l), r(r) { }
    node * clone() {
        node * ans = new node(l, r);
        ans -> right = right;
        ans -> left = left;
        ans -> value = value;
        ans -> unPushed = unPushed;
        return ans;
    }
};
vector<node *> v;
int sum(node * left, node * right) {
    int ans = 0;
    if(left != nullptr) ans += left -> value;
    if(right != nullptr) ans += right -> value;
    return ans;
}
void push(node *(&k)) {
    k -> unPushed %= 2;
    if (k -> unPushed) {
        int center = (k -> l + k -> r) / 2;
        if (k -> left == nullptr) k -> left = new node(k -> l, center);
        else k -> left = k -> left -> clone();
        if (k -> right == nullptr) k -> right = new node(center + 1, k -> r);
        else k -> right = k -> right -> clone();
        ++k -> left -> unPushed;
        ++k -> right -> unPushed;
        k -> left -> value = (center - k -> l + 1) - k -> left -> value;
        k -> right -> value = (k -> r - center) - k -> right -> value;
        k -> unPushed = 0;
    }
   
}
void updateSegment(node *(&k), int left, int right, int l, int r) {
    if(k == nullptr) k = new node(left, right);
    else k = k -> clone();
    if(l > r) return;
    if(l == left && r == right) {
        ++k -> unPushed;
        k -> value = (r - l + 1) - k -> value;
        return;
    }
    int center = (left + right) / 2;
    push(k);
    updateSegment(k -> left, left, center, l, min(r, center));
    updateSegment(k -> right, center + 1, right, max(l, center + 1), r);
    push(k -> left);
    push(k -> right);
    k -> value = sum(k -> left, k -> right);
}
void update(node *&k, int left, int right, int pos, int a) {
    if (k == nullptr) k = new node(left, right);
    else k = k -> clone();
    if (left == right) {
        k -> value = a;
        return;
    }
    int center = (left + right) / 2;
    push(k);
    if(pos <= center) {
        update(k -> left, left, center, pos, a);
        push(k -> left);
    }
    else {
        update(k -> right, center + 1, right, pos, a);
        push(k -> right);
    }
    k -> value = sum (k -> left, k -> right);
}
int query(node *k, int left, int right, int l, int r) {
    if (l > r) return 0;
    if(k == nullptr) return 0;
    if(left == l && r == right) return k -> value;
    int center = (left + right) / 2;
    push(k);
    return query(k -> left, left, center, l, min(center, r)) + query(k -> right, center + 1, right, max(l, center + 1), r);
}

int main() {
    int n, m, type, pos, l, r;
    scanf("%d %d", &n, &m);
    v.push_back(new node(1, n));
    for(int i = 1; i <= m; i++) {
        scanf("%d", &type);
        if(type <= 2) {
            scanf("%d", &pos);
            type = 2 - type;
            v.push_back(v.back() -> clone());
            int k = query(v.back(), 1, n, pos, pos);
            if(k != type) updateSegment(v.back(), 1, n, pos, pos);
        }
        else if(type == 3) {
            scanf("%d %d", &l, &r);
            v.push_back(v.back() -> clone());
            updateSegment(v.back(), 1, n, l, r);
        }
        else if(type == 4) {
            scanf("%d", &pos);
            v.push_back(v[pos] -> clone());
        }
        else if(type == 5) {
            scanf("%d %d", &l, &r);
            v.push_back(v.back() -> clone());
            printf("%d\n", query(v.back(), 1, n, l, r));
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

#include <iostream>

#include <vector>

using namespace std;

struct node {

int value = 0;

node * right, * left;

int l, r;

int unPushed = 0;

node(int l, int r) : left(nullptr), right(nullptr), l(l), r(r) { }

node * clone() {

node * ans = new node(l, r);

ans -> right = right;

ans -> left = left;

ans -> value = value;

ans -> unPushed = unPushed;

return ans;

}

};

vector<node *> v;

int sum(node * left, node * right) {

int ans = 0;

if(left != nullptr) ans += left -> value;

if(right != nullptr) ans += right -> value;

return ans;

}

void push(node *(&k)) {

k -> unPushed %= 2;

if (k -> unPushed) {

int center = (k -> l + k -> r) / 2;

if (k -> left == nullptr) k -> left = new node(k -> l, center);

else k -> left = k -> left -> clone();

if (k -> right == nullptr) k -> right = new node(center + 1, k -> r);

else k -> right = k -> right -> clone();

++k -> left -> unPushed;

++k -> right -> unPushed;

k -> left -> value = (center - k -> l + 1) - k -> left -> value;

k -> right -> value = (k -> r - center) - k -> right -> value;

k -> unPushed = 0;

}

void updateSegment(node *(&k), int left, int right, int l, int r) {

if(k == nullptr) k = new node(left, right);

else k = k -> clone();

if(l > r) return;

if(l == left && r == right) {

++k -> unPushed;

k -> value = (r - l + 1) - k -> value;

return;

}

int center = (left + right) / 2;

push(k);

updateSegment(k -> left, left, center, l, min(r, center));

updateSegment(k -> right, center + 1, right, max(l, center + 1), r);

push(k -> left);

push(k -> right);

k -> value = sum(k -> left, k -> right);

}

void update(node *&k, int left, int right, int pos, int a) {

if (k == nullptr) k = new node(left, right);

else k = k -> clone();

if (left == right) {

k -> value = a;

return;

}

int center = (left + right) / 2;

push(k);

if(pos <= center) {

update(k -> left, left, center, pos, a);

push(k -> left);

}

else {

update(k -> right, center + 1, right, pos, a);

push(k -> right);

}

k -> value = sum (k -> left, k -> right);

}

int query(node *k, int left, int right, int l, int r) {

if (l > r) return 0;

if(k == nullptr) return 0;

if(left == l && r == right) return k -> value;

int center = (left + right) / 2;

push(k);

return query(k -> left, left, center, l, min(center, r)) + query(k -> right, center + 1, right, max(l, center + 1), r);

}

int main() {

int n, m, type, pos, l, r;

scanf("%d %d", &n, &m);

v.push_back(new node(1, n));

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

scanf("%d", &type);

if(type <= 2) {

scanf("%d", &pos);

type = 2 - type;

v.push_back(v.back() -> clone());

int k = query(v.back(), 1, n, pos, pos);

if(k != type) updateSegment(v.back(), 1, n, pos, pos);

}

else if(type == 3) {

scanf("%d %d", &l, &r);

v.push_back(v.back() -> clone());

updateSegment(v.back(), 1, n, l, r);

}

else if(type == 4) {

scanf("%d", &pos);

v.push_back(v[pos] -> clone());

}

else if(type == 5) {

scanf("%d %d", &l, &r);

v.push_back(v.back() -> clone());

printf("%d\n", query(v.back(), 1, n, l, r));

}

return 0;

}

Рішення

Спочатку потрібно декілька з’ясувати умову завдання, адже в ній не сказано за що відповідає перше число в кожному запиті. Це число — це номер операції, які задані в умові задачі, вони нумеруються від $1$ до $5.$ Це завдання будемо вирішувати за допомогою персистентного дерева відрізків. Зміст персистентного дерева відрізків в тому, що воно зберігає всі попередні версії самого дерева, тобто всі його стани після будь-яких модифікацій. Суть в тому, що коли ми спускаємося по дереву ми всього лише пройдемо максимум по $\log (n)$ його вершинах, що дає нам при запиті на модифікацію можливість не просто «тупо» скопіювати весь масив з $4 \cdot n$ елементів, а зберегти нову версію дерева, де зміняться лише $\log (n)$ вершин. Тобто сумарно $k \cdot \log (n)$ пам’яті замість $k \cdot n.$ Побудова персистентного дерева відрізків буде аналогічно побудові звичайного дерева відрізків за винятком того, що тепер для кожної вершини додатково доведеться в явному вигляді зберігати посилання на дочірні вершини. Додатково будемо зберігати вектор вершин, що є корінням у відповідних версіях дерева. При будові, в нього додамо єдину вершину, що є коренем отриманого дерева. Таким чином, складність побудови залишилася незмінною, а саме $O(n).$ При зміні вершини до нього будуть додані тільки ті вершини, які повинні були змінитися, і замість зміни значень старих вершин, перераховані значення будуть збережені в нові. Всі нові вершини будуть посилатися на одну вершину з дерева старої версії і на одну з щойно доданих. Тим самим, при запиті оновлення буде створено $O (\log (n))$ нових вершин, у тому числі буде створено новий корінь дерева відрізків, а вся попередня версія дерева, підвішена за старий корінь, залишиться без змін. Наприкінці потрібно зазанчити, що задача заходить на eolymp за часом лише з використанням функцій вводу/виводу scanf() та printf().

Посилання

ideone

e-olymp

Дерево відрізків на e-maxx

Related Images:

e-olymp 4852. Кратчайшее расстояние

23/05/2019 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Дан ориентированный граф. Найдите кратчайшее расстояние от вершины $x$ до всех остальных вершин графа.

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

В первой строке содержатся два натуральных числа $n$ и $x$ $(1 \leqslant n \leqslant 1000, 1 \leqslant x \leqslant n)$ — количество вершин в графе и стартовая вершина соответственно. Далее в $n$ строках по $n$ чисел — матрица смежности графа: в $i$-ой строке на $j$-ом месте стоит «$1$», если вершины $i$ и $j$ соединены ребром, и «$0$», если ребра между ними нет. На главной диагонали матрицы стоят нули.

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

Выведите через пробел числа $d_1$, $d_2$, …, $d_n$, где $d_i$ равно $-1$, если путей между $x$ и $i$ нет, в противном случае это минимальное рaсстояние между $x$ и $i$.

Тесты

#	Входные данные	Выходные данные
1	3 3 0 1 1 1 0 1 1 0 0	1 2 0
2	6 5 0 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0	2 2 1 1 0 -1
3	3 1 0 0 0 0 0 1 1 1 0	0 -1 -1

Код

#include <iostream>
#include <queue>
using namespace std;
int graph[1001][1001], d[1001];
queue <int> q;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, x, v;
    cin >> n >> x;
    x--;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        d[i] = -1;
    }
    q.push(x);
    d[x] = 0;
    while (!q.empty()) {
        v = q.front();
        q.pop();
        for (int i = 0; i < n; i++) {
            if (d[i] == -1 && graph[v][i]) {
                q.push(i);
                d[i] = d[v] + 1;
            }
        }
    } 
    for(int i = 0; i < n; i ++) {
        cout << d[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int graph[1001][1001], d[1001];

queue <int> q;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int n, x, v;

cin >> n >> x;

x--;

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

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

cin >> graph[i][j];

}

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

d[i] = -1;

}

q.push(x);

d[x] = 0;

while (!q.empty()) {

v = q.front();

q.pop();

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

if (d[i] == -1 && graph[v][i]) {

q.push(i);

d[i] = d[v] + 1;

}

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

cout << d[i] << " ";

}

return 0;

}

Решение

Данную задачу будем решать поиском в ширину. Сам граф будем хранить в двумерном массиве graph[][], в массиве d[] будем хранить кратчайшее расстояние между заданной вершиной и $i$-ой. В очереди queue <int> q будем хранить обрабатываемые вершины. В самом начале там будет хранится только наша исходная вершина, затем пока в очереди хранятся какие-либо вершины достаем верхнюю и смотрим ребра, выходящие из нее, если ранее вершины не были задействованными, то помещаем в конец очереди. Очередь опустеет, когда будут просмотрены все вершины, в которые можно попасть из исходной $x$. Сложность алгоритма $O(n)$.

Ссылки

ideone

e-olymp

Поиск в ширину на e-maxx

Related Images:

e-olymp 4844. Поиск общей подстроки

24/02/2019 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Дана строка [latex] A = [/latex] [latex] a_1a_2…a_n [/latex] и строка [latex] B = [/latex] [latex] b_1b_2…b_m [/latex]. Также дано число [latex] L [/latex].

Нужно узнать, есть ли у строк [latex] A [/latex] и [latex] B [/latex] общая подстрока длиной [latex] L [/latex].

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

В первых двух строках записаны строки [latex]A[/latex] и [latex]B[/latex], состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более [latex]100000[/latex] символов. В третьей строке записано целое число [latex]L (0 \leq L \leq 100000) [/latex] — длина общей подстроки.

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

В выходной файл выведите [latex]YES[/latex], если существует общая подстрока такой длины. В противном случае выведите [latex]NO[/latex].

Тесты

#	Входные данные	Выходные данные
1	saaa baaa 3	YES
2	raabc taaac 3	NO
3	aaaaaaaka akaa 3	YES
4	abcdfeg qwertycdfeg 10	NO

Код 1

#include <iostream>
#include <map>
using namespace std;
 
struct state {
    int len, link;
    map <char,int> next;
};
 
state st[2*100000]; 
int sz, last;
 
void sa_init() {
    sz = 0;
    last = 0;
    st[0].len = 0;
    st[0].link = -1;
    sz++;
}
 
void sa_extend (char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p;
    for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;
    if (p == -1) st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
 
int longest_common_string (string a, string b) {
    sa_init();
    for (int i = 0; i < a.length(); i++) sa_extend (a[i]);
    int v = 0, l = 0, best = 0, bestpos = 0;
    for (int i = 0; i < b.length(); i++) {
        while (v != 0 && ! st[v].next.count(b[i])) {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next.count(b[i])) {
            v = st[v].next[b[i]];
            l++;
        }
        if (l > best){
            best = l;
            bestpos = i;
        }
    }
    return best;
}
 
int main() {
    string a, b;
    int n;
    cin >> a >> b >> n;
    if (longest_common_string(a, b) >= n) cout << "YES";
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

struct state {

int len, link;

map <char,int> next;

};

state st[2*100000];

int sz, last;

void sa_init() {

sz = 0;

last = 0;

st[0].len = 0;

st[0].link = -1;

sz++;

}

void sa_extend (char c) {

int cur = sz++;

st[cur].len = st[last].len + 1;

int p;

for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;

if (p == -1) st[cur].link = 0;

else {

int q = st[p].next[c];

if (st[p].len + 1 == st[q].len) st[cur].link = q;

else {

int clone = sz++;

st[clone].len = st[p].len + 1;

st[clone].next = st[q].next;

st[clone].link = st[q].link;

st[q].link = st[cur].link = clone;

}

last = cur;

}

int longest_common_string (string a, string b) {

sa_init();

for (int i = 0; i < a.length(); i++) sa_extend (a[i]);

int v = 0, l = 0, best = 0, bestpos = 0;

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

while (v != 0 && ! st[v].next.count(b[i])) {

v = st[v].link;

l = st[v].len;

}

if (st[v].next.count(b[i])) {

v = st[v].next[b[i]];

l++;

}

if (l > best){

best = l;

bestpos = i;

}

return best;

}

int main() {

string a, b;

int n;

cin >> a >> b >> n;

if (longest_common_string(a, b) >= n) cout << "YES";

else cout << "NO";

return 0;

}

Решение 1

Суффиксный автомат

Создадим структуру struct state, которая будет хранить информацию о переходах. len — это длина строки (далее будем использовать, как длину строки в каком-то состоянии), link — это суффиксальная ссылка, список переходов будем хранить в контейнере map <char, int> next, где ключом будет выступать символ, а значением — номер состояния.. Сам суффиксный автомат будем хранить в массиве этой структуры. Заведем переменные last и sz, отвечающие за последнее состояние и номер нового состояния соответственно.

Нам потребуется функция инициализирующая суффиксный автомат sa_init(). Так как вначале состояние лишь одно, то его длина равна [latex]0[/latex], а суффиксную ссылку приравняем к [latex]-1[/latex].

В автомат будем добавлять символы поочередно, для чего нам потребуется еще одна функция sa_extend(). В начале которой будем присваивать новому состоянию соответствующий номер. А затем будем просматривать все переходы из последнего состояния по текущему символу. Таким образом переход либо будет, либо нет. Если его нет, то добавим его в текущее состояние cur и продолжим смотреть дальше, если же при этом мы дошли до состояния, на которое указывает суффиксная ссылка изначального состояния (нулевого), то суффиксную ссылку текущего состояния приравняем к нулю. Далее рассматриваем случай, когда из текущего состояния по символу переход существует, обозначим q за состояние, куда ведет переход.

Поиск наибольшей общей подстроки

Сначала для строки a построим суффиксный автомат. Заведем две переменные, благодаря которым найдем совпадающую часть двух строк. Для этого нужна переменная, отвечающая за состояние v и переменная, отвечающая за длину совпадающей части l. Если есть переход, то переходим и увеличиваем длину на 1. Если нету, то уменьшаем длину совпадающей подстроки и переходим в новое состояние, меняя l. Цикл будет работать до тех пор, пока не найдем переход. Однако, если по суффиксным ссылкам мы дошли до состояния, в которое ведет ссылка изначальной вершины, то символ не встретился. Теперь длина наибольшей общей подстроки bestpos — это максимум из всех значений l.

Код 2

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    char a[100001], b[100001]; 
    int l1, l2, l, k = 0;
    cin >> a >> b >> l;
    l1 = strlen(a);
    l2 = strlen(b);
    if (l1 < l || l2 < l) cout << "NO";
    else {
        for (int i = 0; i < l1; i ++) {
            for (int j = i; j <= l ; j ++) {
                if (a[j] == b[j]) k ++;
                else i ++;
                if (k == l) {
                    cout << "YES";
                    return 0;
                }
            }
            k = 0;
        }
        cout << "NO";
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char a[100001], b[100001];

int l1, l2, l, k = 0;

cin >> a >> b >> l;

l1 = strlen(a);

l2 = strlen(b);

if (l1 < l || l2 < l) cout << "NO";

else {

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

for (int j = i; j <= l ; j ++) {

if (a[j] == b[j]) k ++;

else i ++;

if (k == l) {

cout << "YES";

return 0;

}

k = 0;

}

cout << "NO";

}

return 0;

}

Решение 2

Стоит отметить сразу, что данный код, по сути не работает на некоторых тестах, например когда символы, которые должны входить в искомую наибольшую подстроку, стоят в начале или конце обоих строк или хотя бы одной из них. Однако, как показывает практика, тесты на e-olymp данный способ посимвольного сравнения проходит. В данном варианте решения будем использовать c-string. Сами строки объявлены так: char a[100001], b[100001];, где [latex]100001[/latex] — это максимальная длина строки, которая может быть по условию задачи, и еще [latex]+1[/latex]. Объявить можно было еще и так: char * a = new char [100001];

Ссылки

Related Images:

e-olymp 4557. Одинокий король

21/12/2018 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Одинокий король долго бродил по бесконечной шахматной доске. Известна последовательность из $n$ его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.) — возможные ходы короля показаны на рисунке снизу.
Определите, побывал ли король дважды на одном и том же поле за свои [latex] n [/latex] ходов.

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

В первой строке задано общее число ходов короля [latex] n [/latex] [latex](0 ≤ n ≤ 1000)[/latex]. В последующих [latex] n [/latex] строках заданы направления перемещения короля: строка под номером [latex] i + 1 [/latex] задаёт направление перемещения короля на [latex]i[/latex]-ом ходу.

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

Выведите единственное число — номер хода, на котором король впервые попал на какую-то клетку во второй раз. Если же такое событие не произошло, то в первой строке выведите сообщение «Ok» (без кавычек), а во второй — манхэттенское расстояние между начальной и конечной точками путешествия одинокого короля.
Напоминаем, что манхэттенское расстояние между точками с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] определяется по формуле: [latex]d = |x_2 — x_1| + |y_2 — y_1|[/latex].

Тесты

#	Входные данные	Выходные данные
1	5 1 2 4 7 4	4
2	5 1 2 4 6 4	Ok 2
3	3 1 2 1	Ok 5
4	3 1 5 1	2
5	8 8 8 8 8 8 8 8 8	Ok 8

Код

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

int main() {
    int *x, *y, n, pos, x1 = 0, y1 = 0;
    bool f = true;
    cin >> n;
    x = new int [n];
    y = new int [n];
    for (int i = 1; i <= n; i ++){
        cin >> pos;
        if (pos == 1){
            x1 -= 1;
            y1 += 1;
        }
        else if (pos == 2) y1 += 1;
        else if (pos == 3){
            x1 += 1;
            y1 += 1;
        }
        else if (pos == 4) x1 += 1;
        else if (pos == 5){
            x1 += 1;
            y1 -= 1;
        }
        else if (pos == 6) y1 -= 1;
        else if (pos == 7){
            x1 -= 1;
            y1 -= 1;
        }
        else if (pos == 8) x1 -= 1;
        x[i] = x1;
        y[i] = y1;
    }
    for (int i = 1; i < n && f; i++)
        for (int j = 0; j < i; j++)
            if ((x[i] == x[j]) && (y[i] == y[j])){
                cout << i; 
                f = false;
            }
    if (f) cout << "Ok" << endl << abs(x[n]) + abs(y[n]);
    delete []x;
    delete []y;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int *x, *y, n, pos, x1 = 0, y1 = 0;

bool f = true;

cin >> n;

x = new int [n];

y = new int [n];

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

cin >> pos;

if (pos == 1){

x1 -= 1;

y1 += 1;

}

else if (pos == 2) y1 += 1;

else if (pos == 3){

x1 += 1;

y1 += 1;

}

else if (pos == 4) x1 += 1;

else if (pos == 5){

x1 += 1;

y1 -= 1;

}

else if (pos == 6) y1 -= 1;

else if (pos == 7){

x1 -= 1;

y1 -= 1;

}

else if (pos == 8) x1 -= 1;

x[i] = x1;

y[i] = y1;

}

for (int i = 1; i < n && f; i++)

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

if ((x[i] == x[j]) && (y[i] == y[j])){

cout << i;

f = false;

}

if (f) cout << "Ok" << endl << abs(x[n]) + abs(y[n]);

delete []x;

delete []y;

return 0;

}

Решение

За изначальное местоположение короля возьмем точку с координатами [latex](0, 0)[/latex], а все передвижения короля по шахматной доске — это изменение абсциссы и (или) ординаты данной точки. Создадим два динамических массива x = new int [n]; и y = new int [n]; на [latex] n [/latex] элементов каждый, для абсцисс и ординат соответственно. Они будут хранить изменения координат всех точек, в которых побывал король. При этом, так как мы считаем, что начинаем движение с начала координат начнем заполнение массивов со второго элемента. Когда массивы в цикле for (int i = 1; i <= n; i ++); заполнятся будем искать совпадающие точки в другом цикле, если же таких не найдется, посчитаем расстояние между конечным и начальным местоположением короля, однако так как начальное местоположение короля — это начало координат, то ограничимся лишь немного упрощенной формулой [latex]d = |x_n| + |y_n|[/latex], или же в коде это выглядит так: abs(x[n]) + abs(y[n]);. После, не забываем удалить уже использованные массивы, чтобы освободить память.

Код 2

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

int main() {
    int *x, n, pos, x1 = 0, y1 = 0;
    bool f = true;
    cin >> n;
    int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};
    int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};
    x = new int [2*n+2];
    for (int i = 2; i < (2 * n + 2); i += 2){
        cin >> pos;
        x1 += X[pos-1];
        y1 += Y[pos-1];
        x[i] = x1;
        x[i+1] = y1;
    }
    for (int i = 0; i < (2 * n + 2) && f; i += 2)
        for (int j = 0; j < i; j += 2)
            if ((x[i] == x[j]) && (x[i+1] == x[j+1])){
                cout << i / 2; 
                f = false;
            }
    if (f) cout << "Ok" << endl << abs(x[2*n+1]) + abs(x[2*n]);
    delete []x;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int *x, n, pos, x1 = 0, y1 = 0;

bool f = true;

cin >> n;

int X[] = {-1, 0, 1, 1, 1, 0, -1, -1};

int Y[] = {1, 1, 1, 0, -1, -1, -1, 0};

x = new int [2*n+2];

for (int i = 2; i < (2 * n + 2); i += 2){

cin >> pos;

x1 += X[pos-1];

y1 += Y[pos-1];

x[i] = x1;

x[i+1] = y1;

}

for (int i = 0; i < (2 * n + 2) && f; i += 2)

for (int j = 0; j < i; j += 2)

if ((x[i] == x[j]) && (x[i+1] == x[j+1])){

cout << i / 2;

f = false;

}

if (f) cout << "Ok" << endl << abs(x[2*n+1]) + abs(x[2*n]);

delete []x;

return 0;

}

Решение 2

Данный способ будет отличаться тем, что в отличии от предыдущего решения мы ограничимся лишь одним массивом, содержащим попарно координаты абсцисс и ординат соответственно. Также операторы if(); можно заменить массивами X[]; и Y[]; , которые на соответствующих местах уже содержат изменение абсциссы и ординаты положения короля при конкретном перемещении.

Код 3

#include <iostream>
#include <cmath>
using namespace std;
 
int x[2001][2001];
 
int main() {
    int n;
    cin >> n;
    int pos;
    bool f = true;
    int x1 = 1001, y1 = 1001;
    for (int i = 0; i< n && f; i++){
        cin >> pos;
        if(x[x1][y1] == 1){ 
            cout << i;
            f = false;
        }
        else x[x1][y1] = 1;
        switch (pos){
            case 1: x1--; y1++; break;
            case 3: x1++;
            case 2: y1++; break;
            case 4: x1++; break;
            case 5: x1++;
            case 6: y1--; break;
            case 7: y1--; 
            case 8: x1--;
        }
    }
    if (f) cout << "Ok" << endl << abs(x1-1001) + abs(y1-1001);
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int x[2001][2001];

int main() {

int n;

cin >> n;

int pos;

bool f = true;

int x1 = 1001, y1 = 1001;

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

cin >> pos;

if(x[x1][y1] == 1){

cout << i;

f = false;

}

else x[x1][y1] = 1;

switch (pos){

case 1: x1--; y1++; break;

case 3: x1++;

case 2: y1++; break;

case 4: x1++; break;

case 5: x1++;

case 6: y1--; break;

case 7: y1--;

case 8: x1--;

}

if (f) cout << "Ok" << endl << abs(x1-1001) + abs(y1-1001);

return 0;

}

Решение 3

Изначально создаем двумерный массив заполненый нулями. Однако будем считать изначальное положение короля в точке с координатами [latex](1001, 1001)[/latex], чтобы не было проблем с отрицательными значениями. В данном варианте кода для большей краткости и разнообразия будем использовать оператор switch();. Если король в клетке не был, то поставим [latex]1[/latex], если же был — выводим номер хода. Высчитываем манхэттенское расстояние если король не был в одной точке дважды.

Ссылки

Засчитанное решение 1 на e-olymp.
Засчитанное решение 2 на e-olymp.
Засчитанное решение 3 на e-olymp.
Код 1 в ideone.
Код 2 в ideone.
Код 3 в ideone.

Related Images:

e-olymp 479. Вышивка “крестиком”

28/11/2018 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

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

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

Сначала кол-во макетов, потом их номера. Все номера узоров у Вали имели одну странность — всегда были нечетными и не превышали 80.

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

Макеты, в порядке, перечисленном во входном файле, разделенные пустой строкой.

Тесты

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

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

2 3 5

X X
X
X X

X X
X X
X
X X
X X

1 9

X X
X X
X X
X X
X
X X
X X
X X
X X

Код

#include <iostream>
using namespace std;
 
int main() {
    int n, x;
    cin >> n;
    for (int l = 0; l < n; l ++){
        cin >> x;
        for (int j = 0; j < x; j ++){
            for (int i = 0; (i <= j) or (i <= x - 1 - j); i ++){
                if ((i == j) or (j == x - 1 - i)) cout << "X";
                else cout << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, x;

cin >> n;

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

cin >> x;

for (int j = 0; j < x; j ++){

for (int i = 0; (i <= j) or (i <= x - 1 - j); i ++){

if ((i == j) or (j == x - 1 - i)) cout << "X";

else cout << " ";

}

cout << endl;

}

cout << endl;

}

return 0;

}

Решение

В данной задаче будем использовать потоковую обработку. Сначала считываем количество макетов [latex] n [/latex]. Затем в цикле for (int l = 0; l < n; l ++); считываем номера узоров. Выводить [latex] X [/latex] будем по диагоналям (справа налево и наоборот). Однако, стоит учесть, что после последнего символа [latex] X [/latex] в строке, выводить пробел не стоит. В условии задачи данный факт не фигурирует, однако, если же сделать иначе, то задача на сайте e-olymp не пройдет. Из этого вытекает, что пробелы должны располагаться исключительно до последнего крестика в строке. Для этого во внутреннем цикле ставим соответсвующее условие, чтобы при достижении последнего крестика в строке осуществлялся переход на другую строку, если это возможно. Также стоит не забыть, что между разными узорами нужно пропускать строку.

Ссылки

Засчитанное решение на e-olymp.

Код в ideone.

Related Images:

e-olymp 1452. Кролики

14/10/2018 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Как-то наконец земляне нашли обитаемую планету, назвали ее ТТВ, и отправили вместе с кораблем туда одного кролика. Кролику понравился климат новой планеты и через месяц он произвел на свет еще одного кролика. Известно, что каждый месяц каждый кролик, присутствующий на планете, производил на свет еще одного кролика. На планете откуда-то взялся монстр, который в начале месяца съедал [latex] k [/latex] кроликов, если только их становилось строго больше [latex] k [/latex]. В задаче необходимо определить количество кроликов, которое будет на планете через [latex] n [/latex]месяцев после прибытия туда космического корабля с первым кроликом.

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

Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex] (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.

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

Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].

Тесты

#	Входные данные	Выходные данные
1	0 10	1
2	1 10	2
3	10 7	128
4	7 128	12
5	30 0	1073741824
6	29 29	2
7	20 20	16
8	90 90	64

Cпособ 1 (с циклом)

Код

#include <iostream>
using namespace std;
 
int main() {
    long int r = 1, n, k;
    cin >> n >> k;
    for (int i = n; i > 0; i--){
        if (r > k) r -= k;
        r *= 2;
    }
    cout << r;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int r = 1, n, k;

cin >> n >> k;

for (int i = n; i > 0; i--){

if (r > k) r -= k;

r *= 2;

}

cout << r;

return 0;

}

Решение

Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex] k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.

Способ 2 (без цикла)

Код

#include <iostream>
using namespace std;

int f2(long int r, long int n, long int k){
    if (n == 0) return r;
    if (r <= k) return f2(r * 2, n - 1, k);
    return f2(2 * (r-k), n - 1, k);
}   

int main() {
    long int n, k, r = 1;
    cin >> n >> k;
    cout << f2(r, n, k);
    return 0;
}

#include <iostream>

using namespace std;

int f2(long int r, long int n, long int k){

if (n == 0) return r;

if (r <= k) return f2(r * 2, n - 1, k);

return f2(2 * (r-k), n - 1, k);

}

int main() {

long int n, k, r = 1;

cin >> n >> k;

cout << f2(r, n, k);

return 0;

}

Решение

Сам алгоритм похож на 1 способ, однако здесь мы будем использовать рекурсивную функцию, а не цикл. Функция int f2(); будет вызывать сама себя до тех пор, пока количество месяцев [latex] n [/latex] не станет равным нулю.

Ссылки

Засчитанное решение на e-olymp.

1 Код в ideone.

2 Код в ideone.

Related Images:

e-olymp 939. Квадрат суммы

15/09/2018 by Владимир Дроздин

Задача взята с сайта e-olimp.

Задача

Найти квадрат суммы цифр двузначного натурального числа.

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

Одно натуральное двузначное число.

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

Квадрат суммы цифр заданного числа.

Тесты

#	Входный данные	Выходные данные
1	23	25
2	25	49
3	36	81
4	60	36
5	99	324

Код

#include <iostream>
using namespace std;

int main() {
    int n, c2, c1;
    cin >> n;
    c2 = n % 10;
    c1 = n / 10;
    cout << (c2 + c1) * (c2 + c1) << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, c2, c1;

cin >> n;

c2 = n % 10;

c1 = n / 10;

cout << (c2 + c1) * (c2 + c1) << endl;

return 0;

}

Решение

Разобьем двузначное натуральное число [latex] n [/latex] на два числа, содержащих соответственно его первую цифру ( [latex] c_1 [/latex] ) и вторую — ( [latex] c_2 [/latex] ), где [latex] c_2 = n \mod 10[/latex], в то время как [latex] c_1 = \frac {n} {10} [/latex]. Теперь, чтобы получить квадрат суммы цифр двузначного натурального числа, сложим два эти числа и умножим еще раз на их сумму [latex] (c_2 + c_1) \cdot (c_2 + c_1) [/latex].

Ссылки

ideone

e-olymp