e-olymp 4481. В стране невыученных уроков

27/06/2016 by Катя Писова

Задача

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа [latex]l[/latex] и [latex]r[/latex], и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от [latex]l[/latex] до [latex]r[/latex] включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

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

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

Первая строка содержит количество элементов [latex]n[/latex] [latex](1\leq n\leq 10^5)[/latex] в массиве. Во второй строке находится [latex]n[/latex] чисел – элементы [latex]a_i[/latex] [latex](1\leq a_i\leq 10^9)[/latex] массива. В третьей строке находится количество запросов [latex]m[/latex] [latex](1\leq m\leq 10^5)[/latex]. Далее в [latex]m[/latex] строках находятся по три числа [latex]q[/latex], [latex]l[/latex], [latex]r[/latex] [latex](1\leq l\leq r\leq n)[/latex]. Если [latex]q=1[/latex], требуется посчитать НОД элементов на промежутке [latex][l,r][/latex], если [latex]q=2[/latex], то надо заменить элемент в позиции [latex]l[/latex] на число [latex]r[/latex].

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

Для каждого запроса с номером [latex]l[/latex] в отдельной строке выведите ответ на запрос.

Тесты

Входные данные:	Выходные данные:
5 2 4 6 10 8 6 1 1 5 1 2 3 2 5 15 2 3 10 1 3 5 1 1 5	2 2 5 1

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

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

vector<int> tree;
int n;

int gcd (int a, int b){
    if (a == 0) return b;
   return gcd(b % a, a);
}

void build(int a[], int v = 1, int tl = 0, int tr = n - 1){
    if(tl == tr){
        tree[v] = a[tl];
    }else{
        int middle = (tl + tr) / 2;
        build(a, v * 2, tl, middle);
        build(a, v * 2 + 1, middle + 1, tr);
        tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);
    }
}
 
int get(int a[], int l, int r, int v = 1, int tl = 0, int tr = n-1){
    if(l > r){
        return 0;
    }
    if(tl == l && tr == r){
        return tree[v];
    }
    int middle = (tl + tr) / 2;
    int L = get(a, l, min(middle, r), v * 2, tl, middle);
    int R = get(a, max(middle + 1, l), r, v*2 + 1, middle + 1, tr);
    return gcd(L, R);

}
void update(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){
    if(tl == tr){
        tree[v] = val;
    }else{
        int middle = (tl + tr) / 2;
        if(pos <= middle){
            update(pos, val, v * 2, tl, middle);
        }else{
            update(pos, val, v * 2 + 1, middle + 1, tr);
        }
        tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);
    }
}
 
int main(){
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    tree.resize(4 * n);
    build(a);
    int m, l, r, q; 
    cin >> m;
    while (m--){
        cin >> q >> l >> r;
        if (q == 1){
            cout << get(a, l - 1, r - 1) << endl;
        }
        else{
            update(l - 1, r);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector<int> tree;

int n;

int gcd (int a, int b){

if (a == 0) return b;

return gcd(b % a, a);

}

void build(int a[], int v = 1, int tl = 0, int tr = n - 1){

if(tl == tr){

tree[v] = a[tl];

}else{

int middle = (tl + tr) / 2;

build(a, v * 2, tl, middle);

build(a, v * 2 + 1, middle + 1, tr);

tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);

}

int get(int a[], int l, int r, int v = 1, int tl = 0, int tr = n-1){

if(l > r){

return 0;

}

if(tl == l && tr == r){

return tree[v];

}

int middle = (tl + tr) / 2;

int L = get(a, l, min(middle, r), v * 2, tl, middle);

int R = get(a, max(middle + 1, l), r, v*2 + 1, middle + 1, tr);

return gcd(L, R);

}

void update(int pos, int val, int v = 1, int tl = 0, int tr = n - 1){

if(tl == tr){

tree[v] = val;

}else{

int middle = (tl + tr) / 2;

if(pos <= middle){

update(pos, val, v * 2, tl, middle);

}else{

update(pos, val, v * 2 + 1, middle + 1, tr);

}

tree[v] = gcd(tree[v * 2], tree[v * 2 + 1]);

}

int main(){

cin >> n;

int a[n];

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

cin >> a[i];

}

tree.resize(4 * n);

build(a);

int m, l, r, q;

cin >> m;

while (m--){

cin >> q >> l >> r;

if (q == 1){

cout << get(a, l - 1, r - 1) << endl;

}

else{

update(l - 1, r);

}

return 0;

}

Алгоритм решения

Данная задача решена с помощью структуры данных «дерево отрезков». В каждой вершине дерева храним НОД всех чисел на соответствующем отрезке массива. Функции, отвечающие за построение самого дерева отрезков, нахождение НОД на отрезке и запрос на модификацию элемента являются рекурсивными. Дерево строим следующим образом: листьями данного дерева будут сами элементы исходного массива, а значения элементов, находящихся на уровень выше, будут представлять собой НОД двух соседних листов. Таким же образом считаем значения вершин следующего уровня и т.д. Чтобы найти НОД на заданном отрезке рассматриваем случаи расположения данного отрезка. Он может полностью принадлежать одному потомку, а может быть разбит между правым и левым потомками. В первом случае функцию запускаем от одного потомка и получаем требуемое, во втором случае функцию запускаем от двух потомков и находим от полученных результатов НОД. При выполнении запроса на модификацию запускаем функцию от корня, спускаемся до требуемого элемента, изменяем его, и поднимаемся обратно к корню, модифицируя значения вершин, для которых данный элемент является подотрезком.

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

Для получения подробной информации о структуре данных «Дерево отрезков» можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

Related Images:

e-olymp 1455. Цикл

12/05/2016 by Катя Писова

Задача

Дан граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

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

Первая строка содержит количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках находится по n чисел — матрица смежности графа. Веса ребер не превышают по модулю 10000. Если ребра нет, соответствующее значение равно 100000.

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

В первой строке выведите «YES«, если цикл существует, или «NO» в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковыми первую и последнюю) и в третьей строке — вершины, входящие в этот цикл в порядке обхода. Если циклов несколько — выведите любой.

Тесты

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

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

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

struct edge{
    int from, to, cost;
};
const int INF = 1e9;;

int main(){
    int n;
    cin >> n;
    vector <edge> E;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            int x;
            cin >> x;
            if(x != 0 && x != 100000){
                E.push_back({i,j,x});
            }
        }
    }
    int x ;
    vector<int> d(n, INF), p(n, -1);
    d[0] = 0;
    for(int i = 0; i < n; i++){
        x = -1;
        for(int j = 0; j < E.size(); j++){
            int from = E[j].from;
            int to = E[j].to;
            int cost = E[j].cost;
            if(d[to] > d[from] + cost ){
                d[to] = max(d[from] + cost, -INF);
                p[to] = from;
                x = to;
            }
        }
    }
    if(x == -1){
        cout << "NO" << endl;
    }else{
        int y = x;
        for(int i = 0; i < n; i++){
            y = p[y];
        }
        vector <int> path;
        for(int cur = y;; cur = p[cur]){
            path.push_back(cur);
            if(cur == y && path.size() > 1){
                break;
            }
        }
        reverse(path.begin(), path.end());
        cout << "YES" << endl;
        cout << path.size() << endl;
        for(int i = 0; i < path.size(); i++){
            cout << path[i] + 1;
            if(i != path.size()-1){
                cout << ' ';
            }
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

struct edge{

int from, to, cost;

};

const int INF = 1e9;;

int main(){

int n;

cin >> n;

vector <edge> E;

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

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

int x;

cin >> x;

if(x != 0 && x != 100000){

E.push_back({i,j,x});

}

int x ;

vector<int> d(n, INF), p(n, -1);

d[0] = 0;

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

x = -1;

for(int j = 0; j < E.size(); j++){

int from = E[j].from;

int to = E[j].to;

int cost = E[j].cost;

if(d[to] > d[from] + cost ){

d[to] = max(d[from] + cost, -INF);

p[to] = from;

x = to;

}

if(x == -1){

cout << "NO" << endl;

}else{

int y = x;

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

y = p[y];

}

vector <int> path;

for(int cur = y;; cur = p[cur]){

path.push_back(cur);

if(cur == y && path.size() > 1){

break;

}

reverse(path.begin(), path.end());

cout << "YES" << endl;

cout << path.size() << endl;

for(int i = 0; i < path.size(); i++){

cout << path[i] + 1;

if(i != path.size()-1){

cout << ' ';

}

cout << endl;

}

return 0;

}

Алгоритм решения:

Для решения данной задачи задействован алгоритм Беллмана-Форда, который позволяет проверить наличие или отсутствие цикла отрицательного веса в графе, а при его наличии — найти один из таких циклов. Создадим вектор, который будет содержать в себе элементы матрицы смежности графа. По определению смежных вершин графа, учитывая условие задачи (если ребра нет, соответствующее значение равно [latex]100000[/latex]), заполним этот вектор. Далее будем использовать алгоритм Беллмана-Форда. Если алгоритм даст отрицательный ответ на вопрос задачи, то выводим NO. Если цикл все-таки существует, то выводим YES. В вектор записываем вершины, входящие в цикл отрицательного веса. Далее выводим их количество, а затем и сами вершины в порядке обхода.

Для получения подробной информации об алгоритме Беллмана-Форда можно перейти по данной ссылке
Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

Related Images:

e-olymp 6127. Очередь неограниченного размера

15/04/2016 by Катя Писова

Задача

Реализуйте структуру данных «очередь«. Напишите программу, содержащую описание очереди и моделирующую работу очереди, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

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

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер очереди должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций front и popпрограмма должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция frontилиpop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

Тесты

№	Входные данные	Выходные данные:
1	push 1 front exit	ok 1 bye
2	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

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

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

struct node{
    int value;
    node *next;
    node():value(0), next(NULL){}
    node(int value, node *next)
    :value(value), next(next){}
};

struct _queue{
    int _size;
    node *first;
    node *last;
    _queue():_size(0), first(NULL), last(NULL){}

    void push (int v){
        node *new_node = new node(v, last);
        if(_size == 0){
            first = last = new_node;
        }
        else{
            last->next = new_node;
            last = new_node;
        }
        _size++;
    }

    void pop(){
        if (_size > 0){
            int val = first->value;
            first = first->next;
            _size--;
            cout << val;
        }
        else throw 0;
    }

    void front(){
        if (_size > 0) cout << first->value;
        else throw 0;
    }
    
    int size(){
        return _size;
    }

    void clear(){
        while (_size > 0){
            node *new_node = first->next;
            delete first;
            first = new_node;
            _size--;
        }
        first = NULL;
        last = NULL;
    }
};


int main()
{
    _queue q;
    string s;
    int n;
    while (cin >> s){
        if (s == "size"){
            cout << q.size() << endl;
        }
        if (s == "push"){
            cin >> n;
            q.push(n);
            cout << "ok" << endl;
        }
        if (s == "pop"){
            try{
                q.pop();
            }
            catch(int e){cout << "error";}
            cout << endl;
        }
        if (s == "front"){
            try {
                q.front();
            }
            catch(int e){cout << "error";}
            cout<<endl;
        }
        if (s == "clear"){
            q.clear();
            cout << "ok" << endl;
        }
        if (s == "exit"){
            cout << "bye" <<endl;
            return 0;
        }
    }
    return 0;
}

100

101

102

#include <iostream>

#include <string>

#include <exception>

using namespace std;

struct node{

int value;

node *next;

node():value(0), next(NULL){}

node(int value, node *next)

:value(value), next(next){}

};

struct _queue{

int _size;

node *first;

node *last;

_queue():_size(0), first(NULL), last(NULL){}

void push (int v){

node *new_node = new node(v, last);

if(_size == 0){

first = last = new_node;

}

else{

last->next = new_node;

last = new_node;

}

_size++;

}

void pop(){

if (_size > 0){

int val = first->value;

first = first->next;

_size--;

cout << val;

}

else throw 0;

}

void front(){

if (_size > 0) cout << first->value;

else throw 0;

}

int size(){

return _size;

}

void clear(){

while (_size > 0){

node *new_node = first->next;

delete first;

first = new_node;

_size--;

}

first = NULL;

last = NULL;

}

};

int main()

{

_queue q;

string s;

int n;

while (cin >> s){

if (s == "size"){

cout << q.size() << endl;

}

if (s == "push"){

cin >> n;

q.push(n);

cout << "ok" << endl;

}

if (s == "pop"){

try{

q.pop();

}

catch(int e){cout << "error";}

cout << endl;

}

if (s == "front"){

try {

q.front();

}

catch(int e){cout << "error";}

cout<<endl;

}

if (s == "clear"){

q.clear();

cout << "ok" << endl;

}

if (s == "exit"){

cout << "bye" <<endl;

return 0;

}

return 0;

}

Алгоритм решения:

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

Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

Related Images:

A304

27/03/2016 by Катя Писова

Задача

Даны действительные числа [latex]a_{1},a_{2},\cdots[/latex] (читать до конца входного потока). Переставить члены последовательности так, чтобы сначала расположились все ее неотрицательные члены, а потом — все отрицательные. Порядок как среди неотрицательных членов, так и среди отрицательных должен быть сохранен прежним.

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

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    vector <long double> v1, v2, v3;
    long double n;
    while (cin >> n){
        v1.push_back(n);
    }
    for (int i = 0; i < v1.size(); i++){
        if (v1[i] < 0) v3.push_back(v1[i]);
        else v2.push_back(v1[i]);
    }
    v2.insert(v2.end(), v3.begin(), v3.end());
    for (int i = 0; i < v2.size(); i++){
        cout << v2[i] << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector <long double> v1, v2, v3;

long double n;

while (cin >> n){

v1.push_back(n);

}

for (int i = 0; i < v1.size(); i++){

if (v1[i] < 0) v3.push_back(v1[i]);

else v2.push_back(v1[i]);

}

v2.insert(v2.end(), v3.begin(), v3.end());

for (int i = 0; i < v2.size(); i++){

cout << v2[i] << " ";

}

cout << endl;

return 0;

}

Тесты

Test №	Input	Output
1	-23 45 17 -78 0 34	45 17 0 34 -23 -78
2	-56 -56.34 0.2 56 9	0.2 56 9 -56 -56.34
3	-1 3 2 1 0 -3 -2	3 2 1 0 -1 -3 -2
4	-0.333 -1 0 1 0 -2 0 2	0 1 0 0 2 -0.333 -1 -2
5	9 -9 0 -96 -11 27 -13	9 0 27 -9 -96 -11 -13

Алгоритм решения

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

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

Related Images:

A279

13/03/2016 by Катя Писова

Задача

Даны действительные числа [latex]a_{1},[/latex] … [latex], a_{n},[/latex] [latex]b_{1},[/latex] … [latex], b_{n}[/latex]. Вычислить [latex](a_{1} + b_{n})(a_{2} + b_{n-1})[/latex] … [latex](a_{n} + b_{1})[/latex].

Тесты

Test №	Input	Output
1	1 2 3 4 5 6	343
2	1 1 1 1	4
3	0.5 0.1 0.07 -4 7 13	-376.691
4	0 0 0 0 0 0 0 0	0
5	0.4 0.3 2 -1 0.7 0.6	1

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

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

int main()
{
    vector <long double> c;
    long double m, sum = 0, result = 1;
    while (cin >> m){
        c.push_back(m);
    }
    for (int i = 0; i < c.size()/2; i++){
        sum = c[i] + c[c.size() - 1 - i];
        result *= sum;
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector <long double> c;

long double m, sum = 0, result = 1;

while (cin >> m){

c.push_back(m);

}

for (int i = 0; i < c.size()/2; i++){

sum = c[i] + c[c.size() - 1 - i];

result *= sum;

}

cout << result << endl;

return 0;

}

Алгоритм решения

Считываем все действительные числа до конца входного потока и записываем их в один вектор c. Далее работаем по такому алгоритму: складываем первый элемент вектора с последним, а полученный результат умножаем на переменную result, значение которой изначально равно единице, т.к, единица — нейтральный элемент при умножении. Далее складываем второй элемент вектора с предпоследним, а полученный результат снова умножаем на переменную result и т.д. Так делаем до тех пор, пока не дойдем но середины вектора c. Затем выводим полученное значение переменной result.

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

Related Images:

MLoops 11

19/12/2015 by Катя Писова

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел $n > 0$ (количество столбцов) и $m > 0$ (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр $k < n$ .
Замечание 2. Многоточие означает продолжение последовательности. Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

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

Три числа: количество столбцов и строк, параметр [latex]k[/latex].

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

+-------+-------+-------+
|123...k|123...k|123...k|
|23...k1|23...k1|23...k1|
|3...k12|3...k12|3...k12|
|.......|.......|.......|
|k123...|k123...|k123...|
+-------+-------+-------+
|123...k|123...k|123...k|
|23...k1|23...k1|23...k1|

+-------+-------+-------+

|123...k|123...k|123...k|

|23...k1|23...k1|23...k1|

|3...k12|3...k12|3...k12|

|.......|.......|.......|

|k123...|k123...|k123...|

+-------+-------+-------+

|123...k|123...k|123...k|

|23...k1|23...k1|23...k1|

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

#include <iostream>
using namespace std;
 
int main() 
{
	int m, n, k;
	cin >> m >> n >> k;
	for (int i = 0; i < m; i++)
	{
		if (i % (k + 1) == 0)
		{
			for (int j = 0; j < n; j++)
			{
				cout << (j % (k + 1) == 0 ? "+" : "-");
			}
		}
		else
		{
			for (int j = 0; j < n; j++)
			{
				if (j % (k + 1) == 0)
				{
					cout << "|";
				}
				else
				{
					int a = (j % (k + 1) + i % (k + 1) - 1) % k;
					cout << (a == 0 ? k : a);
				}
			}
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int m, n, k;

cin >> m >> n >> k;

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

{

if (i % (k + 1) == 0)

{

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

{

cout << (j % (k + 1) == 0 ? "+" : "-");

}

else

{

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

{

if (j % (k + 1) == 0)

{

cout << "|";

}

else

{

int a = (j % (k + 1) + i % (k + 1) - 1) % k;

cout << (a == 0 ? k : a);

}

cout << endl;

}

return 0;

}

Решение:

Для построения данной таблицы нужно найти закономерность чередования символов в таблице. Решение данной задачи можно осуществить с помощью двух циклов. Первый отвечает за строки, а второй — за столбцы. Пусть нумерация строк и столбцов начинается с нуля. Тогда, если номер строчки нацело делится на [latex](k+1)[/latex], то рассматриваем столбцы этой строчки. Если номер столбца нацело делится на [latex](k+1)[/latex], то записываем «+», иначе «-«. Если номер строки не делится нацело на [latex](k+1)[/latex], а номер столбца в этой строке — делится, то записываем «|». Если номер строки и столбца не делятся нацело на [latex](k+1)[/latex], то создаем переменную, с помощью которой будем заполнять таблицу цифрами. Так как, каждый столбик и каждая строка имеют свой номер, то с помощью нахождения суммы остатка от деления строки и столбца на [latex](k+1)[/latex] будем находит значение элемента, стоящего на пересечении [latex]i- [/latex]ой строки и [latex]i-[/latex]ого столбца, но этого не достаточно, в таблице есть перестановка, чтобы ее реализовать отнимаем от суммы единицу, делая этим сдвиг вправо. Также от полученного результата нужно найти остаток от деления на параметр [latex]k[/latex] для того, чтобы выполнялась правильная последовательность символов. Если результат вычисления переменной равен нулю, то записываем значение параметра [latex]k[/latex], иначе — результат вычисления переменной.

Тесты:

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

+----
|1234
|2345
|3456
|4567

+----

|1234

|2345

|3456

|4567

+-----+-----+
|12345|12345|
|23451|23451|
|34512|34512|
|45123|45123|
|51234|51234|
+-----+-----+
|12345|12345|
|23451|23451|
|34512|34512|
|45123|45123|
|51234|51234|
+-----+-----+
|12345|12345|

+-----+-----+

|12345|12345|

|23451|23451|

|34512|34512|

|45123|45123|

|51234|51234|

+-----+-----+

|12345|12345|

|23451|23451|

|34512|34512|

|45123|45123|

|51234|51234|

+-----+-----+

|12345|12345|

+-----+
|12345|
|23451|
|34512|
|45123|
|51234|
+-----+
|12345|
|23451|

+-----+

|12345|

|23451|

|34512|

|45123|

|51234|

+-----+

|12345|

|23451|

+-------+-------+-------+-----
|1234567|1234567|1234567|12345
|2345671|2345671|2345671|23456
|3456712|3456712|3456712|34567
|4567123|4567123|4567123|45671
|5671234|5671234|5671234|56712
|6712345|6712345|6712345|67123
|7123456|7123456|7123456|71234
+-------+-------+-------+-----
|1234567|1234567|1234567|12345
|2345671|2345671|2345671|23456
|3456712|3456712|3456712|34567
|4567123|4567123|4567123|45671
|5671234|5671234|5671234|56712
|6712345|6712345|6712345|67123
|7123456|7123456|7123456|71234
+-------+-------+-------+-----

+-------+-------+-------+-----

|1234567|1234567|1234567|12345

|2345671|2345671|2345671|23456

|3456712|3456712|3456712|34567

|4567123|4567123|4567123|45671

|5671234|5671234|5671234|56712

|6712345|6712345|6712345|67123

|7123456|7123456|7123456|71234

+-------+-------+-------+-----

|1234567|1234567|1234567|12345

|2345671|2345671|2345671|23456

|3456712|3456712|3456712|34567

|4567123|4567123|4567123|45671

|5671234|5671234|5671234|56712

|6712345|6712345|6712345|67123

|7123456|7123456|7123456|71234

+-------+-------+-------+-----

Код программы на ideone.com

Related Images:

MLoop 10

08/11/2015 by Катя Писова

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

Решение задачи:

Для нахождения значения функции $f\left( x \right) = \text{ch}x$ (гиперболический косинус) с точностью [latex]\varepsilon[/latex] воспользуемся формулой Тейлора (разложение функции в бесконечную сумму степенных функций):[latex]chx=1+\frac{x^2}{2}+\frac{x^4}{4}+[/latex]…[latex]=\sum_{n=0}^{\infty}\frac{1}{(2n+1)!}\times x^{2n}[/latex]. [latex]x_n=\frac{1}{(2n+1)!}\times x^{2n}[/latex], тогда [latex]x_{n-1}=\frac{1}{(2(n-1)+1)!}\times x^{2(n-1)}[/latex]. Рекуррентное соотношение [latex]x_n[/latex] и [latex]x_{n-1}=[/latex][latex]\frac{x_n}{x_{n-1}}=\frac{x^2}{2n\times(2n-1)}[/latex].

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

#include <iostream>
#include <cmath>
using namespace std;
 
double ch(double x, double e)
{
	double result = 1;
	double member = 1;
	for (int i = 1; abs(member) >= e; i++)
	{
		member *= x * x;
		member /= 2*i * (2*i - 1);
		result += member;
	}
	return result;
}
 
int main() 
{ 
	double x, e;
	cin >> x >> e;
	cout << ch(x, e);
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double ch(double x, double e)

{

double result = 1;

double member = 1;

for (int i = 1; abs(member) >= e; i++)

{

member *= x * x;

member /= 2*i * (2*i - 1);

result += member;

}

return result;

}

int main()

{

double x, e;

cin >> x >> e;

cout << ch(x, e);

return 0;

}

Тесты:

Входные данные		Выходные данные
x	e	ch(x)
9	0.01	4051.54
16	0.0001	4.44306e+06
0.85	0.00001	1.38353
0.11	0.001	1.00606

Здесь можно посмотреть решение задачи на ideone.com

Related Images:

Mif 17.8

10/10/2015 by Катя Писова

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

Решение:

Фигура, изображенная на рисунке, ограничена двумя дугами окружностей с центрами в начале координат. Для того, чтобы точка принадлежала ей необходимо, чтобы ее ордината была больше либо равнялась двум, а также, чтобы выполнялись такие неравенства: [latex]{x}^{2}+{y}^{2}>=16[/latex] и [latex]{x}^{2}+{y}^{2}<=36[/latex], где [latex]16[/latex] и [latex]36[/latex] — радиусы двух окружностей, возведенные в квадрат по формуле.

Код:

#include <iostream>
using namespace std;
 
int main() {
    double x,y;
    cin>>x>>y;
    cout<<( y >= 2 && x*x + y*y >= 16 && x*x + y*y <= 36 ? "YES" : "NO");
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y;

cin>>x>>y;

cout<<( y >= 2 && x*x + y*y >= 16 && x*x + y*y <= 36 ? "YES" : "NO");

return 0;

}

Тесты:

x	y	Результат
0	0	NO
-1	4	YES
6	-2	NO
2.5	3	NO

Тут можно посмотреть решение задачи на ideone.com

Related Images:

Mif 12

29/09/2015 by Катя Писова

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

Банк предлагает три вида депозитов на 3 месяца ( $p_3%$ годовых), на 6 месяцев ( $p_6%$ годовых) и на 12 месяцев ( $p_{12}%$ годовых). Какой депозит принесёт больше дохода при многолетнем вложении.

Алгоритм решения:

Для решения данной задачи нужно использовать формулу вычисления сложных процентов: [latex]{(1+\frac{p}{100\%})}^n[/latex], где [latex]p-[/latex]процентная ставка за расчетный период, а [latex]n-[/latex]количество расчетных периодов. Для депозита на [latex]3[/latex] месяца получаем формулу [latex]{(1+\frac{p_3}{4\times100\%})}^4[/latex], для депозита на [latex]6[/latex] месяцев получаем формулу [latex]{(1+\frac{p_6}{2\times100\%})}^2[/latex], для депозита на [latex]12[/latex] месяцев получаем формулу [latex](1+\frac{p_{12}}{100\%})[/latex]. Программа будет сравнивать полученные результаты и выводить максимальный.

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

#include <iostream>
using namespace std;
 
int main() 
{
	double p3, p6, p12;
	cin >> p3 >> p6 >> p12;
	double profit3, profit6, profit12;
	profit3 = (1 + p3/400.0)*(1 + p3/400.0)*(1 + p3/400.0)*(1 + p3/400.0);
	profit6 = (1 + p6/200.0)*(1 + p6/200.0);
	profit12 = (1 + p12/100.0);
	cout<<profit3<<" "<<profit6<<" "<<profit12<<endl;
	cout << (profit3 > profit6 ? (profit3 > profit12 ? ("На 3 месяца") : ("На 12 месяцев")) : (profit6 > profit12 ?("На 6 месяцев") : ("На 12 месяцев")));
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

double p3, p6, p12;

cin >> p3 >> p6 >> p12;

double profit3, profit6, profit12;

profit3 = (1 + p3/400.0)*(1 + p3/400.0)*(1 + p3/400.0)*(1 + p3/400.0);

profit6 = (1 + p6/200.0)*(1 + p6/200.0);

profit12 = (1 + p12/100.0);

cout<<profit3<<" "<<profit6<<" "<<profit12<<endl;

cout << (profit3 > profit6 ? (profit3 > profit12 ? ("На 3 месяца") : ("На 12 месяцев")) : (profit6 > profit12 ?("На 6 месяцев") : ("На 12 месяцев")));

return 0;

}

Тесты:

	Входные данные		Выходные данные		Входные данные		Выходные данные
Срок вклада	Ставка(%)	Прибыль	Выгода	Срок вклада	Ставка(%)	Прибыль	Выгода
3 месяца	1	1.01004		3 месяца	10	1.10381
6 месяцев	10	1.1025		6 месяцев	20	1.21
12 месяцев	30	1.3	На 12 месяцев	12 месяцев	30	1.3	На 12 месяцев

	Входные данные		Выходные данные		Входные данные		Выходные данные
Срок вклада	Ставка(%)	Прибыль	Выгода	Срок вклада	Ставка(%)	Прибыль	Выгода
3 месяца	4	1.0406	На 3 месяца	3 месяца	1	1.01004
6 месяцев	4	1.0404		6 месяцев	38	1.4161	На 6 месяцев
12 месяцев	4	1.04		12 месяцев	9	1.09

	Входные данные		Выходные данные		Входные данные		Выходные данные
Срок вклада	Ставка(%)	Прибыль	Выгода	Срок вклада	Ставка(%)	Прибыль	Выгода
3 месяца	1	1.01004		3 месяца	11	1.11462
6 месяцев	20	1.21		6 месяцев	5	1.05062
12 месяцев	25	1.25	На 12 месяцев	12 месяцев	17	1.17	На 12 месяцев

Рассмотрим работу данной программы на реальных предложениях этого банка для депозитов «Плюс срочный» и «Стандарт срочный».

Плюс срочный	Входные данные		Выходные данные	Стандарт срочный	Входные данные		Выходные данные
Срок вклада	Ставка(%)	Прибыль	Выгода	Срок вклада	Ставка(%)	Прибыль	Выгода
3 месяца	23.5	1.25653		3 месяца	22.5	1.24471
6 месяцев	24.5	1.26001	На 6 месяцев	6 месяцев	23.5	1.24881	На 6 месяцев
12 месяцев	25.5	1.255		12 месяцев	24.5	1.245

В результате получили, что эти оба депозита выгодны при сроке вклада на [latex]6[/latex] месяцев. По тестам видно, что депозит «Плюс срочный» при вкладе на [latex]6[/latex] месяцев приносит большую прибыль, чем депозит «Стандарт срочный». Посчитаем, на сколько первый депозит выгоднее второго, для этого воспользуемся формулой: разница[latex]=[/latex](первый депозит[latex]-[/latex]второй депозит)[latex]\div[/latex]второй депозит[latex]\times{100\%}[/latex]. Подставив значения, получим — на [latex]\approx0.89685\%[/latex].

Здесь можно посмотреть решение задачи на ideone.com

Related Images:

e-olymp 11. Большая точность

24/09/2015 by Катя Писова

Задача. Дана рациональная дробь [latex]\frac{m}{n}[/latex]. Запишите её в виде десятичной дроби с точностью [latex] k[/latex] знаков после запятой.

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

В одной строке записано 3 числа [latex]m,n,k[/latex]. [latex]{{0}<{m,n}\leq{100}}[/latex], [latex]{{0}\leq{k}\leq{1000}}[/latex].

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

Вывести [latex]k[/latex] точных значащих цифр после десятичной точки искомого числа.

Алгоритм решения:

Деление уголком

Разделим [latex]m[/latex] на [latex]n[/latex] в столбик. Определим, сколько раз [latex]n[/latex] помещается в [latex]m[/latex]. Это будет целая часть частного. Умножим ее на [latex]n[/latex] и отнимем от [latex]m[/latex]. Таким образом получим остаток от деления. Будем умножать его на [latex]10[/latex] (эквиваленто сноске [latex]0[/latex]) и проводить такую же операцию, как при нахождении целой части пока не закончится цикл. Так мы определим все цифрs после запятой.

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

#include <iostream>
int main() {
    int m, n, k;
    std::cin >> m >> n >> k;
    std::cout << m / n << ".";
    for (int i = 0; i < k; ++i) {
       m = (m % n) * 10;
       std::cout << m / n;
    }
}

#include <iostream>

int main() {

int m, n, k;

std::cin >> m >> n >> k;

std::cout << m / n << ".";

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

m = (m % n) * 10;

std::cout << m / n;

}

Проверка

(По условию задачи):

Ввод:	#	Вывод:
m	1	0.500
n	2
k	3

Ввод:	#	Вывод:
m	2	0.66666666666666666666
n	3
k	20

Ввод:	#	Вывод:
m	9	1.000000000
n	9
k	9

Ввод:	#
m	1	0.33333333333333333333
n	3
k	20

Здесь можно посмотреть решение на ideone.com

Здесь можно посмотреть условие задачи на e-olymp.com

Related Images:

ML12

23/09/2015 by Катя Писова

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

Даны [latex]x,y,z[/latex]. Вычислить [latex] a = x \arctan{y} — e^{1-z}[/latex] и [latex] b = \frac{\sqrt{\left|3-x^2 \right|}- \sqrt[3]{\left|y-x \right|}}{1-\frac{x^2}{2}+\frac{y^2}{4}-\frac{z^2}{8}}.[/latex]

Алгоритм решения:

1)В условии задачи не указано какие должны быть числа [latex]x,y,z[/latex] , поэтому правильнее всего использовать диапазон long double, чтобы включить как можно больше значений.

2)Подключим библиотеку <cmath> , с помощью которой подключим математические функции и, придерживаясь правил порядка вычислений, расставим скобки.

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    long double x, y, z;
    cin>>x>>y>>z;
    long double a, b;
    a = x*atan(y) - pow(M_E,(1-z)); // M_e - число Эйлера 
    b =(sqrt(abs(3-x*x))-pow(abs(y-x),1.0/3))/(1-x*x/2 + y*y/4 - z*z/8);
    cout<<a<<endl;
    cout<<b<<endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

long double x, y, z;

cin>>x>>y>>z;

long double a, b;

a = x*atan(y) - pow(M_E,(1-z)); // M_e - число Эйлера

b =(sqrt(abs(3-x*x))-pow(abs(y-x),1.0/3))/(1-x*x/2 + y*y/4 - z*z/8);

cout<<a<<endl;

cout<<b<<endl;

return 0;

}

Тесты:

Ввод:	#	Вывод:	#
x	1	a	0.971813
y	2	b	1.10457
z	3

Ввод:	#	Вывод:	#
x	-9	a	-16.1645
y	13	b	2.19263
z	0

Ввод:	#	Вывод:	#
x	7	a	10.361
y	11	b	-0.107389
z	21

Здесь находится код в ideone.com

Related Images:

e-olymp 7336. Пирожки

14/09/2015 by Катя Писова

Условие задачи можно посмотреть здесь

Постановка задачи

Пирожок в столовой стоит [latex]a[/latex] гривен и [latex]b[/latex] копеек. Найдите сколько гривен и копеек заплатит Петя за [latex]n[/latex] пирожков.

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

Три натуральных числа [latex]a, b[/latex], [latex]n[/latex] [latex](0\leq a, b, n\leq 100)[/latex].

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

Через пропуск два числа: стоимость покупки в рублях и копейках.

Решение

#include <iostream>
using namespace std;
int main()
{
    int a;
    cin>>a;
    int b;
    cin>>b;
    int n;
    cin>>n;
    int p;
    p=(a*100+b)*n;
    cout<<p/100<<" "<<p%100;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int a;

cin>>a;

int b;

cin>>b;

int n;

cin>>n;

int p;

p=(a*100+b)*n;

cout<<p/100<<" "<<p%100;

return 0;

}

Описание решения

Для решения данной задачи нужно использовать тип данных int, потому что вводим целочисленные данные: гривны, копейки и количество.

Этой формулой мы считаем, сколько в копейках заплатил Петя за определенное количество пирожков: [latex]p=(a\cdot 100 + b)\cdot n[/latex]

Далее, из количества копеек высчитываем количество гривен [latex]p/ 100[/latex] и с помощью деления по модулю находим количество копеек [latex]p\% 100[/latex], и выводим ответ на экран.

Для того, чтобы посмотреть выполненное задание, надо нажать сюда.

Для того, чтобы посмотреть, как работает программа со входными данными [latex]1, 25, 2,[/latex] нужно нажать сюда.