e-olymp 5071. Проверка на неориенитрованность

29/04/2016 by Кудымовская Вика

Задача. Проверка на неориенитрованность

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

По заданной квадратной матрице [latex]n\times n[/latex] из нулей и единиц определите, может ли данная матрица быть матрицей смежности простого неориентированного графа.

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

Входной файл содержит число [latex]n(1\leq n\leq 100)[/latex] — размер матрицы, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — саму матрицу.

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

Выведите в выходной файл YES если приведенная матрица может быть матрицей смежности простого неориентированного графа и NO в противном случае.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	3 0 1 1 1 0 1 1 1 0	YES
2.	3 0 1 0 1 0 1 1 1 0	NO
3.	3 0 1 0 1 1 1 0 1 0	NO

Реализация

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n; 
    cin >> n;
    vector<int> G(n*n);
    for (int i = 0; i < G.size(); i++) 
    { 
        cin >> G[i];
    }
    int j = 0, c = 0, s = 0;
    /*с - счетчик циклов, сигнализирует о завершении текущего цикла сравнения 
    элементов i строки и j столбца; j - служит индексом для элементов столбца;
    s - счетчик столбцов, служит для задания нового начального значения индексу 
    j при переходе к следующему циклу сравнения элементов i строки и j столбца;*/
    bool f = true;              
    for (int i = 0; i < n*n; i++)//задаем цикл по всему массиву
    {
        if (G[i] != G[j]) { f=false; break; }
        if (c == n - 1)             
        {                   
            c = 0; s++; j = s;      
        }
        /*если уже сравнили n-1 строку и столбец, обнуляем c, увеличиваем s 
        и присваиваем его как новое начальное значение для индекса элементов столбца j*/
        else
        {
            j = j + n;//на каждом шаге устанавливаем индекс для элемента столбца
            c++;                
        }
    }
    for (int i = 0; i < n*n; i = i + n + 1)
    /*цикл для определения равенства нулю элементов главной диагонали - индекс 
    увеличивается на n+1 на каждом шаге*/
    {                   
        if (G[i] != 0) { f = false; break; }    
    }
    if (f) cout << "YES";
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector<int> G(n*n);

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

{

cin >> G[i];

}

int j = 0, c = 0, s = 0;

/*с - счетчик циклов, сигнализирует о завершении текущего цикла сравнения

элементов i строки и j столбца; j - служит индексом для элементов столбца;

s - счетчик столбцов, служит для задания нового начального значения индексу

j при переходе к следующему циклу сравнения элементов i строки и j столбца;*/

bool f = true;

for (int i = 0; i < n*n; i++)//задаем цикл по всему массиву

{

if (G[i] != G[j]) { f=false; break; }

if (c == n - 1)

{

c = 0; s++; j = s;

}

/*если уже сравнили n-1 строку и столбец, обнуляем c, увеличиваем s

и присваиваем его как новое начальное значение для индекса элементов столбца j*/

else

{

j = j + n;//на каждом шаге устанавливаем индекс для элемента столбца

c++;

}

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

/*цикл для определения равенства нулю элементов главной диагонали - индекс

увеличивается на n+1 на каждом шаге*/

{

if (G[i] != 0) { f = false; break; }

}

if (f) cout << "YES";

else cout << "NO";

return 0;

}

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

Чтобы введённая матрица была матрицей смежности простого неориентированного графа, она должна, во-первых, быть симметричной, то есть элементы на соответствующих позициях должны быть равны между собой: [latex]a[i][j]=a[j][i][/latex]. Во-вторых, необходимо, чтобы элементы главной диагонали матрицы равнялись нулю. Таким образом, нам нужно проверить, выполняются ли указанные условия.
Создаём переменную f типа bool. Изначально f=true. Если при проверке на симметричность и равенство нулю главной диагонали хоть одно значение элемента матрицы не удовлетворяет условию, флаг устанавливается в «ложь» и происходит выход из цикла проверки. Это означает соответственно, что введённая матрица не является матрицей смежности неориентированного графа, — на экран выводится «NO». Если же оба условия выполняются, приведённая матрица — матрица смежности. Выводим «YES».

Подробнее о графах и матрице смежности можно прочесть, используя следующие интернет-ресурсы:

Для запроса на выполнение следует перейти по ссылке.

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

Related Images:

A305

27/04/2016 by Кудымовская Вика

Задача A305

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

Даны действительные числа [latex]a_{1},\dots,a_{n}[/latex]. Оставить без изменения последовательность [latex]a_{1},\dots,a_{n}[/latex], если она упорядочена по неубыванию или по невозрастанию; в противном случае удалить из последовательности те члены, порядковые номера которых кратны четырём, сохранив прежним порядок оставленных членов.

Тестирование

№	Входные данные	Выходные данные
1.	5 -1 2 3 4 5	-1 2 3 4 5
2.	6 6 0 2 3 4 6.7	0 2 3 6.7
3.	10 1 2 5 7 -10 3 1 3 2 1	2 5 7 3 1 3 1
4.	5 1 5 6 7.5 0	5 6 7.5
5.	3 -23 46 -80	46 -80

Реализация

#include <iostream>
#include <vector>
#include <iterator>
 
using namespace std;
 
int main()
{
    int size_of_the_sequence;
    int temp = 0; //счетчик
    cin >> size_of_the_sequence;  
    vector<double> v1 (size_of_the_sequence);
    vector<double> v2;
    bool h = true, l = true;
    for (int i = 0; i < size_of_the_sequence; i++)
    {
        cin >> v1[i];
        if (i % 4 == 0) temp++;
    }
    for (int i = 1; i < size_of_the_sequence; i++)
    {
        if (v1[i - 1] <= v1[i])
        {
            l = false;
        }
        if (v1[i - 1] >= v1[i])
        {
            h = false;
        }
    }
    if (!l && !h)//исходная последовательность не упорядочена ни по возрастанию, ни по убыванию
    {
        v2.resize(size_of_the_sequence - temp);
        int size_of_the_sequence = 0;
        for (int i = 0; i < v1.size(); i++)
        {
            if (i % 4 == 0) { size_of_the_sequence++; continue; }
            else v2[i - size_of_the_sequence] = v1[i];
        }
        v1.resize(size_of_the_sequence - temp);
        v1 = v2;
        v1.shrink_to_fit();
        v2.clear();
    }
    copy(v1.begin(), v1.end(), ostream_iterator<double>(cout, " "));//выводим исходную последовательность без изменений
    return 0;
}

#include <iostream>

#include <vector>

#include <iterator>

using namespace std;

int main()

{

int size_of_the_sequence;

int temp = 0; //счетчик

cin >> size_of_the_sequence;

vector<double> v1 (size_of_the_sequence);

vector<double> v2;

bool h = true, l = true;

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

{

cin >> v1[i];

if (i % 4 == 0) temp++;

}

for (int i = 1; i < size_of_the_sequence; i++)

{

if (v1[i - 1] <= v1[i])

{

l = false;

}

if (v1[i - 1] >= v1[i])

{

h = false;

}

if (!l && !h)//исходная последовательность не упорядочена ни по возрастанию, ни по убыванию

{

v2.resize(size_of_the_sequence - temp);

int size_of_the_sequence = 0;

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

{

if (i % 4 == 0) { size_of_the_sequence++; continue; }

else v2[i - size_of_the_sequence] = v1[i];

}

v1.resize(size_of_the_sequence - temp);

v1 = v2;

v1.shrink_to_fit();

v2.clear();

}

copy(v1.begin(), v1.end(), ostream_iterator<double>(cout, " "));//выводим исходную последовательность без изменений

return 0;

}

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

Считываем все действительные числа до конца входного потока и записываем их в вектор v1. Проверяем, упорядочена ли последовательность по возрастанию или по убыванию. Если да, выводим на экран исходную последовательность без изменений с помощью функции copy() и итератора вывода ostream_iterator, который записывает элементы последовательно в выходной поток. Если же последовательность не упорядочена ни по убыванию, ни по возрастанию, удаляем из неё элементы, порядковые номера которых кратны четырём. Важно сохранить прежним порядок оставленных членов.
Работаем следующим образом:
1. Создаём вектор v_2.
2. Уменьшаем размер контейнера с помощью функции resize(): v2.resize(size_of_the_sequence - temp). Инициализируем переменную size_of_the_sequence значением ноль.
3. Если порядковый номер элемента неупорядоченной последовательности кратен четырём, то увеличиваем количество элементов на единицу с каждой итерацией. Иначе, присваиваем вектору v_2 значение вектора v_1: v2[i - size_of_the_sequence] = v1[i].
4. Уменьшаем размер контейнера v_1. Присваиваем вектору v_1 значение вектора v_2.
5. С помощью функции shrink_to_fit() уменьшаем количество используемой памяти вектора v_1.
6. Извлекаем все элементы из вектора v_2 с помощью функции clear().

Для запроса на выполнение следует перейти по ссылке.

Related Images:

e-olymp 6128. Простой дек

04/04/2016 by Кудымовская Вика

Задача. Простой дек

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

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

push_front

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

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

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

pop_back

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

front

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

back

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

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

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

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

pop_front,
pop_back,
front,
back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

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

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

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

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

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	push_back 3 push_front 14 size clear push_front 1 back push_back 2 front pop_back size pop_front size exit	ok ok 2 ok ok 1 ok 1 2 1 1 0 bye
2.	push_front 5 pop_front size push_back 3 push_front 10 back pop_back size clear front exit	ok 5 0 ok ok 3 3 1 ok -1 bye
3.	push_front 1 push_back 12 back front size pop_front size exit	ok ok 12 1 2 1 1 bye

Реализация

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

#define SIZE 10000
struct deque
{
    int storage[SIZE];
    int _size = 0, start = 0, end = 0;
    void push_front(int n)
    {
        if (_size == SIZE) { cout << "Full\n"; }
        else if (_size == 0) { storage[start] = n; _size++; }
        else { 
            if (start == 0) { start = SIZE - 1; storage[start] = n; _size++; }
            else { start--; storage[start] = n; _size++; }
            }
    }
    void push_back(int n)
    {
        if (_size == SIZE) { cout << "Full\n"; }
        else if (_size == 0) { storage[end] = n; _size++; }
        else {
            if (end == SIZE-1) { end = 0; storage[end] = n; _size++; }
            else { end++; storage[end] = n; _size++; }
        }
    }
    int pop_front()
    {
        int b;
        if (_size != 0 && (start == end)) { b = storage[start]; _size--; return b; }
        else if (_size == 0) { return -1; }
        else
        {
            b = storage[start];
            if (start == SIZE - 1) { start = 0; _size--; }
            else { start++; _size--; }
            return b;
        }
    }
    int pop_back()
    {
        int b;
        if (_size != 0 && (start == end)) { b = storage[end]; _size--; return b; }
        else if (_size == 0) { return -1; }
        else
        {
            b = storage[end];
            if (end == 0) { end = SIZE - 1; _size--; }
            else { end--; _size--; }
            return b;
        }
    }
    int front() { if (_size == 0) return -1; else return storage[start]; }
    int back() { if (_size == 0) return -1; else return storage[end]; }
    int size() { return _size; }
    void clear()
    {
        _size = 0;
        start = end = 0; 
    }
};

int main()
{
    deque d;
    string s;
    int n;
    while (cin >> s)
    {
        if (s == "push_front")
        {
            cin >> n;
            d.push_front(n);
            cout << "ok\n";
        }
        else if (s == "push_back")
        {
            cin >> n;
            d.push_back(n);
            cout << "ok\n";
        }
        else if (s == "pop_front")
        {
            cout << d.pop_front() << endl;
        }
        else if (s == "pop_back")
        {
            cout << d.pop_back() << endl;
        }
        else if (s == "front")
        {
            cout << d.front() << endl;
        }
        else if (s == "back")
        {
            cout << d.back() << endl;
        }
        else if (s == "size")
        {
            cout << d.size() << endl;
        }
        else if (s == "clear")
        {
            d.clear();
            cout << "ok\n";
        }

        else if (s == "exit") {
            cout << "bye\n";
            return 0;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

#include <iostream>

#include <string>

using namespace std;

#define SIZE 10000

struct deque

{

int storage[SIZE];

int _size = 0, start = 0, end = 0;

void push_front(int n)

{

if (_size == SIZE) { cout << "Full\n"; }

else if (_size == 0) { storage[start] = n; _size++; }

else {

if (start == 0) { start = SIZE - 1; storage[start] = n; _size++; }

else { start--; storage[start] = n; _size++; }

}

void push_back(int n)

{

if (_size == SIZE) { cout << "Full\n"; }

else if (_size == 0) { storage[end] = n; _size++; }

else {

if (end == SIZE-1) { end = 0; storage[end] = n; _size++; }

else { end++; storage[end] = n; _size++; }

}

int pop_front()

{

int b;

if (_size != 0 && (start == end)) { b = storage[start]; _size--; return b; }

else if (_size == 0) { return -1; }

else

{

b = storage[start];

if (start == SIZE - 1) { start = 0; _size--; }

else { start++; _size--; }

return b;

}

int pop_back()

{

int b;

if (_size != 0 && (start == end)) { b = storage[end]; _size--; return b; }

else if (_size == 0) { return -1; }

else

{

b = storage[end];

if (end == 0) { end = SIZE - 1; _size--; }

else { end--; _size--; }

return b;

}

int front() { if (_size == 0) return -1; else return storage[start]; }

int back() { if (_size == 0) return -1; else return storage[end]; }

int size() { return _size; }

void clear()

{

_size = 0;

start = end = 0;

}

};

int main()

{

deque d;

string s;

int n;

while (cin >> s)

{

if (s == "push_front")

{

cin >> n;

d.push_front(n);

cout << "ok\n";

}

else if (s == "push_back")

{

cin >> n;

d.push_back(n);

cout << "ok\n";

}

else if (s == "pop_front")

{

cout << d.pop_front() << endl;

}

else if (s == "pop_back")

{

cout << d.pop_back() << endl;

}

else if (s == "front")

{

cout << d.front() << endl;

}

else if (s == "back")

{

cout << d.back() << endl;

}

else if (s == "size")

{

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

}

else if (s == "clear")

{

d.clear();

cout << "ok\n";

}

else if (s == "exit") {

cout << "bye\n";

return 0;

}

return 0;

}

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

Реализуем двустороннюю очередь с помощью массива. Ввиду особенности структуры дека, необходимым является указание области, активной во время выполнения операций push_front, push_back, pop_front, pop_back, front и back. Это либо начало дека(переменная start), либо его конец(переменная end).
1. Перед выполнением операций push_front и push_back обязательной является проверка дека на заполненность и соответственно на пустоту. Таким образом, если размер дека равен максимально допустимому количеству элементов в структуре данных, программа выводит Full — ни одна из двух вышеупомянутых команд не выполняется. Аналогично, если размер дека равен нулю, увеличиваем его на единицу. Иначе: команды успешно выполняются с проверкой условий, представленных в коде программы. Программа выводит «ok».
2. Далее переходим к командам pop_front и pop_back. Здесь, как и в случае предыдущих операций, в первую очередь проверяем дек на пустоту. Если двусторонняя очередь не содержит элементов, то программа выводит -1. Важной также является проверка на равенство начала и конца дека, в этом случае нужно уменьшить размер структуры на единицу. Если дек содержит хотя бы один элемент, команды успешно выполняются и выводятся значения извлекаемых элементов.
3. Аналогично, перед выполнением команд front и back проверяем, содержит ли дек хотя бы один элемент. Если нет, выводится -1. Иначе: выводятся значения первого и последнего элемента соответственно.
4. Используем команду size, чтобы получить размер дека. Программа выводит количество элементов в деке.
5. Далее, с помощью команды clear удаляем из дека все элементы: присваиваем переменной _size(размер дека) и переменным start и end значение ноль. Программа выводит «ok».
6. Команда exit выводит «bye» — программа завершает работу.
Реализация вывода на экран всех требуемых значений происходит в теле функции main() с помощью строки s.

Для запроса на выполнение следует перейти по ссылке.

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

Related Images:

A278

16/03/2016 by Кудымовская Вика

Задача A278

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

Даны натуральные числа [latex]n_{1},\dots,n_{m}[/latex], действительные числа [latex]x_{1},\dots,x_{m}[/latex]. Вычислить [latex]\frac{n_{1}\cdot x_{1}+\dots+n_{m}\cdot x_{m}}{n_{1}+\dots+n_{m}}[/latex].

Тестирование

№	Входные данные	Выходные данные
1.	1 2 4 -1	-0.4
2.	1 2 3 4 5 0.6	1.88889
3.	5 -2 1 0.2 3 -3 2 0	-1.70909
4.	10 3.3 4 0.4 6 0.01 8 1 1 8	1.7469
5.	3 -0.5 2 -0.4 1 -0.3 5 32 11 5 20 -1	4.58095

Реализация (класс vector)

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	vector<int> n;
	vector<double> x;
	int a, sum2 = 0;
	double b, res = 0, sum1 = 0; 
	while (cin >> a >> b) 
	{ 
		n.push_back(a); 
		x.push_back(b); 
	} 
	for (int i=0; i < x.size(); i++) 
	{ 
		sum1 += n[i] * x[i];
		sum2 += n[i];
		res = sum1 / sum2;
	} 
	cout << res << endl; 
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector<int> n;

vector<double> x;

int a, sum2 = 0;

double b, res = 0, sum1 = 0;

while (cin >> a >> b)

{

n.push_back(a);

x.push_back(b);

}

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

{

sum1 += n[i] * x[i];

sum2 += n[i];

res = sum1 / sum2;

}

cout << res << endl;

return 0;

}

Алгоритм решения (класс vector)

Считываем все натуральные числа до конца входного потока и записываем их в вектор [latex]n[/latex]. Аналогично, считываем все действительные числа до конца входного потока и записываем их в вектор [latex]x[/latex].

Вычисляем значение выражения [latex]n_1\cdot x_1+\dots+n_m\cdot x_m[/latex], накапливая сумму sum1.
Вычисляем значение выражения [latex]n_1+\dots+n_m[/latex], накапливая сумму sum2.
Находим результат res от деления sum1 на sum2.

Реализация (потоковая обработка)

#include <iostream>
#include <cmath> 
using namespace std;
 
int main()
{
	int member1, sum2 = 0;
	double member2, res = 0, sum1 = 0;
	while (cin >> member1 >> member2)
	{
		if (member1=='e') break;
		sum1 += member1 * member2;
		sum2 += member1;
	}
	res = sum1 / sum2;
	cout<< res << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int member1, sum2 = 0;

double member2, res = 0, sum1 = 0;

while (cin >> member1 >> member2)

{

if (member1=='e') break;

sum1 += member1 * member2;

sum2 += member1;

}

res = sum1 / sum2;

cout<< res << endl;

return 0;

}

Алгоритм решения (потоковая обработка)

Считываем все натуральные числа до конца входного потока и записываем их в переменную member1. Аналогично, считываем все действительные числа до конца входного потока и записываем их в переменную member2.
Пока вводятся данные:

Вычисляем значение выражения [latex]n_1\cdot x_1+\dots+n_m\cdot x_m[/latex], накапливая сумму sum1.
Вычисляем значение выражения [latex]n_1+\dots+n_m[/latex], накапливая сумму sum2.
Находим результат res от деления sum1 на sum2.

Для запроса на выполнение следует перейти по ссылке (класс vector).

Для запроса на выполнение следует перейти по ссылке (потоковая обработка).

Related Images:

e-olymp 2162. Палиндром

19/12/2015 by Кудымовская Вика

Задача. Палиндром

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

Палиндром — это строка, которая одинаково читается слева направо и справа налево. Составьте программу, которая проверяет, является ли заданный текст палиндромом. Не забудьте, что при чтении пробел никак не произносится.

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

Дана строка [latex]S[/latex], [latex]|S| \leq 255[/latex], состоящая из строчных латинских букв и пробелов. Под [latex]|S|[/latex] подразумевается длина строки.

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

Требуется вывести «YES«, если текст является палиндромом, «NO» если не является.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	palindrom	NO
2.	a roza upala na lapu azora	YES
3.	my gym	YES
4.	character	NO

Реализация (с использованием c-string)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main()
{
	const int startSize = 256;
	char s[startSize];
	char s_1[startSize];
	cin.getline(s, 256);
	int j = 0;
	for (int i = 0; i < startSize; i++)
	{
		if (s[i] == ' ') continue; 
		//учитываем, что пробел при чтении никак не произносится
		s_1[j] = s[i];
		j++;
	}
	int resSize = strlen(s_1);
	char * s_2 = new char[resSize + 1];
	for (int i = 0; i < resSize; i++)
	{
		s_2[i] = s_1[resSize - 1 - i];
	}
	s_2[resSize] = '\0';
	if (!strcmp(s_1, s_2))
	{
		cout << "YES\n";
	}
	else
	{
		cout << "NO\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int main()

{

const int startSize = 256;

char s[startSize];

char s_1[startSize];

cin.getline(s, 256);

int j = 0;

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

{

if (s[i] == ' ') continue;

//учитываем, что пробел при чтении никак не произносится

s_1[j] = s[i];

j++;

}

int resSize = strlen(s_1);

char * s_2 = new char[resSize + 1];

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

{

s_2[i] = s_1[resSize - 1 - i];

}

s_2[resSize] = '\0';

if (!strcmp(s_1, s_2))

{

cout << "YES\n";

}

else

{

cout << "NO\n";

}

return 0;

}

Алгоритм решения (c-string)

С помощью функции [latex]strcmp()[/latex] сравниваем символы строк [latex] s_1[/latex] и [latex]s_2[/latex], предварительно учтя тот факт, что пробел при чтении никак не произносится. Если они идентичны, введенный текст одинаково читается слева направо и справа налево, то есть является палиндромом. В противном случае, текст палиндромом не является. Важно отметить, что функция [latex]strcmp()[/latex] учитывает регистр введенных символов, согласно условию мы должны использовать строчные латинские буквы.

Для запроса на выполнение следует перейти по ссылке.

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

Реализация (с использованием string)

#include <iostream>
#include <string>
using namespace std;
 
int main() {
	string s;
    char c;
    while (cin >> c)
    {
        if (c != ' ') 
        	s.push_back(c);
    }
    if (s.empty())
    {
        cout << "YES";
        return 0;
    }
    bool palindrom = true;
    for (int i = 0; i <= s.length()/2; i++)
    {
        if (s.at(i) != s.at(s.length()-1-i))
        {
            palindrom = false;
            break;
        }
    }
    cout << (palindrom ? "YES" : "NO");
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

char c;

while (cin >> c)

{

if (c != ' ')

s.push_back(c);

}

if (s.empty())

{

cout << "YES";

return 0;

}

bool palindrom = true;

for (int i = 0; i <= s.length()/2; i++)

{

if (s.at(i) != s.at(s.length()-1-i))

{

palindrom = false;

break;

}

cout << (palindrom ? "YES" : "NO");

return 0;

}

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

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

Для запроса на выполнение следует перейти по ссылке.

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

Related Images:

MLoop 20

01/11/2015 by Кудымовская Вика

Задача. Вычислите с точностью [latex]\varepsilon[/latex] сумму ряда [latex]\sum_{i=1}^{\infty}{\frac{i}{3^i}}[/latex].

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

Точность [latex]\varepsilon[/latex].

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

Вывести значение суммы ряда.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	0.1	0.666667
2.	0.01	0.736626
3.	0.001	0.749276
4.	0.0001	0.749903
5.	0.0000001	0.75

Реализация (первый вариант кода)

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

int main() {
	int i;
	double E; // переменная для обозначения точности
	double a = 1/3.0, sum = 1/3.0;
  	//присваиваем переменным a(член ряда) и sum значение первого члена ряда
 	cin >> E;
 	/*a *= (i+1)/(3*i) - формула для вычисления очередного члена ряда*/
 	for (i = 1; fabs(a *= (double)(i+1)/(3*i)) >= E; i++)
 	{
    	sum +=a;
 	}
 	cout << sum << endl;
 	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int i;

double E; // переменная для обозначения точности

double a = 1/3.0, sum = 1/3.0;

//присваиваем переменным a(член ряда) и sum значение первого члена ряда

cin >> E;

/*a *= (i+1)/(3*i) - формула для вычисления очередного члена ряда*/

for (i = 1; fabs(a *= (double)(i+1)/(3*i)) >= E; i++)

{

sum +=a;

}

cout << sum << endl;

return 0;

}

Реализация (второй вариант кода)

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

double arr(double sum, double a, double E, int i)
{
	if (fabs(a *= (double)(i + 1) * pow(3 * i, -1)) < E)
	{
		return sum;
	}
	else
	{
		i++;
		sum += a;
		return arr(sum, a, E, i);
	}
}
int main()
{
	int i=1;
	double E; // переменная для обозначения точности
	double a = 1 / 3.0, sum = 1 / 3.0;
	//присваиваем переменным a(член ряда) и sum значение первого члена ряда
	cin >> E;
	cout << arr(sum, a, E, i) << endl;
	system("pause");
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double arr(double sum, double a, double E, int i)

{

if (fabs(a *= (double)(i + 1) * pow(3 * i, -1)) < E)

{

return sum;

}

else

{

i++;

sum += a;

return arr(sum, a, E, i);

}

int main()

{

int i=1;

double E; // переменная для обозначения точности

double a = 1 / 3.0, sum = 1 / 3.0;

//присваиваем переменным a(член ряда) и sum значение первого члена ряда

cin >> E;

cout << arr(sum, a, E, i) << endl;

system("pause");

return 0;

}

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

Выводим формулу для вычисления значения каждого последующего члена ряда: [latex]a_{n+1}=a_n\cdot \frac{i+1}{3^{i+1}}\cdot \frac{3^i}{i}=a_n\cdot \frac{i+1}{3i}[/latex].
Вычисляем значение первого члена ряда: [latex]a[/latex]: [latex]a=\frac{i}{3^i}=\frac{1}{3}[/latex].
Присваиваем [latex]sum[/latex] значение первого члена ряда.
Абсолютное значение каждого последующего члена ряда сравниваем с [latex]\varepsilon[/latex]: при условии, что [latex]|a_{n+1}|\geq\varepsilon[/latex], накапливается сумма (значение суммы увеличивается на очередной член ряда [latex]a_{n+1}[/latex]). Если же [latex]|a_{n+1}|<\varepsilon[/latex], выводится значение суммы ряда.

Для запроса на выполнение следует перейти по ссылке (первый вариант кода).

Для запроса на выполнение следует перейти по ссылке (второй вариант кода).

Related Images:

e-olymp 60. Площадь многоугольника

06/10/2015 by Кудымовская Вика

Задача. Площадь многоугольника

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

Заданы координаты [latex]n[/latex] последовательных вершин многоугольника. Определить его площадь.

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

Первая строка содержит количество вершин многоугольника [latex]n[/latex]. В следующих [latex]n[/latex] строках через пробел заданы целочисленные координаты его последовательных вершин [latex]x_i, y_i[/latex]. Известно, что [latex]3 \leq n \leq 1000, -1000 \leq x[i], y[i] \leq 1000[/latex].

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

Площадь многоугольника [latex]S[/latex], вычисленная с точностью до трех десятичных знаков.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные ([latex]n[/latex], [latex]x_i, y_i[/latex])	Выходные данные
1.	3, (0, 0), (0, 2), (2, 0)	2.000
2.	4, (-1000, 500), (-500, 1000), (2, 10), (35, 60)	339865.000
3.	10, (51, -20), (15, 3), (45, 200), (100, -100), (201, 55), (70, -80), (25, 333), (999, 0), (500, 77), (5, -6)	124562.500
4.	5, (13, -92), (44, 0), (-800, 30), (27, 2), (1, 2)	1446.000

Реализация

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main() { 
    int n, x1, x2, y1, y2, x, y; 
    double sum=0; 
    cin >> n >> x >> y; 
    x1=x; 
    y1=y; 
    for (int i=0; i<(n-1); i++) { 
        cin >> x2 >> y2; 
        sum=sum+(x1+x2)*(y2-y1); 
        x1=x2; 
        y1=y2; 
    } 
    sum=sum+(x+x2)*(y-y2); 
    cout << fixed << setprecision(3) << abs(sum) / 2 << endl;
    return 0; 
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

int n, x1, x2, y1, y2, x, y;

double sum=0;

cin >> n >> x >> y;

x1=x;

y1=y;

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

cin >> x2 >> y2;

sum=sum+(x1+x2)*(y2-y1);

x1=x2;

y1=y2;

}

sum=sum+(x+x2)*(y-y2);

cout << fixed << setprecision(3) << abs(sum) / 2 << endl;

return 0;

}

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

Даны координаты последовательных [latex]n[/latex] вершин многоугольника: [latex]x_i, y_i[/latex]. Для того, чтобы вычислить его площадь, воспользуемся формулой: [latex]S=\frac{1}{2}\cdot |\sum_{i=1}^{n}{(x_i + x_{i+1})\cdot (y_i — y_{i+1})}|[/latex], где [latex]x_0, y_0=x_{n+1}, y_{n+1}[/latex].

Подробнее о вычислении площади произвольного многоугольника можно прочесть здесь.

Для запроса на выполнение перейдите по ссылке.

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

Related Images:

Mif 17.15

01/10/2015 by Кудымовская Вика

Задача Mif17.15

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

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

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

В одной строке задано два числа – координаты точки latex[/latex].

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

Вывести: «Принадлежит» или «Не принадлежит»(без кавычек).

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные	Выходные данные
1.	1.5 7	Не принадлежит
2.	3 4	Не принадлежит
3.	2 -3.6	Принадлежит
4.	5 0	Принадлежит
5.	0 1	Не принадлежит
6.	0 -4	Не принадлежит
7.	3 3	Принадлежит
8.	2 3	Принадлежит

Реализация

#include <iostream>
using namespace std;
 
int main () {
    double x, y, k, m, n;
    int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника
    cin >> x >> y; //координаты произвольной точки
    k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);
    m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);
    n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);
    cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");
    return 0;
}

#include <iostream>

using namespace std;

int main () {

double x, y, k, m, n;

int x1=2, y1=5, x2=5, y2=0, x3=2, y3=-4; //координаты вершин треугольника

cin >> x >> y; //координаты произвольной точки

k= (x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y);

m= (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y);

n= (x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y);

cout << ((k>=0 && m>=0 && n>=0) || (k<=0 && m<=0 && n<=0)? "Принадлежит": "Не принадлежит");

return 0;

}

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

Пусть на плоскости дан треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]C(x_3, y_3)[/latex]. А [latex]D(x, y)[/latex] — произвольная точка на координатной плоскости. Положим, [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] — векторы.

Для того, чтобы точка [latex]D(x, y)[/latex] принадлежала данному треугольнику, необходимо, чтобы псевдоскалярное (косое) произведение соответствующих векторов было больше или же меньше нуля.
Если векторы заданы своими координатами [latex]a(x_1, y_1), b(x_2, y_2)[/latex], то их косое произведение [latex][a,b]=x_1\cdot y_2 — x_2\cdot y_1[/latex]. Пользуясь данной формулой, запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]B(x_2, y_2)[/latex] и [latex]D(x, y)[/latex]: [latex]k=x_1y_2 — x_2y_1 — x_1y + xy_1 + x_2y — xy_2=(x_1 — x)\cdot (y_2 — y_1) — (x_2 — x_1)\cdot (y_1 — y)[/latex].
Далее запишем косое произведение векторов [latex]B(x_2, y_2)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex]: [latex]m=x_2y_3 — x_3y_2 — x_2y + xy_2 + x_3y — xy_3=(x_2 -x)\cdot (y_ 3- y_2) — (x_3 — x_2)\cdot (y_2 — y)[/latex].
Запишем косое произведение векторов [latex]A(x_1, y_1)[/latex], [latex]C(x_3, y_3)[/latex] и [latex]D(x, y)[/latex] : [latex]n=x_1y_3 — x_3y_1 — x_1y + xy_1 + x_3y — xy_3=(x_3 — x)\cdot (y_1 — y_3) — (x_1 — x_3)\cdot (y_3 — y)[/latex].
Если [latex]k \leq 0 [/latex] и [latex]m \leq 0[/latex] и [latex]n \leq 0[/latex] или [latex]k \geq 0[/latex] и [latex]m \geq 0[/latex] и [latex]n \geq 0[/latex], то делаем вывод: точка принадлежит треугольнику.
Если ни одно из вышеуказанных условий не выполняется, то точка не принадлежит треугольнику.

Ознакомиться с теоретическим материалом можно здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

Ю2.6

30/09/2015 by Кудымовская Вика

Условие

Четырёхугольник [latex]ABCD[/latex] задан координатами своих вершин на плоскости: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex] и [latex]C(x_c,y_c)[/latex], [latex]D(x_d,y_d)[/latex]. Определить тип четырёхугольника: прямоугольник, параллелограмм, трапеция, произвольный четырёхугольник. Учесть погрешность вычислений.

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

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

В одной строке заданы 8 чисел [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex] — координаты вершин четырёхугольника [latex]ABCD[/latex], значения которых не превышают по модулю [latex]50[/latex].

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

В первой строке вывести: «Тип четырёхугольника: «(без кавычек).
Во второй строке вывести: «Произвольный четырёхугольник» или «Прямоугольник» или «Параллелограмм» или «Трапеция»(без кавычек). Одно исключает другое.

Также условие задачи можно посмотреть, скачав ознакомительную версию задачника А.Юркина здесь.

Тестирование

№	Координаты [latex]x_a, x_b, x_c, x_d, y_a, y_b, y_c, y_d[/latex]	Вердикт (тип четырёхугольника)
1.	-5 -4 -1 -2 -4 3 -1 -8	Параллелограмм
2.	-2 -3 7 3 -2 1 7 1	Трапеция
3.	0 0 1 1 0 1 1 0	Прямоугольник
4.	50 -20 3 -50 7 6 2 3	Произвольный четырёхугольник
5.	2 -3 -6 -1 4 7 6 3	Параллелограмм
6.	1 -5 6 20 2 0 13 -9	Произвольный четырёхугольник
7.	0 1 2 1 0 1 1 0	Параллелограмм
8.	-6 0 6 0 1 5 -4 -8	Прямоугольник

Реализация

#include <iostream>
#include <cmath>
using namespace std;
 
int main () {
    setlocale(LC_ALL,"Russian");
    int xa, xb, xc, xd, ya, yb, yc, yd; 
    cout << "Тип четырёхугольника: " << endl;
    cin >> xa >> xb >> xc >> xd >> ya >> yb >> yc >> yd;
    //диагонали AC и BD четырёхугольника ABCD обозначим, как l и m, они являются векторами
    long double l= abs(sqrt((xc - xa) * (xc - xa) + (yc - ya) * (yc -ya)));
    long double m= abs(sqrt((xd - xb) * (xd - xb) + (yd - yb) * (yd -yb)));
    if (((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)) || ((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya))) { 
        if (((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya)) && ((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb))) 
            if (l==m)
                cout << "Прямоугольник" << endl;
            else {
                cout << "Параллелограмм" << endl;
            }
        else {
            cout << "Трапеция" << endl;
        }
    }
    else {
        cout << "Произвольный четырехугольник" << endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main () {

setlocale(LC_ALL,"Russian");

int xa, xb, xc, xd, ya, yb, yc, yd;

cout << "Тип четырёхугольника: " << endl;

cin >> xa >> xb >> xc >> xd >> ya >> yb >> yc >> yd;

//диагонали AC и BD четырёхугольника ABCD обозначим, как l и m, они являются векторами

long double l= abs(sqrt((xc - xa) * (xc - xa) + (yc - ya) * (yc -ya)));

long double m= abs(sqrt((xd - xb) * (xd - xb) + (yd - yb) * (yd -yb)));

if (((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)) || ((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya))) {

if (((xb - xa) * (yc - yd) == (xc - xd) * (yb - ya)) && ((xc - xb) * (yd - ya) == (xd - xa) * (yc - yb)))

if (l==m)

cout << "Прямоугольник" << endl;

else {

cout << "Параллелограмм" << endl;

}

else {

cout << "Трапеция" << endl;

}

else {

cout << "Произвольный четырехугольник" << endl;

}

return 0;

}

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

Задан четырёхугольник [latex]ABCD[/latex] с такими координатами вершин: [latex]A(x_a,y_a)[/latex], [latex]B(x_b,y_b)[/latex], [latex]C(x_c,y_c)[/latex] и [latex]D(x_d,y_d)[/latex]. В данной задаче будет уместным использование аппарата векторной алгебры. Пусть стороны четырёхугольника — векторы.
Очевидно, что для того, чтобы определить тип данного четырёхугольника, необходимо воспользоваться известными свойствами, а именно: свойствами прямоугольника, параллелограмма и трапеции. Так как в задаче используется аппарат векторной алгебры, обращаемся к таким свойствам векторов, как коллинеарность и равенство.
Сразу же установим: является ли четырёхугольник трапецией. Проверим одну из двух пар сторон на параллельность. Для этого воспользуемся условием коллинеарности векторов на плоскости: [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}[/latex], если [latex]a_i, b_i\ne0[/latex]. Координаты векторов [latex]\vec{b}[/latex] и [latex]\vec{d}[/latex] должны быть пропорциональны, что означает, что соответствующие стороны параллельны. Следовательно, [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Или же координаты векторов [latex]\vec{a}[/latex] и [latex]\vec{c}[/latex] должны быть пропорциональны. Проверяем: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex]. Если условие не выполняется, четырёхугольник произвольный. Если, напротив, координаты хотя бы одной пары векторов пропорциональны, четырёхугольник является трапецией.
Если четырёхугольник — параллелограмм, то обе пары его противоположных сторон параллельны. Проверим, выполняется ли: [latex]\frac{x_b — x_a}{x_c — x_d}=\frac{y_b — y_a}{y_c — y_d}[/latex] и [latex]\frac{x_c — x_b}{x_d — x_a}=\frac{y_c — y_b}{y_d — y_a}[/latex]. Если условие выполняется, то заданный четырёхугольник — параллелограмм.
Частным случаем параллелограмма является прямоугольник. Диагонали [latex] AC, BD[/latex] обозначим как [latex] l, m[/latex] соответственно. Пусть [latex] l, m[/latex] — векторы. Вычислим длины векторов [latex]\vec{l}[/latex], [latex]\vec{m}[/latex], пользуясь формулой. Получаем: [latex]\vec{|l|}= \sqrt{(x_c — x_a)\cdot (x_c -x_a) + (y_c — y_a)\cdot (y_c -y_a)}[/latex], [latex]\vec{|m|}= \sqrt{(x_d — x_b)\cdot (x_d -x_b) + (y_d — y_b)\cdot (y_d -y_b)}[/latex]. При условии, что [latex]\vec{l}=\vec{m}[/latex], имеем прямоугольник.

Более детально со свойствами и видами четырёхугольников можно ознакомиться здесь, а с основными сведениями из векторной алгебры — здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

ML18

28/09/2015 by Кудымовская Вика

Задача ML18

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

Найти периметр треугольника по заданным координатам вершин [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex].

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

В одной строке заданы 9 чисел [latex]x_1, x_2, x_3, y_1, y_2, y_3, z_1, z_2, z_3[/latex] — координаты вершин треугольника [latex]ABC[/latex], значения которых не превышают по модулю [latex]100[/latex].

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

Вывести периметр [latex]p[/latex] данного треугольника.

Также условие задачи можно посмотреть здесь.

Тестирование

№	Входные данные ([latex]x_i, y_j, z_k; i, j, k= 1, 2, 3 [/latex])	Выходные данные
1	2 2 5 1 0 -1 3 5 10	16.0261556346
2	1 4 5 3 6 0 10.5 -2 -1	31.9047289894
3	15 26 13 32 18 56 80 0 -6.2	212.0962807371
4	-13 68 44 99 -100 70 0 2 1	450.5748518262
5	100 9 17 18 29 88 65 -16 0.36	310.4318979186

Реализация

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main ()
{
	double x1, x2, x3, y1, y2, y3, z1, z2, z3;
	long double a, b, c, p;
	//стороны AB, BC, AC треугольника ABC обозначим 
	//соответственно, используя переменные a, b, c
	//используем значения переменных с плавающей точкой
	cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;
	a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));
	b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));
	c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));
	p= a + b + c;
	//вычисляем периметр 
	cout << fixed << setprecision(10) << p << endl;
	//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой
	return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main ()

{

double x1, x2, x3, y1, y2, y3, z1, z2, z3;

long double a, b, c, p;

//стороны AB, BC, AC треугольника ABC обозначим

//соответственно, используя переменные a, b, c

//используем значения переменных с плавающей точкой

cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;

a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));

b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));

c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));

p= a + b + c;

//вычисляем периметр

cout << fixed << setprecision(10) << p << endl;

//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой

return 0;

}

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

Задан произвольный треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex]. Обозначим стороны треугольника [latex] AB, BC, AC[/latex] как [latex]a, b, c[/latex] соответственно.
Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[latex]a=\sqrt {(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}[/latex]; [latex]b= \sqrt {(x_3-x_2)^2 + (y_3-y_2)^2 + (z_3-z_2)^2}[/latex]; [latex]c= \sqrt {(x_3-x_1)^2 + (y_3-y_1)^2 + (z_3-z_1)^2} [/latex].
Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

Подробнее о декартовой системе координат можно прочесть здесь.

Для запроса на выполнение следует перейти по ссылке.

Related Images:

e-olymp 63. Анфиса и цветы

14/09/2015 by Кудымовская Вика

Задача. Анфиса и цветы

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

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

Посчитать, какое наибольшее количество кусочков сыра получит Анфиса, если она все время старается сохранить как можно больше цветов. При каждом очередном своем проходе Анфиса обязательно должна собрать как минимум один цветок.

h4″>Входные данные

В одной строке заданы два числа m и n [latex]\left( n, 0 < m, n ≤ 2\cdot 10^9 \right)[/latex].

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

Вывести наибольшее количество кусочков сыра, которые может получить Анфиса.

Также условие задачи можно посмотреть здесь.

Реализация

#include <iostream>     
using namespace std;
int main () {
    long m, n, p;
    cin >> m >> n;
    p = (m * n - (m + n - 1)) + 1;
    cout << p << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main () {

long m, n, p;

cin >> m >> n;

p = (m * n - (m + n - 1)) + 1;

cout << p << endl;

return 0;

}

Тестирование

№	Входные данные (m, n)	Выходные данные
1	2, 3	3
2	3, 3	5
3	3, 4	7
4	4, 3	7
6	5, 7	25

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

Задана цветочная клумба в виде шахматной доски размерами [latex]m[/latex] на [latex]n[/latex]. Очевидно, что количество цветов на данной клумбе равно [latex]m\cdot n[/latex]. Пусть Анфиса, совершая свое очередное передвижение, начиная с левого верхнего угла клумбы и направляясь к правому нижнему, съедает latex\cdot(n-1)[/latex] цветов, так как, согласно условию задачи, Анфиса обязательно должна собрать как минимум один цветок при каждом проходе. После каждого такого прохода на выходе она получает один кусочек сыра.

Следовательно, имеет место следующая формула: [latex]p=(m-1)\cdot(n-1)+1[/latex], где p — наибольшее количество кусочков сыра, которое может получить Анфиса. Действительно, если [latex]m=2[/latex], [latex]n=3[/latex], то получаем [latex]p=3[/latex].

Ссылка на засчитанное решение.

Для запроса на выполнение нажать здесь.