e-olymp 976. Флойд — существование

14/05/2015 by Осецимський Анатолій Вадимович

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

e-olymp 974. Флойд 1
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

Пройденный тесты.

e-olymp 976. Флойд — существование

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

Кратчайший путь может не существовать по двум причинам:

Нет ни одного пути.
Есть путь сколь угодно маленького веса

Пройденный тесты.

Первая задача решается Алгоритмом Флойда-Уоршела. Поскольку отрицательных ребер в графе нет, и просят вывести кратчайший путь к каждой из вершин, то надо было всего лишь определить, что мы возьмем за бесконечность. Я выбрал [latex]10001[/latex], поскольку максимальное количество вершин [latex]100[/latex], а вес ребер не превышает [latex]100[/latex], соответственной максимально возможное расстояние не превосходит [latex]100*100 = 10000[/latex].

Во второй задаче была та же идея, но в данной ситуация у нас были ребра отрицательного веса. И у нас появилась проблема, могли существовать циклы отрицательной длины(с каждым проходом расстояние до вершин уменьшалось). Поскольку мы пользовались [latex]while[/latex] -ом, мы зацикливались. По этому необходимо было прекращать добавлять вершины, которую имеют отрицательную индексацию и порогом выбрано [latex]-102[/latex], поскольку цикл мог содержать отрицательные ребра, но при это быть положительным, по этому [latex]<0[/latex] нам не подошло. Дальше необходимо было вывести матрицу существования, методом [latex]way[/latex] мы выходили из вершины и определяли индексацию, пуская из всех вершин, мы можем построково выводить матрицу, только необходимо восстанавливать к исходному виду сам граф. В выводе мы определяли, существует путь и мал ли он. Существование проверялось тем, что эта вершина была посещена, а путь к вершине проверялся по индексу, если он меньше половины порога остановки[latex](-50)[/latex], то путь к этой вершине бесконечен.

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

struct vertax{ // структура вершина
	int vert, index, father; bool visited;
	vertax(int a){vert = a; index = 10001; father = a;visited = false;}
	vertax(int a, int b){
		vert = a;
		father = b;
		index = 10001;visited = false;
	}
	vertax(int a, int b, int x){
		vert = a;
		father = b;
		index = x;visited = false;
	}
	vector<vertax> follow;// с кем связанна эта вершина
	~vertax(){}
};

struct graph{
	vector<vertax> v; // list of vertax
	int count;
	graph(){};
	graph(int n){
		count = n;
	}
	void get(){//инициализируем граф
		for(int i = 1; i <= count; i++){
			vertax v(i);
			for(int j = 1; j <= count; j++){
				int x;
				cin >> x;
				if(x != 0){
					vertax temp(j, i, x);
					v.follow.push_back(temp);
				}
			}
			graph::v.push_back(v);
		}
	}
	void write(){//вывод вершины, и с кем она связанна
		for(int i = 0; i < count; i++){
			cout << v[i].index << ":";
			for(int j = 0; j < v[i].follow.size(); j++){
				cout << v[i].follow[j].vert << " ";
			}
			cout << endl;
		}
	}
	void way(vertax& x){//алгоритм
		deque<vertax> list;
		x.index = 0;
		x.visited = true;
		list.push_front(x);
		while(!list.empty()){
			vertax& y = list[0];
			for(int i = 0; i < y.follow.size();i++){
				v[y.follow[i].vert -1].visited = true;
				if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){
					v[y.follow[i].vert-1].index = y.index+y.follow[i].index;
					if(v[y.follow[i].vert-1].index > -102){
						list.push_back(v[y.follow[i].vert-1]);
					}
				}
			}
			list.pop_front();
		}
	}
	void def(){//фунция к приведению значений по умолчанию
		for(int i = 0; i < v.size(); i++){
			v[i].index = 10001;
			v[i].visited = false;
		}
	}
	void task1(){ // Решение задачи e-olymp.com №976: Флойд - существование
		for(int i = 0; i < v.size(); i++){
			way(v[i]);
			for(int j = 0; j < v.size()-1; j++){
				if(!v[j].visited){
					cout << 0 << " ";
				}else if(v[j].index < -50){
					cout << 2 << " ";
				}else{
					cout << 1 << " ";
				}
			}
			if(!v[v.size()-1].visited){
					cout << 0 ;
				}else if(v[v.size()-1].index < -50){
					cout << 2 ;
				}else{
					cout << 1 ;
				}
			def();
			cout << endl;
		}
	}
	void task2(){ // Решение задачи e-olymp.com №974: Флойд-1
		for(int i = 0; i < v.size(); i++){
			way(v[i]);
			for(int j = 0; j < v.size()-1; j++){
				if(!v[j].visited){
					cout << 0 << " ";
				}else{
					cout << v[j].index << " ";
				}
			}
			if(!v[v.size()-1].visited){
					cout << 0 ;
				}else{
					cout << v[v.size()-1].index;
				}
			def();
			cout << endl;
		}
	}
};


int main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	graph dog(n);
	dog.get();
	dog.task1();// Решаем задачу №976: Флойд - существование
	dog.task2();// Решаем задачу №974: Флойд-1
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <vector>

#include <deque>

using namespace std;

struct vertax{ // структура вершина

int vert, index, father; bool visited;

vertax(int a){vert = a; index = 10001; father = a;visited = false;}

vertax(int a, int b){

vert = a;

father = b;

index = 10001;visited = false;

}

vertax(int a, int b, int x){

vert = a;

father = b;

index = x;visited = false;

}

vector<vertax> follow;// с кем связанна эта вершина

~vertax(){}

};

struct graph{

vector<vertax> v; // list of vertax

int count;

graph(){};

graph(int n){

count = n;

}

void get(){//инициализируем граф

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

vertax v(i);

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

int x;

cin >> x;

if(x != 0){

vertax temp(j, i, x);

v.follow.push_back(temp);

}

graph::v.push_back(v);

}

void write(){//вывод вершины, и с кем она связанна

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

cout << v[i].index << ":";

for(int j = 0; j < v[i].follow.size(); j++){

cout << v[i].follow[j].vert << " ";

}

cout << endl;

}

void way(vertax& x){//алгоритм

deque<vertax> list;

x.index = 0;

x.visited = true;

list.push_front(x);

while(!list.empty()){

vertax& y = list[0];

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

v[y.follow[i].vert -1].visited = true;

if(v[y.follow[i].vert-1].index > y.index+y.follow[i].index){

v[y.follow[i].vert-1].index = y.index+y.follow[i].index;

if(v[y.follow[i].vert-1].index > -102){

list.push_back(v[y.follow[i].vert-1]);

}

list.pop_front();

}

void def(){//фунция к приведению значений по умолчанию

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

v[i].index = 10001;

v[i].visited = false;

}

void task1(){ // Решение задачи e-olymp.com №976: Флойд - существование

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

way(v[i]);

for(int j = 0; j < v.size()-1; j++){

if(!v[j].visited){

cout << 0 << " ";

}else if(v[j].index < -50){

cout << 2 << " ";

}else{

cout << 1 << " ";

}

if(!v[v.size()-1].visited){

cout << 0 ;

}else if(v[v.size()-1].index < -50){

cout << 2 ;

}else{

cout << 1 ;

}

def();

cout << endl;

}

void task2(){ // Решение задачи e-olymp.com №974: Флойд-1

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

way(v[i]);

for(int j = 0; j < v.size()-1; j++){

if(!v[j].visited){

cout << 0 << " ";

}else{

cout << v[j].index << " ";

}

if(!v[v.size()-1].visited){

cout << 0 ;

}else{

cout << v[v.size()-1].index;

}

def();

cout << endl;

}

};

int main() {

ios::sync_with_stdio(false);

int n;

cin >> n;

graph dog(n);

dog.get();

dog.task1();// Решаем задачу №976: Флойд - существование

dog.task2();// Решаем задачу №974: Флойд-1

return 0;

}

link

А706 Алгоритм быстрого возведения в степень

14/05/2015 by Осецимський Анатолій Вадимович

Степень

Входная матрица

Результирующая матрица

0	1
2	3

2	3
6	11

0	1
2	3

6	11
22	39

Пусть даны квадратная матрица [latex]A[/latex] порядка [latex]m[/latex] и натуральное число [latex]n[/latex]; требуется найти [latex]A^{n}[/latex]. Алгоритм, основанный на непосредственной применении формулы [latex]A^{n} = A*A*A…*A [/latex]([latex]n[/latex] сомножителей), слишком разорителен. Например, [latex]A^{4}[/latex] экономичнее вычислять как [latex]A^{2^{2}}[/latex]. Идея одного достаточно экономичного алгоритма вычисления [latex]A^{n}[/latex] заключается в следующем: если [latex]n = 2k[/latex], то [latex]A^{n} = (A^{2})^{k}[/latex]; если же [latex]n = 2k + 1[/latex], то [latex]A^{n} = (A^{2})^{k} * A[/latex]. Степень с показателем [latex]k[/latex] вычисляется с учетом этих же соображений. Итак, надо разделить [latex]n[/latex] на [latex]2[/latex] с остатком:[latex] n = 2k + l [/latex] [latex](0\le l\le 1[/latex]), потом это же проделать с [latex]k[/latex] и т.д. Эти действия приводят, как известно, к построению двоичной записи [latex]n[/latex]. Алгоритм, основанный на этой идее, состоит в том, что последовательно вычисляются [latex]A^{a_{0}}, A^{a_{1}*a_{0}}, …,A^{a_{l}*…*a_{0}}, a_{l}*…*a_{0}[/latex] — двоичная запись числа [latex]n[/latex]. Для этого вычисляется, цифра за цифрой, двоичная запись [latex]n[/latex] и, параллельно, степень за степенью,[latex]A^{(2^{0})}, A^{(2^{1})}, …[/latex] — каждая следующая степень получается из предыдущей возведением в квадрат. Подсчитывается произведение тех из вычисленных степеней, для которых соответствующая цифра двоичного представления равна 1. Например, запись [latex]9[/latex] в двоичной системе есть [latex]1001[/latex][latex](9 = 1*8 + 0*4 + 0*2 + 1)[/latex]; для вычисления [latex]A^{9}[/latex] достаточно найти [latex]A^{2},A^{4},A^{8},[/latex]([latex]3[/latex] умножения), а затем определить [latex]A*A^{8},[/latex] ([latex]1[/latex] умножение).

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

Написать программу, реализующую предположенный алгоритм.

Суть алгоритма была описана в задании. Реализация была через свою структуру данных, такую как матрица. В ней мы определили умножение и присваивание, для удобства. Есть несколько конструкторов, но нужен по сути только самый первый, остальные для разыгравшейся фантазии. Инициализация при создании матрицы обязательна, поскольку может выдавать неправильный ответ в связи с забытым в памяти мусором. Как перемножать матрицы можно узнать здесь. Нам понадобятся три матрицы, исходная, временная и матрица для ответа. Само двоичное представление удобно хранить в строке, поскольку идя по ней и находя [latex]1[/latex] мы можем домножить на временную матрицу матрицу ответ.

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

class matrix{ //создаем класс матрицы, в основном для красивого перемножения
    private:
        int n,m;
        int long long **arr;
    public:
        matrix(){
            n = 1; m = 1;
        }
        matrix(int x){
            n = x; m = x;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = 0;
                }
            }
        }
        matrix(int x, int y){
            n = x; m = y;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
            for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = 0;
                }
            }
        } // выше были описанны конструкторы
        ~matrix(){
            for(int i = 0; i < n; i++){
                delete arr[i];
            }
            delete arr;
        }// деструктор
        void read(){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    cin >> arr[j][k];
                }
            }
        }//функция ввода
        void write(){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    cout << arr[j][k] << " ";
                }
                cout << endl;
            }
        }// функция вывода
        void create(int x, int y){
            n = x; m = y;
            arr = new int long long *[n];
            for(int i = 0; i < n; i++){
                arr[i] = new int long long [m];
            }
        }//функция измененияколичества выделяемой под нас памяти
        matrix& operator=(const matrix& x){
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    arr[j][k] = x.arr[j][k];
                }
            }
            return *this;
        }// переопределение оператора присваивания для матриц
        const matrix operator*(const matrix& x){
            matrix ans(this->n, this->m);
            for(int i = 0; i < this->n; i++){
                for(int j = 0; j < this->m; j++){
                    for(int k = 0; k < this->m; k++){
                        ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
                    }
                }
            }
            return ans;
        }//переопределение умножения для матриц
        matrix& operator*=(const matrix& x){
            matrix ans(this->n, this->m);
            for(int i = 0; i < this->n; i++){
                for(int j = 0; j < this->m; j++){
                    for(int k = 0; k < this->m; k++){
                        ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];
                    }
                }
            }
            *this=ans;
            return *this;
        }//переопределение присвоить равно
        
        matrix& pow(int n){
            string s;
            for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0
                s+= to_string((n >> i)&1);; 
            }
            int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки
            for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой 
            matrix ans(this->n,this->m);
            for(int j = 0; j < this->n; j++){
                for(int k = 0; k < this->m; k++){
                    if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0; 
                }
            }
            matrix temp(this->n,this->m);
            temp = *this;
            for(int j = 0; j <= i; j++){
                if(s[j] == '1'){
                    ans*=temp;
                }
                temp*=temp;
            }
            *this=ans;
            return *this;
        }
};

int main() {
    int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа
    cin >> n;
    matrix mas(size); // создаем матрицу
    mas.read();
    mas.pow(n);
    mas.write();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

#include <iostream>

#include <string>

#include <vector>

#include <deque>

using namespace std;

class matrix{ //создаем класс матрицы, в основном для красивого перемножения

private:

int n,m;

int long long **arr;

public:

matrix(){

n = 1; m = 1;

}

matrix(int x){

n = x; m = x;

arr = new int long long *[n];

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

arr[i] = new int long long [m];

}

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

for(int k = 0; k < this->m; k++){

arr[j][k] = 0;

}

matrix(int x, int y){

n = x; m = y;

arr = new int long long *[n];

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

arr[i] = new int long long [m];

}

for(int j = 0; j < this->n; j++){ // необходимо инициализировать нулями,покольку в памяти может быть забытый мусор

for(int k = 0; k < this->m; k++){

arr[j][k] = 0;

}

} // выше были описанны конструкторы

~matrix(){

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

delete arr[i];

}

delete arr;

}// деструктор

void read(){

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

for(int k = 0; k < this->m; k++){

cin >> arr[j][k];

}

}//функция ввода

void write(){

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

for(int k = 0; k < this->m; k++){

cout << arr[j][k] << " ";

}

cout << endl;

}

}// функция вывода

void create(int x, int y){

n = x; m = y;

arr = new int long long *[n];

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

arr[i] = new int long long [m];

}

}//функция измененияколичества выделяемой под нас памяти

matrix& operator=(const matrix& x){

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

for(int k = 0; k < this->m; k++){

arr[j][k] = x.arr[j][k];

}

return *this;

}// переопределение оператора присваивания для матриц

const matrix operator*(const matrix& x){

matrix ans(this->n, this->m);

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

for(int j = 0; j < this->m; j++){

for(int k = 0; k < this->m; k++){

ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];

}

return ans;

}//переопределение умножения для матриц

matrix& operator*=(const matrix& x){

matrix ans(this->n, this->m);

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

for(int j = 0; j < this->m; j++){

for(int k = 0; k < this->m; k++){

ans.arr[i][j]+= this-> arr[i][k] * x.arr[k][j];

}

*this=ans;

return *this;

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

matrix& pow(int n){

string s;

for(int i = 0; i < sizeof(int)*8 -1; i++){// цикл где мы побитово сдвигаем вправо и умножаем на 1, если в этом бите была 1,то мы добавим в строку 1,если был 0,то 0 конъюнкия 1 будет 0

s+= to_string((n >> i)&1);;

}

int i = s.size()-1; // заводим переменную, в которой будет храниться наивисший разряд двойки

for(; s[i]!= '1'; i--){} //находим этот разряд,двигаясь с конца в поисках первой

matrix ans(this->n,this->m);

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

for(int k = 0; k < this->m; k++){

if(j == k) ans.arr[j][k] = 1; else ans.arr[j][k] = 0;

}

matrix temp(this->n,this->m);

temp = *this;

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

if(s[j] == '1'){

ans*=temp;

}

temp*=temp;

}

*this=ans;

return *this;

}

};

int main() {

int n,size = 2; string s; //n число,в которую нам надо возвести в степень,размеры матрицы и строка,в которой будем для удобства хранить двоичное представление числа

cin >> n;

matrix mas(size); // создаем матрицу

mas.read();

mas.pow(n);

mas.write();

return 0;

}

link.

e-olymp 4853. Кратчайший путь

13/05/2015 by Осецимський Анатолій Вадимович

Задан неориентированный граф. Найдите кратчайший путь от вершины a до вершины b.

Условие задачи на e-olimp.
Cсылка на пройденный тесты.

Раз нам надо найти кратчайший путь путь, то будем использовать BFS- поиск в ширину. Мы будем постепенно просматривать вершины, внося в «план» те вершины с которыми они связанны и которые еще не внесены в «план». Для удобства я использовал вектора. В начале создаем вектор векторов, как бы это тавтологически не звучало, для этого я использовал вектор ответа, как объект, который добавлялся в вектор «graf», выступающий в роли графа, причем мы добавляем сразу к вершинам ([latex] graf[x].push_back(y);[/latex]) то есть [latex] x[/latex] — ая вершина получает связь с вершиной [latex] y[/latex], и наоборот, поскольку граф неориентированный. После чего, проверяем связанна ли начальная вершина хоть с кем — нибудь, если да, что работаем [latex] while [/latex] — ом, пока не наткнемся на начальную вершину, или все вершины в «плане» не будут пройдены. Если мы дошли до конечной вершины, то функция [latex] bfs[/latex] вернет [latex] 1[/latex], что запустит тело [latex] if [/latex]- а и мы начнем восстанавливать путь. Для этого мы заводили дополнительный вектор [latex] family[/latex], в который по мере добавления в «план», также добавлялись и вершины «отцы»(откуда пришла [latex] i [/latex] -ая вершина). Восстановленный путь записываем в вектор [latex] ans[/latex]. После чего [latex] while[/latex] прекращает свою работу и мы переходим к выводу результата. Если вектор ответа пуст, то выводим [latex]-1[/latex], иначе выводим количество вершин, участвующих в построении пути и сам путь.

link.

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

int n,m,a,b,count = 0;
vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные
    count++;
    if(beg == end){
        ok = true;
        return 1;
    }else{
        for(int i = graf[beg].size() - 1;i >= 0;i--){
            if(!popa[graf[beg][i]]){
                ver.push_back(graf[beg][i]);
                family.push_back(beg);
                popa[graf[beg][i]] = true;
            }
        }
    }
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> a >> b;
    for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов
            graf.push_back(ans);
            popa.push_back(false);
    }
    ver.push_back(a);family.push_back(a);
    for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна 
        int x,y;
        cin >> x >> y;
        if(x != y){ // проверка на петлю
            graf[x].push_back(y);
            graf[y].push_back(x);
        }
    }
    if(!graf[a].empty()){ //если вершины начала не изолированна 
        while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"
            if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути
                count--;// Нам надо начать с последней вершины,а это count - 1 вершина
                int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины
                ans.push_back(b);//вектор ответа
                while(ver[count] != a){ // пока не дошли до начальной вершины
                    while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА
                        p++;
                    }
                    ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)
                    count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины 
                    p = 1;
                }
            }
        }
        if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)
            cout << ans.size()-1 << endl;
            for(int i = ans.size()-1; i >= 0; i--){
                cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии
            }
        }else{ // иначе -1
            cout << "-1\n";
        }
    }else{//если начальная вершина изолирована,то сразу выводим -1
        cout << "-1\n";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int n,m,a,b,count = 0;

vector<vector<int> > graf; vector<int> ver; vector<int> family; bool ok = false; vector<int> ans; vector<bool> popa;

int bfs(int beg, int end){ // функция которая добавляет вершины в вектор вершин,которые мы просмотрим,и помечает их как уже проверенные

count++;

if(beg == end){

ok = true;

return 1;

}else{

for(int i = graf[beg].size() - 1;i >= 0;i--){

if(!popa[graf[beg][i]]){

ver.push_back(graf[beg][i]);

family.push_back(beg);

popa[graf[beg][i]] = true;

}

return 0;

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

cin >> a >> b;

for(int i = 0 ; i <= n; i++){ // создаем векто ввекторов

graf.push_back(ans);

popa.push_back(false);

}

ver.push_back(a);family.push_back(a);

for(int i = 0; i < m; i++){ //в вектор вершины добавляем те вершины,с которым она связанна

int x,y;

cin >> x >> y;

if(x != y){ // проверка на петлю

graf[x].push_back(y);

graf[y].push_back(x);

}

if(!graf[a].empty()){ //если вершины начала не изолированна

while(!ok && count < ver.size() ){ //цикл,пока мы не найдем конечную вершину,или если мы не прошли все вершины в векторе "плана"

if(bfs(ver[count],b)){ //если мы нашли выход,то начать восстанавливать пути

count--;// Нам надо начать с последней вершины,а это count - 1 вершина

int p = 1; //Новая переменная,которая нужна,для нахождения первого вхождения "отца" данной вершины

ans.push_back(b);//вектор ответа

while(ver[count] != a){ // пока не дошли до начальной вершины

while(ver[p] != family[count]){//двигаемся слева пройденных по вектору вершин плана,и ищем первое вхождение вершины ОТЦА

p++;

}

ans.push_back(ver[p]);//добавляем в ответ вершину,из которой мы попали в предыдущую (отца)

count = p;// теперь ищем отца отца и так далее,пока не дойдем до начальной вершины

p = 1;

}

if(ans.size() > 0){ // если вектор ответа не пуст(имеет хотябы одну вершины из пути)

cout << ans.size()-1 << endl;

for(int i = ans.size()-1; i >= 0; i--){

cout << ans[i] << " "; // выводим ответ справа на лево,так сказано в условии

}

}else{ // иначе -1

cout << "-1\n";

}

}else{//если начальная вершина изолирована,то сразу выводим -1

cout << "-1\n";

}

return 0;

}

АА22

15/03/2015 by Осецимський Анатолій Вадимович

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

input	output	Описание
./Task22 «he,.llo,. wo.,.,.,.,r.l. d»	HELLOWORLD	На входе поступает один параметр в кавычках, вкотором есть пробел. Он убирается программой.
./Task22 2425s,Go.oD b24.ye	2425SGOODB24YE	На входе поступает два параметра, пробел между параметрами убирается автоматически (пробел служил разделением между параметрами).

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

int main(int argc, char* argv[]) {
    string s="";
    if(argc > 1){
    	for( int i = 1 ; i < argc; i++){
    		for( int j = 0; j < strlen(argv[i]); j++){
    			if(argv[i][j]==' '||argv[i][j]=='.'||argv[i][j]==','){
    			    s+="";
    			}else{
    				s+=toupper(argv[i][j]);
    			}
    		}
    	}
    }else{s="Sorry";}
    cout << s << endl;
	return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

int main(int argc, char* argv[]) {

string s="";

if(argc > 1){

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

for( int j = 0; j < strlen(argv[i]); j++){

if(argv[i][j]==' '||argv[i][j]=='.'||argv[i][j]==','){

s+="";

}else{

s+=toupper(argv[i][j]);

}

}else{s="Sorry";}

cout << s << endl;

return 0;

}

А409

14/03/2015 by Осецимський Анатолій Вадимович

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

1	3	1	1	1	1	1	1	2
1	1	1	1	1	1	1	1	1
1	1	1	1	1	4	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	5
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
Ответ	14

1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	2	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1

Ответ

Нету элементов с такими свойствами

Находим наибольший из нижних элементов (элементы, расположенные ниже главной диагонали). Потом сравниваем каждый элемент верхнего множества (элементы, расположенные выше главной диагонали и на самой диагонали) с наибольшим элементов ([latex]bigger[/latex]) всех нижних элементов и если это число больше, то прибавляем это число к переменной [latex]summa[/latex].

#include <iostream>
using namespace std;

int main() {
    int size = 9; bool ok = false;
    double mat[size][size];//Матрица 9 на 9
    for(int vert = 0;vert < size;vert++)//вводим матрицу
    {
        for(int gor = 0;gor < size;gor++)
        {
            cin >> mat[vert][gor];
        }
    }
    double bigger = mat[1][0],summa = 0.0;//bigger (наибольший элемент нижжней треугольнйо матрицы диагонали)
    for(int vert = 1;vert < size;vert++)//(Находим этот элемент)
    {
        for(int gor = 0;gor < vert;gor++)
        {
            if(bigger < mat[vert][gor]){
                bigger = mat[vert][gor];
            }
        }
    }
    for(int vert=0;vert < size;vert++)//Проверка каждого диагонального элемента и элементов выше диагонали,на то,больше ли он bigger или нет,и если больше,то увеличиваем переменную summa на этот элемент
    {
        for(int gor=vert;gor < size;gor++)
        {
            if(mat[vert][gor] > bigger)
            {
                ok = true;
                summa+=mat[vert][gor];
            }
        }
    }
    if(ok)//Провека для вывода ответа
    {
        cout << summa;
    }
    else
    {
        cout << "Нету элементов с такими свойствами";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int size = 9; bool ok = false;

double mat[size][size];//Матрица 9 на 9

for(int vert = 0;vert < size;vert++)//вводим матрицу

{

for(int gor = 0;gor < size;gor++)

{

cin >> mat[vert][gor];

}

double bigger = mat[1][0],summa = 0.0;//bigger (наибольший элемент нижжней треугольнйо матрицы диагонали)

for(int vert = 1;vert < size;vert++)//(Находим этот элемент)

{

for(int gor = 0;gor < vert;gor++)

{

if(bigger < mat[vert][gor]){

bigger = mat[vert][gor];

}

for(int vert=0;vert < size;vert++)//Проверка каждого диагонального элемента и элементов выше диагонали,на то,больше ли он bigger или нет,и если больше,то увеличиваем переменную summa на этот элемент

{

for(int gor=vert;gor < size;gor++)

{

if(mat[vert][gor] > bigger)

{

ok = true;

summa+=mat[vert][gor];

}

if(ok)//Провека для вывода ответа

{

cout << summa;

}

else

{

cout << "Нету элементов с такими свойствами";

}

return 0;

}

link

Java

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int size = 9; boolean ok = false;
    	double[][] mat = new double[size][size];//Матрица 9 на 9
	    for(int vert = 0;vert < size;vert++)//вводим матрицу
	    {
	        for(int gor = 0;gor < size;gor++)
	        {
	            mat[vert][gor] = in.nextDouble();
	        }
	    }
	    double bigger = mat[1][0],summa = 0.0;//bigger (наибольший элемент нижжней треугольнйо матрицы диагонали)
	    for(int vert = 1;vert < size;vert++)//(Находим этот элемент)
	    {
	        for(int gor = 0;gor < vert;gor++)
	        {
	            if(bigger < mat[vert][gor]){
	                bigger = mat[vert][gor];
	            }
	        }
	    }
	    for(int vert=0;vert < size;vert++)//Проверка каждого диагонального элемента и элементов выше диагонали,на то,больше ли он bigger или нет,и если больше,то увеличиваем переменную summa на этот элемент
	    {
	        for(int gor=vert;gor < size;gor++)
	        {
	            if(mat[vert][gor] > bigger)
	            {
	                ok = true;
	                summa+=mat[vert][gor];
	            }
	        }
	    }
	    if(ok)//Провека для вывода ответа
	    {
	        System.out.println(summa);
	    }
	    else
	    {
	        System.out.println("Нету элементов с такими свойствами");
	    }
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int size = 9; boolean ok = false;

double[][] mat = new double[size][size];//Матрица 9 на 9

for(int vert = 0;vert < size;vert++)//вводим матрицу

{

for(int gor = 0;gor < size;gor++)

{

mat[vert][gor] = in.nextDouble();

}

double bigger = mat[1][0],summa = 0.0;//bigger (наибольший элемент нижжней треугольнйо матрицы диагонали)

for(int vert = 1;vert < size;vert++)//(Находим этот элемент)

{

for(int gor = 0;gor < vert;gor++)

{

if(bigger < mat[vert][gor]){

bigger = mat[vert][gor];

}

{

for(int gor=vert;gor < size;gor++)

{

if(mat[vert][gor] > bigger)

{

ok = true;

summa+=mat[vert][gor];

}

if(ok)//Провека для вывода ответа

{

System.out.println(summa);

}

else

{

System.out.println("Нету элементов с такими свойствами");

}

А810

14/03/2015 by Осецимський Анатолій Вадимович

Дано натуральное число [latex]n (n <= 1000)[/latex]. Записать это число русскими словами (семнадцать, двести пятьдесят три, тысяча и т. д. ).

Ход решения очень простой, читаем наше [latex]n[/latex] в тиме [latex]integer[/latex] и проверяем, если оно равно [latex]1000[/latex], то выводим ответ «тысяча», иначе берем число по модулю [latex]100[/latex] и присваиваем(дописываем) строке [latex]s[/latex] значение уже заранее описанного для [latex]n mod 100[/latex] ответа. Дальше проверяем так же по десяткам, здесь есть маленький нюанс, для чисел от [latex]10[/latex] до [latex]19[/latex] — эти числа имеют собственное названием, если же [latex](n mod 100)/10[/latex] от [latex]2[/latex] до [latex]9[/latex], то дописываем в [latex]s[/latex] соответствующее значение. И последний шаг — это запись едениц, мы берем все число по модулю [latex]10[/latex] ([latex]n mod 10[/latex]) и дописываем то, что осталось.

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

int main() {
int n;
string s;
cin >> n;
if(n==1000){
    s="тысяча";
    }else{
    s="";
    switch(n/100){
        case 1:s="сто";break;
        case 2:s="двести";break;
        case 3:s="триста";break;
        case 4:s="четыреста";break;
        case 5:s="пятьсот";break;
        case 6:s="шестьсот";break;
        case 7:s="семьсот";break;
        case 8:s="восемьсот";break;
        case 9:s="девятьсот";break;
    }
    if(n >= 100 && n%100 >= 10){ s+=" ";}
    switch((n%100)/10){
        case 2:s=s+"двадцать";break;
        case 3:s=s+"тридцать";break;
        case 4:s=s+"сорок";break;
        case 5:s=s+"пятьдесят";break;
        case 6:s=s+"шестьдесят";break;
        case 7:s=s+"семьдесят";break;
        case 8:s=s+"восемьдесят";break;
        case 9:s=s+"девяносто";break;
    }
    if(n%100>=10&n%100<20){
        switch(n%100){
            case 10:s=s+"десять";break;
            case 11:s=s+"одиннадцать";break;
            case 12:s=s+"двенадцать";break;
            case 13:s=s+"тринадцать";break;
            case 14:s=s+"четырнадцать";break;
            case 15:s=s+"пятнадцать";break;
            case 16:s=s+"шестнадцать";break;
            case 17:s=s+"семнадцать";break;
            case 18:s=s+"восемнадцать";break;
            case 19:s=s+"девятнадцать";break;
        }
        }else{
        if(n%10 != 0 && (n % 100 >= 20 || n >= 100)){ s+=" ";}
            switch(n%10){
            case 1:s=s+"один";break;
            case 2:s=s+"два";break;
            case 3:s=s+"три";break;
            case 4:s=s+"четыре";break;
            case 5:s=s+"пять";break;
            case 6:s=s+"шесть";break;
            case 7:s=s+"семь";break;
            case 8:s=s+"восемь";break;
            case 9:s=s+"девять";break;
            }
        }
    }
cout << s << endl;
return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

int main() {

int n;

string s;

cin >> n;

if(n==1000){

s="тысяча";

}else{

s="";

switch(n/100){

case 1:s="сто";break;

case 2:s="двести";break;

case 3:s="триста";break;

case 4:s="четыреста";break;

case 5:s="пятьсот";break;

case 6:s="шестьсот";break;

case 7:s="семьсот";break;

case 8:s="восемьсот";break;

case 9:s="девятьсот";break;

}

if(n >= 100 && n%100 >= 10){ s+=" ";}

switch((n%100)/10){

case 2:s=s+"двадцать";break;

case 3:s=s+"тридцать";break;

case 4:s=s+"сорок";break;

case 5:s=s+"пятьдесят";break;

case 6:s=s+"шестьдесят";break;

case 7:s=s+"семьдесят";break;

case 8:s=s+"восемьдесят";break;

case 9:s=s+"девяносто";break;

}

if(n%100>=10&n%100<20){

switch(n%100){

case 10:s=s+"десять";break;

case 11:s=s+"одиннадцать";break;

case 12:s=s+"двенадцать";break;

case 13:s=s+"тринадцать";break;

case 14:s=s+"четырнадцать";break;

case 15:s=s+"пятнадцать";break;

case 16:s=s+"шестнадцать";break;

case 17:s=s+"семнадцать";break;

case 18:s=s+"восемнадцать";break;

case 19:s=s+"девятнадцать";break;

}

}else{

if(n%10 != 0 && (n % 100 >= 20 || n >= 100)){ s+=" ";}

switch(n%10){

case 1:s=s+"один";break;

case 2:s=s+"два";break;

case 3:s=s+"три";break;

case 4:s=s+"четыре";break;

case 5:s=s+"пять";break;

case 6:s=s+"шесть";break;

case 7:s=s+"семь";break;

case 8:s=s+"восемь";break;

case 9:s=s+"девять";break;

}

cout << s << endl;

return 0;

}

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

А137е

28/11/2014 by Осецимський Анатолій Вадимович

Даны натуральные [latex] n[/latex], действительные [latex] a_{1},\ldots,a_{n}[/latex].

Вывести: [latex] a_1+1!, a_2 +2!, …, a_n+n![/latex].

	n	a1	a2	a3	a4
Input:	4	1	2	3	4	Output:	2.00	4.00	9.00	28.00
Input:	4	0.1	0.2	0.3	0.4	Output:	1.10	2.20	6.30	24.40

#include <iostream>
using namespace std;

int main() {
    int n;
    double a,fact=1.0;
    scanf("%d",&n);//читаем n
    for(int k=1;k<=n;k++)
    {
        scanf("%lf",&a);//читаем из потока k-ый элемент 
        fact*=k;//увеличиваем фаториал
        printf("%.2lf ",(a+fact));//выводим сумму цифры из потока и факториала
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

double a,fact=1.0;

scanf("%d",&n);//читаем n

for(int k=1;k<=n;k++)

{

scanf("%lf",&a);//читаем из потока k-ый элемент

fact*=k;//увеличиваем фаториал

printf("%.2lf ",(a+fact));//выводим сумму цифры из потока и факториала

}

return 0;

}

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл [latex]for[/latex], от [latex]1[/latex] до [latex]n[/latex]. Дальше в теле цикла описываем чтение элементов, увеличение факториала и вывод суммы цифр из потока и факториала.

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

А116е

22/10/2014 by Осецимський Анатолій Вадимович

Вычислить [latex] \prod_{i=1}^{n}{\frac{(1-x)^{i+1}+1}{((i-1)!+1)^2}} [/latex]

Числа [latex] n [/latex] и [latex] x [/latex] вводятся с клавиатуры.

n	x	Ответ
1	3	1.25
2	3	-2.1875
3	3	-4.13194

#include <iostream>
using namespace std;

int main() {
	double pro = 1;// искомое произведение
	int n,x;
	cin >> n >> x;//Вводим числа
	double v = 1-x,u = 1;//v-это у нас 1-х, которое возводится в степень, а u-это факториал
        v*=1-x;
        pro*=(v+1)/((1+1)*(1+1));
	for(int i = 2;i <= n;i++)
	{
		v*=(1-x);u*=i-1;
		pro*=(v+1)/((u+1)*(u+1));
	}
	cout << pro;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double pro = 1;// искомое произведение

int n,x;

cin >> n >> x;//Вводим числа

double v = 1-x,u = 1;//v-это у нас 1-х, которое возводится в степень, а u-это факториал

v*=1-x;

pro*=(v+1)/((1+1)*(1+1));

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

{

v*=(1-x);u*=i-1;

pro*=(v+1)/((u+1)*(u+1));

}

cout << pro;

return 0;

}

Вводим n и x типа int. Инициализируем переменные v=1-x и u=1 типа double. Присваем значение переменной pro, при n=1. Запускаем цикл от 2 до n в котором увеличиваем факториал u*=i-1 и степень v*=1-x. Так цикл пройдет n раз и в конце выдаст итоговое произведение cout<< pro.

Link

Java

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double pro = 1;
		int n = in.nextInt(), x = in.nextInt();
		double v = 1 - x, u = 1;
		v*=1-x;
        pro*=(v+1)/((1+1)*(1+1));
		for(int i = 2; i <= n; i++){
			v *= (1-x);u *= i - 1; pro *= (v+1)/((u+1)*(u+1));
		}
		System.out.println((double)pro);
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double pro = 1;

int n = in.nextInt(), x = in.nextInt();

double v = 1 - x, u = 1;

v*=1-x;

pro*=(v+1)/((1+1)*(1+1));

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

v *= (1-x);u *= i - 1; pro *= (v+1)/((u+1)*(u+1));

}

System.out.println((double)pro);

}

Ю4.13

22/10/2014 by Осецимський Анатолій Вадимович

Задача. Дан массив [latex]A(n)[/latex]. Все положительные его элементы поместить в начало массива [latex]B(n)[/latex], а отрицательные элементы- в начало массива [latex]C(n)[/latex]. Подсчитать количество тех и других.

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

-1

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

#include <iostream>
using namespace std;

int main() {
    int n=0,otr=0,pol=0;
    scanf("%d",&n);//размеры массива
    double A[n],B[n],C[n];//создаем три массива
    for(int i=0;i<n;i++)// цикл для ввода значений массива и сортировки
    {
        cin >> A[i];
        A[i]>=0?B[pol++]=A[i]:C[otr++]=A[i];//В данной строке команда printf используется вместо двух ifов,чтобы было приятнее глазу, Если элемент из массива А положительный,то в массив В добавляем новый элемент и увеличиваем счетчик на 1, а если отрицательно, то в массив С
    }
	cout << "Negative " << otr << " Positive " << pol << endl;//выводим количество отрицательных и положительных чисел
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n=0,otr=0,pol=0;

scanf("%d",&n);//размеры массива

double A[n],B[n],C[n];//создаем три массива

for(int i=0;i<n;i++)// цикл для ввода значений массива и сортировки

{

cin >> A[i];

A[i]>=0?B[pol++]=A[i]:C[otr++]=A[i];//В данной строке команда printf используется вместо двух ifов,чтобы было приятнее глазу, Если элемент из массива А положительный,то в массив В добавляем новый элемент и увеличиваем счетчик на 1, а если отрицательно, то в массив С

}

cout << "Negative " << otr << " Positive " << pol << endl;//выводим количество отрицательных и положительных чисел

return 0;

}

Заводим счетчик для отрицательных и положительных чисел,а также переменную для количества элементов массива типа [latex]int[/latex]. Читаем количество элементов и создаем три массива типа [latex]double[/latex](вдруг нам буду вводить действительные числа). В цикле читаем элемент [latex]A[i][/latex] и условием определяем положительное число или нет, и увеличиваем соответствующий счетчик. Выводим полученные результаты.

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

Java

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), p = 0, o = 0;
		int[] A = new int[n], B = new int[n], C = new int[n];
		for(int i = 0; i < n; i++){
			A[i] = in.nextInt();
			if(A[i] >= 0) B[p++] = A[i]; else C[o++] = A[i];
		}
		System.out.println("Positive:"+p + " Negative:"+o);
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), p = 0, o = 0;

int[] A = new int[n], B = new int[n], C = new int[n];

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

A[i] = in.nextInt();

if(A[i] >= 0) B[p++] = A[i]; else C[o++] = A[i];

}

System.out.println("Positive:"+p + " Negative:"+o);

}

Ю3.24

22/10/2014 by Осецимський Анатолій Вадимович

Задача. Композиция [latex]n[/latex]- ого порядка [latex]f^{[n]}(x)[/latex] функции [latex]f(x)[/latex] назовем результат [latex]n[/latex]- кратного вычисления функции [latex]f [/latex], то есть [latex]f^{[1]}(x)=f(x)[/latex], [latex]f^{[ 2]}(x)=f(f(x))[/latex], и так далее. Для заданных [latex]n[/latex] и [latex]x[/latex] вычислить [latex] (expln)^{[n]} (x)[/latex] и [latex] exp^{[n]} ln^{[n]} (x)[/latex], результаты сравнить с [latex] x[/latex], то есть вывести значения аргумента, композиции функции и разности между ними.

[latex]x[/latex]	[latex]n[/latex]	[latex](expln)^{[n]}(x)[/latex]	[latex]exp^{[n]} ln^{[n]}(x)[/latex]	[latex]x-(expln)^{[n]}(x)[/latex]	[latex]x-exp^{[n]}ln^{[n]} (x)[/latex]
3	3	3	3	-4.44089e-16	-4.44089e-16
3	4	3	nan	-4.44089e-16	nan

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


double f(double x,int n)//композиция expln
{
    if(n != 0)
    {
        x=exp(log(x));
        return n<=1?x:f(x,n-1);
    }
    else return(x);
}

double fln(double x,int n) //логарифм композиции ln
{
    if(n != 0)
    {
        x=log(x);
        return n<=1?x:fln(x,n-1);
    }
    else return(x);
}

double fexp(double x,int n) //алгоритм композиции exp
{
    if(n!=0)
    {
        x=exp(x);
        return n<=1?x:fexp(x,n-1);
    }
    else return(x);
}

int main() {
    double x;int n=0;
    cin >> x >> n;
        printf("%lg %lg %lg %lg",f(x,n),fexp(fln(x,n),n),x-f(x,n),x-fexp(fln(x,n),n));//выводятся значения expln^n(x),exp^nln^n(x) и погрешности,возникшие при композиции этих функций
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

double f(double x,int n)//композиция expln

{

if(n != 0)

{

x=exp(log(x));

return n<=1?x:f(x,n-1);

}

else return(x);

}

double fln(double x,int n) //логарифм композиции ln

{

if(n != 0)

{

x=log(x);

return n<=1?x:fln(x,n-1);

}

else return(x);

}

double fexp(double x,int n) //алгоритм композиции exp

{

if(n!=0)

{

x=exp(x);

return n<=1?x:fexp(x,n-1);

}

else return(x);

}

int main() {

double x;int n=0;

cin >> x >> n;

printf("%lg %lg %lg %lg",f(x,n),fexp(fln(x,n),n),x-f(x,n),x-fexp(fln(x,n),n));//выводятся значения expln^n(x),exp^nln^n(x) и погрешности,возникшие при композиции этих функций

return 0;

}

Задаем функцию, которая будет возвращать нам [latex]double[/latex] и иметь два параметра типа [latex]double[/latex] и [latex]int[/latex](число [latex]n[/latex]- количество композиций). В ней проверяем равна ли переменная нулю latex[/latex], если равна, то нет необходимости производить композицию, если же не равна нулю, то присваиваем [latex]x[/latex] значение функции и возвращаем [latex]x[/latex], если [latex]n<=1[/latex], иначе вызываем эту же функцию, но на порядок ниже latex[/latex] и так пока [latex]n==1[/latex] (то есть задаем рекурсию). Точно также описываем формулы [latex]exp[/latex] и [latex]ln[/latex] (В C++ [latex]log(x)[/latex]- это логарифм числа [latex]x[/latex] по основанию [latex]e[/latex]). В основной программе вызываем эти две функции и выводим их значения и разность между аргументом и значением функции для определения погрешности. (Возможны такие варианты, когда у вас будет логарифм отрицательным, что приведет к ответу [latex]nan[/latex])

Java

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    static double fln(double x, double n){
        if(n != 0){
            x = Math.log(x);
            return n <=1 ? x:fln(x, n-1);
        }else return x;
    }
    static double f(double x, double n){
        if(n != 0){
            x = Math.exp(Math.log(x));
            return n <=1 ? x:f(x, n-1);
        }else return x;
    }
    static double fexp(double x, double n){
        if(n != 0){
            x = Math.exp(x);
            return n <=1 ? x:fexp(x, n-1);
        }else return x;
    }

    
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double x = in.nextDouble(), n = in.nextDouble();
        System.out.println(f(x,n)+" "+fexp(fln(x, n), n)+" "+ (x-f(x, n)) +" " + (x-fexp(fln(x, n), n)));
    }
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

static double fln(double x, double n){

if(n != 0){

x = Math.log(x);

return n <=1 ? x:fln(x, n-1);

}else return x;

}

static double f(double x, double n){

if(n != 0){

x = Math.exp(Math.log(x));

return n <=1 ? x:f(x, n-1);

}else return x;

}

static double fexp(double x, double n){

if(n != 0){

x = Math.exp(x);

return n <=1 ? x:fexp(x, n-1);

}else return x;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double x = in.nextDouble(), n = in.nextDouble();

System.out.println(f(x,n)+" "+fexp(fln(x, n), n)+" "+ (x-f(x, n)) +" " + (x-fexp(fln(x, n), n)));

}

А137е(а)

22/10/2014 by Осецимський Анатолій Вадимович

Даны натуральные [latex] n[/latex], действительные [latex] a_{1}…a_{n}[/latex].

Вывести: [latex] a_1+1!, a_2 +2!, …, a_n+n![/latex].

Input : 1	2	3	4	Output: 2.00	4.00	9.00	28.00
Input : 0.1	0.2	0.3	0.4	Output: 1.10	2.20	6.30	24.40

#include <iostream>
using namespace std;

int main() {
    int i=1;
    double a,fact=1.0;
    while(scanf("%lf",&a)!=EOF)//читаем поток
    {
        fact*=i;//увеличиваем факториал
        printf("%.2lf ",(a+fact));//выводим сумму цифры из потока и факториала
        i++;//увеличиваем i для увеличения факториала каждый раз при  проходе цикла
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int i=1;

double a,fact=1.0;

while(scanf("%lf",&a)!=EOF)//читаем поток

{

fact*=i;//увеличиваем факториал

printf("%.2lf ",(a+fact));//выводим сумму цифры из потока и факториала

i++;//увеличиваем i для увеличения факториала каждый раз при проходе цикла

}

return 0;

}

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл [latex]while[/latex], у которого в условии ставим:

scanf("%lf",&a)!=EOF

1	scanf("%lf",&a)!=EOF

(Работать, пока файл не закончится (конец потока)). Дальше в теле цикла описываем увеличение факториала и выводим сумму цифр из потока и факториала, в конце цикла увеличиваем [latex]i[/latex] для увеличения факториала.

Java

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		long i = 1,fact = 1;
		while(in.hasNext()){
			double r = in.nextDouble();
			fact *= i;i++;
			System.out.print(r+fact + " ");
		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

long i = 1,fact = 1;

while(in.hasNext()){

double r = in.nextDouble();

fact *= i;i++;

System.out.print(r+fact + " ");

}

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

А59з

22/10/2014 by Осецимський Анатолій Вадимович

Задача. Даны действительные числа [latex]x, y[/latex]. Определить, принадлежит ли точка с координатам [latex]x, y[/latex] заштрихованной части плоскости (рис. ниже).

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

int main() {
	double x,y;
	cin >> x >> y;
	if(y>=(-2)&&fabs(x)<=1&&y<=fabs(x))//проверяем лежит ли у выше нижней линии,потом ограничен ли х он прямыми 1 и -1,потом диагонали-это функция у=|x|
		cout << "Yes" << endl;
		else
		cout << "No" << endl;
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double x,y;

cin >> x >> y;

if(y>=(-2)&&fabs(x)<=1&&y<=fabs(x))//проверяем лежит ли у выше нижней линии,потом ограничен ли х он прямыми 1 и -1,потом диагонали-это функция у=|x|

cout << "Yes" << endl;

else

cout << "No" << endl;

return 0;

}

Объявляем две переменные [latex]x,y[/latex] типа [latex]double[/latex] (точки могут иметь дробные координаты). Читаем координаты точки. В условии проверяем три пункта:

Лежит ли [latex]y[/latex] выше [latex]-2[/latex] [latex](y>=-2)[/latex].
Находится ли точка между двумя прямыми [latex](|x|<=1)[/latex].
Лежит ли точка ниже диагоналей,описанных функцией [latex]y=|x|[/latex].

Если все эти три условия соблюдены, то точка находится в закрашенной области, иначе вне этой области.

Реализация на Java:

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone{
	
	static double fabs(double x){
		return x > 0? x:-x;
	}
	
	public static void main (String[] args)	{
		double d1, d2;//переменные для определения длинны до центра круга при радиусе r
		Scanner in = new Scanner(System.in);
		double x = in.nextDouble(),y = in.nextDouble();
		if(y >= (-2) && fabs(x) <= 1 && y <= fabs(x))//проверяем лежит ли у выше нижней линии,потом ограничен ли х он прямыми 1 и -1,потом диагонали-это функция у=|x|
			System.out.println("Yes");
		else
			System.out.println("No");
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone{

static double fabs(double x){

return x > 0? x:-x;

}

public static void main (String[] args) {

double d1, d2;//переменные для определения длинны до центра круга при радиусе r

Scanner in = new Scanner(System.in);

double x = in.nextDouble(),y = in.nextDouble();

if(y >= (-2) && fabs(x) <= 1 && y <= fabs(x))//проверяем лежит ли у выше нижней линии,потом ограничен ли х он прямыми 1 и -1,потом диагонали-это функция у=|x|

System.out.println("Yes");

else

System.out.println("No");

}

e-olymp 3. Спичечная модель

22/10/2014 by Осецимський Анатолій Вадимович

Спичечная модель с http://www.e-olimp.com.ua/problems/3

Задача.

Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.

Для построения модели трех кубиков он использовал [latex]28[/latex] спичек.

Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?

Все числа в задаче не превышают [latex]2*10^9[/latex].

Технические условия

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

Одно число [latex] N [/latex] – количество кубиков.

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

Одно число – количество спичек.

Ссылка на саму задачу.

Пройденные тесты программы.

Input	Output	Comments
0	0	Смотрим,что выдает при 0 кубов
3	28	Проверяем пример данный в задаче
[latex]2*10^9[/latex]	6.00953Е9	Не вылезает ли за рамки переменных

Для решения задачи желательно придумать, как мы будем строить спичечную модель. Самый оптимальный и правильный вариант — это строить в форме куба. (если не верите, поэкспериментируйте с другими формами построения)

Для лучшего понимания сколько нам понадобится спичек, рекомендую представить на бумаге как будут выглядеть «этажи» нашего куба.

Первый этаж будет выглядеть так. (Для примера берем куб [latex]444[/latex], т.к. он самый наглядный и не громоздкий)

8	5	5	5
8	5	5	5
8	5	5	5
12	8	8	8

Для построения самого первого куба нам понадобится 12 спичек, для достройки к нему второго и третьего понадобится по 8, для достройки четвертого куба уже понадобится 5 и так далее.

Второй этаж будет выглядеть так. (аналогично для последующих)

5	3	3	3
5	3	3	3
5	3	3	3
8	5	5	5

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

Получаем [latex]8i+4+5i(i-1)2+3(i-1)2+3i(i-1)^2+2(i-1)^2[/latex] (Где i — это «размерность» куба. К примеру: подставив i=4, мы найдем необходимое количество спичек для построение куба [latex]44*4[/latex]).

Теперь возник вопрос, как в задаче определить размерность куба? Очень просто. Максимальное количество возможных кубов равно [latex]i^3[/latex], следовательно зная количество кубов (Дано в начале задачи) можно определить [latex]i[/latex]. Описываем цикл, увеличивающий [latex]i[/latex] пока [latex]i^3<n[/latex].

Задаем функцию с тремя параметрами. ([latex]u[/latex] — определяет, в какую степень возводить)

int bit(int i,int n,int u)
{
    do
    {
        i=i+1;
    }while(pow(i,u)<n);
    return i;
}

int bit(int i,int n,int u)

{

i=i+1;

}while(pow(i,u)<n);

return i;

}

Имея размерность, можно узнать, сколько нам надо спичек для построения куба прошлой размерности по формуле. Следовательно мы знаем, сколько кубов принадлежит размерности [latex]i[/latex] ([latex]p=n-i^3[/latex]). Разобьем на этапы построение куба размерности [latex]i[/latex] из куба размерности [latex]i-1[/latex]. Пример:

Имея куб [latex]333[/latex] мы начнем достраивать к нему боковую стенку, потом заднюю, и в самом конце так называемую «крышу».

При построении боковой стены мы получаем куб равный [latex] 433[/latex](увеличилась его длинна).

Вид сверху:

[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]

При построении задней стены он расшириться в ширине [latex]443[/latex].

[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]
[ ]	[ ]	[ ]	[ ]

На третьем этапе увеличиться высота куба. Следовательно куб будет иметь такую форму [latex]444[/latex].

Определяем этап. Если мы находимся на третьем этапе, то разность между количеством кубов([latex]n[/latex]) и количеством кубов нашей размерности без крыши([latex]i^2(i-1)[/latex] должно быть больше нуля — [latex]n-i^2(i-1)>0[/latex]. Если больше нуля, то переходим к третьем этапу, иначе смотрим, не на первом ли мы этапе случайно? Для этого количество кубов([latex]n[/latex]) должно быть меньше или равно количеству кубов на первом этапе нашей размерности([latex]i(i-1)(i-1)[/latex]) — [latex]i(i-1)(i-1)>=n[/latex]. Если это выполняется, то переходим к первому этапу, иначе ко второму этапу.

Этап определён. Осталось придумать самый экономный способом построения оставшихся кубов. (В этом и заключается подвох задачи) Самый экономный способ, это если мы будем строить боковую стенку (заднюю или «крышу») в такой последовательности:

16	15	14	13
9	8	7	12
4	3	6	11
1	2	5	10

В количестве затраченных спичек выглядит вот так:

3	3	3	5
3	3	5	3
3	5	3	3
8	5	5	5

По диагонали и по основанию мы тратим по 5 спичек, остальные кубы требуют по 3 (для построения первого куба необходимо 8 спичек). Можно заметить, что номера кубов, для построения которых надо 5 спичек, имеют зависимость, которую можно использовать. По размерности боковой плоскости можно определить количество спичек необходимых для построения плоскости прошлой размерности по формуле [latex]8+(g-2)25+3((g-1)(g-1)-1-(g-2)2)[/latex]. Формула при размерности 1 выдаст неправильный ответ, по этому ставим условие, если [latex]g=1[/latex], то результат увеличиваем на 8, иначе на всю эту формулу. После этого у нас осталость некое количество кубов. Запускаем цикл от номера последнего элемента нашей прошлой разрмерности latex(g-1)+i<=p[/latex].

for (long int i = 1;(g-1)*(g-1)+i <= p;i++)
{
    if ((i == 1 || i == g) && g != 1)
    {
        result+=5;
    }
    else if (g != 1)
    {
        result+=3;
    }
}

for (long int i = 1;(g-1)*(g-1)+i <= p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g != 1)

{

result+=3;

}

Разобравшись во всех нюансах задачи, приступаем к напсианию кода.

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

int bit(int i,int n,int u)
{
    do
    {
        i=i+1;
    }while(pow(i,u)<n);
    return i;
}


int main() {
double n,result,p;//переменные для результата и количество кубиков,на всякий случай большой размерности
long long int i=0,g=0;//объявляем переенные для разрядностей
cin>>n;
i=bit(i,n,3);//находим разрядность куба
if ((i*i*(i-1))>=n)//проверка третьего этапа
    {
        if (((i-1)*(i-1)*i)>=n)//проверка первого этапа и если правда,то решение первого этапа
        {
            double o=i-1;
            result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1);//результату присваем прошылй куб
            p=n-o*o*o;//количество оставшихся кубов
            g=bit(g,p,2);//разрядность плоскости
            if (g==1)//проверка разрядности на 1
                result+=8;//увеличение результата на 8 при разрядности 1
            else
                result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);//увеличение результата по формуле
            for (long int i = 1;(g-1)*(g-1)+i <= p;i++)
            {
                if ((i == 1 || i == g) && g != 1)
                {
                    result+=5;
                }
                else if (g != 1)
                {
                    result+=3;
                }
            }
             
        }
        else//решение второго этапа
        {
            double o=i-1;
            result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1)+o*o*3+5+2*2*(o-1);//результат по формуле+ещё достроеная на первом этапе стенка
            p=n-o*o*(o+1);
            g=bit(g,p,2);
            if (g==1)
                result+=8;
            else
                result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);
            for (long int i=1;((g-1)*(g-1)+i)<=p;i++)
            {
                if ((i == 1 || i == g) && g != 1)
                {
                    result+=5;
                }
                else if (g!=1)
                {
                    result+=3;
                }
            }
        }
    }
    else//решение третьего этапа
    {
        double o=i;
        result=8*(o-1)+4+5*(o-1)*(o-1)*2+3*(o-1)*2+3*(o-1)*(o-1)*(o-1)+2*(o-1)*(o-1);//результат по формуле разрядности,только на высоту раную i-1
        p=n-(o-1)*o*o;
            g=bit(g,p,2);
        if (g==1)
            result+=8;
        else
            result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);
        for (long int i=1;((g-1)*(g-1)+i)<=p;i++)
        {
            if ((i == 1 || i == g) && g != 1)
            {
                result+=5;
            }
                else if (g!=1)
            {
                result+=3;
            }
        }
    }
 cout <<result<< endl;
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <math.h>

using namespace std;

int bit(int i,int n,int u)

{

i=i+1;

}while(pow(i,u)<n);

return i;

}

int main() {

double n,result,p;//переменные для результата и количество кубиков,на всякий случай большой размерности

long long int i=0,g=0;//объявляем переенные для разрядностей

cin>>n;

i=bit(i,n,3);//находим разрядность куба

if ((i*i*(i-1))>=n)//проверка третьего этапа

{

if (((i-1)*(i-1)*i)>=n)//проверка первого этапа и если правда,то решение первого этапа

{

double o=i-1;

result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1);//результату присваем прошылй куб

p=n-o*o*o;//количество оставшихся кубов

g=bit(g,p,2);//разрядность плоскости

if (g==1)//проверка разрядности на 1

result+=8;//увеличение результата на 8 при разрядности 1

else

result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);//увеличение результата по формуле

for (long int i = 1;(g-1)*(g-1)+i <= p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g != 1)

{

result+=3;

}

else//решение второго этапа

{

double o=i-1;

result=8*o+4+5*o*(o-1)*2+3*(o-1)*2+3*o*(o-1)*(o-1)+2*(o-1)*(o-1)+o*o*3+5+2*2*(o-1);//результат по формуле+ещё достроеная на первом этапе стенка

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

g=bit(g,p,2);

if (g==1)

result+=8;

else

result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);

for (long int i=1;((g-1)*(g-1)+i)<=p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g!=1)

{

result+=3;

}

else//решение третьего этапа

{

double o=i;

result=8*(o-1)+4+5*(o-1)*(o-1)*2+3*(o-1)*2+3*(o-1)*(o-1)*(o-1)+2*(o-1)*(o-1);//результат по формуле разрядности,только на высоту раную i-1

p=n-(o-1)*o*o;

g=bit(g,p,2);

if (g==1)

result+=8;

else

result+=8+(g-2)*2*5+3*((g-1)*(g-1)-1-(g-2)*2);

for (long int i=1;((g-1)*(g-1)+i)<=p;i++)

{

if ((i == 1 || i == g) && g != 1)

{

result+=5;

}

else if (g!=1)

{

result+=3;

}

cout <<result<< endl;

return 0;

}

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

Ю2.11

19/09/2014 by Осецимський Анатолій Вадимович

Задача жестянщика. Можно ли из круглой заготовки радиусом [latex]r[/latex] вырезать две прямоугольные пластинки с размерами [latex] a[/latex] × [latex] b[/latex] и [latex] c[/latex] × [latex]d[/latex]?

1.6 3 0 3 0	We can
1.6 3 1 3 1	We can’t
2 3 1 3 1	We can
2 5 1 4 1	We can’t

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

double sort(double a,double b) //ссортировка сторон прямоугольника на длину и ширину
{
	double q;
	if (b>a)
	{
		q=b;
		a=b;
		a=q;
	}
	return a,b;
}

int main() {
	float r,a,b,c,d,q;//вводим переменные для входных данных
	float d1,d2;//переменные для определения длинны до центра круга при радиусе r
	scanf("%f %f %f %f %f", &r , &a , &b , &c , &d );
	sort(a,b);sort(c,d);
	if ((a<r*2) && (c<r*2))//проверка не больше ли стороны ,чем диаметр
		{
			d1 = sqrt(r*r-(a/2)*(a/2));//ищем расстояние до центра от середины длины первого прямоугольника
			d2 = sqrt(r*r-(c/2)*(c/2));//ищем расстояние до центра от середины длины второго прямоугольника
			if (d < d2+(d1-b))//если ширина второго прямоугольника меньше суммы его длинны до центра круга и разности длинны до центра первого прямоугольник с его шириной(Если ширина первого прямоугольника  больше его длинны до центра,то для ширины второго будет меньше места,это понятно)
				{
					printf("We can");
				}
				else
				{
					printf("We can't");
				}
		}
		else
		{
			printf("We can't!");
		}
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

double sort(double a,double b) //ссортировка сторон прямоугольника на длину и ширину

{

double q;

if (b>a)

{

q=b;

a=b;

a=q;

}

return a,b;

}

int main() {

float r,a,b,c,d,q;//вводим переменные для входных данных

float d1,d2;//переменные для определения длинны до центра круга при радиусе r

scanf("%f %f %f %f %f", &r , &a , &b , &c , &d );

sort(a,b);sort(c,d);

if ((a<r*2) && (c<r*2))//проверка не больше ли стороны ,чем диаметр

{

d1 = sqrt(r*r-(a/2)*(a/2));//ищем расстояние до центра от середины длины первого прямоугольника

d2 = sqrt(r*r-(c/2)*(c/2));//ищем расстояние до центра от середины длины второго прямоугольника

if (d < d2+(d1-b))//если ширина второго прямоугольника меньше суммы его длинны до центра круга и разности длинны до центра первого прямоугольник с его шириной(Если ширина первого прямоугольника больше его длинны до центра,то для ширины второго будет меньше места,это понятно)

{

printf("We can");

}

else

{

printf("We can't");

}

else

{

printf("We can't!");

}

return 0;

}

Рассмотрим как выглядит прямоугольник в круге.

Можно заметить, что [latex] h=d1[/latex] (длина до центра окружности) — это катет прямоугольного треугольника, значит его можно найти по теореме Пифагора , зная радиус круга [latex] R[/latex] и катит [latex] r[/latex] (в нашем случае [latex] a/2[/latex]) [latex] h=\sqrt{R^2-r^2}[/latex]). Вычитая из полученного [latex] h=d1[/latex] ширину [latex] b[/latex] мы получим сколько он места занимает при данной длине и ширине относительно центра круга. (Если у нас [latex] b<d1[/latex], то для второго прямоугольника у нас будет больше места) Тоже самое мы проделываем и для второго прямоугольника и получаем наше [latex] h2=d2[/latex]. Дальше размещаем наши прямоугольники параллельно друг другу и смотрим, хватает ли места второму прямоугольнику места с учетом его ширины (Если по ширине второй прямоугольник не превышает оставшегося места) [latex]d<d2+(d1-b)[/latex].

Реализация на Java:

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone{
	
	static void swap(double a, double b){
		if(b > a){
			double q = a;
			a = b;
			b = q;
		}
	}
	
	public static void main (String[] args)	{
		double d1, d2;//переменные для определения длинны до центра круга при радиусе r
		Scanner in = new Scanner(System.in);
		double r = in.nextDouble();
		double a = in.nextDouble();
		double b = in.nextDouble();
		double c = in.nextDouble();
		double d = in.nextDouble();
		swap(a, b);swap(c, d);
		if ((a < r*2) && (c < r*2)){
			d1 = Math.sqrt(r*r-(a/2)*(a/2));//ищем расстояние до центра от середины длины первого прямоугольника
			d2 = Math.sqrt(r*r-(c/2)*(c/2));//ищем расстояние до центра от середины длины второго прямоугольника
			if (d < d2 + (d1 -  b)){
					System.out.println("We can");
				}
				else{
					System.out.println("We can't");
				}
		}
		else{
			System.out.println("We can't!");
		}
	}
}

/* package whatever; // don't place package name! */

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone{

static void swap(double a, double b){

if(b > a){

double q = a;

a = b;

b = q;

}

public static void main (String[] args) {

double d1, d2;//переменные для определения длинны до центра круга при радиусе r

Scanner in = new Scanner(System.in);

double r = in.nextDouble();

double a = in.nextDouble();

double b = in.nextDouble();

double c = in.nextDouble();

double d = in.nextDouble();

swap(a, b);swap(c, d);

if ((a < r*2) && (c < r*2)){

d1 = Math.sqrt(r*r-(a/2)*(a/2));//ищем расстояние до центра от середины длины первого прямоугольника

d2 = Math.sqrt(r*r-(c/2)*(c/2));//ищем расстояние до центра от середины длины второго прямоугольника

if (d < d2 + (d1 - b)){

System.out.println("We can");

}

else{

System.out.println("We can't");

}

else{

System.out.println("We can't!");

}

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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Осецимський Анатолій Вадимович

e-olymp 976. Флойд — существование

А706 Алгоритм быстрого возведения в степень

e-olymp 4853. Кратчайший путь

АА22

А409

А810

А137е

А116е

Ю4.13

Ю3.24

А137е(а)

А59з

e-olymp 3. Спичечная модель

Ю2.11

1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	2	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1

1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	2	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1

1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	2	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1
1	1	1	1	1	1	1	1	1