e-olymp 1060. Линии

28/06/2016 by Кондратюк Настя

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

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

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

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

В первой строке находится число [latex]n \left (2\leq n\leq 40 \right )[/latex], в каждой из следующих [latex]n[/latex] строк — по [latex]n[/latex] символов. Символом точки обозначена свободная клетка, латинской заглавной [latex]O[/latex] — шарик, [latex]@[/latex] — исходное положение шарика, который должен двигаться, латинской заглавной [latex]X[/latex] — конечное положение шарика.

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

В первой строке выводится [latex]Y[/latex], если движение возможно, или [latex]N[/latex], если нет. Если движение возможно далее следует [latex]n[/latex] строк по [latex]n[/latex] символов — как и на вводе, но [latex]X[/latex], а также все точки на пути заменяются плюсами.

Тесты

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

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

5
....X
.OOOO
.....
OOOO.
@....

....X

.OOOO

.....

OOOO.

@....

Y
+++++
+OOOO
+++++
OOOO+
@++++

+++++

+OOOO

+++++

OOOO+

@++++

5
..X..
.....
OOOOO
.....
..@..

..X..

.....

OOOOO

.....

..@..

N

5
...X.
.....
O.OOO
.....
....@

...X.

.....

O.OOO

.....

....@

Y
..++.
.++..
O+OOO
.++++
....@

..++.

.++..

O+OOO

.++++

....@

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

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

/* нахождение пути*/
void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){
    if(!visited[row][col]){
        /* проверяем не вышли ли мы за границы лабиринта, есть ли клетка 
        в массиве посещенных и можно ли через нее пройти*/
        if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&
            (lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {
                path[row+1][col] = path[row][col] + 1;
                plan.push(row+1);
                plan.push(col);
        }
        if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] && 
            (lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {
                path[row-1][col] = path[row][col] + 1;
                plan.push(row-1);
                plan.push(col);
        }
        if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] && 
            (lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {
                path[row][col+1] = path[row][col] + 1;
                plan.push(row);
                plan.push(col+1);
        }
        if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] && 
            (lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {
                path[row][col-1] = path[row][col] + 1;
                plan.push(row);
                plan.push(col-1);
        }
        visited[row][col] = 1; /* отмечаем клетку в которой побывали */
    }
}
 
int main() {
    int n, x_start, y_start, x_end, y_end, x, y;
    queue <int> plan; 
    cin >> n;
    char** lab = new char* [n];
    int** visited = new int * [n];
    int** path = new int * [n];
    for(int i=0; i<n; i++){
        lab[i] = new char [n];   /* массив для хранения лабиринта */
        visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/
        path[i] = new int [n];  /* массив для хранения найденных путей */
        for(int j=0; j<n; j++){
            visited[i][j] = 0;  
            path[i][j] = -1;   
            cin >> lab[i][j]; 
            if (lab[i][j] == '@') { /* находим начало пути*/
                x_start = i;
                y_start = j;
                plan.push(i);  /* заносим начальную клетку */
                plan.push(j);  /* в план посещения */
                path[i][j] = 1;
            }
            else if (lab[i][j] == 'X') { /* находим конечную точку */
                x_end = i;
                y_end = j;
            }
        }
    }
    while(!plan.empty()){ /* пока очередь посещения клеток непустая*/
        x=plan.front();
        plan.pop();
        y=plan.front();
        plan.pop();
        find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/
    }
    if(!visited[x_end][y_end]){
        cout << "N" << endl;
    }
    else {
        cout << "Y" << endl;
            x = x_end;
            y = y_end;
            lab[x][y] = '+';
            while (path[x][y] != 2) { /* восстановление пути*/
                if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {
                    x = x-1;
                    lab[x][y] = '+';
                }
                else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {
                    x = x+1;
                    lab[x][y] = '+';
                }
                else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {
                    y = y-1;
                    lab[x][y] = '+';
                }
                else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {
                    y = y+1;
                    lab[x][y] = '+';
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    cout << lab[i][j];
                }
                cout << endl;
            }
        }
    return 0;
}

100

101

102

103

104

105

106

107

#include <iostream>

#include <queue>

using namespace std;

/* нахождение пути*/

void find_path(int n, int row, int col, char** lab, int** visited, int** path, queue<int>& plan){

if(!visited[row][col]){

/* проверяем не вышли ли мы за границы лабиринта, есть ли клетка

в массиве посещенных и можно ли через нее пройти*/

if ((row+1) < n && (row+1) >= 0 && !visited[row+1][col] &&

(lab[row+1][col] == '.' || lab[row+1][col] == 'X')) {

path[row+1][col] = path[row][col] + 1;

plan.push(row+1);

plan.push(col);

}

if((row-1) < n && (row-1) >= 0 && !visited[row-1][col] &&

(lab[row-1][col] == '.' || lab[row-1][col] == 'X')) {

path[row-1][col] = path[row][col] + 1;

plan.push(row-1);

plan.push(col);

}

if((col + 1) < n && (col + 1) >= 0 && !visited[row][col+1] &&

(lab[row][col+1] == '.' || lab[row][col+1] == 'X')) {

path[row][col+1] = path[row][col] + 1;

plan.push(row);

plan.push(col+1);

}

if((col - 1) < n && (col - 1) >= 0 && !visited[row][col-1] &&

(lab[row][col-1] == '.' || lab[row][col-1] == 'X')) {

path[row][col-1] = path[row][col] + 1;

plan.push(row);

plan.push(col-1);

}

visited[row][col] = 1; /* отмечаем клетку в которой побывали */

}

int main() {

int n, x_start, y_start, x_end, y_end, x, y;

queue <int> plan;

cin >> n;

char** lab = new char* [n];

int** visited = new int * [n];

int** path = new int * [n];

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

lab[i] = new char [n]; /* массив для хранения лабиринта */

visited[i] = new int [n]; /* массив для хранения информации о посещении клеток*/

path[i] = new int [n]; /* массив для хранения найденных путей */

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

visited[i][j] = 0;

path[i][j] = -1;

cin >> lab[i][j];

if (lab[i][j] == '@') { /* находим начало пути*/

x_start = i;

y_start = j;

plan.push(i); /* заносим начальную клетку */

plan.push(j); /* в план посещения */

path[i][j] = 1;

}

else if (lab[i][j] == 'X') { /* находим конечную точку */

x_end = i;

y_end = j;

}

while(!plan.empty()){ /* пока очередь посещения клеток непустая*/

x=plan.front();

plan.pop();

y=plan.front();

plan.pop();

find_path(n, x, y, lab, visited, path, plan); /* продолжаем поиск пути*/

}

if(!visited[x_end][y_end]){

cout << "N" << endl;

}

else {

cout << "Y" << endl;

x = x_end;

y = y_end;

lab[x][y] = '+';

while (path[x][y] != 2) { /* восстановление пути*/

if ((x-1) >= 0 && (x-1) < n && (path[x-1][y] == path[x][y] - 1)) {

x = x-1;

lab[x][y] = '+';

}

else if ((x+1) >= 0 && (x+1) < n && (path[x+1][y] == path[x][y] - 1)) {

x = x+1;

lab[x][y] = '+';

}

else if ((y-1) >= 0 && (y-1) < n && (path[x][y-1] == path[x][y] - 1)) {

y = y-1;

lab[x][y] = '+';

}

else if ((y+1) >= 0 && (y+1) < n && (path[x][y+1] == path[x][y] - 1)) {

y = y+1;

lab[x][y] = '+';

}

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

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

cout << lab[i][j];

}

cout << endl;

}

return 0;

}

ideone.com

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

Решение

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

Затем, если клетка с конечным положением шарика достижима, необходимо восстановить кратчайший путь. Двигаясь от конечной позиции в начальную, на каждом шаге выбираем клетку значение которой на единицу меньше текущего положения, при этом символы в соответствующих клетках исходного лабиринта заменяем на символ [latex]+.[/latex]

Related Images:

e-olymp 2941. Дима и массив

27/06/2016 by Кондратюк Настя

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

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

Мама подарила мальчику Диме массив длины [latex]n[/latex]. Массив этот не простой, а особенный. Дима может выбрать два числа [latex]i[/latex] и [latex]d[/latex] ([latex]1\leq i\leq n[/latex], [latex]-1000\leq d\leq 1000[/latex]), и элемент с индексом [latex]i[/latex] магически становится равным [latex]d[/latex]. Дима играет со своим массивом, а мама время от времени задает ему вопросы — какова сумма всех чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex]? Дима легко справился с этими вопросами, сможете ли Вы?

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

В первой строке находятся два целых числа [latex]n[/latex] и [latex]q[/latex] [latex]1\leq n\leq 5\cdot 10^{5},~1\leq q\leq 10^{5}[/latex] — количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано [latex]n[/latex] чисел [latex]a_{1},a_{2},\ldots,a_{n}[/latex] [latex]\left ( -1000\leq a_{i}\leq 1000 \right )[/latex] — начальное состояние массива. В следующих [latex]q[/latex] строках заданы операции и запросы. Первый символ в строке может быть [latex]=[/latex] или [latex]?[/latex]. Если строка начинается с [latex]=[/latex], то это операция присваивания. Далее следуют [latex]i[/latex] и [latex]d[/latex], ограничения на которые описаны в условии. Если строка начинается с [latex]?[/latex], то это запрос. Далее следуют числа [latex]f[/latex] и [latex]t[/latex] [latex]\left (1\leq f,~t\leq n \right )[/latex].

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

Для каждого запроса выведите сумму чисел в массиве с индексами от [latex]f[/latex] до [latex]t[/latex], по одному результату в строке.

Тесты

Входные данные	Выходные данные
3 3 1 2 3 ? 1 3 = 3 2 ? 1 3	6 5
5 3 1 2 3 4 5 ? 1 5 = 1 7 ? 1 3	15 12
5 6 1 2 3 4 5 ? 1 5 = 1 0 ? 1 5 = 2 7 ? 1 5 ? 1 3	15 14 19 10

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

#include <iostream>
using namespace std;
 
// построение дерева 
void build (int tree[], int arr[], int v, int left, int right) {   
    if (left != right) {
        int middle = (left + right) / 2;
        build (tree, arr, v*2, left, middle);
        build (tree, arr, v*2+1, middle+1, right);
        tree[v] = tree[v*2] + tree[v*2+1];
    } else tree[v] = arr[left];}
 
// запрос суммы
int sum (int tree[], int v, int left, int right, int from, int to) { 
    if (from > to) return 0;
    if (from == left && to == right) return tree[v];
    int middle = (left + right) / 2;
    return sum(tree,v*2,left,middle,from,min(to,middle))+sum(tree,v*2+1,middle+1,right,max(from,middle+1),to);
}
 
// операция присваивания
void update (int tree[], int v, int left, int right, int index, int new_val) { 
    if (left != right) {
        int middle = (left + right) / 2;
        if (index <= middle) update (tree, v*2, left, middle, index, new_val);
        else update (tree, v*2+1, middle+1, right, index, new_val);
        tree[v] = tree[v*2] + tree[v*2+1];
    } else tree[v] = new_val;
}

int main() {
    int n, q, i, d, from, to;
    char query;
    cin >> n >> q;
    int size = 2*n; /* максимальный размер дерева*/
    int arr[n], tree[size];
    for(int i = 0; i < n; i++) cin >> arr[i];
    /* передаем функции построения массив для записи дерева, исходный массив, 
       корень и границы отрезка, принадлежащего корню */
    build(tree, arr, 1, 0, n-1); 
    for (q; q>0; q--) {
        cin >> query;
        if (query == '=') {
            cin >> i >> d;
            update(tree, 1, 0, n-1, i-1, d); 
        } else if (query == '?') {
            cin >> from >> to;
            cout << sum(tree, 1, 0, n-1, from-1, to-1) << endl;
        }
    }
}

#include <iostream>

using namespace std;

// построение дерева

void build (int tree[], int arr[], int v, int left, int right) {

if (left != right) {

int middle = (left + right) / 2;

build (tree, arr, v*2, left, middle);

build (tree, arr, v*2+1, middle+1, right);

tree[v] = tree[v*2] + tree[v*2+1];

} else tree[v] = arr[left];}

// запрос суммы

int sum (int tree[], int v, int left, int right, int from, int to) {

if (from > to) return 0;

if (from == left && to == right) return tree[v];

int middle = (left + right) / 2;

return sum(tree,v*2,left,middle,from,min(to,middle))+sum(tree,v*2+1,middle+1,right,max(from,middle+1),to);

}

// операция присваивания

void update (int tree[], int v, int left, int right, int index, int new_val) {

if (left != right) {

int middle = (left + right) / 2;

if (index <= middle) update (tree, v*2, left, middle, index, new_val);

else update (tree, v*2+1, middle+1, right, index, new_val);

tree[v] = tree[v*2] + tree[v*2+1];

} else tree[v] = new_val;

}

int main() {

int n, q, i, d, from, to;

char query;

cin >> n >> q;

int size = 2*n; /* максимальный размер дерева*/

int arr[n], tree[size];

for(int i = 0; i < n; i++) cin >> arr[i];

/* передаем функции построения массив для записи дерева, исходный массив,

корень и границы отрезка, принадлежащего корню */

build(tree, arr, 1, 0, n-1);

for (q; q>0; q--) {

cin >> query;

if (query == '=') {

cin >> i >> d;

update(tree, 1, 0, n-1, i-1, d);

} else if (query == '?') {

cin >> from >> to;

cout << sum(tree, 1, 0, n-1, from-1, to-1) << endl;

}

ideone.com

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

Решение

Для решения данной задачи необходимо воспользоваться структурой данных «дерево отрезков».

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

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

Для выполнения запроса суммы также используется рекурсивная функция. Она запускается либо от правого, либо от левого сына текущей вершины, если границы исходного запроса лежат в одном из их отрезков. Либо запускается от обоих сыновей, если границы исходного запроса принадлежат пересечению их отрезков, суммируя результаты двух запросов. Таким образом функция доходит до отрезка, границы которого совпадают с текущим запросом или до листа и возвращает их значение.

Для решения данной задачи были использованы материалы сайта e-maxx.ru.

Related Images:

e-olymp 1342. Периодические строки

24/04/2016 by Кондратюк Настя

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

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

Будем говорить, что символьная строка имеет период [latex]k[/latex], если она может быть образована путем объединения одной или нескольких одинаковых строк длиной [latex]k[/latex]. Например, строка «[latex]abcabcabcabc[/latex]» имеет период [latex]3[/latex], так как она может быть образована путём объединения [latex]4[/latex]-х строк «[latex]abc[/latex]». Она также имеет период [latex]6[/latex] (объединение двух строк «[latex]abcabc[/latex]») и [latex]12[/latex] (сама строка «[latex]abcabcabcabc[/latex]»).

Напишите программу определяющую наименьший период заданной строки.

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

В первой строке задано количество тестовых случаев [latex]N[/latex] во входных данных. Каждый тестовый случай размещен в отдельной строке и содержит не более [latex]80[/latex] символов без пробелов.

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

Вывести для каждого тестового случая искомое значение наименьшего периода строки. Разные тестовые случаи должны быть разделены пустой строкой.

Тесты

Входные данные	Выходные данные
2 HoHoHo mama	2 2
2 abcdefg abcabcabc	7 3
3 b bbb bbbbb	1 1 1

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

    #include <iostream>
    #include <cstring>
    using namespace std;
     
    int strPeriod(char *str){
        int period;
        period = strlen(str); // 
        for(int i=1; i<=(strlen(str)/2); i++){ /* разбиваем строку                    
                                                 на подстроки*/
                int j;
            for(j=0; j<strlen(str)-i; ){ /* ограничение номера символа,
                                              чтобы не выйти за границы строки*/
                if(str[j] == str[j+i]){
                    j++;
                }
                else{
                    break;
                }
            }
        if(j == (strlen(str) - i)){  /* если цикл дошел до конца 
                                        строки - период найден*/
                    period = i;
                    break;
            }
        }
     
        return period;
    }
     
    int main() {
        const int n = 81;
        int tests;
        cin >> tests;
        cin.ignore(1, ' '); /* пропуск символа перехода на новую строку*/
        char *str = new char[n];
        for(int j=0; j<tests; j++){
            cin.getline(str, n);
            cout << strPeriod(str);
            if(j != tests - 1){
                cout << endl << endl;
            }
        }
        return 0;
    }

#include <iostream>

#include <cstring>

using namespace std;

int strPeriod(char *str){

int period;

period = strlen(str); //

for(int i=1; i<=(strlen(str)/2); i++){ /* разбиваем строку

на подстроки*/

int j;

for(j=0; j<strlen(str)-i; ){ /* ограничение номера символа,

чтобы не выйти за границы строки*/

if(str[j] == str[j+i]){

j++;

}

else{

break;

}

if(j == (strlen(str) - i)){ /* если цикл дошел до конца

строки - период найден*/

period = i;

break;

}

return period;

}

int main() {

const int n = 81;

int tests;

cin >> tests;

cin.ignore(1, ' '); /* пропуск символа перехода на новую строку*/

char *str = new char[n];

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

cin.getline(str, n);

cout << strPeriod(str);

if(j != tests - 1){

cout << endl << endl;

}

return 0;

}

ideone.com

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

Решение

Строка длины [latex]s[/latex] может быть образована подстрокой, длина которой не превышает половины длины строки. Следовательно, период лежит в промежутке [latex]\left [ 1;s/2 \right ][/latex], либо равен длине строки. Последовательно разбивая строку на подстроки длиной от [latex]1[/latex] до [latex]s/2[/latex], проверяем равны ли они между собой. Если такие подстроки не нашлись, то период равен длине строки.

Related Images:

A294

30/03/2016 by Кондратюк Настя

С.А.Абрамов. Задачи по программированию.

Задача

Даны действительные числа [latex]r_{1},\ldots,r_{n}[/latex], среди которых заведомо есть как отрицательные, так и не отрицательные. Получить [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex], где [latex]x_{1},\ldots,x_{p}[/latex] — отрицательные члены последовательности [latex]r_{1},\ldots,r_{n}[/latex], взятые в порядке следования, [latex]y_{1},\ldots,y_{q}[/latex] — неотрицательные члены, взятые в обратном порядке, [latex]s=min\left ( p,q \right )[/latex] .

Тесты

Входные данные	Выходные данные
-1 1	-1
-1	0
-1 -1	0
1 2 -5 10 -2	-54
4 6 3 4 -8 2 7 5	-40

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

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

int main() {
	double r, sum=0;
	int s;
	vector <double> x;
	vector <double> y;
	while(cin >> r){
		if(r<0){
			x.push_back(r);
		}
		else y.push_back(r);
	}
	s = min(x.size(), y.size());
	for(int i=0; i < s; i++){
		sum += x[i] * y.back();/* умножение отрицательных чисел в порядке 
                следования на неотрицательные в обратном порядке */
		y.pop_back();
	}
	cout << sum;
	return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

double r, sum=0;

int s;

vector <double> x;

vector <double> y;

while(cin >> r){

if(r<0){

x.push_back(r);

}

else y.push_back(r);

}

s = min(x.size(), y.size());

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

sum += x[i] * y.back();/* умножение отрицательных чисел в порядке

следования на неотрицательные в обратном порядке */

y.pop_back();

}

cout << sum;

return 0;

}

ideone.com

Решение

Считывая числа из входного потока, выполняем проверку и записываем положительные в вектор [latex]y[/latex], отрицательные — в вектор [latex]x[/latex]. Затем вычисляем [latex]s[/latex]. Вычисляем [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex].

Related Images:

e-olymp 2040. Обычная перестановка.

20/12/2015 by Кондратюк Настя

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

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

По заданным двум строкам a и b следует вывести такую строку x наибольшей длины, которая одновременно является подстрокой перестановки a и подстрокой перестановки b.

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

Состоит из нескольких тестов, каждый их которых содержит две строки. То есть строки 1 и 2 — это первый тест, строки 3 и 4 — второй тест и т.д. Каждая строка состоит из символов нижнего регистра, причём первой строкой в паре является a, а второй строкой b. Максимальная длина каждой строки 1000 символов.

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

Для каждого теста следует в отдельной строке вывести строку x. Если таких строк несколько, то вывести наименьшую в алфавитном порядке.

Тесты

Входные данные	Выходные данные
walking down	nw
the street	et
abcd efg
abbcdd badbc	abbcd

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

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

int main() {
	string a, b;
	while(getline(cin, a) && getline(cin, b)){
		for(char letter ='a'; letter <= 'z'; ){
			if((a.find(letter)!=string::npos) && 
			   (b.find(letter)!=string::npos)){ /* если буква есть в 
                            обеих строках */
				cout << letter;
				a.erase(a.find(letter),1); /* стираем найденную 
				букву в первой строке */
				b.erase(b.find(letter),1); /* стираем найденную 
				букву во второй строке */
			}
			else letter++; /* если буквы нет в обеих строках,
                        переходим к следующей букве алфавита */
		}
	    cout << endl;
	}

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string a, b;

while(getline(cin, a) && getline(cin, b)){

for(char letter ='a'; letter <= 'z'; ){

if((a.find(letter)!=string::npos) &&

(b.find(letter)!=string::npos)){ /* если буква есть в

обеих строках */

cout << letter;

a.erase(a.find(letter),1); /* стираем найденную

букву в первой строке */

b.erase(b.find(letter),1); /* стираем найденную

букву во второй строке */

}

else letter++; /* если буквы нет в обеих строках,

переходим к следующей букве алфавита */

}

cout << endl;

}

return 0;

}

ideone.com

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

Решение

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

Related Images:

MLoop 17

16/12/2015 by Кондратюк Настя

Задача

Вычислите с точностью [latex]\varepsilon[/latex] значение функции [latex]f\left( x \right) = \ln \left( 1-x^2 \right)[/latex] . При вычислениях допустимо использовать только арифметические операции.

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

В одной строке заданы значение переменной [latex]x[/latex] и точность вычислений [latex]\varepsilon[/latex].
[latex]\left | x \right |< 1[/latex]

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

Значение функции в точке [latex]x[/latex] .

Тесты

[latex]\varepsilon[/latex]	[latex]x[/latex]	[latex]ln(1-x^2)[/latex]	Результат
0.001	0.5	[latex]ln(0.75)[/latex]	-0.287435
0.0001	0.5	[latex]ln(0.75)[/latex]	-0.287671
0.01	0.1	[latex]ln(0.99)[/latex]	-0.01005
0.001	-0.1	[latex]ln(0.99)[/latex]	-0.01005
0.1	0	[latex]ln(1.00)[/latex]	0
0.01	0	[latex]ln(1.00)[/latex]	0

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

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

int main() {
    double E, logarithm = 0, ai = 1, p = 1, x;
    int i = 1;
    cin >> x >> E;
    while(ai > E){
        p *= x*x;  // вычисление числителя члена ряда
        ai = p / i; // вычисление члена ряда
        logarithm -= ai; 
        i++;
    }
    cout <<  logarithm;
	
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double E, logarithm = 0, ai = 1, p = 1, x;

int i = 1;

cin >> x >> E;

while(ai > E){

p *= x*x; // вычисление числителя члена ряда

ai = p / i; // вычисление члена ряда

logarithm -= ai;

i++;

}

cout << logarithm;

return 0;

}

ideone.com

Решение

Функцию [latex]f\left( x \right) = \ln \left( 1-x^2 \right)[/latex] можно представить в виде:
[latex]ln\left ( 1-x^2 \right )= ln\left ( 1-x \right )\left ( 1+x \right ) = ln\left ( 1-x \right )+ln\left ( 1+x \right )[/latex] (по свойствам логарифма).

Для решения задачи необходимо воспользоваться формулой Тейлора для натурального логарифма с опорной точкой [latex]x_{0}=0[/latex] (ряд Маклорена). Для функции [latex]ln\left (1+x\right )[/latex] она имеет следующий вид:

[latex]ln\left (1+x\right )=x-\frac{x^{2}}{2}+\frac{x^{3}}{3}-\cdots+\frac{\left ( -1 \right )^{n-1}}{n}x^{n}=\sum_{n=1}^{\infty}\frac{\left (-1\right )^{n-1}}{n}x^{n}[/latex]

Подставив в формулу [latex]-x[/latex] вместо [latex]x[/latex] , получим:

[latex]ln\left (1-x\right )=-x-\frac{x^{2}}{2}-\frac{x^{3}}{3}-\cdots -\frac{x^{n}}{n}=-\sum_{n=1}^{\infty}\frac{x^{n}}{n}[/latex]

Тогда,

[latex]ln\left (1+x\right )+ln\left (1-x\right )=\sum_{n=1}^{\infty}\frac{\left (-1\right )^{n-1}}{n}x^{n}-\sum_{n=1}^{\infty}\frac{x^{n}}{n}=[/latex] [latex]=\sum_{n=1}^{\infty }\left[\frac{\left (-1\right )^{n-1}}{n}x^{n}-\frac{x^{n}}{n}\right]=\sum_{n=1}^{\infty }\frac{x^{n}\left (\left (-1\right )^{n-1}-1\right )}{n}=[/latex][latex]=-x^{2}+0-\frac{x^{4}}{2}+0-\frac{x^{6}}{3}+0-\cdots[/latex]

Так как при нечетном [latex]n[/latex] члены данного ряда обращаются в ноль, его можно записать в виде:

[latex]-\sum_{0}^{\infty}\frac{x^{2n+2}}{n+1}=-x^{2}-\frac{x^{4}}{2}-\frac{x^{6}}{3}-\cdots-\frac{x^{2n+2}}{n+1}[/latex]

Далее необходимо найти рекуррентную формулу для членов данного ряда.

[latex]\frac{a_{n}}{a_{n-1}}=\frac{x^{2n+2}}{n+1}\cdot\frac{n-1+1}{x^{2\left ( n-1 \right )+2}}=\frac{x^{2}\cdot n }{n+1}[/latex]

Затем необходимо суммировать до тех пор пока очередное слагаемое не будет меньше заданной точности.

Related Images:

MLoops 16

01/12/2015 by Кондратюк Настя

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex] n>0[/latex] (количество столбцов) и [latex]m>0[/latex] (количество строк).

123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231

Тесты

[latex]m[/latex] [latex]n[/latex]
4 3	123 231 132 123
8 8	12312312 23123123 13213213 12312312 23123123 13213213 12312312 23123123
10 27	123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123

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

#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> m >> n;
	for(int i=1; i<=m; i++){
		for(int j=1; j<=n; j++){
			if((i+j)%3==0) cout << 2;
			else{
				if(j%3==0){
					if((i+j+1)%3==0) cout << 1;
					else cout << 3;
				}
				else if((j-1)%3==0) cout << 1;
				     else cout << 3;
			}
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

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

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

if((i+j)%3==0) cout << 2;

else{

if(j%3==0){

if((i+j+1)%3==0) cout << 1;

else cout << 3;

}

else if((j-1)%3==0) cout << 1;

else cout << 3;

}

cout << endl;

}

return 0;

}

ideone.com

Решение

Пронумеруем строки от [latex]1[/latex] до [latex]m[/latex] , столбцы — от [latex]1[/latex] до [latex]n[/latex].

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

Положение символа [latex]2[/latex] определяется однозначно для всей таблицы [latex]\left (n+m \right )\vdots 3[/latex]. В столбцах, где [latex]n\vdots 3[/latex], положение символа [latex]1[/latex] — [latex]\left ( n+m+1 \right )\vdots 3[/latex] , на оставшихся свободных местах — символ [latex]3[/latex] . В столбцах, где [latex]\left ( n-1\right )\vdots 3[/latex], на свободных местах стоит символ [latex]1[/latex]. В оставшихся столбцах на свободных местах стоит символ [latex]3[/latex].

Related Images:

Ю2.16

07/10/2015 by Кондратюк Настя

Задача

Задача взята из задачника А.Юркина

Кратные пары

Среди заданных целых чисел [latex]k, l, m[/latex] найти пары кратных.

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

Целые числа [latex]k, l, m[/latex].
[latex] \left | k,l,m \right |< 2\cdot 10^{9} [/latex]

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

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

Тесты

	Входные данные	Выходные данные
1.	1 2 3	1 2 1 3
2.	0 2 4	2 4
3.	1 2 6	1 2 1 6 2 6
4.	5 5 2	5 5
5.	0 0 3
6.	2 5 3
7.	-10 5 2

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

#include <iostream>
using namespace std;

int main() {
	int k,l,m;
	cin >> k >> l >> m;
	if (k>0){
		if (l>0){
			if (m>0){
				if ((k%m==0)||(m%k==0)) 
					cout << k << " " << m << endl;
				if ((k%l==0)||(l%k==0)) 
					cout << k << " " << l << endl;
				if ((l%m==0)||(m%l==0)) 
					cout << l << " " << m << endl;
			}
			else if ((k%l==0)||(l%k==0)) 
					cout << k << " " << l << endl;
		}
		else if ((m>0) && ((m%k==0)||(k%m==0))) 
				cout << m << " " << k << endl;
	}
	else if ((l>0) && (m>0) && ((l%m==0)||(m%l==0))) 
			cout << l << " " << m << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int k,l,m;

cin >> k >> l >> m;

if (k>0){

if (l>0){

if (m>0){

if ((k%m==0)||(m%k==0))

cout << k << " " << m << endl;

if ((k%l==0)||(l%k==0))

cout << k << " " << l << endl;

if ((l%m==0)||(m%l==0))

cout << l << " " << m << endl;

}

else if ((k%l==0)||(l%k==0))

cout << k << " " << l << endl;

}

else if ((m>0) && ((m%k==0)||(k%m==0)))

cout << m << " " << k << endl;

}

else if ((l>0) && (m>0) && ((l%m==0)||(m%l==0)))

cout << l << " " << m << endl;

return 0;

}

ideone.com

Решение

Хотя свойство делимости определено на всём множестве целых чисел, обычно рассматривается лишь делимость натуральных чисел.

Кратное натурального числа [latex]b[/latex] — это натуральное число [latex]a[/latex], которое делится на [latex]b[/latex] нацело. Наименьшим кратным данного числа является само это число.

Related Images:

e-olymp 248. Юный садовод

01/10/2015 by Кондратюк Настя

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

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

Мама попросила Васю полить все молодые деревца в саду. Вася знает, что пока деревья маленькие, их надо очень хорошо поливать. А вот сколько поливать — неизвестно. Но Вася — очень умный мальчик. Он внимательно прочитал весь учебник ботаники для средней школы и выяснил, что полив прямо пропорционален количеству листьев на дереве. Для хорошего роста деревьев достаточно выливать под дерево ежедневно по одному литру воды на каждый лист.

К счастью Васи оказалось, что листья на деревьях растут ярусами, причем на верхнем ярусе два листа, на втором — четыре, на следующем — шесть, и так далее, на каждом последующем ярусе на два листа больше по сравнению с предыдущим. А на самой верхушке растет еще один листик. Хитрый Вася послал младшую сестренку Машеньку подсчитать количество ярусов на каждом дереве, а Вас просит написать программу, которая для каждого дерева вычислит количество литров воды для его полива.

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

Количество ярусов [latex]n (0 \leq n \leq 1000)[/latex] на дереве.

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

Вывести количество литров воды для полива этого дерева.

Тесты

	Входные данные	Выходные данные
1.	3	13
2.	0	1
3.	50	2551
4.	560	314161

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

#include <iostream>
using namespace std;

int main() {
    int n,a=0,sum=0;
    cin >> n;
    for(int i=0 ; i<n ; i++){
        a = a + 2;
        sum = sum + a;
    }
    cout << (sum+1) << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,a=0,sum=0;

cin >> n;

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

a = a + 2;

sum = sum + a;

}

cout << (sum+1) << endl;

return 0;

}

ideone.com

Решение

Для решения этой задачи необходимо найти сумму арифметической прогрессии, где [latex]N=n,[/latex] [latex]a_{1} = 2[/latex] и [latex]d = 2[/latex] и добавить к ней единицу (лист с верхушки). Для этого можно воспользоваться формулой суммы арифметической прогрессии [latex]Sn=\frac{2a_{1}+d\left(n-1 \right)}{2}n \rightarrow n^2+n[/latex], либо при помощи цикла [latex]n[/latex] раз прибавлять к [latex]a[/latex] двойку, получая при этом следующий член прогрессии и добавлять его к сумме.

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

Related Images:

Mif 17.10

01/10/2015 by Кондратюк Настя

Задача

Принадлежит ли точка [latex]\left( x;y \right)[/latex] фигуре на рисунке?

Тесты

	[latex]\left( x;y \right)[/latex]	Ответ
1.	(1;6)	нет
2.	(-5;3)	нет
3.	(0;0)	нет
4.	(3.5;1.7)	да
5.	(2;4)	да

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

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

int main() {
	double x,y;
	cin >> x >> y;
	if (x>=0 && y>=0 && ((x*x+y*y)<=36) && (y>=(3-x))){
		cout << "YES";
	}
    else cout << "NO";

	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double x,y;

cin >> x >> y;

if (x>=0 && y>=0 && ((x*x+y*y)<=36) && (y>=(3-x))){

cout << "YES";

}

else cout << "NO";

return 0;

}

ideone.com

Решение

Рисунок находится в I четверти, следовательно только точка с положительными [latex]x[/latex] и [latex]y[/latex] может принадлежать этому рисунку. Далее необходимо воспользоваться уравнением окружности [latex]\left(x-a \right)^2+\left(y-b \right)^2=R^2[/latex], т.к. центр окружности(сегмент которой изображен на рисунке) находится в начале координат формула имеет такой вид: [latex]x^2+y^2=R^2[/latex]. Также рисунок ограничен прямой [latex]y=3-x[/latex]. Если [latex]x>0[/latex] и [latex]y>0[/latex] , [latex]R\leq6[/latex] , [latex]y\geq3-x[/latex], то точка принадлежит фигуре на рисунке.

Related Images:

ML17

27/09/2015 by Кондратюк Настя

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

Входные данные
В одной строке заданы гипотенуза [latex] (c)[/latex] и катет [latex] (a)[/latex] прямоугольного треугольника, не превышающие [latex]1000[/latex].

Выходные данные
В одной строке через пробел — второй катет и радиус вписанной окружности с точностью два знака после запятой.

Тесты

	Входные данные		Выходные данные
1.	5	4	3.00	1.00
2.	3.25	1	3.09	0.42
3.	15	8	12.69	2.85
4.	42.2	25	34.00	8.40
5.	62	23	57.58	9.29
6.	125	47	115.83	18.91
7.	1000	758	652.25	205.13

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

#include <iostream>
#include <math.h>
#include <iomanip>
using namespace std;
 
int main() {
	double a,c,b;
	cin >> c >> a;
	b=sqrt(c*c-a*a); 
	cout<< fixed << setprecision(2) << b << " " << (a+b-c)/2 << endl;
	return 0;
}

#include <iostream>

#include <math.h>

#include <iomanip>

using namespace std;

int main() {

double a,c,b;

cin >> c >> a;

b=sqrt(c*c-a*a);

cout<< fixed << setprecision(2) << b << " " << (a+b-c)/2 << endl;

return 0;

}

ideone.com

Решение
Для нахождения катета необходимо воспользоваться теоремой Пифагора [latex]c^2=a^2+b^2 \ \Rightarrow \ b^2=c^2-a^2 \ \Rightarrow \ b=\sqrt(c^2-a^2)[/latex].
Радиус окружности, вписанной в прямоугольный треугольник:
рассмотрим прямоугольный треугольник [latex]ABC[/latex] со вписанной окружностью с центром в точке [latex]O[/latex].

[latex]OD=OE=r[/latex] ; [latex]AC[/latex], [latex]CB[/latex], [latex]AB[/latex] — касательные к окружности. По свойствам касательных (1.касательная к окружности перпендикулярна радиусу, проведенному в точку касания; 2.отрезки касательных, проведенных из одной точки равны) [latex]AE=AD, DC=FC, BF=BE[/latex] ; [latex]OD\perp AC, OE\perp AC[/latex], следовательно [latex]AEOD[/latex] — квадрат и [latex]AD=AE=r[/latex].
Пусть [latex]AC=a, AB=b, BC=c[/latex], тогда [latex]\begin{cases}r+DC=a\\r+BE=b\\DC+BE=c\end{cases}\Rightarrow \begin{cases}DC=a-r\\BE=b-r\\a+b-2r=c\end{cases} \Rightarrow[/latex] [latex]r=\frac{a+b-c}{2}[/latex].

Related Images:

e-olymp 903. Первая или последняя?

14/09/2015 by Кондратюк Настя

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

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

Задано трехзначное число. Какая цифра в нем больше: первая или последняя?

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

Одно трехзначное число.

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

Вывести большую из указанных цифр. В случае их равенства вывести знак «=» (без кавычек).

Тесты:

	Входные данные	Результат
1	328	8
2	956	9
3	384	4
4	672	6
5	558	8
6	733	7
7	797	=
8	555	=

#include <iostream>
using namespace std;

int main() {
    int n,a,b;
    cin >> n;
    a=(n/100);
    b=(n%10);
    cout << (a==b ? (char)(61) : (a>b ? (char)(48+a) : (char)(48+b)));
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,a,b;

cin >> n;

a=(n/100);

b=(n%10);

cout << (a==b ? (char)(61) : (a>b ? (char)(48+a) : (char)(48+b)));

return 0;

}

ideone.com

Пояснение:

Для того чтобы определить первую цифру [latex] (a) [/latex] трехзначного числа [latex]n[/latex] необходимо найти целую часть от деления этого числа на сто, воспользовавшись формулой [latex]a = n/100[/latex]. Чтобы определить вторую цифру [latex] (b) [/latex] необходимо найти остаток от деления числа на десять, воспользовавшись формулой [latex]b=n[/latex][latex]\%[/latex][latex]10[/latex] . Затем необходимо проверить равны ли эти цифры, если нет-найти большую.

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

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…