e-olymp 2401. Обход в ширину

31/05/2016 by Андрей Яроцкий

Задача 2401

Условие

Дан неориентированный граф. В нём необходимо найти расстояние от одной заданной вершины до другой.

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

В первой строке содержится три натуральных числа [latex]n, s[/latex] и [latex]f (1 [/latex] [latex]\le[/latex] [latex]s, f[/latex] [latex]\le[/latex] [latex]n[/latex] [latex]\le[/latex] [latex]100)[/latex] — количество вершин в графе и номера начальной и конечной вершин соответственно. Далее в n строках задана матрица смежности графа. Если значение в [latex]j[/latex]-м элементе [latex]i[/latex]-й строки равно [latex]1[/latex], то в графе есть направленное ребро из вершины [latex]i[/latex] в вершину [latex]j[/latex].

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

Вывести минимальное расстояние от начальной вершины до конечной. Если пути не существует, выведите [latex]0[/latex].

Тесты

№	Входные данные	Выходные данные
1	1 1 1 1	0
2	3 1 3 0 1 0 1 0 0 0 0 0	0
3	4 4 3 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0	2
4	5 1 4 0 1 0 0 1 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0	2

#include <iostream>
using namespace std;

struct node{
    int value;
    node * next;
    node(int v, node * n = NULL){
        value = v;
        next = n;
    }
};
 
struct queue{ // Структура очередь
    node * start;
    node * finish;
    int len = 0;
    queue(node * s = NULL, node * f = NULL){
        start = s;
        finish = f;
    }
    string push(int n){
        if(len == 0){
            node * new_node = new node(n,finish);
            start = new_node;
            finish = new_node;
        }else{
            node * new_node = new node(n,NULL);
            start -> next = new_node;
            start = new_node;
        }
        len++;
        return "ok";
    }
    int pop(){
        int v = finish -> value;
        finish = finish -> next;
        len--;
        return v;
    }
    int front(){
        return finish -> value;
    }
    int size(){
        return len;
    }
};

int main() {
    int n, s, f;
    cin >> n >> s >> f;
    int graph[n][n];
    int dist[n]; // Массив расстояний от начальной до i-ой вершины
    bool used[n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> graph[i][j];
        }
    }
    for(int i = 0; i < n; i++){
        dist[i] = 0;
        used[i] = false;
    }
    queue vertex; // Очередь вершин
    vertex.push(s-1);
    used[s-1] = true;
    while(vertex.size() != 0){
        int v = vertex.front();
        for(int i = 0; i < n; i++){
            if(graph[v][i] == 1 && used[i] == false){
                vertex.push(i);
                dist[i] = dist[v] + 1; 
                used[i] = true; // i-ая вершина пройдена и не будет корректироваться позже
            }
        }
        used[v] = true;
        vertex.pop();
    }
    cout << dist[f-1];
    return 0;
}

#include <iostream>

using namespace std;

struct node{

int value;

node * next;

node(int v, node * n = NULL){

value = v;

next = n;

}

};

struct queue{ // Структура очередь

node * start;

node * finish;

int len = 0;

queue(node * s = NULL, node * f = NULL){

start = s;

finish = f;

}

string push(int n){

if(len == 0){

node * new_node = new node(n,finish);

start = new_node;

finish = new_node;

}else{

node * new_node = new node(n,NULL);

start -> next = new_node;

start = new_node;

}

len++;

return "ok";

}

int pop(){

int v = finish -> value;

finish = finish -> next;

len--;

return v;

}

int front(){

return finish -> value;

}

int size(){

return len;

}

};

int main() {

int n, s, f;

cin >> n >> s >> f;

int graph[n][n];

int dist[n]; // Массив расстояний от начальной до i-ой вершины

bool used[n];

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

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

cin >> graph[i][j];

}

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

dist[i] = 0;

used[i] = false;

}

queue vertex; // Очередь вершин

vertex.push(s-1);

used[s-1] = true;

while(vertex.size() != 0){

int v = vertex.front();

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

if(graph[v][i] == 1 && used[i] == false){

vertex.push(i);

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

used[i] = true; // i-ая вершина пройдена и не будет корректироваться позже

}

used[v] = true;

vertex.pop();

}

cout << dist[f-1];

return 0;

}

Решение

Для решения данной задачи необходимо использовать алгоритм «Поиск в ширину». Суть данного алгоритма полагает в том, что все вершины, начиная с начальной, помещаются в структуру очередь [latex](queue)[/latex] в порядке удаления от начальной вершины. По мере заполнения очереди, каждой вершине приписывается величина расстояния [latex](dist)[/latex] от начальной вершины, после чего соответствующая вершина помечается как пройденная [latex](used)[/latex] и её расстояние от начальной вершины более не переписывается даже при повторном просмотре. Таким образом, каждой вершине, для которой существует путь, соединяющий её с начальной вершиной, сопоставляется минимальное расстояние от нее до начальной вершины. Если такого пути не существует, расстояние остается равным нулю. Подробней об этом алгоритме можно прочесть здесь

Ссылки

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

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

Решенная задача

Related Images:

AL6

26/05/2016 by Андрей Яроцкий

Задача AL6

Условие

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

Тесты

№	Входные данные	Выходные данные
1	(	NO
2	))	NO
3	[}	NO
4	{}	YES
5	(){}[]	YES
6	({[]}{})	YES
7	[({}())[]	NO

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

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
 
struct stack{
        char *bkt = new char;
        int cur;
        stack(){cur = 0;}
        void push(char x){
            bkt[cur++] = x;
        }
        void pop(){
            cur--;
        }
        char back(){
            return bkt[cur-1];
        }
        int size(){
            return cur;
        }
};
 
int main() {
    string brace;
    cin >> brace;
    stack x;
    if(brace[0] == '(' || brace[0] == '{' || brace[0] == '[') x.push(brace[0]); //Правильное выражение начинается только с открывающей скобки
    else{
        if(brace == "") cout << "YES";//Выражение без скобок также првильное
        else cout << "NO";
        return 0;
    }
    for(int i = 1; i < brace.length(); i++){
        if(brace[i] == '(' || brace[i] == '{' || brace[i] == '['){ //Любую открывающую скобку добавляем в стек
            x.push(brace[i]);
        }
        else if(abs(brace[i] - x.back()) < 3 && x.size() != 0){//Модуль разницы скобок одного типа меньше трех
            x.pop();
        }
        else{
            cout << "NO";
            return 0;
        }
    }
    if(x.size() == 0) cout << "YES";//Правильное арифметическое выражение получим при пустом стэке
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <string>

#include <cstring>

#include <cmath>

using namespace std;

struct stack{

char *bkt = new char;

int cur;

stack(){cur = 0;}

void push(char x){

bkt[cur++] = x;

}

void pop(){

cur--;

}

char back(){

return bkt[cur-1];

}

int size(){

return cur;

}

};

int main() {

string brace;

cin >> brace;

stack x;

if(brace[0] == '(' || brace[0] == '{' || brace[0] == '[') x.push(brace[0]); //Правильное выражение начинается только с открывающей скобки

else{

if(brace == "") cout << "YES";//Выражение без скобок также првильное

else cout << "NO";

return 0;

}

for(int i = 1; i < brace.length(); i++){

if(brace[i] == '(' || brace[i] == '{' || brace[i] == '['){ //Любую открывающую скобку добавляем в стек

x.push(brace[i]);

}

else if(abs(brace[i] - x.back()) < 3 && x.size() != 0){//Модуль разницы скобок одного типа меньше трех

x.pop();

}

else{

cout << "NO";

return 0;

}

if(x.size() == 0) cout << "YES";//Правильное арифметическое выражение получим при пустом стэке

else cout << "NO";

return 0;

}

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать структуру [latex]stack[/latex], в которую поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Ссылки

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

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

Related Images:

А291а

25/05/2016 by Андрей Яроцкий

Задача: А291а

Условие:

Даны действительные числа [latex]a_{1},\ldots,a_{30}.[/latex] Получить [latex]\max (a_{1}+ a_{30},a_{2}+a_{29},\ldots,a_{15}+a_{n}).[/latex]

Тесты:

№	Входные данные	Выходные данные
1	2 3 5 4	8
2	2 3 7 5 4	14
3	4.5 1.1 3 9.25 0.75	10.35
4	-4.5 -2 0 -7.1 5	0.5

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

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

bool f(double a, double b){ //Вспомогательная функция для сортировки вектора по убыванию
    return a>b;
}

int main() {
    vector<double> real;
    double value;
    while(cin >> value){
        real.push_back(value);
    }
    int size = real.size();
    int size_of_sum = ceil(size%2==0?size/2:size/2+1); //Размер вектора сумм
    vector<double> sum;
    for(int i = 0; i < size_of_sum; i++){
        if(i == size_of_sum-1 && size%2 != 0) sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size
        else sum.push_back(real[i] + real[size - i - 1]);
    }
    sort(sum.begin(),sum.end(),f); // Сортировка по убыванию
    cout << sum[0];
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

bool f(double a, double b){ //Вспомогательная функция для сортировки вектора по убыванию

return a>b;

}

int main() {

vector<double> real;

double value;

while(cin >> value){

real.push_back(value);

}

int size = real.size();

int size_of_sum = ceil(size%2==0?size/2:size/2+1); //Размер вектора сумм

vector<double> sum;

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

if(i == size_of_sum-1 && size%2 != 0) sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size

else sum.push_back(real[i] + real[size - i - 1]);

}

sort(sum.begin(),sum.end(),f); // Сортировка по убыванию

cout << sum[0];

return 0;

}

Решение:

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

Ссылки:

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

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

Related Images:

e-olymp 2164. Шифр Юлия

06/12/2015 by Андрей Яроцкий

Задача. Юлий Цезарь использовал свой способ шифрования текста. Каждая буква заменялась на следующую по алфавиту через [latex]k[/latex] позиций по кругу. Необходимо по заданной шифровке определить исходный текст.

Входные данные: В первой строке дана шифровка, состоящая из не более чем 255 заглавных латинских букв. Во второй строке число [latex]k (1[/latex] [latex]\leq[/latex] [latex]k[/latex] [latex]\leq[/latex] [latex]10)[/latex].

Выходные данные: Требуется вывести результат расшифровки.

Тесты:

№

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

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

XPSE

WORD

ZABC

WXYZ

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

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

int main() {
	const int MAX_SIZE = 256; // 256 - максимальное кол-во букв по условию + нулевой символ
	char *cipher = new char [MAX_SIZE]; 
	cin.getline (cipher,MAX_SIZE);
	int k;
	cin >> k;
	for(int i = 0; i < strlen(cipher); i++){  // Цикл дешифровки выполняется до последней буквы
		if(cipher[i] >= 'A' + k) cipher[i] -= k;
		else cipher[i] = 'Z' - (k - (cipher[i] - '@')); //cipher[i] - '@' расстояние между i-ым символом и символом 'A', где '@' - символ идущий перед символом 'A'
		/* Если полученный символ принадлежит к заглавным латинским буквам, ставим его на место зашифрованного
		   Если нет, то возвращаемся к символу "Z" и отступаем от него на k минус уже пройденное кол-во символов */
	}
	cout << cipher;
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

const int MAX_SIZE = 256; // 256 - максимальное кол-во букв по условию + нулевой символ

char *cipher = new char [MAX_SIZE];

cin.getline (cipher,MAX_SIZE);

int k;

cin >> k;

for(int i = 0; i < strlen(cipher); i++){ // Цикл дешифровки выполняется до последней буквы

if(cipher[i] >= 'A' + k) cipher[i] -= k;

else cipher[i] = 'Z' - (k - (cipher[i] - '@')); //cipher[i] - '@' расстояние между i-ым символом и символом 'A', где '@' - символ идущий перед символом 'A'

/* Если полученный символ принадлежит к заглавным латинским буквам, ставим его на место зашифрованного

Если нет, то возвращаемся к символу "Z" и отступаем от него на k минус уже пройденное кол-во символов */

}

cout << cipher;

return 0;

}

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

Каждая буква строки является элементом массива [latex]cipher[/latex]. Чтобы расшифровать строку нужно от значения [latex]i[/latex]-го элемента массива отнять [latex]k[/latex], тем самым сдвинуть символ на [latex]k[/latex] единиц по алфавиту, и заменить первоначальный символ на полученный результат. В случае если разница символа [latex]i[/latex]-го элемента и числа [latex]k[/latex] не входит в множество заглавных латинских букв, требуется от символа «Z» отнять оставшееся кол-во шагов [latex]k[/latex] (то есть не считая те которые уже были пройдены от изначального символа символа до крайнего символа «A»), и заменить первоначальный символ на полученный результат. Можно не беспокоиться о том, что символ вернется к «Z» более чем один раз так как условие исключает этот вариант ([latex]k<=10[/latex] при 26-ти символах латинского алфавита).

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

Код программы с типом данных string:

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

int main() {
	string cipher;
	getline(cin,cipher);
	int k;
	const int ABC_SIZE = 26; // Количество символов латинского алфавита
	cin >> k;
	string alp = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
	for(int i = 0; i < cipher.length(); i++){
	    int find = cipher[i] - 'A';
	    if(find - k < 0) cipher.at(i) = alp.at(ABC_SIZE - (k - find));
	    else cipher.at(i) = alp.at(find-k);
	}
	cout << cipher;
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string cipher;

getline(cin,cipher);

int k;

const int ABC_SIZE = 26; // Количество символов латинского алфавита

cin >> k;

string alp = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

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

int find = cipher[i] - 'A';

if(find - k < 0) cipher.at(i) = alp.at(ABC_SIZE - (k - find));

else cipher.at(i) = alp.at(find-k);

}

cout << cipher;

return 0;

}

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

Чтобы расшифровать слово, находящееся в строке [latex]cipher[/latex], необходимо заменить каждую букву данной строки на букву, находящуюся на [latex](find — k)[/latex] позиции строки [latex]alp[/latex], где [latex]alp[/latex] — строка, содержащая латинский алфавит, а [latex]find[/latex] — позиция заменяемой буквы в алфавите. В случае если разница [latex]find[/latex] и [latex]k[/latex] меньше нуля, заменяем букву строки [latex]cipher[/latex] на букву, находящуюся на [latex](26 — (k — find))[/latex] позиции строки [latex]alp[/latex], то-есть не считая то количество позиций которые уже были пройдены от изначального символа символа до первого символа строки [latex]alp[/latex]. Можно не беспокоиться о том, что символ вернется к к концу алфавита более чем один раз так как условие исключает этот вариант ([latex]k<=10[/latex] при 26-ти символах латинского алфавита).

Related Images:

MLoop 23

31/10/2015 by Андрей Яроцкий

Задача:

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

Входные данные: Точность [latex]\varepsilon[/latex].

Выходные данные: Сумма ряда [latex]{\sum_{i=1}^\infty}\frac{(-1)^i}{i!}[/latex] с точностью [latex]\varepsilon[/latex].

Тесты:

0.1

0.01

0.001

0.0001

№	Точность [latex]\varepsilon[/latex]	Сумма ряда [latex]{\sum_{i=1}^\infty}\frac{(-1)^i}{i!}[/latex]
1	0.1	0.375
2	0.01	0.366667
3	0.001	0.367857
4	0.0001	0.367882

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

int main() {
   double E; // Точность
   cin >> E;
   double x = 1;// ((-1)^0)/0! = 1 : первое слагаемое
   double sum = 1;// При любой точности сумма начинается с первого члена
   for(int i = 1; abs(x) > E; i++){ // Цикл подсчета суммы пока слагаемое больше точности
      x = -x/i; // С каждым действием знак меняется на противоположный
      sum += x;
   }
   cout << sum;
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double E; // Точность

cin >> E;

double x = 1;// ((-1)^0)/0! = 1 : первое слагаемое

double sum = 1;// При любой точности сумма начинается с первого члена

for(int i = 1; abs(x) > E; i++){ // Цикл подсчета суммы пока слагаемое больше точности

x = -x/i; // С каждым действием знак меняется на противоположный

sum += x;

}

cout << sum;

return 0;

}

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

В условии нам дана формула суммы ряда [latex]{\sum_{i=1}^\infty}\frac{(-1)^i}{i!}[/latex] с точностью [latex]\varepsilon[/latex].

Для начала, программа читает входные данные и присваивает их переменной [latex]\varepsilon[/latex](точность). Также вводим переменную [latex]sum[/latex], равную первому члену (на случай если введенная точность не позволит циклу начаться), накапливающую сумму ряда.

Далее следует цикл [latex]for[/latex] считающий сумму членов [latex]x[/latex] пока не достигнет точности [latex]\varepsilon[/latex]. Цикл прибавляет к [latex]sum[/latex] слагаемое, деленное на [latex]i[/latex] и с противоположным знаком. По окончании цикла выводим значение суммы [latex]sum[/latex] .

Ссылка на условие задачи

Ссылка на компилятор с кодом

Related Images:

MLoops 4

31/10/2015 by Андрей Яроцкий

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

-+-+-*-+-+-*-+-+-*-+-+-*-
+-+-*-+-+-*-+-+-*-+-+-*-+
-+-*-+-+-*-+-+-*-+-+-*-+-
+-*-+-+-*-+-+-*-+-+-*-+-+
+*-+-+-*-+-+-*-+-+-*-+-+-
*-+-+-*-+-+-*-+-+-*-+-+-*
-+-+-*-+-+-*-+-+-*-+-+-*-
+-+-*-+-+-*-+-+-*-+-+-*-+

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

Количество столбцов [latex]n > 0[/latex] и строк [latex]m > 0[/latex].

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

Таблица размером [latex]n[/latex] [latex]\times[/latex] [latex]m[/latex] аналогичная таблице в условии.

Тесты:

№	[latex]n[/latex] [latex]m[/latex]	Таблица
1	1 1	—
2	1 7	— + — + — * —
3	7 1	-+-+-*-
4	10 10	-+-+--+-+ +-+--+-+- -+--+-+- +--+-+-- --+-+--+ -+-+--+- -+-+--+-+ +-+--+-+- -+--+-+- +--+-+--
5	25 8	-+-+--+-+--+-+--+-+-- +-+--+-+--+-+--+-+--+ -+--+-+--+-+--+-+--+- +--+-+--+-+--+-+--+-+ --+-+--+-+--+-+--+-+- -+-+--+-+--+-+--+-+-* -+-+--+-+--+-+--+-+-- +-+--+-+--+-+--+-+--+

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

#include <iostream>
using namespace std;

int main() {
	int n, m;  // Количество столбцов и строк соответственно
	cin >> n >> m;
	for(int i = 0;i < m;i++){             // Цикл для перехода на новую строку
		for(int j = 0;j < n;j++){         // Цикл вычисления номера члена
			if(((i+j+1) % 6 == 0)&&((i+j) != 0)){ // Проверка на кратность шести
				cout << "*";
			}
			else cout << ((i+j+1) % 2 == 0?"+":"-");  // Проверка на кратность двум
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m; // Количество столбцов и строк соответственно

cin >> n >> m;

for(int i = 0;i < m;i++){ // Цикл для перехода на новую строку

for(int j = 0;j < n;j++){ // Цикл вычисления номера члена

if(((i+j+1) % 6 == 0)&&((i+j) != 0)){ // Проверка на кратность шести

cout << "*";

}

else cout << ((i+j+1) % 2 == 0?"+":"-"); // Проверка на кратность двум

}

cout << endl;

}

return 0;

}

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

Посмотрев на таблицу можно заметить, что знак «-» выводится когда номер члена последовательности нечетный, знак «+» когда четный и знак «*» когда член последовательности кратный 6. После объявления переменных [latex]n[/latex] и [latex]m[/latex](количество столбцов и строк соответственно) создаем два цикла — один внутри другого. Внешний цикл считает номер строки и, после выполнения внутреннего, переносит последовательность на новую строку. Внутренний цикл считает номер столбца и выполняет проверку на кратность шести, в этом случае выводится знак «*». В противном случае проводится проверка на кратность двум. Если номер члена последовательности кратен двум выводиться знак «+», в противном случае — «-«.

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

Код в компиляторе

Related Images:

Mif 14

30/10/2015 by Андрей Яроцкий

Задача:

Пересекаются ли отрезки. Для двух отрезков [latex]AB[/latex] и [latex]CD[/latex], заданных целочисленными координатами вершин в трёхмерном пространстве, определить имеют ли они общие точки.

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

Координаты отрезков [latex]AB[/latex] и [latex]CD[/latex]:

[latex]A(x_1;y_1),B(x_2;y_2),C(x_3;y_3),D(x_4;y_4)[/latex].

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

Расположение отрезков [latex]AB[/latex] и [latex]CD[/latex] относительно друг друга:

Прямые в разных плоскостях,
Прямые параллельны,
Отрезки находятся на одной прямой но не совпадают,
Отрезки совпадают,
Отрезки пересекаются,
Отрезки не пересекаются;

Тесты:

№	Координаты [latex]A(x_1;y_1)B(x_2;y_2)C(x_3;y_3)D(x_4;y_4)[/latex]	Расположение отрезков
1	1 1 1 2 2 2 0 5 0 2 6 -1	Прямые в разных плоскостях
2	1 1 1 -1 -1 -1 0 0 -1 2 2 1	Прямые параллельны
3	1 1 0 2 2 1 4 4 3 5 5 4	Отрезки находятся на одной прямой но не совпадают
4	0 0 0 3 3 6 2 2 4 5 5 10	Отрезки совпадают
5	0 0 0 1 1 1 0 1 1 0 -1 -1	Отрезки пересекаются
6	0 0 1 1 1 1 5 -2 5 4 -1 4	Отрезки не пересекаются
7	1 0 0 1 1 0 0 0 1 1 0 1	Прямые в разных плоскостях
8	1 1 0 1 1 5 2 4 -1 2 4 1	Прямые параллельны
9	1 1 0 2 1 0 5 1 0 6 1 0	Отрезки находятся на одной прямой но не совпадают

10	-1 -1 -1 1 1 1 0 0 0 2 2 2	Отрезки совпадают
11	1 1 4 2 2 4 2 1 4 1 2 4	Отрезки пересекаются
12	1 0 3 1 3 3 2 2 3 4 4 3	Отрезки не пересекаются

#include <iostream>
using namespace std;
 
double Mixed(double ax, double ay, double az, double bx, double by, double bz, double cx, double cy, double cz){
    return (ax*by*cz)+(ay*bz*cx)+(az*bx*cy)-(az*by*cx)-(ay*bx*cz)-(ax*bz*cy);   // Формула смешаного произведения, если = 0, то одна плоскость
}
 
bool Collinear(double ax, double bx, double ay, double by, double az, double bz){
    return ((ax/bx) == (ay/by) && (ay/by) == (az/bz)) ? true:false;   // Коллинеарность
}
 
bool VectorEquation(double x, double x0, double y, double y0, double z, double z0, double Vx, double Vy, double Vz){
    return  (x - x0)/Vx == (y - y0)/Vy && (y - y0)/Vy == (z - z0)/Vz ? true:false;   // уравнение прямой в пространстве 
}
 
double Min(double X1, double X2){
    return X1 < X2 ? X1:X2;
}
double Max(double X1, double X2){
    return X1 > X2 ? X1:X2;
}
bool CollinearforPerp(double ax, double ay, double az, double bx, double by, double bz){    // Условие коллинеарности при bx,by,bz=0
    return ((ay*bz-az*by == 0) && (az*bx-ax*by == 0) && (ax*by-ay*bx == 0)) ? true:false;
}
 
 
int main() {
    double Xa, Ya, Za, Xb, Yb, Zb, Xc, Yc, Zc, Xd, Yd, Zd;    // Координаты концов отрезков
    cin >> Xa >> Ya >> Za >> Xb >> Yb >> Zb >> Xc >> Yc >> Zc >> Xd >> Yd >> Zd;
    double VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz; //Координаты векторов
 
    VectorABx = Xb-Xa;
    VectorABy = Yb-Ya;
    VectorABz = Zb-Za;
 
    VectorCDx = Xd-Xc; 
    VectorCDy = Yd-Yc;
    VectorCDz = Zd-Zc;
 
    VectorACx = Xc-Xa;
    VectorACy = Yc-Ya;
    VectorACz = Zc-Za;

    if (Mixed(VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz) == 0){ // Смешанное произведение
        if(Xc == Xd || Yc == Yd || Zc == Zd){                                                                           // Частный случай, если прямая перпендикулярна какой-либо оси
            if(CollinearforPerp(VectorABx,VectorABy,VectorABz,VectorCDx,VectorCDy,VectorCDz)){                                     // Прямые Коллинеарны
                if((Xc == Xd && Xa != Xc) || (Yc == Yd && Ya != Yc) || (Zc == Zd && Za != Zd)){                         // Условие параллельности 
                    cout << "Прямые параллельны" << endl; 
                }
                else{
                    if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){
                        if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){
                            if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){
                                cout << "Отрезки совпадают" << endl;                                    // Пресечение отрезков
                            }
                            else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;
                        }
                        else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;
                    }
                    else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;                   
                }                           
            }
            else{
                if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){
                        if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){
                            if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){
                                cout << "Отрезки пересекаются" << endl;
                            }
                            else cout << "Отрезки не пересекаются" << endl;
                        }
                        else cout << "Отрезки не пересекаются" << endl;
                    }
                    else cout << "Отрезки не пересекаются" << endl;
            }
            return 0;
        }
        else{
            if (Collinear(VectorABx, VectorCDx, VectorABy, VectorCDy, VectorABz, VectorCDz)){                    // Прямые коллинеарны
                if(VectorEquation(Xa, Xc, Ya, Yc, Za, Zc, VectorCDx, VectorCDy, VectorCDz)){             // Совпадение прямых
                    if((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd)){ // Совпадение отрезков
                        cout<< "Отрезки совпадают" << endl;
                    }
                    else{ 
                        cout << "Отрезки на одной прямой но не совпадают" << endl;
                    }
                }
                else{
                    cout << "Прямые параллельны" << endl;
                }
            }
            else{
                if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) || (Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){
                    cout << "Отрезки пересекаются" << endl;
                }
                else cout << "Отрезки не пересекаются" << endl;
                }
        }
    }
    else{
        cout << "Прямые в разных плоскостях" << endl;
    }
    return 0;
}

100

101

102

103

#include <iostream>

using namespace std;

double Mixed(double ax, double ay, double az, double bx, double by, double bz, double cx, double cy, double cz){

return (ax*by*cz)+(ay*bz*cx)+(az*bx*cy)-(az*by*cx)-(ay*bx*cz)-(ax*bz*cy); // Формула смешаного произведения, если = 0, то одна плоскость

}

bool Collinear(double ax, double bx, double ay, double by, double az, double bz){

return ((ax/bx) == (ay/by) && (ay/by) == (az/bz)) ? true:false; // Коллинеарность

}

bool VectorEquation(double x, double x0, double y, double y0, double z, double z0, double Vx, double Vy, double Vz){

return (x - x0)/Vx == (y - y0)/Vy && (y - y0)/Vy == (z - z0)/Vz ? true:false; // уравнение прямой в пространстве

}

double Min(double X1, double X2){

return X1 < X2 ? X1:X2;

}

double Max(double X1, double X2){

return X1 > X2 ? X1:X2;

}

bool CollinearforPerp(double ax, double ay, double az, double bx, double by, double bz){ // Условие коллинеарности при bx,by,bz=0

return ((ay*bz-az*by == 0) && (az*bx-ax*by == 0) && (ax*by-ay*bx == 0)) ? true:false;

}

int main() {

double Xa, Ya, Za, Xb, Yb, Zb, Xc, Yc, Zc, Xd, Yd, Zd; // Координаты концов отрезков

cin >> Xa >> Ya >> Za >> Xb >> Yb >> Zb >> Xc >> Yc >> Zc >> Xd >> Yd >> Zd;

double VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz; //Координаты векторов

VectorABx = Xb-Xa;

VectorABy = Yb-Ya;

VectorABz = Zb-Za;

VectorCDx = Xd-Xc;

VectorCDy = Yd-Yc;

VectorCDz = Zd-Zc;

VectorACx = Xc-Xa;

VectorACy = Yc-Ya;

VectorACz = Zc-Za;

if (Mixed(VectorABx, VectorABy, VectorABz, VectorCDx, VectorCDy, VectorCDz, VectorACx, VectorACy, VectorACz) == 0){ // Смешанное произведение

if(Xc == Xd || Yc == Yd || Zc == Zd){ // Частный случай, если прямая перпендикулярна какой-либо оси

if(CollinearforPerp(VectorABx,VectorABy,VectorABz,VectorCDx,VectorCDy,VectorCDz)){ // Прямые Коллинеарны

if((Xc == Xd && Xa != Xc) || (Yc == Yd && Ya != Yc) || (Zc == Zd && Za != Zd)){ // Условие параллельности

cout << "Прямые параллельны" << endl;

}

else{

if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){

if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){

if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){

cout << "Отрезки совпадают" << endl; // Пресечение отрезков

}

else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;

}

else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;

}

else cout << "Отрезки находятся на одной прямой но не совпадают" << endl;

}

else{

if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){

if(((Min(Ya,Yb) <= Yc && Max(Ya,Yb) >= Yc) ||(Min(Ya,Yb) <= Yd && Max(Ya,Yb) >= Yd))||(((Min(Yc,Yd) <= Ya && Max(Yc,Yd) >= Ya) ||(Min(Yc,Yd) <= Yb && Max(Yc,Yd) >= Yb)))){

if(((Min(Za,Zb) <= Zc && Max(Za,Zb) >= Zc) ||(Min(Za,Zb) <= Yd && Max(Za,Zb) >= Zd))||(((Min(Zc,Zd) <= Za && Max(Zc,Zd) >= Ya) ||(Min(Zc,Zd) <= Zb && Max(Zc,Zd) >= Zb)))){

cout << "Отрезки пересекаются" << endl;

}

else cout << "Отрезки не пересекаются" << endl;

}

else cout << "Отрезки не пересекаются" << endl;

}

else cout << "Отрезки не пересекаются" << endl;

}

return 0;

}

else{

if (Collinear(VectorABx, VectorCDx, VectorABy, VectorCDy, VectorABz, VectorCDz)){ // Прямые коллинеарны

if(VectorEquation(Xa, Xc, Ya, Yc, Za, Zc, VectorCDx, VectorCDy, VectorCDz)){ // Совпадение прямых

if((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) ||(Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd)){ // Совпадение отрезков

cout<< "Отрезки совпадают" << endl;

}

else{

cout << "Отрезки на одной прямой но не совпадают" << endl;

}

else{

cout << "Прямые параллельны" << endl;

}

else{

if(((Min(Xa,Xb) <= Xc && Max(Xa,Xb) >= Xc) || (Min(Xa,Xb) <= Xd && Max(Xa,Xb) >= Xd))||(((Min(Xc,Xd) <= Xa && Max(Xc,Xd) >= Xa) ||(Min(Xc,Xd) <= Xb && Max(Xc,Xd) >= Xb)))){

cout << "Отрезки пересекаются" << endl;

}

else cout << "Отрезки не пересекаются" << endl;

}

else{

cout << "Прямые в разных плоскостях" << endl;

}

return 0;

}

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

Для решения задачи нам понадобятся следующие функции:

1.[latex]Mixed[/latex] — функция возвращающая значение смешанного произведения векторов

(Основная формула [latex]a_xb_yc_z+a_yb_zc_x+a_zb_xc_y-a_zb_yc_x-a_yb_xc_z-a_xb_zc_y [/latex])

2.[latex]Collinear[/latex] — функция принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.

(Основная формула [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex] )

3.[latex]VectorEquation[/latex] — Функция принимающая координаты двух точек принадлежащих разным прямым и координаты направляющего вектора, и возвращающая логическое значение true, если они принадлежат одной прямой, и false в противном случае.

(Основная формула [latex]\frac{x — x_0}{V_x} =\frac{y — y_0}{V_y} = \frac{z — z_0}{V_z}[/latex] )

4.[latex]Min[/latex] — возвращает минимум двух чисел.

5.[latex]Max[/latex] – возвращает максимум двух чисел.

6.[latex]CollinearforPerp[/latex] — функция принимающая координаты векторов, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае. Используется в случае для формулы коллинеарности [latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex] при [latex]b_x=0[/latex] , [latex]b_y=0[/latex] или [latex]b_z=0[/latex].

(Основная формула [latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex] )

Для удобства, заведем переменные для координат векторов соответствующих отрезкам. Первая проверка определяет чему равно смешанное произведение векторов. Если произведение равно [latex]0[/latex] то векторы находятся в одной плоскости, в противном случае — в разных.

Далее проверяем является ли какой либо вектор перпендикулярным какой-либо оси. Это необходимо так как в таком случае координаты вектора [latex] \vec{CD}[/latex] равны нулю, что недопустимо при делении функций на координаты данного вектора.

В случае если какой либо вектор перпендикулярный какой-либо оси, проверяем их коллинеарность по формуле [latex]CollinearforPerp[/latex]:

[latex]a_yb_z-a_zb_y = a_zb_x-a_xb_y = a_xb_y-a_yb_x = 0[/latex]

Если векторы коллинеарны то они параллельны в том случае, если координата вектора перпендикулярного некой оси не равна координате другого вектора той же оси [latex](X_c=X_d and X_a \neq X_c)[/latex] [latex]||[/latex] [latex](Y_c=Y_d and Y_a \neq Y_c)[/latex] [latex]||[/latex] [latex](Z_c=Z_d and Z_a \neq Z_c)[/latex] . В противном случае прямые совпадают. Отрезки также совпадают если одна из координат одного отрезка находится между большим и меньшем значением координат другого отрезка, для всех осей:

[latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_c and Max(X_a,X-b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

В противном случае отрезки находятся на одной прямой но не совпадают.

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

[latex](Min(X_a,X_b)[/latex][latex]\le[/latex][latex]X_c and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_c)[/latex] [latex]||[/latex] [latex](Min(X_a,X_b)[/latex] [latex]\le[/latex] [latex]X_d and Max(X_a,X_b)[/latex] [latex]\ge[/latex] [latex]X_d)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_a and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_a)[/latex] [latex]||[/latex] [latex](Min(X_c,X_d)[/latex] [latex]\le[/latex] [latex]X_b and Max(X_c,X_d)[/latex] [latex]\ge[/latex] [latex]X_b)[/latex]

Если же ни один вектор не перпендикулярен ни одной оси, проверяем вектора на коллинеарность стандартным способом ([latex]\frac{a_x}{b_x}=\frac{a_y}{b_y}= \frac{a_z}{b_z}[/latex])

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

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

Ссылка на код программы

Ссылка на условие задачи

Related Images:

e-olymp 2061. Юные программисты

30/09/2015 by Андрей Яроцкий

Задача

Известно, что в школе не менее чем [latex]k_1[/latex] учеников, но не более чем [latex]k_2[/latex] учеников. Также известно, что каждый мальчик дружит с [latex]n[/latex] девочками, а каждая девочка с [latex]m[/latex] мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Тесты:

№	Ввод	Вывод
1	20 30 4 5	27 15 12
2	40 50 5 4	45 20 25

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

#include <iostream>
using namespace std;
 
int main() {
   int k1, k2, n, m;
   int b, g; //b-boys;g-girls
   cin >> k1 >> k2 >> n >> m;
   for (g = n; true; g++)
   {
      b = g * m / n;
      if (((g * m) % n) == 0 && b + g >= k1) break; // перебираем варианты пока количество мальчиков не станет целым а сумма всех учеников будет больше k1
   }
   cout << b + g << " " << b << " " << g << endl;
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1, k2, n, m;

int b, g; //b-boys;g-girls

cin >> k1 >> k2 >> n >> m;

for (g = n; true; g++)

{

b = g * m / n;

if (((g * m) % n) == 0 && b + g >= k1) break; // перебираем варианты пока количество мальчиков не станет целым а сумма всех учеников будет больше k1

}

cout << b + g << " " << b << " " << g << endl;

return 0;

}

Решение:

Увеличиваем количество девочек на 1 пока количество мальчиков по формуле [latex]b = g \cdot m / n[/latex] не станет целочисельным значением и сумма мальчиков и девочек будет больше или равна минимальному возможному количеству учеников [latex]k_1[/latex].

Условие задачи можно найти на сайте e-olymp.
Ссылка на решение задачи на ideone.com здесь.
Ссылка на полностью решенную задачу здесь.

Related Images:

Mif17.11

30/09/2015 by Андрей Яроцкий

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

Тесты:

№	Ввод [latex](x,y)[/latex]	Вывод
1	3 1	YES
2	-3 1	NO
3	-3 -1	NO
4	3 -1	YES
5	4 7	NO
6	4 -7	NO

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

#include <iostream>
#include <math.h>
using namespace std;

int main() {
   double x, y, l; // x,y - координаты точки; l - расстояние от центра круга до точки
   double x1 = 0, y1 = 0, r = 6; // x1,y1 - центр круга; r - радиус
   double xz = 2; // начало сегмента круга
   cin >> x >> y;
   l = (x-x1)*(x-x1)+(y-y1)*(y-y1);
   if(x >= xz && r*r >= l) cout << "YES"; // область допустимых значений x
   else cout << "NO";
   return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double x, y, l; // x,y - координаты точки; l - расстояние от центра круга до точки

double x1 = 0, y1 = 0, r = 6; // x1,y1 - центр круга; r - радиус

double xz = 2; // начало сегмента круга

cin >> x >> y;

l = (x-x1)*(x-x1)+(y-y1)*(y-y1);

if(x >= xz && r*r >= l) cout << "YES"; // область допустимых значений x

else cout << "NO";

return 0;

}

Решение:

Изучив рисунок, находим координаты трех точек сегмента круга. После, находим координаты центра круга и его радиус с помощью данного сайта. Если проекция точки на ось [latex]OX[/latex] не находиться в области допустимых значений [latex]x[/latex], то точка не принадлежит сегменту круга в любом случае. Если же первое условие выполняется, то точка принадлежит сегменту круга тогда, когда квадрат расстояния ([latex]l[/latex]) от центра круга до точки меньше либо равно квадрату радиуса ([latex]r[/latex]) круга ([latex]r*r[/latex] >= [latex]l[/latex])

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

Ссылка на решение задачи на компиляторе ideone.com здесь.

Related Images:

ML14

28/09/2015 by Андрей Яроцкий

Задача

. Вычислить период колебания маятника длины [latex]l[/latex].

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

Длина нити маятника [latex]l[/latex].

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

Период колебаний маятника.

Тесты

№	Входные данные	Выходные данные
1	0,3	1.09891
2	1	2.00632
3	40	12.6891

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

#include<iostream>
#include<cmath>
using namespace std;
int main() {
 double T, l, g = 9.8075; //Где Т-период колебаний маятника, l-длина маятника, g-ускорение свободного падения на поверхности Земли в Одессе
 cin >> l;
 T = 2*M_PI*sqrt(l/g); //Формула периода колебаний маятника, где M_PI - константа π ~ 3,14
 cout << T;
 return 0;
}

#include<iostream>

#include<cmath>

using namespace std;

int main() {

double T, l, g = 9.8075; //Где Т-период колебаний маятника, l-длина маятника, g-ускорение свободного падения на поверхности Земли в Одессе

cin >> l;

T = 2*M_PI*sqrt(l/g); //Формула периода колебаний маятника, где M_PI - константа π ~ 3,14

cout << T;

return 0;

}

Пояснение

Условием задачи было вычислить период колебаний маятника [latex]T[/latex], имея длину маятника [latex]l[/latex]. Период колебаний маятника можно рассчитать с помощью формулы: [latex]T = 2\pi\sqrt{\frac{l}{g}}[/latex]. Мы объявляем три переменные типа [latex]double[/latex] [latex]T, l, g,[/latex] где [latex]T[/latex]-период колебаний маятника, [latex]l[/latex] — длина маятника, [latex]g[/latex] = [latex]9.8075[/latex] — ускорение свободного падения на поверхности Земли в Одессе. [latex]l[/latex] — входной параметр. Затем, используя формулу [latex]T = 2\pi\sqrt{\frac{l}{g}}[/latex], вычисляем и выводим значение периода.

Условие задачи здесь.
Ссылка на решение на ideone.com здесь.

Related Images:

e-olymp 929 Параллелограмм

14/09/2015 by Андрей Яроцкий

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

Условие:

Задано 4 числа [latex]a, b, c, d[/latex] определяющие длины отрезков. Определить, можно ли с этих отрезков образовать параллелограмм.

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

В единственной строке задано 4 числа через пробел.

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

Вывести в единственной строке слово «YES«, если параллелограмм образовать можно или «NO» (без кавычек) в противном случае.

Тесты

№	Входные данные	Выходные данные
1	2 4 2 4	YES
2	2 4 2.5 4	NO

#include <iostream>
using namespace std;
int main() {
   double a,b,c,d;
   cin>>a>>b>>c>>d;
   cout<<((a==c && b==d)||(a==b && c==d])||(a==d && c==b)?"YES":"NO");
   return 0;
}

#include <iostream>

using namespace std;

int main() {

double a,b,c,d;

cin>>a>>b>>c>>d;

cout<<((a==c && b==d)||(a==b && c==d])||(a==d && c==b)?"YES":"NO");

return 0;

}

Решение:

Параллелограммом называется четырехугольник у которого противолежащие стороны равны. Чтобы четырехугольник со сторонами [latex]a, b, c, d[/latex] являлся параллелограммом должно выполнятся одно из трех условий:

[latex]a=c[/latex] и [latex]b=d[/latex];

[latex]a=b[/latex] и [latex]c=d[/latex];

[latex]a=d[/latex] и [latex]c=b[/latex],

Код на IDEONE можно увидеть здесь.

Ссылку на полностью засчитанное решение на сайте e-olymp.com можно найти здесь